We explore a sufficient condition for the hamiltonicity of vertex envelopes of plane graphs. In particular we show that if a plane graph G contains an independent set of vertices such that is a tree, then its vertex envelope is Hamiltonian. Based on this criteria, we identify classes of plane graphs whose vertex envelopes are Hamiltonian. We also describe constructions that produce plane graphs whose vertex envelopes are Hamiltonian, and investigate the hamiltonicity of graphs obtained through edge subdivisions.
FleischnerH. (1974a). On spanning subgraphs of a connected bridgeless graph and their application to graphs. Journal of Combinatorial Theory, Series B, 16, 17–28.
2.
FleischnerH. (1974b). The square of every two-connected graph is Hamiltonian. Journal of Combinatorial Theory, Series B, 16, 29–34.
3.
FleischnerH.HobbsA. M. (1975). Hamiltonian total graphs. Mathematische Nachrichten, 68, 59–82.
4.
FleischnerH.HobbsA. M.MuzheveM. T. (2009). Hamiltonicity in vertex envelopes of plane cubic graphs. Discrete Mathematics, 309(14), 4793–4809.
5.
HararyF.Nash-WilliamsC. St. J. A. (1965). On Eulerian and Hamiltonian graphs and line graphs. Canadian Mathematical Bulletin, 8(6), 701–709.
6.
WestD. (2001). Introduction to Graph Theory. Prentice Hall.
