Total domination critical graphs with respect to relative complements

Teresa W. Haynes; Michael A. Henning; Lucas C. Van der Merwe

Total domination critical graphs with respect to relative complements

Teresa W. Haynes, Michael A. Henning, Lucas C. Van der Merwe

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

11 Citations (Scopus)

Abstract

A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ_t(G) is the minimum cardinality of a total dominating set of G. Let G be a spanning subgraph of K_s,s and let H be the complement of G relative to K_s,s; that is, K_s,s = G ⊕ H is a factorization of K_s,s. The graph G is k_t-critical relative to K_s,s if γ_t(G) = k and γ _t(G + e) < k for all e ∈ E(H). We study k _t-critical graphs relative to K_s,s for small values of k. In particular, we characterize the 3_t-critical and 4 _t-critical graphs.

Original language	English
Pages (from-to)	169-179
Number of pages	11
Journal	Ars Combinatoria
Volume	64
Publication status	Published - Jul 2002
Externally published	Yes

ASJC Scopus subject areas

General Mathematics

Cite this

@article{35bfe369a7a948a0bfbebd1882875feb,

title = "Total domination critical graphs with respect to relative complements",

abstract = "A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. Let G be a spanning subgraph of Ks,s and let H be the complement of G relative to Ks,s; that is, Ks,s = G ⊕ H is a factorization of Ks,s. The graph G is kt-critical relative to Ks,s if γt(G) = k and γ t(G + e) < k for all e ∈ E(H). We study k t-critical graphs relative to Ks,s for small values of k. In particular, we characterize the 3t-critical and 4 t-critical graphs.",

author = "Haynes, {Teresa W.} and Henning, {Michael A.} and {Van der Merwe}, {Lucas C.}",

year = "2002",

month = jul,

language = "English",

volume = "64",

pages = "169--179",

journal = "Ars Combinatoria",

issn = "0381-7032",

publisher = "Charles Babbage Research Centre",

}

TY - JOUR

T1 - Total domination critical graphs with respect to relative complements

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - Van der Merwe, Lucas C.

PY - 2002/7

Y1 - 2002/7

N2 - A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. Let G be a spanning subgraph of Ks,s and let H be the complement of G relative to Ks,s; that is, Ks,s = G ⊕ H is a factorization of Ks,s. The graph G is kt-critical relative to Ks,s if γt(G) = k and γ t(G + e) < k for all e ∈ E(H). We study k t-critical graphs relative to Ks,s for small values of k. In particular, we characterize the 3t-critical and 4 t-critical graphs.

AB - A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. Let G be a spanning subgraph of Ks,s and let H be the complement of G relative to Ks,s; that is, Ks,s = G ⊕ H is a factorization of Ks,s. The graph G is kt-critical relative to Ks,s if γt(G) = k and γ t(G + e) < k for all e ∈ E(H). We study k t-critical graphs relative to Ks,s for small values of k. In particular, we characterize the 3t-critical and 4 t-critical graphs.

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

M3 - Article

AN - SCOPUS:0142231023

SN - 0381-7032

VL - 64

SP - 169

EP - 179

JO - Ars Combinatoria

JF - Ars Combinatoria

ER -

Total domination critical graphs with respect to relative complements

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this