More Web Proxy on the site http://driver.im/

article

Progress on the Murty---Simon Conjecture on diameter-2 critical graphs: a survey

Authors:

Teresa W. Haynes,

Michael A. Henning,

Lucas C. Merwe,

Anders YeoAuthors Info & Claims

Journal of Combinatorial Optimization, Volume 30, Issue 3

Pages 579 - 595

https://doi.org/10.1007/s10878-013-9651-7

Published: 01 October 2015 Publication History

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.

References

[1]

Balbuena V, Hansberg A, Haynes TW, Henning MA On total domination edge critical graphs with total domination number three and with many dominating pairs. Submitted for publication.

[2]

Bollobás B (1969) Graphs with given diameter and maximal valency and with a minimal number of edges. Combinatorial mathematics and its applications. Proc Conf Oxford, Academic Press, London, pp 25-37.

[3]

Bondy JA, Murty USR (1972) Extremal graphs of diameter two with prescribed minimum degree. Studia Sci Math Hung 7:239-241.

[4]

Caccetta L, Häggkvist R (1979) On diameter critical graphs. Discret Math 28(3):223-229.

Digital Library

[5]

Chudnovsky M (2012) The structure of bull-free graphs I-three-edge-paths with centers and anticenters. J Comb Theory Ser B 102:233-251.

Digital Library

[6]

Chudnovsky M (2012b) The structure of bull-free graphs II and III-A summary. J Comb Theory Ser B 102:252-282.

Digital Library

[7]

Chudnovsky M, Robertson N, Seymour P, Thomas R (2006) The strong perfect graph theorem. Ann Math 164:51-229.

[8]

Chudnovsky M, Safra S (2008) The Erdös-Hajnal conjecture for bull-free graphs. J Comb Theory Ser B 98:1301-1310.

Digital Library

[9]

Chudnovsky M, Seymour P (2007) Claw-free graphs. I. Orientable prismatic graphs. J Comb Theory Ser B 97(6):867-903.

Digital Library

[10]

Chudnovsky M, Seymour P (2008) Claw-free graphs. II. Non-orientable prismatic graphs. J Comb Theory Ser B 98(2):249-290.

Digital Library

[11]

Chudnovsky M, Seymour P (2008a) Claw-free graphs. III. Circular interval graphs. J Comb Theory Ser B 98(4):812-834.

Digital Library

[12]

Chudnovsky M, Seymour P (2008b) Claw-free graphs. IV. Decomposition theorem. J Comb Theory Ser B 98(5):839-938.

Digital Library

[13]

Chudnovsky M, Seymour P (2008c) Claw-free graphs. V. Global structure. J Comb Theory Ser B 98(6):1373-1410.

Digital Library

[14]

Chvátal V, Sbihi N (1987) Bull-free Berge graphs are perfect. Graphs Comb 3:127-139.

Digital Library

[15]

Cockayne E, Dawes R, Hedetniemi S (1980) Total domination in graphs. Networks 10:211-219.

[16]

Erdös P, Hajnal A (1989) Ramsey-type theorems. Discret Appl Math 25:37-52.

Digital Library

[17]

Fan G (1987) On diameter 2-critical graphs. Discret Math 67:235-240.

Digital Library

[18]

Flandrin E, Faudree R, Ryjá¿ek Z (1997) Claw-free graphs-a survey. Discret Math 164:87-147.

Digital Library

[19]

Füredi Z (1992) The maximum number of edges in a minimal graph of diameter 2. J Graph Theory 16:81-98.

Digital Library

[20]

Gliviak F (1968) On certain classes of graphs of diameter two without superfluous edges. Acta F.R.N Univ Com Math 21:39-48.

[21]

Gliviak F (1975a) On the impossibility to construct diametrically critical graphs by extensions. Arch Math (Brno) 11(3):131-137.

[22]

Gliviak F (1975b) On certain edge-critical graphs of a given diameter. Matematicky ¿asopis 25(3):249-263.

[23]

Gliviak F, Ky¿ P, Plesník J (1969) On the extension of graphs with a given diameter without superfluous edges. Matematicky ¿asopis 19:92-101.

[24]

Hanson D, Wang P (2003) A note on extremal total domination edge critical graphs. Util Math 63:89-96.

[25]

Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Marcel Dekker, Inc., New York.

[26]

Haynes TW, Hedetniemi ST, Slater P (1998b) Domination in graphs: advanced topics. Marcel Dekker, Inc., New York.

[27]

Haynes TW, Henning MA (2012a) A characterization of diameter-2-critical graphs with no antihole of length four. Central Eur J Math 10(3):1125-1132.

[28]

Haynes TW, Henning MA (2012b) A characterization of diameter-2-critical graphs whose complements are diamond-free. Discret Appl Math 160:1979-1985.

Digital Library

[29]

Haynes TW, Henning MA (in press) The Murty Simon Conjecture for bull-free graphs.

[30]

Haynes TW, Henning MA A characterization of P ₅-free, diameter-2-critical graphs. Submitted for publication.

[31]

Haynes TW, Henning MA, van der Merwe LC, Yeo A (2011) On a conjecture of Murty and Simon on diameter-2-critical graphs. Discret Math 311:1918-1924.

Digital Library

[32]

Haynes TW, Henning MA, van der Merwe LC, Yeo A A maximum degree theorem for diameter-2-critical graphs. Submitted for publication.

[33]

Haynes TW, Henning V, van der Merwe V, Yeo A A completion of three proofs related to the Murty-Simon Conjecture. Manuscript.

[34]

Haynes TW, Henning MA, Yeo A (2011) A proof of a conjecture on diameter two critical graphs whose complements are claw-free. Discret Optim 8:495-501.

Digital Library

[35]

Haynes TW, Henning MA, Yeo A (2012) On a conjecture of Murty and Simon on diameter two critical graphs II. Discret Math 312:315-323.

Digital Library

[36]

Haynes TW, Mynhardt CM, van der Merwe LC (1998) Criticality index of total domination. Congr Numerantium 131:67-73.

[37]

Haynes TW, Mynhardt CM, van der Merwe LC (1998) Total domination edge critical graphs. Util Math 54:229-240.

[38]

Haynes TW, Mynhardt CM, van der Merwe LC (2001) Total domination edge critical graphs with maximum diameter. Discuss Math Graph Theory 21:187-205.

[39]

Haynes TW, Mynhardt CM, van der Merwe LC (2003) Total domination edge critical graphs with minimum diameter. Ars Combin 66:79-96.

[40]

Henning MA (2009) Recent results on total domination in graphs: a survey. Discret Math 309:32-63.

Digital Library

[41]

Henning MA, Yeo A. Total domination in graphs (Springer Monographs in Mathematics) 2013. ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 (Online).

[42]

Krishnamoorthy V, Nandakumar R (1981) A class of counterexamples to a conjecture on diameter critical graphs. Combinatorics and Graph Theory, Lecture Notes in Mathematics, Springer, Berlin, pp 297-300.

[43]

Madden J (1999) Going critical: an investigation of diameter-critical graphs. M.Sc Degree. The University of Victoria Columbia.

[44]

Mantel W (1906) Problem 28. Wiskundige Opgaven 10:60-61.

[45]

Murty USR (1968) On critical graphs of diameter 2. Math Mag 41:138-140.

[46]

Plesník J (1975) Critical graphs of given diameter. Acta FRN Univ Comen Math 30:71-93.

[47]

Plesník J (1986) On minimal graphs of diameter 2 with every edge in a 3-cycle. Math Slovaca 36:145-149.

[48]

Turán P (1941) Eine Extremalaufgabe aus der Graphentheorie. Mat Fiz Lapok 48:436-452.

[49]

van der Merwe LC (2000) Total Domination Edge Critical Graphs. Ph.D. Dissertation, University of South Africa.

[50]

Wang P. On Murty-Simon Conjecture. Manuscript. http://arxiv.org/abs/1205.4397.

[51]

Wang T., Wang v, Yu Q. On Murty-Simon Conjecture II. Manuscript. http://arxiv.org/abs/1301.0460.

[52]

Xu J (1984) A proof of a conjecture of Simon and Murty (in Chinese). J Math Res Expo 4:85-86.

Cited By

Kirchweger MSzeider S(2024)SAT Modulo Symmetries for Graph Generation and EnumerationACM Transactions on Computational Logic10.1145/367040525:3(1-30)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3670405
Loh PMa J(2018)Diameter critical graphsJournal of Combinatorial Theory Series B10.1016/j.jctb.2015.11.004117:C(34-58)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.jctb.2015.11.004

Progress on the Murty---Simon Conjecture on diameter-2 critical graphs: a survey
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

A characterization of P5 -free, diameter-2-critical graphs

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no induced path on five vertices. Murty and Simon conjectured that the number ...
Total Domination Edge Critical Graphs with Total Domination Number Three and Many Dominating Pairs

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 \...
On a conjecture of Murty and Simon on diameter 2-critical graphs

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 of order n is at most n^2/4 and that the extremal graphs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Combinatorial Optimization

Journal of Combinatorial Optimization Volume 30, Issue 3

October 2015

435 pages

ISSN:1382-6905

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer Science+Business Media New York.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 October 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kirchweger MSzeider S(2024)SAT Modulo Symmetries for Graph Generation and EnumerationACM Transactions on Computational Logic10.1145/367040525:3(1-30)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3670405
Loh PMa J(2018)Diameter critical graphsJournal of Combinatorial Theory Series B10.1016/j.jctb.2015.11.004117:C(34-58)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1016/j.jctb.2015.11.004

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents