Brause, Christoph and Henning, Michael A. and Krzywkowski, Marcin - A characterization of trees with equal 2-domination and 2-independence numbers

dmtcs:3158 - Discrete Mathematics & Theoretical Computer Science, March 9, 2017, Vol 19 no. 1
A characterization of trees with equal 2-domination and 2-independence numbers

Authors: Brause, Christoph and Henning, Michael A. and Krzywkowski, Marcin

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.


Source : oai:arXiv.org:1604.06382
Volume: Vol 19 no. 1
Section: Graph Theory
Published on: March 9, 2017
Submitted on: February 24, 2017
Keywords: Mathematics - Combinatorics,05C05, 05C69


Share

Browsing statistics

This page has been seen 210 times.
This article's PDF has been downloaded 116 times.