2-Trees: Structural insights and the study of Hamiltonian paths

DOI10.1142/S1793830922501130MaRDI QIDQ6132868zbMATH OpenOpenAlexWikidataFDO

Authors P. Renjith, N. Sadagopan

Publication date 15 July 2023

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.02038

zbMATH Keywords

2-treesHamiltonian path

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: For a connected graph, a path containing all vertices is known as emph{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.

Recommendations

• On regular 2-connected 2-path Hamiltonian graphs
• Hamiltonian paths in some classes of grid graphs
• Sufficient Conditions for a Connected Graph to Have a Hamiltonian Path
• Hamiltonian paths in L-shaped grid graphs
• Spanning trees and Hamiltonicity

Cites work

• A linear time recognition algorithm for proper interval graphs
• A method in graph theory
• A note on Hamiltonian circuits
• A note on the Hamiltonian circuit problem on directed path graphs
• A Problem in Graph Theory
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• Advances on the Hamiltonian problem -- a survey
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• An Infinite Class of Hypohamiltonian Graphs
• Characterizing forbidden pairs for hamiltonian properties
• Degree conditions for k‐ordered hamiltonian graphs
• Finding Hamiltonian circuits in interval graphs
• Forbidden subgraphs and Hamiltonian properties and graphs
• Forbidden subgraphs, hamiltonicity and closure in claw-free graphs
• Four sufficient conditions for hamiltonian graphs
• General solutions to the single vehicle routing problem with pickups and deliveries
• Graph theory with applications
• Hamiltonian circuits determining the order of chromosomes
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonian circuits in interval graph generalizations
• Hamiltonian properties of triangular grid graphs
• scientific article; zbMATH DE number 4191710 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 3754737 (Why is no real title available?)
• Hypohamiltonian and hypotraceable graphs
• k-ordered Hamiltonian graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• Neighbourhood unions and Hamiltonian properties in graphs
• Note on Hamilton Circuits
• On Hamilton's ideals
• On Hamiltonian Circuits in Finite Graphs
• On some intriguing problems in Hamiltonian graph theory---a survey
• Onk-ordered graphs
• Onk-ordered Hamiltonian graphs
• Reducibility among combinatorial problems
• Some Theorems on Abstract Graphs
• Sufficient conditions for a graph to be Hamiltonian
• The number of Hamiltonian paths in a rectangular grid
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Updating the hamiltonian problem—A survey

This page was built for publication: 2-Trees: Structural insights and the study of Hamiltonian paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132868)