nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.10.2015

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

verfasst von: Teresa W. Haynes, Michael A. Henning, Lucas C. van der Merwe, Anders Yeo

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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 \(\lfloor n^2/4 \rfloor \) and that the extremal graphs are the complete bipartite graphs \(K_{{\lfloor n/2 \rfloor },{\lceil n/2 \rceil }}\). 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.

Vorheriger Artikel Approximating minimum power edge-multi-covers

Nächster Artikel The game Grundy indices of graphs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Gliviak F (1975b) On certain edge-critical graphs of a given diameter. Matematický časopis 25(3):249–263MathSciNetMATH

Gliviak F, Kyš P, Plesník J (1969) On the extension of graphs with a given diameter without superfluous edges. Matematický časopis 19:92–101MATH

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

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

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

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–1132MathSciNetCrossRefMATH

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

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

Haynes TW, Henning MA A characterization of \(P_5\)-free, diameter-2-critical graphs. Submitted for publication.

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–1924CrossRefMATH

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

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

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–501MathSciNetCrossRefMATH

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

Titel: Progress on the Murty–Simon Conjecture on diameter-2 critical graphs: a survey
verfasst von: Teresa W. Haynes
Michael A. Henning
Lucas C. van der Merwe
Anders Yeo
Publikationsdatum: 01.10.2015
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 3/2015
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-013-9651-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2015

A unified linear-programming modeling of some topological indices

An extended approach for lifting clique tree inequalities

A 0.5358-approximation for Bandpass-2

Co-2-plex vertex partitions

Rank bounds for a hierarchy of Lovász and Schrijver

The game Grundy indices of graphs