Title

Total Domination Edge Critical Graphs with Total Domination Number Three and Many Dominating Pairs

Document Type

Article

Publication Date

9-24-2015

Description

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph G of order n is at most ⌊n2/4⌋ and that the extremal graphs are the complete bipartite graphs K⌊n/2⌋,⌈n/2⌉. A graph is t-edge-critical, abbreviated 3tEC, if its total domination number is 3 and the addition of any edge decreases the total domination number. It is known that proving the Murty–Simon Conjecture is equivalent to proving that the number of edges in a 3tEC graph of order n is greater than ⌈n(n-2)/4⌉. We study a family F of 3tEC graphs of diameter 2 for which every pair of nonadjacent vertices dominates the graph. We show that the graphs in F are precisely the bull-free 3tEC graphs and that the number of edges in such graphs is at least ⌊(n2-4)/4⌋, proving the conjecture for this family. We characterize the extremal graphs, and conjecture that this improved bound is in fact a lower bound for all 3tEC graphs of diameter 2. Finally we slightly relax the requirement in the definition of F—instead of requiring that all pairs of nonadjacent vertices dominate to requiring that only most of these pairs dominate—and prove the Murty–Simon equivalent conjecture for these 3tEC graphs.

Link to Full Text
COinS