DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

C. Lewchalermvongs and N. Ananchuen

Title:

Internally 4-connected graphs with no $\{$cube, $V_8 \}$-minor

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-06-28, Revised: 2018-12-29, Accepted: 2019-01-10, https://doi.org/10.7151/dmgt.2205

Abstract:

A simple graph is a minor of another if the first is obtained from the second by deleting vertices, deleting edges, contracting edges, and deleting loops and parallel edges that are created when we contract edges. A cube is an internally 4-connected planar graph with eight vertices and twelve edges corresponding to the skeleton of the cube in the platonic solid, and the Wagner graph $V_8$ is an internally 4-connected nonplanar graph obtained from a cube by introducing a twist. A complete characterization of all internally 4-connected graphs with no $V_8$ minor is given in J. Maharry and N. Robertson, The structure of graphs not topologically containing the Wagner graph, J. Combin. Theory Ser. B 121 (2016) 398–420; on the other hand, only a characterization of 3-connected graphs with no cube minor is given in J. Maharry, A characterization of graphs with no cube minor, J. Combin. Theory Ser. B 80 (2008) 179–201. In this paper we determine all internally 4-connected graphs that contain neither cube nor $V_8$ as minors. This result provides a step closer to a complete characterization of all internally 4-connected graphs with no cube minor.

Keywords:

internally 4-connected, minor, cube graph, $V_8$

PDF
Close