Article ID Journal Published Year Pages File Type
419613 Discrete Applied Mathematics 2014 11 Pages PDF
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
, ,