Abstract | ||
---|---|---|
A graph $$G$$G is diameter $$2$$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$$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¿. We survey the progress made to date on this conjecture, concentrating mainly on recent results developed from associating the conjecture to an equivalent one involving total domination. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/s10878-013-9651-7 | Journal of Combinatorial Optimization |
Keywords | Field | DocType |
Total domination,Diameter-2-critical,Total domination edge-critical,05C69 | Discrete mathematics,Graph,Combinatorics,Bipartite graph,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 3 | 1382-6905 |
Citations | PageRank | References |
3 | 0.39 | 24 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Teresa W. Haynes | 1 | 774 | 94.22 |
Michael A. Henning | 2 | 1865 | 246.94 |
Lucas C. van der Merwe | 3 | 94 | 11.53 |
Anders Yeo | 4 | 1225 | 108.09 |