PDF
Discussiones Mathematicae Graph Theory 24(3) (2004)
539-543
DOI: https://doi.org/10.7151/dmgt.1251
A GALLAI-TYPE EQUALITY FOR THE TOTAL DOMINATION NUMBER OF A GRAPH
Sanming Zhou
Department of Mathematics and Statistics
The University of Melbourne
Parkville, VIC 3010, Australia
e-mail: smzhou@ms.unimelb.edu.au
Abstract
We prove the following Gallai-type equality
|
for any graph G with no isolated vertex, where p is the number of vertices of G, γt(G) is the total domination number of G, and εt(G) is the maximum integer s such that there exists a spanning forest F with s the number of pendant edges of F minus the number of star components of F.
Keywords: domination number; total domination number; Gallai equality.
2000 Mathematics Subject Classification: 05C69.
References
| [1] | B. Bollobás, E.J. Cockayne and C.M. Mynhardt, On Generalized Minimal Domination Parameters for Paths, Discrete Math. 86 (1990) 89-97, doi: 10.1016/0012-365X(90)90352-I. |
| [2] | E.J. Cockayne, S.T. Hedetniemi and R. Laskar, Gallai Theorems for Graphs, Hypergraphs and Set Systems, Discrete Math. 72 (1988) 35-47, doi: 10.1016/0012-365X(88)90192-6. |
| [3] | T. Gallai, Über Extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 2 (1959) 133-138. |
| [4] | S.T. Hedetniemi, Hereditary Properties of Graphs, J. Combin. Theory 14 (1973) 16-27. |
| [5] | S.T. Hedetniemi and R. Laskar, Connected Domination in Graphs, in: B. Bollobás ed., Graph Theory and Combinatorics (Academic Press, 1984) 209-218. |
| [6] | J. Nieminen, Two Bounds for the Domination Number of a Graph, J. Inst. Math. Appl. 14 (1974) 183-187, doi: 10.1093/imamat/14.2.183. |
Received 9 October 2003
Revised 14 April 2004
Close