Browsing by Subject "2-dominating set"

Now showing 1 - 2 of 2

Access status: Open Access ,
On minimum intersections of certain secondary dominating sets in graphs
(Wydawnictwa AGH, 2023) Kosiorowska, Anna; Michalski, Adrian; Włoch, Iwona
In this paper we consider secondary dominating sets, also named as $(1,k)$-dominating sets, introduced by Hedetniemi et al. in 2008. In particular, we study intersections of the $(1,1)$-dominating sets and proper $(1,2)$-dominating sets. We introduce $(1,\overline{2})$-intersection index as the minimum possible cardinality of such intersection and determine its value for some classes of graphs.
Access status: Open Access ,
Trees whose 2-domination subdivision number is 2
(2012) Atapour, Maryam; Sheikholeslami, Seyed Mahmoud; Khodkar, Abdollah
A set S of vertices in a graph $G=(V,E)$ is a $2$-dominating set if every vertex of $V\setminus S$ is adjacent to at least two vertices of $S$. The $2$-domination number of a graph $G$, denoted by $\gamma_2(G)$, is the minimum size of a $2$-dominating set of $G$. The $2$-domination subdivision number $sd_{\gamma_2}(G)$ is the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the $2$-domination number. The authors have recently proved that for any tree $T$ of order at least $3$, $1 \leq sd_{\gamma_2}(T)\leq 2$. In this paper we provide a constructive characterization of the trees whose $2$-domination subdivision number is $2$.