The maximum average connectivity among all orientations of a graph (Q2125229)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The maximum average connectivity among all orientations of a graph |
scientific article |
Statements
The maximum average connectivity among all orientations of a graph (English)
0 references
13 April 2022
0 references
This paper studies the maximum average connectivity among all orientations of a graph. The average connectivity of a directed graph \(D\) is denoted by \(\bar{k}(D)\), which is the average of the connectivity between two vertices over all such possible pairs in \(D\). The maximum average connectivity among all orientations of a given graph \(G\) is denoted by \(\bar{k}_{\max}(G)\). If a graph \(G\) is \(r\)-regular over \(n\) vertices for some odd \(r\), it is shown that \(\bar{k}_{\max}(G)\le\frac{r-1}{2}+\frac{n}{4(n-1)}\). If \(G\) is minimally 2-connected over \(n\) vertices, then \(1\le \bar{k}_{\max}(G)<5/4\). For each minimally 2-connected graph \(G\), it is shown that \(4/9<\bar{k}_{\max}(G)/\bar{k}(G)<5/8\). When \(G\) is a maximal outerplanar graph, it is shown that \(\bar{k}_{\max}(G)\le 3/2+(n-5)/(n^2-n)\).
0 references
connectivity
0 references
average connectivity
0 references
orientations
0 references
cubic graphs
0 references
minimally 2-connected graphs
0 references
maximal outerplanar graphs
0 references