Geodesic
A characterization of trees with equal 2-domination and 2-independence numbers
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1.

Voir la notice de l'article provenant de la source Episciences

A set $S$ of vertices in a graph $G$ is a $2$-dominating set if every vertex of $G$ not in $S$ is adjacent to at least two vertices in $S$, and $S$ is a $2$-independent set if every vertex in $S$ is adjacent to at most one vertex of $S$. The $2$-domination number $\gamma_2(G)$ is the minimum cardinality of a $2$-dominating set in $G$, and the $2$-independence number $\alpha_2(G)$ is the maximum cardinality of a $2$-independent set in $G$. Chellali and Meddah [{\it Trees with equal $2$-domination and $2$-independence numbers,} Discussiones Mathematicae Graph Theory 32 (2012), 263--270] provided a constructive characterization of trees with equal $2$-domination and $2$-independence numbers. Their characterization is in terms of global properties of a tree, and involves properties of minimum $2$-dominating and maximum $2$-independent sets in the tree at each stage of the construction. We provide a constructive characterization that relies only on local properties of the tree at each stage of the construction. 
@article{DMTCS_2017_19_1_a3,
     author = {Brause, Christoph and Henning, Michael A. and Krzywkowski, Marcin},
     title = {A characterization of trees with equal 2-domination and 2-independence numbers},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-1-1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-1/}
}
TY  - JOUR
AU  - Brause, Christoph
AU  - Henning, Michael A.
AU  - Krzywkowski, Marcin
TI  - A characterization of trees with equal 2-domination and 2-independence numbers
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-1/
DO  - 10.23638/DMTCS-19-1-1
LA  - en
ID  - DMTCS_2017_19_1_a3
ER  - 
%0 Journal Article
%A Brause, Christoph
%A Henning, Michael A.
%A Krzywkowski, Marcin
%T A characterization of trees with equal 2-domination and 2-independence numbers
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-1/
%R 10.23638/DMTCS-19-1-1
%G en
%F DMTCS_2017_19_1_a3
Brause, Christoph; Henning, Michael A.; Krzywkowski, Marcin. A characterization of trees with equal 2-domination and 2-independence numbers. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 1. doi : 10.23638/DMTCS-19-1-1. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-1-1/

Cité par Sources :