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

dmtcs:1443 - Discrete Mathematics & Theoretical Computer Science, March 9, 2017, Vol. 19 no. 1 - https://doi.org/10.23638/DMTCS-19-1-1
A characterization of trees with equal 2-domination and 2-independence numbersArticle

Authors: Christoph Brause ; Michael A. Henning ; Marcin Krzywkowski

    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 γ2(G) is the minimum cardinality of a 2-dominating set in G, and the 2-independence number α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.


    Volume: Vol. 19 no. 1
    Section: Graph Theory
    Published on: March 9, 2017
    Accepted on: January 12, 2017
    Submitted on: February 24, 2017
    Keywords: Mathematics - Combinatorics,05C05, 05C69

    Consultation statistics

    This page has been seen 1244 times.
    This article's PDF has been downloaded 799 times.