Maximum size of digraphs of given radius

DOI10.1016/J.DISC.2023.113429MaRDI QIDQ6041555zbMATH OpenOpenAlexFDO

Authors Stijn Cambie

Publication date 31 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

extremal problemsmaximum sizeoutradiusstrong digraphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

Abstract: In $1967$, Vizing determined the maximum size of a graph with given order and radius. In $1973$, Fridman answered the same question for digraphs with given order and outradius. We investigate that question when restricting to biconnected digraphs. Biconnected digraphs are the digraphs with a finite total distance and hence the interesting ones, as we want to note a connection between minimizing the total distance and maximizing the size under the same constraints. We characterize the extremal digraphs maximizing the size among all biconnected digraphs of order $n$ and outradius $3$, as well as when the order is sufficiently large compared to the outradius. As such, we solve a problem of Dankelmann asymptotically. We also consider these questions for bipartite digraphs and solve a second problem of Dankelmann partially.

Recommendations

• Distance and size in digraphs
• scientific article; zbMATH DE number 1416462
• Maximum size of digraphs with some parameters
• On strong distances in oriented graphs
• Minimum size of a graph or digraph of given radius

Cites work

• An asymptotic resolution of a problem of Plesník
• Diameters in graphs
• Distance and size in digraphs
• Extremal total distance of graphs of given radius I
• Graphs \& digraphs
• scientific article; zbMATH DE number 3255492 (Why is no real title available?)
• Minimum size of a graph or digraph of given radius
• On the sum of all distances in a graph or digraph
• The number of edges in a bipartite graph of given radius
• Wiener index of graphs with radius two

Cited in

(9)

• On the sizes of the graphs G, G^r, G^r G: the directed case
• Maximum size of digraphs with some parameters
• Distance and size in digraphs
• scientific article; zbMATH DE number 824561 (Why is no real title available?)
• scientific article; zbMATH DE number 824573 (Why is no real title available?)
• THE DIAMETER AND RADIUS OF RADIALLY MAXIMAL GRAPHS
• Extremal total distance of graphs of given radius I
• The maximum radius of graphs with given order and minimum degree
• Turán number of strong digraphs forbidden at least two triangles

This page was built for publication: Maximum size of digraphs of given radius

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