Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419613 | Discrete Applied Mathematics | 2014 | 11 Pages |
Abstract
Let GG be a graph, each component of which has order at least 3, and let GG have order nn, size mm, total domination number γtγt and maximum degree Δ(G)Δ(G). Let Δ=3Δ=3 if Δ(G)=2Δ(G)=2 and Δ=Δ(G)Δ=Δ(G) if Δ(G)≥3Δ(G)≥3. It is known [M.A. Henning, A linear Vizing-like relation relating the size and total domination number of a graph, J. Graph Theory 49 (2005) 285–290; E. Shan, L. Kang, M.A. Henning, Erratum to: a linear Vizing-like relation relating the size and total domination number of a graph, J. Graph Theory 54 (2007) 350–353] that m≤Δ(n−γt)m≤Δ(n−γt). In this paper we characterize the extremal graphs GG satisfying m=Δ(n−γt)m=Δ(n−γt).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michael A. Henning, Ernst J. Joubert,