A Gallai-type equality for the total domination number of a graph

Sanming Zhou

ArticleOriginal scientific text

Title

A Gallai-type equality for the total domination number of a graph

Authors ¹

Affiliations

Department of Mathematics and Statistics, The University of Melbourne, Parkville, VIC 3010, Australia

Abstract

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.

Keywords

ENG

domination number, total domination number, Gallai equality

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.
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.
T. Gallai, Über Extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 2 (1959) 133-138.
S.T. Hedetniemi, Hereditary Properties of Graphs, J. Combin. Theory 14 (1973) 16-27.
S.T. Hedetniemi and R. Laskar, Connected Domination in Graphs, in: B. Bollobás ed., Graph Theory and Combinatorics (Academic Press, 1984) 209-218.
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.

Title

A Gallai-type equality for the total domination number of a graph

Affiliations

Abstract

Keywords

Bibliography