Open AccessTwo short proofs on total domination
Author(s) -
Allan Bickle
Publication year - 2012
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.1655
Subject(s) - mathematics , combinatorics , dominating set , vertex (graph theory) , mathematical proof , domination analysis , graph , maximal independent set , discrete mathematics , pathwidth , line graph , geometry
A set of vertices of a graph G is a total dominating set if each vertex of G is adjacent to a vertex in the set. The total domination number of a graph Υt (G) is the minimum size of a total dominating set. We provide a short proof of the result that Υt (G) ≤ 2/3n for connected graphs with n ≥ 3 and a short characterization of the extremal graphs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom