Quantcast

A Characterization of $K_{2,4}$-Minor-Free Graphs

Research paper by M. N. Ellingham, Emily A. Marshall, Kenta Ozeki, Shoichi Tsuchiya

Indexed on: 20 Jun '16Published on: 17 May '16Published in: SIAM Journal on Discrete Mathematics



Abstract

SIAM Journal on Discrete Mathematics, Volume 30, Issue 2, Page 955-975, January 2016. We provide a complete structural characterization of $K_{2,4}$-minor-free graphs. The 3-connected $K_{2,4}$-minor-free graphs consist of nine small graphs on at most eight vertices, together with a family of planar graphs that contains $2n-8$ nonisomorphic graphs of order $n$ for each $n \geq 5$ as well as $K_4$. To describe the 2-connected $K_{2,4}$-minor-free graphs we use $xy$-outerplanar graphs, graphs embeddable in the plane with a Hamilton $xy$-path so that all other edges lie on one side of this path. We show that, subject to an appropriate connectivity condition, $xy$-outerplanar graphs are precisely the graphs that have no rooted $K_{2,2}$ minor where $x$ and $y$ correspond to the two vertices on one side of the bipartition of $K_{2,2}$. Each 2-connected $K_{2,4}$-minor-free graph is then (i) outerplanar, (ii) the union of three $xy$-outerplanar graphs and possibly the edge $xy$, or (iii) obtained from a 3-connected $K_{2,4}$-minor-free graph by replacing each edge $x_iy_i$ in a set $\{x_1 y_1, x_2 y_2, \ldots, x_k y_k\}$ satisfying a certain condition by an $x_i y_i$-outerplanar graph. From our characterization it follows that a $K_{2,4}$-minor-free graph has a Hamilton cycle if it is 3-connected and a Hamilton path if it is 2-connected. Also, every 2-connected $K_{2,4}$-minor-free graph is either planar or else toroidal and projective-planar.