A Gallai-type equality for the total domination number of a graph
Discussiones Mathematicae Graph Theory (2004)
- Volume: 24, Issue: 3, page 539-543
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topSanming Zhou. "A Gallai-type equality for the total domination number of a graph." Discussiones Mathematicae Graph Theory 24.3 (2004): 539-543. <http://eudml.org/doc/270409>.
@article{SanmingZhou2004,
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.
},
author = {Sanming Zhou},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination number; total domination number; Gallai equality},
language = {eng},
number = {3},
pages = {539-543},
title = {A Gallai-type equality for the total domination number of a graph},
url = {http://eudml.org/doc/270409},
volume = {24},
year = {2004},
}
TY - JOUR
AU - Sanming Zhou
TI - A Gallai-type equality for the total domination number of a graph
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 539
EP - 543
AB -
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.
LA - eng
KW - domination number; total domination number; Gallai equality
UR - http://eudml.org/doc/270409
ER -
References
top- [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. Zbl0744.05056
- [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. Zbl0728.05050
- [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. Zbl0243.05115
- [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. Zbl0548.05055
- [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. Zbl0288.05124
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.