The maximum average connectivity among all orientations of a graph

DOI10.1007/S10878-021-00789-ZMaRDI QIDQ2125229zbMATH OpenOpenAlexFDO

Authors Rocío M. Casablanca, Peter Dankelmann, Wayne Goddard, L. A. S. Mól, Ortrud R. Oellermann

Publication date 13 April 2022

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.07219, https://idus.us.es/handle//11441/125645

average connectivity connectivity cubic graphs maximal outerplanar graphs minimally 2-connected graphs orientations

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Connectivity (05C40)

Abstract: For distinct vertices

u

and

v

in a graph

G

, the {em connectivity} between

u

and

v

, denoted

k a p p a_{G} (u, v)

, is the maximum number of internally disjoint

u

--

v

paths in

G

. The {em average connectivity} of

G

, denoted

o v e r l i n e k a p p a (G),

is the average of

k a p p a_{G} (u, v)

taken over all unordered pairs of distinct vertices

u, v

of

G

. Analogously, for a directed graph

D

, the {em connectivity} from

u

to

v

, denoted

k a p p a_{D} (u, v)

, is the maximum number of internally disjoint directed

u

--

v

paths in

D

. The {em average connectivity} of

D

, denoted

o v e r l i n e k a p p a (D)

, is the average of

k a p p a_{D} (u, v)

taken over all ordered pairs of distinct vertices

u, v

of

D

. An {em orientation} of a graph

G

is a directed graph obtained by assigning a direction to every edge of

G

. For a graph

G

, let

o v e r l i n e {k a p p a}_{m a x} (G)

denote the maximum average connectivity among all orientations of

G

. In this paper we obtain bounds for

o v e r l i n e {k a p p a}_{m a x} (G)

and for the ratio

o v e r l i n e {k a p p a}_{m a x} (G) / o v e r l i n e k a p p a (G)

for all graphs

G

of a given order and in a given class of graphs. Whenever possible, we demonstrate sharpness of these bounds. This problem had previously been studied for trees. We focus on the classes of cubic

3

-connected graphs, minimally

2

-connected graphs,

2

-trees, and maximal outerplanar graphs.

Review text

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)\).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: The maximum average connectivity among all orientations of a graph

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