Total domination supercritical graphs with respect to relative complements

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

doi:10.1016/S0012-365X(02)00537-X

Total domination supercritical 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

2 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 connected 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-supercritical relative to K_s,s, if γ_t(G) = k and γ₁(G + e) = k - 2 for all e ∈ E(H). Properties of k-supercritical graphs are presented, and k-supercritical graphs are characterized for small k.

Original language	English
Pages (from-to)	X361-371
Journal	Discrete Mathematics
Volume	258
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(02)00537-X
Publication status	Published - 6 Dec 2002
Externally published	Yes

Keywords

Domination
Relative complement
Total domination
Total domination edge critical graphs
Total domination supercritical graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(02)00537-X

Cite this

@article{054d08bb700642e9b3aacbfacaf4a331,

title = "Total domination supercritical 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 connected 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 k-supercritical relative to Ks,s, if γt(G) = k and γ1(G + e) = k - 2 for all e ∈ E(H). Properties of k-supercritical graphs are presented, and k-supercritical graphs are characterized for small k.",

keywords = "Domination, Relative complement, Total domination, Total domination edge critical graphs, Total domination supercritical graphs",

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

year = "2002",

month = dec,

day = "6",

doi = "10.1016/S0012-365X(02)00537-X",

language = "English",

volume = "258",

pages = "X361--371",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Total domination supercritical graphs with respect to relative complements

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - Van Der Merwe, Lucas C.

PY - 2002/12/6

Y1 - 2002/12/6

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 connected 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 k-supercritical relative to Ks,s, if γt(G) = k and γ1(G + e) = k - 2 for all e ∈ E(H). Properties of k-supercritical graphs are presented, and k-supercritical graphs are characterized for small k.

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 connected 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 k-supercritical relative to Ks,s, if γt(G) = k and γ1(G + e) = k - 2 for all e ∈ E(H). Properties of k-supercritical graphs are presented, and k-supercritical graphs are characterized for small k.

KW - Domination

KW - Relative complement

KW - Total domination

KW - Total domination edge critical graphs

KW - Total domination supercritical graphs

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

U2 - 10.1016/S0012-365X(02)00537-X

DO - 10.1016/S0012-365X(02)00537-X

M3 - Article

AN - SCOPUS:0037032976

SN - 0012-365X

VL - 258

SP - X361-371

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Total domination supercritical graphs with respect to relative complements

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this