Premium
Some remarks on domination
Author(s) -
Archdeacon D.,
EllisMonaghan J.,
Fisher D.,
Froncek D.,
Lam P.C.B.,
Seager S.,
Wei B.,
Yuster R.
Publication year - 2004
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20000
Subject(s) - mathematics , combinatorics
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. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 207–210, 2004