{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T22:09:48Z","timestamp":1784844588617,"version":"3.55.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,8,31]],"date-time":"2013-08-31T00:00:00Z","timestamp":1377907200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s10878-013-9651-7","type":"journal-article","created":{"date-parts":[[2013,8,30]],"date-time":"2013-08-30T05:35:42Z","timestamp":1377840942000},"page":"579-595","source":"Crossref","is-referenced-by-count":8,"title":["Progress on the Murty\u2013Simon Conjecture on diameter-2 critical graphs: a survey"],"prefix":"10.1007","volume":"30","author":[{"given":"Teresa W.","family":"Haynes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael A.","family":"Henning","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lucas C.","family":"van der Merwe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,8,31]]},"reference":[{"key":"9651_CR1","unstructured":"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"},{"key":"9651_CR2","first-page":"25","volume-title":"Combinatorial mathematics and its applications","author":"B Bollob\u00e1s","year":"1969","unstructured":"Bollob\u00e1s 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\u201337"},{"key":"9651_CR3","first-page":"239","volume":"7","author":"JA Bondy","year":"1972","unstructured":"Bondy JA, Murty USR (1972) Extremal graphs of diameter two with prescribed minimum degree. Studia Sci Math Hung 7:239\u2013241","journal-title":"Studia Sci Math Hung"},{"issue":"3","key":"9651_CR4","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0012-365X(79)90129-8","volume":"28","author":"L Caccetta","year":"1979","unstructured":"Caccetta L, H\u00e4ggkvist R (1979) On diameter critical graphs. Discret Math 28(3):223\u2013229","journal-title":"Discret Math"},{"key":"9651_CR5","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/j.jctb.2011.07.003","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky M (2012) The structure of bull-free graphs I-three-edge-paths with centers and anticenters. J Comb Theory Ser B 102:233\u2013251","journal-title":"J Comb Theory Ser B"},{"key":"9651_CR6","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/j.jctb.2011.07.002","volume":"102","author":"M Chudnovsky","year":"2012","unstructured":"Chudnovsky M (2012b) The structure of bull-free graphs II and III-A summary. J Comb Theory Ser B 102:252\u2013282","journal-title":"J Comb Theory Ser B"},{"key":"9651_CR7","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky M, Robertson N, Seymour P, Thomas R (2006) The strong perfect graph theorem. Ann Math 164:51\u2013229","journal-title":"Ann Math"},{"key":"9651_CR8","doi-asserted-by":"crossref","first-page":"1301","DOI":"10.1016\/j.jctb.2008.02.005","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky M, Safra S (2008) The Erd\u00f6s-Hajnal conjecture for bull-free graphs. J Comb Theory Ser B 98:1301\u20131310","journal-title":"J Comb Theory Ser B"},{"issue":"6","key":"9651_CR9","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1016\/j.jctb.2007.02.002","volume":"97","author":"M Chudnovsky","year":"2007","unstructured":"Chudnovsky M, Seymour P (2007) Claw-free graphs. I. Orientable prismatic graphs. J Comb Theory Ser B 97(6):867\u2013903","journal-title":"J Comb Theory Ser B"},{"issue":"2","key":"9651_CR10","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/j.jctb.2007.06.006","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky M, Seymour P (2008) Claw-free graphs. II. Non-orientable prismatic graphs. J Comb Theory Ser B 98(2):249\u2013290","journal-title":"J Comb Theory Ser B"},{"issue":"4","key":"9651_CR11","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1016\/j.jctb.2008.03.001","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky M, Seymour P (2008a) Claw-free graphs. III. Circular interval graphs. J Comb Theory Ser B 98(4):812\u2013834","journal-title":"J Comb Theory Ser B"},{"issue":"5","key":"9651_CR12","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1016\/j.jctb.2007.06.007","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky M, Seymour P (2008b) Claw-free graphs. IV. Decomposition theorem. J Comb Theory Ser B 98(5):839\u2013938","journal-title":"J Comb Theory Ser B"},{"issue":"6","key":"9651_CR13","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1016\/j.jctb.2008.03.002","volume":"98","author":"M Chudnovsky","year":"2008","unstructured":"Chudnovsky M, Seymour P (2008c) Claw-free graphs. V. Global structure. J Comb Theory Ser B 98(6):1373\u20131410","journal-title":"J Comb Theory Ser B"},{"key":"9651_CR14","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01788536","volume":"3","author":"V Chv\u00e1tal","year":"1987","unstructured":"Chv\u00e1tal V, Sbihi N (1987) Bull-free Berge graphs are perfect. Graphs Comb 3:127\u2013139","journal-title":"Graphs Comb"},{"key":"9651_CR15","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1002\/net.3230100304","volume":"10","author":"E Cockayne","year":"1980","unstructured":"Cockayne E, Dawes R, Hedetniemi S (1980) Total domination in graphs. Networks 10:211\u2013219","journal-title":"Networks"},{"key":"9651_CR16","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0166-218X(89)90045-0","volume":"25","author":"P Erd\u00f6s","year":"1989","unstructured":"Erd\u00f6s P, Hajnal A (1989) Ramsey-type theorems. Discret Appl Math 25:37\u201352","journal-title":"Discret Appl Math"},{"key":"9651_CR17","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0012-365X(87)90174-9","volume":"67","author":"G Fan","year":"1987","unstructured":"Fan G (1987) On diameter 2-critical graphs. Discret Math 67:235\u2013240","journal-title":"Discret Math"},{"key":"9651_CR18","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0012-365X(96)00045-3","volume":"164","author":"E Flandrin","year":"1997","unstructured":"Flandrin E, Faudree R, Ryj\u00e1\u010dek Z (1997) Claw-free graphs\u2013a survey. Discret Math 164:87\u2013147","journal-title":"Discret Math"},{"key":"9651_CR19","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1002\/jgt.3190160110","volume":"16","author":"Z F\u00fcredi","year":"1992","unstructured":"F\u00fcredi Z (1992) The maximum number of edges in a minimal graph of diameter 2. J Graph Theory 16:81\u201398","journal-title":"J Graph Theory"},{"key":"9651_CR20","first-page":"39","volume":"21","author":"F Gliviak","year":"1968","unstructured":"Gliviak F (1968) On certain classes of graphs of diameter two without superfluous edges. Acta F.R.N Univ Com Math 21:39\u201348","journal-title":"Acta F.R.N Univ Com Math"},{"issue":"3","key":"9651_CR21","first-page":"131","volume":"11","author":"F Gliviak","year":"1975","unstructured":"Gliviak F (1975a) On the impossibility to construct diametrically critical graphs by extensions. Arch Math (Brno) 11(3):131\u2013137","journal-title":"Arch Math (Brno)"},{"issue":"3","key":"9651_CR22","first-page":"249","volume":"25","author":"F Gliviak","year":"1975","unstructured":"Gliviak F (1975b) On certain edge-critical graphs of a given diameter. Matematick\u00fd \u010dasopis 25(3):249\u2013263","journal-title":"Matematick\u00fd \u010dasopis"},{"key":"9651_CR23","first-page":"92","volume":"19","author":"F Gliviak","year":"1969","unstructured":"Gliviak F, Ky\u0161 P, Plesn\u00edk J (1969) On the extension of graphs with a given diameter without superfluous edges. Matematick\u00fd \u010dasopis 19:92\u2013101","journal-title":"Matematick\u00fd \u010dasopis"},{"key":"9651_CR24","first-page":"89","volume":"63","author":"D Hanson","year":"2003","unstructured":"Hanson D, Wang P (2003) A note on extremal total domination edge critical graphs. Util Math 63:89\u201396","journal-title":"Util Math"},{"key":"9651_CR25","volume-title":"Fundamentals of domination in graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998a) Fundamentals of domination in graphs. Marcel Dekker, Inc., New York"},{"key":"9651_CR26","volume-title":"Domination in graphs: advanced topics","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Hedetniemi ST, Slater P (1998b) Domination in graphs: advanced topics. Marcel Dekker, Inc., New York"},{"issue":"3","key":"9651_CR27","doi-asserted-by":"crossref","first-page":"1125","DOI":"10.2478\/s11533-012-0022-x","volume":"10","author":"TW Haynes","year":"2012","unstructured":"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\u20131132","journal-title":"Central Eur J Math"},{"key":"9651_CR28","doi-asserted-by":"crossref","first-page":"1979","DOI":"10.1016\/j.dam.2012.03.037","volume":"160","author":"TW Haynes","year":"2012","unstructured":"Haynes TW, Henning MA (2012b) A characterization of diameter-2-critical graphs whose complements are diamond-free. Discret Appl Math 160:1979\u20131985","journal-title":"Discret Appl Math"},{"key":"9651_CR29","unstructured":"Haynes TW, Henning MA (in press) The Murty Simon Conjecture for bull-free graphs."},{"key":"9651_CR30","unstructured":"Haynes TW, Henning MA A characterization of $$P_5$$ P 5 -free, diameter-2-critical graphs. Submitted for publication."},{"key":"9651_CR31","doi-asserted-by":"crossref","first-page":"1918","DOI":"10.1016\/j.disc.2011.05.007","volume":"311","author":"TW Haynes","year":"2011","unstructured":"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\u20131924","journal-title":"Discret Math"},{"key":"9651_CR32","unstructured":"Haynes TW, Henning MA, van der Merwe LC, Yeo A A maximum degree theorem for diameter-2-critical graphs. Submitted for publication"},{"key":"9651_CR33","unstructured":"Haynes TW, Henning V, van der Merwe V, Yeo A A completion of three proofs related to the Murty-Simon Conjecture. Manuscript"},{"key":"9651_CR34","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/j.disopt.2011.04.003","volume":"8","author":"TW Haynes","year":"2011","unstructured":"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\u2013501","journal-title":"Discret Optim"},{"key":"9651_CR35","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.disc.2011.09.022","volume":"312","author":"TW Haynes","year":"2012","unstructured":"Haynes TW, Henning MA, Yeo A (2012) On a conjecture of Murty and Simon on diameter two critical graphs II. Discret Math 312:315\u2013323","journal-title":"Discret Math"},{"key":"9651_CR36","first-page":"67","volume":"131","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Mynhardt CM, van der Merwe LC (1998) Criticality index of total domination. Congr Numerantium 131:67\u201373","journal-title":"Congr Numerantium"},{"key":"9651_CR37","first-page":"229","volume":"54","author":"TW Haynes","year":"1998","unstructured":"Haynes TW, Mynhardt CM, van der Merwe LC (1998) Total domination edge critical graphs. Util Math 54:229\u2013240","journal-title":"Util Math"},{"key":"9651_CR38","doi-asserted-by":"crossref","first-page":"187","DOI":"10.7151\/dmgt.1143","volume":"21","author":"TW Haynes","year":"2001","unstructured":"Haynes TW, Mynhardt CM, van der Merwe LC (2001) Total domination edge critical graphs with maximum diameter. Discuss Math Graph Theory 21:187\u2013205","journal-title":"Discuss Math Graph Theory"},{"key":"9651_CR39","first-page":"79","volume":"66","author":"TW Haynes","year":"2003","unstructured":"Haynes TW, Mynhardt CM, van der Merwe LC (2003) Total domination edge critical graphs with minimum diameter. Ars Combin 66:79\u201396","journal-title":"Ars Combin"},{"key":"9651_CR40","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.disc.2007.12.044","volume":"309","author":"MA Henning","year":"2009","unstructured":"Henning MA (2009) Recent results on total domination in graphs: a survey. Discret Math 309:32\u201363","journal-title":"Discret Math"},{"key":"9651_CR41","unstructured":"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)"},{"key":"9651_CR42","doi-asserted-by":"crossref","unstructured":"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\u2013300","DOI":"10.1007\/BFb0092274"},{"key":"9651_CR43","unstructured":"Madden J (1999) Going critical: an investigation of diameter-critical graphs. M.Sc Degree. The University of Victoria Columbia"},{"key":"9651_CR44","first-page":"60","volume":"10","author":"W Mantel","year":"1906","unstructured":"Mantel W (1906) Problem 28. Wiskundige Opgaven 10:60\u201361","journal-title":"Wiskundige Opgaven"},{"key":"9651_CR45","doi-asserted-by":"crossref","first-page":"138","DOI":"10.2307\/2688184","volume":"41","author":"USR Murty","year":"1968","unstructured":"Murty USR (1968) On critical graphs of diameter $$2$$ 2 . Math Mag 41:138\u2013140","journal-title":"Math Mag"},{"key":"9651_CR46","first-page":"71","volume":"30","author":"J Plesn\u00edk","year":"1975","unstructured":"Plesn\u00edk J (1975) Critical graphs of given diameter. Acta FRN Univ Comen Math 30:71\u201393","journal-title":"Acta FRN Univ Comen Math"},{"key":"9651_CR47","first-page":"145","volume":"36","author":"J Plesn\u00edk","year":"1986","unstructured":"Plesn\u00edk J (1986) On minimal graphs of diameter $$2$$ 2 with every edge in a $$3$$ 3 -cycle. Math Slovaca 36:145\u2013149","journal-title":"Math Slovaca"},{"key":"9651_CR48","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n P (1941) Eine Extremalaufgabe aus der Graphentheorie. Mat Fiz Lapok 48:436\u2013452","journal-title":"Mat Fiz Lapok"},{"key":"9651_CR49","unstructured":"van der Merwe LC (2000) Total Domination Edge Critical Graphs. Ph.D. Dissertation, University of South Africa"},{"key":"9651_CR50","unstructured":"Wang P. On Murty-Simon Conjecture. Manuscript. http:\/\/arxiv.org\/abs\/1205.4397"},{"key":"9651_CR51","unstructured":"Wang T. , Wang v, Yu Q. On Murty-Simon Conjecture II. Manuscript. http:\/\/arxiv.org\/abs\/1301.0460"},{"key":"9651_CR52","first-page":"85","volume":"4","author":"J Xu","year":"1984","unstructured":"Xu J (1984) A proof of a conjecture of Simon and Murty (in Chinese). J Math Res Expo 4:85\u201386","journal-title":"J Math Res Expo"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9651-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9651-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9651-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,22]],"date-time":"2019-07-22T13:50:13Z","timestamp":1563803413000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9651-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,31]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["9651"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9651-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8,31]]}}}