Size of graphs and digraphs with given diameter and connectivity constraints
type: Item
instance of: scholarly article
title: Size of graphs and digraphs with given diameter and connectivity constraints
zbMATH Open document ID: 1488.05153
author: Peter Dankelmann
published in: Acta Mathematica Hungarica
publication date: 2021-08-03T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 7377535
zbMATH Keywords: diameter
zbMATH Keywords: connectivity
zbMATH Keywords: edge-connectivity
zbMATH Keywords: digraph
zbMATH Keywords: Eulerian digraph
reviewed by: William G. Brown
MaRDI profile type: Publication
full work available at URL: s10474-021-01137-7
OpenAlex ID: W3158780250
cites work: On size, order, diameter and edge-connectivity of graphs
cites work: Q3773907
cites work: Q3824439
cites work: Graphs of maximum diameter
cites work: The diameter of almost Eulerian digraphs
cites work: Distance and size in digraphs
cites work: Diameter and maximum degree in Eulerian digraphs
cites work: Radius, diameter, and minimum degree
cites work: A note on diameter and the degree sequence of a graph
cites work: On size, order, diameter and minimum degree
cites work: Diameters in graphs
cites work: On the sum of all distances in a graph or digraph
cites work: Minimum orders of Eulerian oriented digraphs with given diameter
cites work: Maximum diameter of regular digraphs
DOI: 10.1007/S10474-021-01137-7
description: scientific article; zbMATH DE number 7377535