Hamiltonicity: Variants and Generalization in P₅-free Chordal Bipartite graphs

MaRDI QIDQ6372465zbMATH OpenFDO

Authors S. Aadhavan, R. Mahendra Kumar, P. Renjith, N. Sadagopan

Publication date 10 July 2021

Mathematics Subject Classification ID

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

Abstract: A bipartite graph is chordal bipartite if every cycle of length at least six has a chord in it. M$ddotmu$ller cite {muller1996Hamiltonian} has shown that the Hamiltonian cycle problem is NP-complete on chordal bipartite graphs by presenting a polynomial-time reduction from the satisfiability problem. The microscopic view of the reduction instances reveals that the instances are $P_9$-free chordal bipartite graphs, and hence the status of Hamiltonicity in $P_8$-free chordal bipartite graphs is open. In this paper, we identify the first non-trivial subclass of $P_8$-free chordal bipartite graphs which is $P_5$-free chordal bipartite graphs, and present structural and algorithmic results on $P_5$-free chordal bipartite graphs. We investigate the structure of $P_5$-free chordal bipartite graphs and show that these graphs have a {em Nested Neighborhood Ordering (NNO)}, a special ordering among its vertices. Further, using this ordering, we present polynomial-time algorithms for classical problems such as the Hamiltonian cycle (path), also the variants and generalizations of the Hamiltonian cycle (path) problem. We also obtain polynomial-time algorithms for treewidth (pathwidth), and minimum fill-in in $P_5$-free chordal bipartite graph. We also present some results on complement graphs of $P_5$-free chordal bipartite graphs.

This page was built for publication: Hamiltonicity: Variants and Generalization in $P_5$-free Chordal Bipartite graphs

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