A Class of Hamiltonian Cubic Planar Graphs: a Brief Exploration of Their Properties

DOI

10.2991/978-94-6463-445-7_17How to use a DOI?

Keywords

bipartite planar cubic graphs; hamiltonian cycles

Abstract

We study properties of a class of 2-connected bipartite planar cubic graphs G db obtained by operating on connected plane graphs with minimum degree two. We show that G db is a hamiltonian graph with 2 | V ( G ) | + 2 | E ( G ) | - 1 different perfect matchings, and demonstrate how G db can be decomposed into unions of K 2 ’s and 2-factors. Additional results include how any hamiltonian cycle in G db induces a spanning non-crossing closed trail T in a graph obtained in an intermediate step of constructing G db . The different kinds of subgraphs induced by the non-crossing trail in G are also discussed. We also explore the connection between hamiltonian cycles in G db and hamiltonian cycles in a set of graphs G v ∗ called vertex envelopes. Specifically, we show that certain hamiltonian cycles in G db can be easily transformed into hamiltonian cycle in G v ∗ . We end by discussing how additional classes of hamiltonian graphs can be obtained by operating on G db .

Copyright

© 2024 The Author(s)

Open Access

Open Access This chapter is licensed under the terms of the Creative Commons Attribution-NonCommercial 4.0 International License (http://creativecommons.org/licenses/by-nc/4.0/), which permits any noncommercial use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

Download article (PDF)

TY  - CONF
AU  - Michael T. Muzheve
PY  - 2024
DA  - 2024/06/29
TI  - A Class of Hamiltonian Cubic Planar Graphs: a Brief Exploration of Their Properties
BT  - Proceedings of the 2nd International Conference on Neural Networks and Machine Learning 2023 (ICNNML 2023)
PB  - Atlantis Press
SP  - 166
EP  - 172
SN  - 1951-6851
UR  - https://doi.org/10.2991/978-94-6463-445-7_17
DO  - 10.2991/978-94-6463-445-7_17
ID  - Muzheve2024
ER  -