Internally 4-Connected Graphs with No {Cube, V<inf>8</inf>}-Minor

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Chanun Lewchalermvongs, Nawarat Ananchuen
Other Authors: Mahidol University
Format: Article
Published: 2022
Subjects:
Online Access:https://repository.li.mahidol.ac.th/handle/123456789/77381
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Mahidol University
id th-mahidol.77381
record_format dspace
spelling th-mahidol.773812022-08-04T15:56:44Z Internally 4-Connected Graphs with No {Cube, V<inf>8</inf>}-Minor Chanun Lewchalermvongs Nawarat Ananchuen Mahidol University Mathematics 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 V8 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 V8 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 V8 as minors. This result provides a step closer to a complete characterization of all internally 4-connected graphs with no cube minor. 2022-08-04T08:56:44Z 2022-08-04T08:56:44Z 2021-05-01 Article Discussiones Mathematicae - Graph Theory. Vol.41, No.2 (2021), 481-501 10.7151/dmgt.2205 20835892 12343099 2-s2.0-85100555636 https://repository.li.mahidol.ac.th/handle/123456789/77381 Mahidol University SCOPUS https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85100555636&origin=inward
institution Mahidol University
building Mahidol University Library
continent Asia
country Thailand
Thailand
content_provider Mahidol University Library
collection Mahidol University Institutional Repository
topic Mathematics
spellingShingle Mathematics
Chanun Lewchalermvongs
Nawarat Ananchuen
Internally 4-Connected Graphs with No {Cube, V<inf>8</inf>}-Minor
description 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 V8 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 V8 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 V8 as minors. This result provides a step closer to a complete characterization of all internally 4-connected graphs with no cube minor.
author2 Mahidol University
author_facet Mahidol University
Chanun Lewchalermvongs
Nawarat Ananchuen
format Article
author Chanun Lewchalermvongs
Nawarat Ananchuen
author_sort Chanun Lewchalermvongs
title Internally 4-Connected Graphs with No {Cube, V<inf>8</inf>}-Minor
title_short Internally 4-Connected Graphs with No {Cube, V<inf>8</inf>}-Minor
title_full Internally 4-Connected Graphs with No {Cube, V<inf>8</inf>}-Minor
title_fullStr Internally 4-Connected Graphs with No {Cube, V<inf>8</inf>}-Minor
title_full_unstemmed Internally 4-Connected Graphs with No {Cube, V<inf>8</inf>}-Minor
title_sort internally 4-connected graphs with no {cube, v<inf>8</inf>}-minor
publishDate 2022
url https://repository.li.mahidol.ac.th/handle/123456789/77381
_version_ 1763489376845692928