DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 24(3) (2004) 539-543
DOI: 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
γt(G)+εt(G) = p

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