THE DIAMETER AND RADIUS OF RADIALLY MAXIMAL GRAPHS

DOI10.1017/S0004972720001471MaRDI QIDQ4959261zbMATH OpenOpenAlexFDO

Authors Pu Qiao, Xingzhi Zhan

Publication date 13 September 2021

Published in Bulletin of the Australian Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

diametereccentricityradially maximal graphradius

Mathematics Subject Classification ID

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

Abstract: A graph is called radially maximal if it is not complete and the addition of any new edge decreases its radius. In 1976 Harary and Thomassen proved that the radius $r$ and diameter $d$ of any radially maximal graph satisfy $rledle2r-2.$ Dutton, Medidi and Brigham rediscovered this result with a different proof in 1995 and they posed the conjecture that the converse is true, that is, if $r$ and $d$ are positive integers satisfying $rledle2r-2,$ then there exists a radially maximal graph with radius $r$ and diameter $d.$ We prove this conjecture and a little more.

Recommendations

• scientific article; zbMATH DE number 637283
• Graphs with given diameter maximizing the spectral radius
• Maximal diameter on a class of circulant graphs
• scientific article; zbMATH DE number 7587174
• Maximum size of digraphs of given radius
• Maximizing the Laplacian spectral radii of graphs with given diameter
• Maximal graphs and graphs with maximal spectral radius
• The maximum girth and minimum circumference of graphs with prescribed radius and diameter
• On radius and typical properties of \(n\)-vertex graphs of given diameter
• Maximizing the spectral radius of k-connected graphs with given diameter

Cites work

• Anticritical graphs
• Changing and unchanging of the radius of a graph
• scientific article; zbMATH DE number 637283 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)

Cited in

(13)

• Radius versus diameter in cocomparability and intersection graphs
• The maximum girth and minimum circumference of graphs with prescribed radius and diameter
• On radius and typical properties of \(n\)-vertex graphs of given diameter
• Radii and centers in iterated line digraphs
• Further results on radial graphs
• Minimal non-selfcentric radially-maximal graphs of radius 4
• Minimal non-selfcentric radially-maximal graphs of radii 4 and 5
• scientific article; zbMATH DE number 637283 (Why is no real title available?)
• scientific article; zbMATH DE number 942765 (Why is no real title available?)
• scientific article; zbMATH DE number 908141 (Why is no real title available?)
• Radial digraphs
• Graphs with prescribed radius, diameter, and center
• The maximum radius of graphs with given order and minimum degree

This page was built for publication: THE DIAMETER AND RADIUS OF RADIALLY MAXIMAL GRAPHS

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