Very strongly connected graphs

A simple connected graph is strongly connected if there exists a directed path between every pair of vertices in both directions. Robbins showed that every \(2\)-edge-connected graph can be given edge orientations that result in the graph being strongly connected. But a random assignment of edge directions may or may not result in a graph being strongly connected. We say that a \(2\)-edge-connected graph is very strongly connected if any choice of edge orientations that does not feature a vertex having maximal or minimal indegree yields a strongly connected graph. We classify all graphs as either very strongly connected or not very strongly connected.

Authors

Institutions

Publication Details

Journal
American Journal of Combinatorics
Published
2025-08-26
DOI
https://doi.org/10.63151/amjc.v4i.36
Primary Topic
Advanced Graph Theory Research
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Very strongly connected graphs

Jeff Rushall, Hannah Golab, M. R. COX, Ruth Perry et al.
American Journal of Combinatorics
Advanced Graph Theory Research
article

Very strongly connected graphs

Jeff Rushall, Hannah Golab, M. R. COX, Ruth Perry, Kaylee Freudenthal
article en

Abstract

A simple connected graph is strongly connected if there exists a directed path between every pair of vertices in both directions. Robbins showed that every \(2\)-edge-connected graph can be given edge orientations that result in the graph being strongly connected. But a random assignment of edge directions may or may not result in a graph being strongly connected. We say that a \(2\)-edge-connected graph is very strongly connected if any choice of edge orientations that does not feature a vertex having maximal or minimal indegree yields a strongly connected graph. We classify all graphs as either very strongly connected or not very strongly connected.

American Journal of CombinatoricsVol. 4
Northern Arizona University (US)
Openalex Percentile: Top 76%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.