A characterization of trees with equal 2-domination and 2-independence numbers
Discrete Mathematics & Theoretical Computer Science · 2017
DOI: 10.23638/dmtcs-19-1-1 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, 2017. Verfasst von Christoph Brause und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).
Abstract (Originalsprache)
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. Comment: 17 pages, 4 figures
Zitieren
APA
Brause, C., Henning, M. A., & Krzywkowski, M. (2017). A characterization of trees with equal 2-domination and 2-independence numbers. Discrete Mathematics & Theoretical Computer Science. https://doi.org/10.23638/dmtcs-19-1-1
Vancouver
Brause C, Henning MA, Krzywkowski M. A characterization of trees with equal 2-domination and 2-independence numbers. Discrete Mathematics & Theoretical Computer Science. 2017. doi:10.23638/dmtcs-19-1-1
BibTeX
@article{Brause2017,
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},
year = {2017},
doi = {10.23638/dmtcs-19-1-1}
}
EUVIMED