The limit case of a domination property

Citation
Lema.ska, Magdalena et A. Rodríguez-velázquez, Juan, The limit case of a domination property, Acta mathematica Sinica. English series (Print) , 28(3), 2012, pp. 463-468
ISSN journal
14398516
Volume
28
Issue
3
Year of publication
2012
Pages
463 - 468
Database
ACNP
SICI code
Abstract
The domination number .(G) of a connected graph G of order n is bounded below by n+2..(G)3, where .(G) denotes the maximum number of leaves in any spanning tree of G. We show that n+2..(G)3=.(G) if and only if there exists a tree T.T(G).R such that n 1(T) = .(G), where n 1(T) denotes the number of leaves of T, R denotes the family of all trees in which the distance between any two distinct leaves is congruent to 2 modulo 3, and T (G) denotes the set composed by the spanning trees of G. As a consequence of the study, we show that if n+2..(G)3=.(G), then there exists a minimum dominating set in G whose induced subgraph is an independent set. Finally, we characterize all unicyclic graphs G for which equality n+2..(G)3=.(G) holds and we show that the length of the unique cycle of any unicyclic graph G with n+2..(G)3=.(G) belongs to {4} . {3, 6, 9, ...}.