Some remarks on domination

D. Archdeacon; J. Ellis-Monaghan; D. Fisher; D. Froncek; P.C.B. Lam; S. Seager; B. Wei; R. Yuster

doi:10.1002/jgt.20000

Some remarks on domination

D. Archdeacon, J. Ellis-Monaghan, D. Fisher, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, R. Yuster

Research output: Contribution to journal › Journal article › peer-review

71 Citations (Scopus)

Abstract

We prove a conjecture of Favaron et al. that every graph of order n and minimum degree at least three has a total dominating set of size at least n/2. We also present several related results about: (1) extentions to graphs of minimum degree two, (2) examining graphs where the bound is tight, and (3) a type of bipartite domination and its relation to transversals in hypergraphs.

Original language	English
Pages (from-to)	207-210
Number of pages	4
Journal	Journal of Graph Theory
Volume	46
Issue number	3
Early online date	7 Apr 2004
DOIs	https://doi.org/10.1002/jgt.20000
Publication status	Published - Jul 2004
Externally published	Yes

Scopus Subject Areas

Geometry and Topology

User-Defined Keywords

Bipartite domination
Total domination
Transversals in hypergraphs

Access to Document

10.1002/jgt.20000

Cite this

@article{ca1acf5d8f904c48a6b24ec567e7a9f9,

title = "Some remarks on domination",

abstract = "We prove a conjecture of Favaron et al. that every graph of order n and minimum degree at least three has a total dominating set of size at least n/2. We also present several related results about: (1) extentions to graphs of minimum degree two, (2) examining graphs where the bound is tight, and (3) a type of bipartite domination and its relation to transversals in hypergraphs.",

keywords = "Bipartite domination, Total domination, Transversals in hypergraphs",

author = "D. Archdeacon and J. Ellis-Monaghan and D. Fisher and D. Froncek and P.C.B. Lam and S. Seager and B. Wei and R. Yuster",

note = "Funding Information: Contract grant sponsors: FRG, HKBU (to P.C.B.L.); National Natural Science Foundation of China (to B.W.); Croucher Foundation of Hong Kong (to B.W.). Publisher copyright: {\textcopyright} 2004 Wiley Periodicals, Inc.",

year = "2004",

month = jul,

doi = "10.1002/jgt.20000",

language = "English",

volume = "46",

pages = "207--210",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - Some remarks on domination

AU - Archdeacon, D.

AU - Ellis-Monaghan, J.

AU - Fisher, D.

AU - Froncek, D.

AU - Lam, P.C.B.

AU - Seager, S.

AU - Wei, B.

AU - Yuster, R.

N1 - Funding Information: Contract grant sponsors: FRG, HKBU (to P.C.B.L.); National Natural Science Foundation of China (to B.W.); Croucher Foundation of Hong Kong (to B.W.). Publisher copyright: © 2004 Wiley Periodicals, Inc.

PY - 2004/7

Y1 - 2004/7

N2 - We prove a conjecture of Favaron et al. that every graph of order n and minimum degree at least three has a total dominating set of size at least n/2. We also present several related results about: (1) extentions to graphs of minimum degree two, (2) examining graphs where the bound is tight, and (3) a type of bipartite domination and its relation to transversals in hypergraphs.

AB - We prove a conjecture of Favaron et al. that every graph of order n and minimum degree at least three has a total dominating set of size at least n/2. We also present several related results about: (1) extentions to graphs of minimum degree two, (2) examining graphs where the bound is tight, and (3) a type of bipartite domination and its relation to transversals in hypergraphs.

KW - Bipartite domination

KW - Total domination

KW - Transversals in hypergraphs

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

U2 - 10.1002/jgt.20000

DO - 10.1002/jgt.20000

M3 - Journal article

AN - SCOPUS:3042521168

SN - 0364-9024

VL - 46

SP - 207

EP - 210

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

Some remarks on domination

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this