On diameter 2-critical graphs
From MaRDI portal
A graph G is diameter 2-critical if \(diam(G)=2\) and \(diam(G-e)>2\) for any its edge e. The reviewer and Simon and Murty conjectured that if G has n vertices and m edges then \(m\leq n^ 2/4\). In this paper it is proved the conjecture for \(n\leq 24\) and also bound \(m<0.2532n^ 2\) for \(n\geq 25\). [Reviewer's remark: Recently Z. Füredi proved the conjecture for very big n.]
Recommendations
- 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
- scientific article; zbMATH DE number 3908467
- Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey
Cites work
Cited in
(35)- The minimum number of edges in a vertex diameter-2-critical graph
- Constructing goal-minimally k-diametric graphs by lifts
- Size in maximal triangle-free graphs and minimal graphs of diameter 2
- Counterexamples to a conjecture of Erdős, Pach, Pollack and Tuza
- On a conjecture of Murty and Simon on diameter 2-critical graphs
- Strengthening the Murty-Simon conjecture on diameter 2 critical graphs
- A characterization of \(P_5\)-free, diameter-2-critical graphs
- Concerning the number of edges in a graph with diameter constraints
- On a conjecture on the diameter of line graphs of graphs of diameter two
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- scientific article; zbMATH DE number 3908467 (Why is no real title available?)
- scientific article; zbMATH DE number 1191010 (Why is no real title available?)
- scientific article; zbMATH DE number 3788665 (Why is no real title available?)
- The maximum number of edges in a minimal graph of diameter 2
- A maximum degree theorem for diameter-2-critical graphs
- scientific article; zbMATH DE number 1222089 (Why is no real title available?)
- A characterization of diameter-2-critical graphs with no antihole of length four
- scientific article; zbMATH DE number 540106 (Why is no real title available?)
- scientific article; zbMATH DE number 1076148 (Why is no real title available?)
- A characterization of diameter-2-critical graphs whose complements are diamond-free
- scientific article; zbMATH DE number 841588 (Why is no real title available?)
- Total domination edge critical graphs with total domination number three and many dominating pairs
- Progress on the Murty-Simon conjecture on diameter-2 critical graphs: a survey
- On the existence of \(k\)-partite or \(K_p\)-free total domination edge-critical graphs
- All my favorite conjectures are critical
- Minimum vertex‐diameter‐2‐critical graphs
- On a conjecture of Murty and Simon on diameter two critical graphs. II.
- Primitive diameter 2-critical graphs
- Perfect matchings in total domination critical graphs
- SAT modulo symmetries for graph generation and enumeration
- A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free
- Extremal graphs domination insensitive to the removal of k edges
- Characterize all \(C_5\)-free diameter-2-critical graphs with at least \(\lfloor \frac{ ( n - 1 )^2}{ 4} \rfloor + 1\) edges
- Diameter critical graphs
- Properties of total domination edge-critical graphs
This page was built for publication: On diameter 2-critical graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1096642)
