Hamiltonicity in vertex envelopes of plane cubic graphs |
| |
Authors: | Herbert Fleischner Michael Tapfuma Muzheve |
| |
Institution: | a Institute of Information Systems, Department of Data Bases and Artificial Intelligence, Technical University of Vienna, Austria b Department of Mathematics, Texas A&M University, College Station, TX 77843, United States c Department of Mathematics, University of Zimbabwe, Zimbabwe |
| |
Abstract: | In this paper we study a graph operation which produces what we call the “vertex envelope” G∗V from a graph G. We apply it to plane cubic graphs and investigate the hamiltonicity of the resulting graphs, which are also cubic. To this end, we prove a result giving a necessary and sufficient condition for the existence of hamiltonian cycles in the vertex envelopes of plane cubic graphs. We then use these conditions to identify graphs or classes of graphs whose vertex envelopes are either all hamiltonian or all non-hamiltonian, paying special attention to bipartite graphs. We also show that deciding if a vertex envelope is hamiltonian is NP-complete, and we provide a polynomial algorithm for deciding if a given cubic plane graph is a vertex envelope. |
| |
Keywords: | Hamiltonian Plane graph Cubic graph Prism Leapfrog |
本文献已被 ScienceDirect 等数据库收录! |
|