Diameter critical graphs

DOI10.1016/J.JCTB.2015.11.004MaRDI QIDQ905895zbMATH OpenOpenAlexFDO

Authors Po-Shen Loh, Jie Ma

Publication date 28 January 2016

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

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

zbMATH Keywords

diameterextremal graph theorycriticalMurty-Simon conjecture

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3750998 (Why is no real title available?)
• scientific article; zbMATH DE number 3788665 (Why is no real title available?)
• scientific article; zbMATH DE number 3497930 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 3218574 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 3259774 (Why is no real title available?)
• A problem of the theory of communication networks
• An Extremal Problem of Graphs with Diameter 2
• Diameters in graphs
• Extremal graphs of diameter 4
• Graphs with small diameter after edge deletion
• Maximal and minimal vertex-critical graphs of diameter two
• Minimum vertex‐diameter‐2‐critical graphs
• On Critical Graphs of Diameter 2
• On diameter 2-critical graphs
• On diameter critical graphs
• On graphs with diameter 2
• On some extremal graphs
• Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey
• The maximum number of edges in a minimal graph of diameter 2

Cited in

(17)

• Exponent-critical primitive graphs and the Kronecker product
• scientific article; zbMATH DE number 1222089 (Why is no real title available?)
• SAT modulo symmetries for graph generation and enumeration
• Strengthening the Murty-Simon conjecture on diameter 2 critical graphs
• Primitive diameter 2-critical graphs
• There exist highly critically connected graphs of diameter three
• scientific article; zbMATH DE number 1332354 (Why is no real title available?)
• scientific article; zbMATH DE number 5248920 (Why is no real title available?)
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Diameter-essential edges in a graph
• Distance-uniform graphs with large diameter
• Complexity and algorithms for constant diameter augmentation problems
• Diameter-vital edges in a graph
• scientific article; zbMATH DE number 1833089 (Why is no real title available?)
• Concerning the number of edges in a graph with diameter constraints
• scientific article; zbMATH DE number 540106 (Why is no real title available?)
• scientific article; zbMATH DE number 1472184 (Why is no real title available?)

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)