2017/11/21 by S. Aadhavan, Aadhavan, S, P. Renjith +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1711.07736
A bipartite graph is chordal bipartite if every cycle of length at least 6 has a chord in it. In this paper, we investigate the structure of P5-free chordal bipartite graphs and show that these graphs have a Nested Neighborhood Ordering, a special ordering among its vertices. Further, using this ordering, we present polynomial-time algorithms for classical problems such as Hamiltonian cycle (path) and longest path. Two variants of Hamiltonian path include Steiner path and minimum leaf spanning tree, and we obtain polynomial-time algorithms for these problems as well restricted to P5-free chordal bipartite graphs.