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
- Jeff Rushall
- Hannah Golab
- M. R. COX
- Ruth Perry
- Kaylee Freudenthal
Institutions
- Northern Arizona University (US)
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