Relationships between total domination, order, size, and maximum degree of graphs

✍ Scribed by Anders Yeo

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 163 KB
• Volume: 55
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20240

✦ Synopsis

Abstract

A total dominating set, S, in a graph, G, has the property that every vertex in G is adjacent to a vertex in S. The total dominating number, γ~t~(G) of a graph G is the size of a minimum total dominating set in G. Let G be a graph with no component of size one or two and with Δ(G) ≥ 3. In 6, it was shown that |E(G)| ≤ Δ(G) (|V(G)|–γ~t~(G)) and conjectured that |E(G)| ≤ (Δ(G)+3) (|V(G)|–γ~t~(G))/2 holds. In this article, we prove that $\leq (\Delta(G)+ 2\sqrt{\Delta}) (|V(G)| - \gamma_{t}(G))/2$ holds and that the above conjecture is false as there for every Δ exist Δ‐regular bipartite graphs G with |E(G)| ≥ (Δ+0.1 ln(Δ)) (|V(G)|–γ~t~(G))/2. The last result also disproves a conjecture on domination numbers from 8. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 325–337, 2007