Minimum average distance of strong orientations of graphs (Q1887055): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.dam.2004.01.005 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1985797130 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4500916 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distances in orientations of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minimal oriented graphs of diameter 2 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The minimum diameter of orientations of complete multipartite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5572949 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the sum of all distances in a graph or digraph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3739159 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3754023 / rank | |||
Normal rank |
Latest revision as of 16:20, 7 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum average distance of strong orientations of graphs |
scientific article |
Statements
Minimum average distance of strong orientations of graphs (English)
0 references
23 November 2004
0 references
The average distance of a graph or digraph \(G\) of order \(n\), denoted by \(\mu (G)\), is the average among the distances between all \(n(n-1)\) ordered pairs of vertices of \(G\) [see e.g. \textit{J. Plesník}, J. Graph Theory 8, 1--21 (1984; Zbl 0552.05048)]. If \(G\) is a 2-edge-connected graph, then \(\overrightarrow{\mu}_{\min }(G)\) is the minimum average distance taken over all strong orientations of \(G\). A sharp lower bound for \(\overrightarrow{\mu}_{\min }(G)\) is established in terms of the order, size, girth and \(\mu (G)\). In general, there is no upper bound for \(\overrightarrow{\mu}_{\min }(G)\) in terms of \(\mu (G)\). However, for some special classes of graphs such a bound is given.
0 references
minimum average distance
0 references
oriented graphs
0 references
bounds
0 references