Hamiltonian Complete Number of Some Variants of Caterpillar Graphs

Tayo Charles Adefokun, Kingsley Nosa Onaiwu

Published 2022-09-09Version 1

A graph G is said to be Hamiltonian if it contains a spanning cycle. In other words, G contains a cycle that passes through all the the vertices in the vertex set V(G) of G. A graph that does not contain a spanning cycle is a non-Hamiltonian graph. In this work, we investigate the the Hamiltonian completeness of certain trees. The Hamiltonian complete number of G, a non-Hamiltonian graph is the optimal number of edges that if added to the edge set E(G) of G, then G becomes Hamiltonian. Our focus is on certain classes of caterpillar graphs.