Internally 4-Connected Graphs With No {Cube, V8}-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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2021-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2205 |
| _version_ | 1797704424755298304 |
|---|---|
| author | Lewchalermvongs Chanun Ananchuen Nawarat |
| author_facet | Lewchalermvongs Chanun Ananchuen Nawarat |
| author_sort | Lewchalermvongs Chanun |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-03-12T05:20:13Z |
| format | Article |
| id | doaj.art-da14e9772ac641f09fabfb5a98bb8a6f |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:20:13Z |
| publishDate | 2021-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-da14e9772ac641f09fabfb5a98bb8a6f2023-09-03T07:47:14ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922021-05-0141248150110.7151/dmgt.2205Internally 4-Connected Graphs With No {Cube, V8}-MinorLewchalermvongs Chanun0Ananchuen Nawarat1Department of Mathematics, Faculty of Science, and Centre of Excellence in Mathematics,Mahidol University, Bangkok10400, ThailandCentre of Excellence in Mathematics,Mahidol University, Bangkok10400, ThailandA 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.https://doi.org/10.7151/dmgt.2205internally 4-connectedminorcube graphv8 graph05c83 |
| spellingShingle | Lewchalermvongs Chanun Ananchuen Nawarat Internally 4-Connected Graphs With No {Cube, V8}-Minor Discussiones Mathematicae Graph Theory internally 4-connected minor cube graph v8 graph 05c83 |
| title | Internally 4-Connected Graphs With No {Cube, V8}-Minor |
| title_full | Internally 4-Connected Graphs With No {Cube, V8}-Minor |
| title_fullStr | Internally 4-Connected Graphs With No {Cube, V8}-Minor |
| title_full_unstemmed | Internally 4-Connected Graphs With No {Cube, V8}-Minor |
| title_short | Internally 4-Connected Graphs With No {Cube, V8}-Minor |
| title_sort | internally 4 connected graphs with no cube v8 minor |
| topic | internally 4-connected minor cube graph v8 graph 05c83 |
| url | https://doi.org/10.7151/dmgt.2205 |
| work_keys_str_mv | AT lewchalermvongschanun internally4connectedgraphswithnocubev8minor AT ananchuennawarat internally4connectedgraphswithnocubev8minor |