pith. sign in

arxiv: 1907.07219 · v1 · pith:GMRK5VAWnew · submitted 2019-07-16 · 🧮 math.CO

The maximum average connectivity among all orientations of a graph

Rocio M. Casablanca , Peter Dankelmann , Wayne Goddard , Ortrud R. Oellermann , Lucas Mol This is my paper

Pith reviewed 2026-05-24 20:42 UTC · model grok-4.3

classification 🧮 math.CO
keywords average connectivitygraph orientationsdirected pathscubic graphs2-connected graphsouterplanar graphs2-trees
0
0 comments X

The pith

For graphs of given order in classes like cubic 3-connected graphs, bounds hold on the maximum average connectivity over all orientations and on its ratio to the undirected average.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives upper bounds on the largest average connectivity obtainable by directing the edges of graphs from several families, including cubic 3-connected graphs, minimally 2-connected graphs, 2-trees, and maximal outerplanar graphs. It also produces bounds on the ratio of this directed maximum to the average connectivity of the undirected graph itself. Sharpness is established for the bounds in all cases where the authors could construct matching examples. The results extend earlier findings that applied only to trees.

Core claim

For every graph G of order n belonging to one of the studied classes, upper bounds exist for both the quantity obtained by maximizing average directed connectivity over all orientations of G and the ratio of that quantity to the average connectivity of the undirected graph G, and these bounds are attained for some graphs in the class.

What carries the argument

overline{kappa}_max(G), the largest value of average directed connectivity over all orientations of G, which is the quantity bounded in each graph class.

If this is right

  • The maximum average connectivity after orientation cannot exceed the derived function of n for every cubic 3-connected graph on n vertices.
  • The ratio of the directed maximum to the undirected average connectivity is at most the stated constant or function for every minimally 2-connected graph.
  • Sharp examples exist showing that the bounds cannot be lowered for 2-trees and for some other classes.
  • The same style of bound applies uniformly across all maximal outerplanar graphs of a fixed order.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same bounding technique might apply directly to other recursively defined graph classes beyond those treated here.
  • Once the bounds are known, it becomes feasible to compare how much connectivity is lost or gained when moving from undirected graphs to their best orientations across different densities.
  • The existence of sharp bounds suggests that algorithms searching for high-connectivity orientations could be tested for optimality on the extremal graphs constructed in the paper.

Load-bearing premise

The standard definition of connectivity as the maximum number of internally disjoint paths applies without change to every orientation of graphs in the classes considered.

What would settle it

A single graph from one of the classes, for example a cubic 3-connected graph on n vertices, in which every orientation has average directed connectivity strictly larger than the upper bound stated for that n.

Figures

Figures reproduced from arXiv: 1907.07219 by Lucas Mol, Ortrud R. Oellermann, Peter Dankelmann, Rocio M. Casablanca, Wayne Goddard.

Figure 1
Figure 1. Figure 1: The orientation D2n of the graph F2n We now describe an orientation D2n of F2n with the property that limn→∞ κ¯(D2n) κ¯(F2n) = 1 (see [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The graph H5,3 Now, let Ds,t be the orientation of Hs,t obtained by placing the sets V1, V2, . . . , V2s around a circle and orienting edges clockwise (see [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: shows a M¨obius ladder of order 14 [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The graphs K4 and I(K4) Lemma 3.4. Let G be a cubic graph. Let F be an orientation of I(G) and let D be the projection of F onto G. If D has exactly C full pairs, then F has at most 4C + 2|V (G)| full pairs. Proof. Suppose Tx and Ty are distinct triangles of I(G). Then, by Lemma 3.3, there are at most four full pairs of vertices of I(G) that have one vertex in Tx and the other in Ty. If P and Q are (intern… view at source ↗
Figure 5
Figure 5. Figure 5: A family of minimally 2-connected graphs with ratio tending to [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The orientation D2n of maximal outerplanar graph G2n Since y ≥ 1 2 x + 2, we have n ≥ x + y ≥ 3 2 x + 2, and thus x ≤ 2 3 n − 4 3 . Elementary calculus shows that the right hand side of (9), as a function of x, is maximized subject to 0 ≤ x ≤ 2 3 n − 4 3 when x = 0. Substituting this yields X {u,v}⊆V (G) θ(u, v) ≤ 3 2 n 2 − 1 2 n − 5, and dividing by n(n − 1) yields the theorem. The bound of Theorem 5.3 is… view at source ↗
Figure 7
Figure 7. Figure 7: A trigon, a lozenge, and the graph G0 Suppose Gi−1 has been constructed for some i > 0. Construct Gi from Gi−1 as follows: glue a trigon to every red outer edge of Gi−1, and then glue two lozenges (red-on-red) onto the two red outer edges of each trigon, so that each vertex in the trigon has degree 5 in the resulting graph (see [PITH_FULL_IMAGE:figures/full_fig_p022_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The graphs G1 and H1 We now consider an arbitrary orientation Di of Hi for some i ≥ 0. Suppose that vertices u and v are not in Gi , and are in distinct copies of Mi (which is the case for almost all pairs of vertices asymptotically). In this case, there must be at least two connector lozenges for u and v, so θ(u, v) ≤ 3. Suppose that θ(u, v) = 3. We may assume, without loss of generality, that κ(u, v) = 2… view at source ↗
Figure 9
Figure 9. Figure 9: An orientation of the black edges of the lozenges adjacen [PITH_FULL_IMAGE:figures/full_fig_p024_9.png] view at source ↗
read the original abstract

For distinct vertices $u$ and $v$ in a graph $G$, the {\em connectivity} between $u$ and $v$, denoted $\kappa_G(u,v)$, is the maximum number of internally disjoint $u$--$v$ paths in $G$. The {\em average connectivity} of $G$, denoted $\overline{\kappa}(G),$ is the average of $\kappa_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 $\kappa_D(u,v)$, is the maximum number of internally disjoint directed $u$--$v$ paths in $D$. The {\em average connectivity} of $D$, denoted $\overline{\kappa}(D)$, is the average of $\kappa_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 $\overline{\kappa}_{\max}(G)$ denote the maximum average connectivity among all orientations of $G$. In this paper we obtain bounds for $\overline{\kappa}_{\max}(G)$ and for the ratio $\overline{\kappa}_{\max}(G)/\overline{\kappa}(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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper derives bounds on the maximum average directed connectivity κ_max(G) over all orientations of G, and on the ratio κ_max(G)/κ(G), for all graphs G of given order belonging to the classes of cubic 3-connected graphs, minimally 2-connected graphs, 2-trees, and maximal outerplanar graphs. Sharpness of the bounds is demonstrated via explicit constructions or extremal examples whenever possible. The work extends prior results known only for trees, relying on the standard Menger-based definitions of undirected and directed connectivity.

Significance. If the derivations and constructions hold, the paper supplies explicit, class-specific bounds on how orientation can increase average connectivity, together with matching examples. These parameter-free results (derived from independent graph-theoretic properties of the listed classes) are useful for extremal problems in directed connectivity and may inform network-design questions. The absence of ad-hoc parameters or circular definitions strengthens the contribution.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'whenever possible' for sharpness demonstrations leaves unclear which of the four classes admit sharp constructions; a brief enumeration would improve readability.
  2. [Introduction] The transition from unordered pairs in the undirected average to ordered pairs in the directed average is correctly noted but could be restated once in §1 for readers new to the directed setting.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and the recommendation of minor revision. No major comments appear in the report, so we have no specific points requiring response or revision at this stage.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes bounds on κ_max(G) and the ratio κ_max(G)/κ(G) for graph classes including cubic 3-connected graphs, minimally 2-connected graphs, 2-trees, and maximal outerplanar graphs by applying Menger's theorem to orientations and exhibiting explicit extremal constructions for sharpness. These steps rely on independent combinatorial arguments and standard definitions of path-disjoint connectivity that do not reduce to self-referential definitions, fitted parameters, or load-bearing self-citations. The derivation chain remains self-contained against external graph-theoretic benchmarks with no equations or claims that collapse by construction to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard graph theory definitions without introducing new free parameters, invented entities, or non-standard axioms.

axioms (1)
  • standard math Connectivity κ_G(u,v) is defined as the maximum number of internally disjoint u-v paths in G.
    This is the foundational definition invoked for both undirected and directed cases throughout the abstract.

pith-pipeline@v0.9.0 · 5866 in / 1077 out tokens · 32041 ms · 2026-05-24T20:42:22.980990+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · 1 internal anchor

  1. [1]

    L. W. Beineke, O. R. Oellermann and R. E. Pippert, The average connectivity of a graph , Discrete Math., 252 (2002), 31–45

    work page 2002

  2. [2]

    R. M. Casablanca, L. Mol and O. R. Oellermann, The average connectivity of minimally 2-connected graphs and the average connectivity of minimall y 2-edge connected graphs, 2018. arXiv:1810.01972

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  3. [3]

    Chv´ atal, Tough graphs and Hamiltonian circuits , Discrete Math., 5 (1973), 215–228

    V. Chv´ atal, Tough graphs and Hamiltonian circuits , Discrete Math., 5 (1973), 215–228

    work page 1973

  4. [4]

    Dankelmann, O

    P. Dankelmann, O. R. Oellermann, On the average connectivity of a graph , Dis- crete Appl. Math., 129 (2003), 305–318

    work page 2003

  5. [5]

    G. A. Dirac, Minimally 2-connected graphs, J. Reine Angew. Math., 228 (1967), 204–216

    work page 1967

  6. [6]

    Durand de Gevigney, On Frank’s conjecture on k-connected orientations

    O. Durand de Gevigney, On Frank’s conjecture on k-connected orientations. arXiv: 12.12.4086, Dec. 2012. 27

    work page 2012

  7. [7]

    M. A. Henning and O. R. Oellermann, The average connectivity of a digraph , Discrete Appl. Math., 140 (2004), 143–153

    work page 2004

  8. [8]

    M. A. Henning and O. R. Oellermann, The average connectivity of regular mul- tipartite tournaments. Austral. J. Combin. 23 (2001), 101–113

    work page 2001

  9. [9]

    Mader, Ecken vom Grad n in minimalen n-fach zusammenh¨ angenden Graphen, Arch

    W. Mader, Ecken vom Grad n in minimalen n-fach zusammenh¨ angenden Graphen, Arch. Math., 23 (1972), 219–224

    work page 1972

  10. [10]

    Mader, A reduction method for edge-connectivity in graphs, Ann

    W. Mader, A reduction method for edge-connectivity in graphs, Ann. Discr. Math. 3 (1978), 145–164

    work page 1978

  11. [11]

    C. St. J. A. Nash-Williams, On orientations, connectivity and odd- vertex- pairings in finite graphs , Canad. J. Math. 12 (1960), 555–567

    work page 1960

  12. [12]

    O. R. Oellermann, Menger’s Theorem, Topics in Structural Graph Theory (L. W. Beineke and R. J. Wilson, eds.), Cambridge University Press, 2013

    work page 2013

  13. [13]

    M. D. Plummer, On Minimal Blocks , Trans. Amer. Math. Soc., 134(1) (1968), 85–94

    work page 1968

  14. [14]

    H. E. Robbins, Questions, discussions, and notes: a theorem on graphs, wit h an application to a problem of traffic control , Amer. Math. Monthly 46 (1939), 281–283

    work page 1939

  15. [15]

    C. Thomassen, Configurations in graphs of large minimum degree, connectiv ity, or chromatic number , Combinatorial Mathematics: Proceedings of the Third International Conference, New York 1985, Ann. New York Acad. Sci., New York 555 (1989), 402–412

    work page 1985

  16. [16]

    Thomassen, Strongly 2-connected orientations of graphs , J

    C. Thomassen, Strongly 2-connected orientations of graphs , J. Combin.Theory Ser B, 110 (2014), 67–78. 28

    work page 2014