Diameter critical graphs

DOI10.1016/J.JCTB.2015.11.004zbMATH Open1329.05097arXiv1406.6736OpenAlexW2150527183MaRDI QIDQ905895FDOQ905895

Authors: Po-Shen Loh, Jie Ma 

Publication date: 28 January 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A graph is called diameter-$k$-critical if its diameter is $k$, and the removal of any edge strictly increases the diameter. In this paper, we prove several results related to a conjecture often attributed to Murty and Simon, regarding the maximum number of edges that any diameter-$k$-critical graph can have. In particular, we disprove a longstanding conjecture of Caccetta and H"aggkvist (that in every diameter-2-critical graph, the average edge-degree is at most the number of vertices), which promised to completely solve the extremal problem for diameter-2-critical graphs. On the other hand, we prove that the same claim holds for all higher diameters, and is asymptotically tight, resolving the average edge-degree question in all cases except diameter-2. We also apply our techniques to prove several bounds for the original extremal question, including the correct asymptotic bound for diameter-$k$-critical graphs, and an upper bound of $(frac16+o(1))n^2$ for the number of edges in a diameter-3-critical graph.

Full work available at URL: https://arxiv.org/abs/1406.6736

Recommendations

• On diameter 2-critical graphs
• On a conjecture of Murty and Simon on diameter 2-critical graphs
• On a conjecture of Murty and Simon on diameter two critical graphs. II.
• A maximum degree theorem for diameter-2-critical graphs
• Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey

zbMATH Keywords

diameterextremal graph theorycriticalMurty-Simon conjecture

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Diameters in graphs
• On diameter 2-critical graphs
• On diameter critical graphs
• The maximum number of edges in a minimal graph of diameter 2
• On Critical Graphs of Diameter 2
• Minimum vertex‐diameter‐2‐critical graphs
• Extremal graphs of diameter 4
• Title not available (Why is that?)
• A problem of the theory of communication networks
• On some extremal graphs
• Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey
• Title not available (Why is that?)
• Graphs with small diameter after edge deletion
• Maximal and minimal vertex-critical graphs of diameter two
• On graphs with diameter 2
• Title not available (Why is that?)
• An Extremal Problem of Graphs with Diameter 2
• Title not available (Why is that?)

Cited In (17)

• Strengthening the Murty-Simon conjecture on diameter 2 critical graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Diameter-essential edges in a graph
• Title not available (Why is that?)
• Primitive diameter 2-critical graphs
• Distance-uniform graphs with large diameter
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exponent-critical primitive graphs and the Kronecker product
• SAT modulo symmetries for graph generation and enumeration
• There exist highly critically connected graphs of diameter three
• Title not available (Why is that?)
• Concerning the number of edges in a graph with diameter constraints
• Title not available (Why is that?)
• Complexity and algorithms for constant diameter augmentation problems
• Diameter-vital edges in a graph
• Title not available (Why is that?)

This page was built for publication: Diameter critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q905895)