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.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-16655 |
| Date | 24 September 2015 |
| Creators | Balbuena, Camino, Hansberg, Adriana, Haynes, Teresa W., Henning, Michael A. |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Source | ETSU Faculty Works |
Page generated in 0.0022 seconds