On strong distances in oriented graphs

DOI10.1016/S0012-365X(02)00807-5MaRDI QIDQ1810644zbMATH OpenFDO

Authors Peter Dankelmann, H. C. Swart, David Day

Publication date 9 June 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(02)00807-5

zbMATH Keywords

directed graphdistancestrong connectivitystrong diameterstrong distancestrong radius

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Review text

Let \(D\) be a strongly connected digraph. The strong distance between two vertices \(u\) and \(v\) in \(D\) is the minimum size of a strongly connected subdigraph of \(D\) containing \(u\) and \(v\). The authors also define the strong connectivity, strong diameter and strong radius. The main results of the paper are: (a) estimation of the strong diameter of \(D\) using either an order and directed girth of \(D\) (Theorem 1) or an order and strong connectivity of \(D\) (Theorem 2); (b) estimation of the strong radius of \(D\).

Cited in

(21)

• Optimal strong \((\kappa ,d)\)-orientation of complete \(k\)-partite graphs
• Distance in digraphs
• Minimum average distance of strong orientations of graphs
• On the strong distance problems of pyramid networks
• Lower and upper orientable strong radius and strong diameter of complete \(k\)-partite graphs
• Lower and upper orientable strong radius and diameter of Cartesian product of paths
• Strongly self-centered orientation of complete k-partite graphs
• scientific article; zbMATH DE number 1029226 (Why is no real title available?)
• scientific article; zbMATH DE number 1153390 (Why is no real title available?)
• scientific article; zbMATH DE number 6107225 (Why is no real title available?)
• scientific article; zbMATH DE number 824573 (Why is no real title available?)
• scientific article; zbMATH DE number 1416462 (Why is no real title available?)
• On the Structure of the Strong Orientations of a Graph
• Orienting and separating distance-transitive graphs
• Parameterized certificate dispersal and its variants
• Maximum size of digraphs of given radius
• The optimal strong radius and optimal strong diameter of the Cartesian product graphs
• Minimum strong diameter of the strong product of complete multipartite graph and path
• Lower and upper orientable strong diameters of graphs satisfying the Ore condition
• The strong distance problem on the Cartesian product of graphs
• Strong orientations of complete k-partite graphs achieving the strong diameter

This page was built for publication: On strong distances in oriented graphs

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