The maximum diameter of total domination edge-critical graphs

Michael A. Henning; Lucas C. Van Der Merwe

doi:10.1016/j.disc.2011.09.032

The maximum diameter of total domination edge-critical graphs

Michael A. Henning, Lucas C. Van Der Merwe

Mathematics and Applied Mathematics

University of Tennessee, Chattanooga

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ_t(G) of G. The graph G is total domination edge-critical if for every edge e in the complement of G, γ_t(G+e)<γ_t(G). We call such graphs γ_tEC. If G isγ_tEC and γ_t(G)=k, we say that G is k_tEC. For k<2, we show that the maximum diameter of a k_tEC graph is at least ⌊3(k-1)/2⌋ and this bound is sharp for small k≤6.

Original language	English
Pages (from-to)	397-404
Number of pages	8
Journal	Discrete Mathematics
Volume	312
Issue number	2
DOIs	https://doi.org/10.1016/j.disc.2011.09.032
Publication status	Published - 28 Jan 2012

Keywords

Bounds
Diameter
Edge-critical
Total domination

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2011.09.032

Cite this

@article{aba779b3869e4d3caabc4173a1d21a44,

title = "The maximum diameter of total domination edge-critical graphs",

abstract = "A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γt(G) of G. The graph G is total domination edge-critical if for every edge e in the complement of G, γt(G+e)<γt(G). We call such graphs γtEC. If G isγtEC and γt(G)=k, we say that G is ktEC. For k<2, we show that the maximum diameter of a ktEC graph is at least ⌊3(k-1)/2⌋ and this bound is sharp for small k≤6.",

keywords = "Bounds, Diameter, Edge-critical, Total domination",

author = "Henning, {Michael A.} and {Van Der Merwe}, {Lucas C.}",

year = "2012",

month = jan,

day = "28",

doi = "10.1016/j.disc.2011.09.032",

language = "English",

volume = "312",

pages = "397--404",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - The maximum diameter of total domination edge-critical graphs

AU - Henning, Michael A.

AU - Van Der Merwe, Lucas C.

PY - 2012/1/28

Y1 - 2012/1/28

N2 - A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γt(G) of G. The graph G is total domination edge-critical if for every edge e in the complement of G, γt(G+e)<γt(G). We call such graphs γtEC. If G isγtEC and γt(G)=k, we say that G is ktEC. For k<2, we show that the maximum diameter of a ktEC graph is at least ⌊3(k-1)/2⌋ and this bound is sharp for small k≤6.

AB - A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γt(G) of G. The graph G is total domination edge-critical if for every edge e in the complement of G, γt(G+e)<γt(G). We call such graphs γtEC. If G isγtEC and γt(G)=k, we say that G is ktEC. For k<2, we show that the maximum diameter of a ktEC graph is at least ⌊3(k-1)/2⌋ and this bound is sharp for small k≤6.

KW - Bounds

KW - Diameter

KW - Edge-critical

KW - Total domination

UR - http://www.scopus.com/inward/record.url?scp=80955134059&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2011.09.032

DO - 10.1016/j.disc.2011.09.032

M3 - Article

AN - SCOPUS:80955134059

SN - 0012-365X

VL - 312

SP - 397

EP - 404

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

The maximum diameter of total domination edge-critical graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this