2021/07/10 by S. Aadhavan, R. Mahendra Kumar, Aadhavan, S. +5
Computer Science · #05C38 #05C45 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2107.04798
openalex publication_date 2021/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A bipartite graph is chordal bipartite if every cycle of length at least six has a chord in it. M\rm uller \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 P9-free chordal bipartite graphs, and hence the status of Hamiltonicity in P8-free chordal bipartite graphs is open. In this paper, we identify the first non-trivial subclass of P8-free chordal bipartite graphs which is P5-free chordal bipartite graphs, and present structural and algorithmic results on P5-free chordal bipartite graphs. We investigate the structure of P5-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 P5-free chordal bipartite graph. We also present some results on complement graphs of P5-free chordal bipartite graphs.