Eternal m-security subdivision numbers in trees
An eternal $m$-secure set of a graph $G = (V,E)$ is a set $S_0\subseteq V$ that can defend against any sequence of single-vertex attacks by means of multiple-guard shifts along the edges of $G$. A suitable placement of the guards is called an eternal $m$-secure set. The eternal $m$-security numb...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Azarbaijan Shahide Madani University
2019-06-01
|
| Series: | Communications in Combinatorics and Optimization |
| Subjects: | |
| Online Access: | http://comb-opt.azaruniv.ac.ir/article_13803_3fd4e7d1ecc4a8bed4b5eb43305015eb.pdf |
| Summary: | An eternal $m$-secure set of a graph $G = (V,E)$ is a
set $S_0\subseteq V$ that can defend against any sequence of
single-vertex attacks by means of multiple-guard shifts along the
edges of $G$. A suitable placement of the guards is called an
eternal $m$-secure set. The eternal $m$-security number
$\sigma_m(G)$ is the minimum cardinality among all eternal
$m$-secure sets in $G$. An edge $uv\in E(G)$ is subdivided if we
delete the edge $uv$ from $G$ and add a new vertex $x$ and two
edges $ux$ and $vx$. The eternal $m$-security subdivision number
${\rm sd}_{\sigma_m}(G)$ of a graph $G$ is the minimum cardinality
of a set of edges that must be subdivided (where each edge in $G$
can be subdivided at most once) in order to increase the eternal
$m$-security number of $G$. In this paper, we study the eternal
$m$-security subdivision number in trees. In particular, we show
that the eternal $m$-security subdivision number of trees is at
most 2 and we characterize all trees attaining this bound. |
|---|---|
| ISSN: | 2538-2128 2538-2136 |