Abstract
Let G be a graph, each component of which has order at least 3, and let G have order n, size m, total domination number γt and maximum degree Δ(G). Let Δ=3 if Δ(G)=2 and Δ=Δ(G) if Δ(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). In this paper we characterize the extremal graphs G satisfying m=Δ(n- γt).
Original language | English |
---|---|
Pages (from-to) | 2014-2024 |
Number of pages | 11 |
Journal | Discrete Applied Mathematics |
Volume | 161 |
Issue number | 13-14 |
DOIs | |
Publication status | Published - Sept 2013 |
Keywords
- Maximum degree
- Order
- Size
- Total domination
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics