2015/11/06 by Renjith, P., Sadagopan, N.
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1511.02038
For a connected graph, a path containing all vertices is known as Hamiltonian path. For general graphs, there is no known necessary and sufficient condition for the existence of Hamiltonian paths and the complexity of finding a Hamiltonian path in general graphs is NP-Complete. We present a necessary and sufficient condition for the existence of Hamiltonian paths in 2-trees. Using our characterization, we also present a linear-time algorithm for the existence of Hamiltonian paths in 2-trees. Our characterization is based on a deep understanding of the structure of 2-trees and the combinatorics presented here may be used in other combinatorial problems restricted to 2-trees.