Paper Info
Title
Total Domination Edge Critical Graphs with Total Domination Number Three and Many Dominating Pairs.
Abstract
A graph $$G$$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$$G of order $$n$$n is at most $$\\lfloor n^2/4 \\rfloor $$¿n2/4¿ and that the extremal graphs are the complete bipartite graphs $$K_{{\\lfloor n/2 \\rfloor },{\\lceil n/2 \\rceil }}$$K¿n/2¿,¿n/2¿. A graph is $$3_t$$3t-edge-critical, abbreviated $$3_tEC$$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 $$3_tEC$$3tEC graph of order $$n$$n is greater than $$\\lceil n(n-2)/4 \\rceil $$¿n(n-2)/4¿. We study a family $$\\mathcal{F}$$F of $$3_tEC$$3tEC graphs of diameter 2 for which every pair of nonadjacent vertices dominates the graph. We show that the graphs in $$\\mathcal{F}$$F are precisely the bull-free $$3_tEC$$3tEC graphs and that the number of edges in such graphs is at least $$\\lfloor (n^2 - 4)/4 \\rfloor $$¿(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 $$3_tEC$$3tEC graphs of diameter 2. Finally we slightly relax the requirement in the definition of $$\\mathcal{F}$$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 $$3_tEC$$3tEC graphs.
Year
DOI
Venue
2015
10.1007/s00373-014-1469-2
Graphs and Combinatorics
Keywords
DocType
Volume
Diameter critical, Domination, Diameter-2-critical, Total domination edge critical, Bull-free, 05C65, 05C69
Journal
31
Issue
ISSN
Citations 
5
1435-5914
0
PageRank 
References 
Authors
0.34
18
4
Name
Order
Citations
PageRank
Camino Balbuena115726.86
adriana hansberg213317.47
Teresa W. Haynes377494.22
Michael A. Henning41865246.94