Graphs with small diameter after edge deletion

DOI10.1016/0166-218X(92)90126-UMaRDI QIDQ1199416zbMATH OpenFDO

Authors Fan Chung

Publication date 16 January 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(92)90126-U

zbMATH Keywords

diameteredge deletionminimum number of edges

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

Let \(g(n,D)\) be a minimum number of edges of a graph on \(n\) vertices such that after removing any edge the resulting graph is of diameter at most \(D\). The problem of finding the values of \(g\) is a special case of a question asked by \textit{K. Vijayan} and \textit{U. S. R. Murty} [Sankhyā, Ser. A 26, 299-302 (1964; Zbl 0134.433)]. In the paper \(g(n,D)\) is determined for general \(n\) and \(D\).

Recommendations

• Publication:3470486
• Diameter bounds for altered graphs
• Extremal graphs of diameter at most 6 after deleting any vertex
• Publication:4723767
• Diameter vulnerability of graphs by edge deletion

Cites work

• A problem of the theory of communication networks
• An Extremal Problem of Graphs with Diameter 2
• Diameter bounds for altered graphs
• Extremal graphs of diameter 4
• scientific article; zbMATH DE number 3959292 (Why is no real title available?)
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3674126 (Why is no real title available?)
• scientific article; zbMATH DE number 3730180 (Why is no real title available?)
• scientific article; zbMATH DE number 3510348 (Why is no real title available?)
• scientific article; zbMATH DE number 3534505 (Why is no real title available?)
• scientific article; zbMATH DE number 3537714 (Why is no real title available?)
• scientific article; zbMATH DE number 3556138 (Why is no real title available?)
• scientific article; zbMATH DE number 3435527 (Why is no real title available?)
• scientific article; zbMATH DE number 3218574 (Why is no real title available?)
• scientific article; zbMATH DE number 3259774 (Why is no real title available?)
• scientific article; zbMATH DE number 3309000 (Why is no real title available?)
• On Critical Graphs of Diameter 2
• On graphs with diameter 2
• On some extremal graphs
• The Diameter of a Cycle Plus a Random Matching
• The diameter of random regular graphs

Cited in

(15)

• Large fault-tolerant interconnection networks
• Vulnerability in graphs of diameter four
• Complexity and algorithms for constant diameter augmentation problems
• On diameter stability of the Johnson graph.
• scientific article; zbMATH DE number 4137792 (Why is no real title available?)
• Extremal graphs of diameter at most 6 after deleting any vertex
• Diameter increase caused by edge deletion
• Characterization of some extremal graphs with diameter no greater than three
• scientific article; zbMATH DE number 3995718 (Why is no real title available?)
• Exponent-critical primitive graphs and the Kronecker product
• Edge deletion and invariance in graphs using \(D\)-distance
• scientific article; zbMATH DE number 2190093 (Why is no real title available?)
• Designing distrance-preserving fault-tolerant topologies
• Witness rectangle graphs
• Diameter critical graphs

This page was built for publication: Graphs with small diameter after edge deletion

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