Size of graphs and digraphs with given diameter and connectivity constraints
For a connected, finite graph or a strongly connected finite digraph, the diameter is the largest of all distances between pairs of vertices; the edge-connectivity is the minimum number of edges (respectively arcs) whose removal renders a graph \(G\) (respectively a strong digraph \(G\)) disconnected (respectively not strongly connected); a strongly connected digraph is Eulerian if, for every vertex, the in-degree and out-degree coincide. In the first instance this paper addresses gaps in the literature relating, for undirected \(G=(V,E)\), \(\vert V\vert \), \(\vert E\vert \), diameter, and edge-connectivity. It also seeks, in \S4, to generalize results to Eulerian digraphs, relating e.g. \textit{P. Dankelmann} and \textit{L. Volkmann} [Electron. J. Comb. 17, No. 1, Research Paper R157, 11 p. (2010; Zbl 1204.05042)]. In Theorem 1 the author determines for graphs \(G=(V,E)\) the maximum of \(\vert E\vert \) given \(\vert V\vert \), diameter, and edge-connectity \(\lambda\), where \(2\le\lambda\le 7\); for \(\lambda=1\) this is a classical result.
- A note on diameter and the degree sequence of a graph
- Diameter and maximum degree in Eulerian digraphs
- Diameters in graphs
- Distance and size in digraphs
- Graphs of maximum diameter
- scientific article; zbMATH DE number 4033779 (Why is no real title available?)
- scientific article; zbMATH DE number 4097420 (Why is no real title available?)
- Maximum diameter of regular digraphs
- Minimum orders of Eulerian oriented digraphs with given diameter
- On size, order, diameter and edge-connectivity of graphs
- On size, order, diameter and minimum degree
- On the sum of all distances in a graph or digraph
- Radius, diameter, and minimum degree
- The diameter of almost Eulerian digraphs
- An inequality relating the order, maximum degree, diameter and connectivity of a strongly connected digraph
- The diameter of directed graphs
- Size in maximal triangle-free graphs and minimal graphs of diameter 2
- The smallest number of edges in a 2-connected graph with specified diameter
- Sizes and transmissions of digraphs with a given clique number
- Construction Techniques for Digraphs with Minimum Diameter
- Maximum size of digraphs with some parameters
- scientific article; zbMATH DE number 1262798 (Why is no real title available?)
- Connectedness of digraphs and graphs under constraints on the conditional diameter
- Distance and size in digraphs
- scientific article; zbMATH DE number 749225 (Why is no real title available?)
- Diameter determination on restricted graph families
- Diameter and connectivity of finite simple graphs
- On size, order, diameter and edge-connectivity of graphs
This page was built for publication: Size of graphs and digraphs with given diameter and connectivity constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2043684)
