Equality in a linear Vizing-like relation that relates the size and total domination number of a graph

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

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 languageEnglish
Pages (from-to)2014-2024
Number of pages11
JournalDiscrete Applied Mathematics
Volume161
Issue number13-14
DOIs
Publication statusPublished - Sept 2013

Keywords

  • Maximum degree
  • Order
  • Size
  • Total domination

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Equality in a linear Vizing-like relation that relates the size and total domination number of a graph'. Together they form a unique fingerprint.

Cite this