PDF files of articles are only available for institutions which have paid for the online version upon signing an Institutional User License.

$n$-Arc connected graphs

Volume 171 / 2023

Paul Gartside, Ana Mamatelashvili, Max Pitz Colloquium Mathematicum 171 (2023), 19-47 MSC: Primary 05C45; Secondary 05C38, 05C40, 05C63. DOI: 10.4064/cm8653-1-2022 Published online: 20 June 2022


Given a graph $G$, of arbitrary size and unbounded vertex degree, denote by $|G|$ the one-complex associated with $G$. The topological space $|G|$ is $n$-arc connected ($n$-ac) if every set of no more than $n$ points of $|G|$ is contained in an arc (a homeomorphic copy of the closed unit interval). For any graph $G$, we show the following are equivalent: (i) $|G|$ is $7$-ac, (ii) $|G|$ is $n$-ac for all $n$, and (iii) $G$ is a subdivision of one of nine graphs. A graph $G$ has $|G|$ $6$-ac if and only if either $G$ is one of the nine $7$-ac graphs, or, after suppressing all degree-2 vertices, is $3$-regular, $3$-connected, and removing any $6$ edges does not disconnect $G$ into four or more components. Similar combinatorial characterizations of graphs $G$ such that $|G|$ is $n$-ac for $n=3, 4$ and $5$ are given. Together these results yield a complete classification of $n$-ac graphs, for all $n$.


  • Paul GartsideDepartment of Mathematics
    University of Pittsburgh
    Pittsburgh, PA 15260, USA
  • Ana MamatelashviliSchool of Mathematics and Statistics
    University of Melbourne
    Melbourne, VIC 3010, Australia
  • Max PitzDepartment of Mathematics
    University of Hamburg
    Bundesstraße 55
    20146 Hamburg, Germany

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image