A note on complementary tree domination number of a tree
DOI:
https://doi.org/10.4067/S0716-09172015000200002Keywords:
Dominating set, Complementary tree dominating set, Edge-vertex dominating set, Tree.Abstract
A complementary tree dominating set of a graph G, is a set D of vertices of G such that D is a dominating set and the induced sub graph (V \ D) is a tree. The complementary tree domination number of a graph G, denoted by γctd(G), is the minimum cardinality of a complementary tree dominating set of G. An edge-vertex dominating set of a graph G is a set D of edges of G such that every vertex of G is incident with an edge of D or incident with an edge adjacent to an edge of D. The edge-vertex domination number of a graph, denoted by γev (G), is the minimum cardinality of an edge-vertex dominating set of G. We characterize trees for which γ(T) = γctd(T) and γctd(T) = γev(T) + 1.References
[1] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, (1998).
[2] T. Haynes, S. Hedetniemi and P. Slater (eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, (1998).
[3] X. Hou, A characterization of trees with equal domination and total domination numbers, Ars Combinatoria 97A, pp. 499—508, (2010).
[4] M. Krzywkowski, On trees with double domination number equal to 2-domination number plus one, Houston Journal of Mathematics 39, pp. 427-440, (2013).
[5] S. Muthammai, M. Bhanumathi and P. Vidhya, Complementary tree Domination number of a graph, International Mathematical Forum 6, pp. 1273—1282, (2011).
[6] J. Peters, Theoretical and Algorithmic Results on Domination and connectivity, Ph. D. Thesis, Clemson University, (1986).
[2] T. Haynes, S. Hedetniemi and P. Slater (eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, (1998).
[3] X. Hou, A characterization of trees with equal domination and total domination numbers, Ars Combinatoria 97A, pp. 499—508, (2010).
[4] M. Krzywkowski, On trees with double domination number equal to 2-domination number plus one, Houston Journal of Mathematics 39, pp. 427-440, (2013).
[5] S. Muthammai, M. Bhanumathi and P. Vidhya, Complementary tree Domination number of a graph, International Mathematical Forum 6, pp. 1273—1282, (2011).
[6] J. Peters, Theoretical and Algorithmic Results on Domination and connectivity, Ph. D. Thesis, Clemson University, (1986).
How to Cite
[1]
B. Krishnakumari and Y. B. Venkatakrishnan, “A note on complementary tree domination number of a tree”, Proyecciones (Antofagasta, On line), vol. 34, no. 2, pp. 127-136, 1.
Issue
Section
Artículos
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
