We prove the following Gallai-type equality γₜ(G) + εₜ(G) = p for any graph G with no isolated vertex, where p is the number of vertices of G, γₜ(G) is the total domination number of G, and εₜ(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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1251,
author = {Sanming Zhou},
title = {A Gallai-type equality for the total domination number of a graph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {24},
year = {2004},
pages = {539-543},
zbl = {1064.05117},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1251}
}
Sanming Zhou. A Gallai-type equality for the total domination number of a graph. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 539-543. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1251/
[000] [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. | Zbl 0744.05056
[001] [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. | Zbl 0728.05050
[002] [3] T. Gallai, Über Extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 2 (1959) 133-138.
[003] [4] S.T. Hedetniemi, Hereditary Properties of Graphs, J. Combin. Theory 14 (1973) 16-27. | Zbl 0243.05115
[004] [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. | Zbl 0548.05055
[005] [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. | Zbl 0288.05124