¹¹institutetext: Indian Institute of Information Technology Design and Manufacturing, Kancheepuram, Chennai, India
¹¹email: [email protected],{coe18d004,sadagopan}@iiitdm.ac.in ²²institutetext: Indian Institute of Information Technology Design and Manufacturing, Kurnool.
²²email: [email protected]

Hamiltonicity: Variants and Generalization in $P_{5}$ -free Chordal Bipartite graphs^†^†thanks: This work is partially supported by DAE-NBHM project, NBHM/ 02011/37/2017/RD II/16646

S.Aadhavan 11 R.Mahendra Kumar 11 P.Renjith 22 N.Sadagopan 11

Abstract

A bipartite graph is chordal bipartite if every cycle of length at least six has a chord in it. M $\ddot{\rm u}$ ller [10] 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 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.

Keywords:

P_{5}

-free chordal bipartite graphs Nested Neighborhood Ordering Hamiltonian cycle (path) Longest cycle (path) Steiner cycle (path) Treewidth Pathwidth Minimum fill-in

1 Introduction

The graphs with forbidden subgraphs possess a nice structural characterization. The structural characterization of these graphs has attracted researchers from both mathematics and computing. The popular graphs are chordal graphs [1], which forbid induced cycles of length at least four, and chordal bipartite graphs [2], which are bipartite graphs that forbid induced cycles of length at least six. Further, these graph classes have a nice structural characterization with respect to minimal vertex separators and a special ordering, namely, perfect elimination ordering [3] among its vertices (edges). These graphs are largely studied in the literature to understand the computational complexity of classical optimization problems such as vertex cover, dominating set, coloring, etc., as these problems are known to be NP-complete on general graphs. Thus these graphs help to identify the gap between NP-complete instances and polynomial-time solvable instances for classical combinatorial problems.

The Hamiltonian cycle (path) problem is a famous problem that asks for the presence of a cycle (path) that visits each node exactly once in a graph. A graph $G$ is said to be Hamiltonian if it has a Hamiltonian cycle. The Hamiltonian problem plays a significant role in various research areas such as circuit design [4], operational research [5], biology [6], etc. On the complexity front, this problem is well studied and it remains NP-complete on general graphs. Interestingly, this problem is polynomial-time solvable on special graphs such as cographs and permutation graphs [7]. Surprisingly, this problem is NP-complete on chordal graphs [8], bipartite graphs [9], and $P_{5}$ -free graphs [3].

M $\ddot{\rm u}$ ller [10] 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. It is natural to study the complexity of the Hamiltonian cycle problem in $P_{8}$ -free chordal bipartite graphs and its subclasses. Since $P_{4}$ -free chordal bipartite graphs are complete bipartite graphs, the first non-trivial graph class in this line of research is $P_{5}$ -free chordal bipartite graphs. Further, the Steiner tree problem and the dominating set problem are also NP-complete for chordal bipartite graphs [11] as there is a polynomial-time reduction from the vertex cover problem. Interestingly, the instances generated have $P_{5}$ in it. This gives us another motivation to study the structure of $P_{5}$ -free chordal bipartite graphs.

It is known from the literature that the Hamiltonian cycle problem is NP-complete on $(C_{4},C_{5},P_{5})$ -free graphs [3]. Therefore, it is NP-complete on $(C_{5},P_{5})$ -free graphs as well. In this paper, we present a polynomial-time algorithm for $(C_{3},C_{5},P_{5})$ -free graphs which are precisely $P_{5}$ -free chordal bipartite graphs.

A graph $G$ is $k$ -bisplit if it has a stable set (an independent set) $X$ such that $G-X$ has at most $k$ bicliques (complete bipartite graphs). A graph $G$ is weak bisplit if it is $k$ -bisplit for some $k$ . It is known from [12], recognizing weak bisplit graphs is NP-complete, whereas recognition of $k$ -bisplit graphs for every fixed $k$ is polynomial-time solvable. A graph $G$ is bisplit if its vertex set can be partitioned into three stable sets $X$ , $Y$ , and $Z$ such that $Y\cup Z$ induces a complete bipartite subgraph (a biclique) in $G$ . Note that 1-bisplit graphs are bisplit graphs. Brandstädt et al. [12] provided $\mathit{O(nm)}$ linear time recognition algorithm for bisplit graphs. Subsequently, Abueida et al. [13] has given $\mathit{O(n^{2})}$ time recognition algorithm for bisplit graphs. Various popular problems like, Hamiltonian cycle (path) problem, domination, independent dominating set and feedback vertex set are NP-complete on bisplit graphs. So, it is natural to investigate the complexities of the problems mentioned above in a subclass of bisplit graphs. Interestingly, chordal bipartite graphs are a subclass of bisplit graphs and hence due to [10] the Hamiltonian cycle (path) problem is NP-complete on this graph class. This is another motivation to investigate the structure of $P_{5}$ -free chordal bipartite graphs, which are a subclass of bisplit graphs.

In recent times, the class of $P_{5}$ -free graphs have received a good attention, and problems such as independent set [14], k-colourbility [15], and feedback vertex set [16] have polynomial-time algorithms restricted to $P_{5}$ -free graphs.

The longest path problem is the problem of finding an induced path of maximum length in $G$ . Since this problem is a generalization of the Hamiltonian path problem, it is NP-complete on general graphs. This problem is polynomial-time solvable in interval graphs [17] and biconvex graphs [18]. A minimum leaf spanning tree is a spanning tree of $G$ with the minimum number of leaves. This problem is NP-complete on general graphs, and polynomial-time solvable on cographs [19]. It is important to highlight that the minimum leaf spanning tree problem in cographs can be solved using the longest path problem as a black box. In this paper, we wish to see whether we can come up with a framework for Hamiltonicity and its variants in $P_{5}$ -free chordal bipartite graphs.

It is important to highlight that other classical problem such as Steiner tree, dominating set, connected dominating set are known to be NP-complete on chordal bipartite graphs [11].

Similar to the Hamiltonian cycle (path) problem, its variants also attracted many researchers. We shall see some of the popular variants of the Hamiltonian cycle (path) problem. A graph $G$ with the vertex set $V(G)$ and the edge set $E(G)$ is pancyclic [20] if it contains cycles of all lengths $l$ , $3\leq l\leq|V(G)|$ . A graph $G$ is (2)-pancyclic graph [21] if it contains exactly two cycles of length $l$ , $3\leq l\leq|V(G)|$ . A graph $G$ is said to be bipancyclic [22] if it contains a cycle of length $2l$ , $2\leq l\leq|V(G)|$ . A graph $G$ is said to be Hamiltonian connected if there exists a Hamiltonian path between every pair of vertices. Asratian [23] and Kewenet et al. [24] have given sufficient conditions for a graph to be Hamiltonian connected. A graph $G$ is said to be homogeneously traceable if there exists a Hamiltonian path beginning at every vertex of $G$ . Skupień [25] has given necessary condition for a graph $G$ to be homogeneously traceable. Chartrand et al.[26] proved that there exists a homogeneously traceable non-Hamiltonian graph of order $n$ for all positive integers $n$ except $3\leq n\leq 8$ . A hypo-Hamiltonian graph is a non-Hamiltonian graph $G$ such that $G-v$ is Hamiltonian for every vertex $v\in V(G)$ . A graph is $k$ -ordered Hamiltonian if for every ordered sequence of $k$ vertices, there exists a Hamiltonian cycle that encounters the vertices of the sequence in the given order. Faudree et al. [27] have given degree conditions for a graph to be $k$ -ordered Hamiltonian. These variants are known to be NP-complete on general graphs, and chordal biparatite graphs.

In the literature, there are many conditions for Hamiltonicity and its variants. Due to the inherent difficulty of the problem, all these conditions are either necessary conditions or sufficient conditions, however no known necessary and sufficient conditions. We show that Chvátal’s Hamiltonian cycle (path) necessary condition is sufficient for $P_{5}$ -free chordal bipartite graphs. We also present a necessary and sufficient condition for the existence of the Steiner path (cycle) in $P_{5}$ -free chordal bipartite graphs.

Our work: In this paper, we study the structure of $P_{5}$ -free chordal bipartite graphs and present a new ordering referred to as Nested Neighbourhood Ordering among its vertices. We present a polynomial-time algorithm for the Hamiltonian cycle (path) problem using the Nested Neighbourhood Ordering. Further, using this ordering, we present polynomial-time algorithms for longest path (cycle), minimum leaf spanning tree, Steiner path (cycle), treewidth (pathwidth), and minimum fill-in. We believe that these results can help us in the study of other combinatorial problems restricted to $P_{5}$ -free chordal bipartite graphs, and also in the structural investigation of $P_{k}$ -free chordal bipartite graphs, $6\leq k\leq 8$ . Further, our understanding shall help us in obtaining a dichotomy: easy vs hard input instances of chordal bipartite graphs. We also present some results on complement graphs of $P_{5}$ -free chordal bipartite graphs.

Related work: Structure of $P_{5}$ -free graphs has been looked at while studying the Difference graph [28], 3-colorable $P_{5}$ -free graphs [29], and $(P_{5},\overline{P_{5}})$ -free graphs [30]. However, the explicit mention of NNO has not been reported in the literature. To the best of our knowledge, the algorithmic results presented in this paper are new and have not been reported in the literature.

1.1 Preliminaries

In this paper, we work with simple, connected, undirected and unweighted graphs. For a graph $G$ , let $V(G)$ denote the vertex set and $E(G)$ denote the edge set. The notation $\{u,v\}$ represents an edge incident on the vertices $u$ and $v$ . The neighborhood of a vertex $v$ of $G$ , $N_{G}(v)$ , is the set of vertices adjacent to $v$ in $G$ . The degree of a vertex $u$ is denoted by $d_{G}(u)=|N_{G}(u)|$ . We use $d(u)$ and $d_{G}(u)$ interchangeably if the graph under consideration is clear from the context. A graph $H$ is called an induced subgraph of $G$ if for all $u,v\in V(H)$ , $\{u,v\}\in E(H)$ if and only if $\{u,v\}\in E(G)$ . The graph induced on $V(G)\setminus\{u\}$ is denoted by $G-u$ . A graph $G$ is said to be connected if there exists a path between every pair of vertices. If $G$ is disconnected, then $c(G)$ denotes the number of connected components in $G$ (each component being maximal). A bipartite graph is chordal bipartite if every cycle of length at least six has a chord. A maximal biclique $K_{i,j}$ is a complete bipartite graph such that there is no strict supergraphs $K_{i+1,j}$ or $K_{i,j+1}$ . A maximum biclique is a maximal biclique with the property that $|i-j|$ is minimum. Note that $P_{5}$ is an induced path of length $5$ and $P_{uv}$ denotes a path that starts at $u$ and ends at $v$ , and $|P_{uv}|$ denotes its length. We use $P_{uv}$ and $P(u,v)$ interchangeably. Let $\overline{G}$ denote the complement of the graph $G$ , where $V(\overline{G})=V(G)$ and $E(\overline{G})=\{\{u,v\}|\{u,v\}\notin E(G)\}$ .

2 Structural Results

In this section, we shall present a structural characterization of $P_{5}$ -free chordal bipartite graphs. Also, we introduce Nested Neighborhood Ordering (NNO) among its vertices. We shall fix the following notation to present our results. For a chordal bipartite $G$ with bipartition $(A,B)$ , let $A=\{x_{1},x_{2},\ldots,x_{m}\}$ and $B=\{y_{1},y_{2},\ldots,y_{n}\}$ . The edge set $E(G)\subseteq\{\{x,y\}~{}|~{}x\in A,y\in B\}$ . Let $A=A_{1}\cup A_{2}$ and $B=B_{1}\cup B_{2}$ , $A_{1}=\{x_{1},x_{2},\ldots,x_{i}\}$ , $A_{2}=\{x_{i+1},x_{i+2},\ldots,x_{m}\}$ and $B_{1}=\{y_{1},y_{2},\ldots,y_{j}\}$ , $B_{2}=\{y_{j+1},y_{j+2},\ldots,y_{n}\}$ , such that $(A_{1},B_{1})$ is a maximum biclique.

Lemma 1

Let $G$ be a $P_{5}$ -free chordal bipartite graph. Then, $\forall x\in A_{2},\exists y_{k}\in B_{1}$ such that $y_{k}\not\in N_{G}(x)$ and $\forall y\in B_{2},\exists x_{k}\in A_{1}$ such that $x_{k}\not\in N_{G}(y)$ .

Proof

Suppose there exists $x$ in $A_{2}$ such that for all $y_{k}$ in $B_{1}$ , $xy_{k}\in E(G)$ . Then $(A_{1}\cup\{x\},B_{1})$ is the maximum biclique, contradicting the fact that $(A_{1},B_{1})$ is maximum. Similar argument is true for $y\in B_{2}$ . Therefore, the lemma follows. ∎

Lemma 2

Let $G$ be a $P_{5}$ -free chordal bipartite graph. Then, $\forall x\in A_{2}$ , $N_{G}(x)\subset B_{1}$ and $\forall y\in B_{2}$ , $N_{G}(y)\subset A_{1}$ .

Proof

On the contrary, $\exists x_{a}\in A_{2}$ , $N(x_{a})\not\subset B_{1}$ . Case 1: $N(x_{a}){=}B_{1}$ . Then, $(A_{1}\cup\{x_{a}\},B_{1})$ is the maximum biclique, a contradiction. Case 2: $N(x_{a})\subseteq B_{2}$ . This implies that there exists $y_{b}\in B_{2}$ such that $y_{b}\in N(x_{a})$ . Since $G$ is connected, $N(y_{b})\cap A_{1}\neq\emptyset$ , say $x_{c}\in N(y_{b})\cap A_{1}$ . In $G$ , $P(x_{a},x_{k})=(x_{a},y_{b},x_{c},y_{k},x_{k})$ is an induced $P_{5}$ . Note that, due to the maximality of $(A_{1},B_{1})$ , as per Lemma 1, we find $x_{k}\not\in N(y_{b}),y_{k}\not\in N(x_{a})$ . This contradicts that $G$ is $P_{5}$ -free. Case 3: $N(x_{a})\cap B_{1}\neq\emptyset$ and $N(x_{a})\cap B_{2}\neq\emptyset$ . I.e., $\exists x_{a}\in A_{2}$ such that $y_{b},y_{c}\in N(x_{a})$ and $y_{b}\in B_{1}$ , $y_{c}\in B_{2}$ . In $G$ , $P(y_{c},y_{k})=(y_{c},x_{a},y_{b},x_{k},y_{k}$ ), $x_{k}\not\in N(y_{c})$ , $y_{k}\not\in N(x_{a})$ is an induced $P_{5}$ . Note that the existence of $x_{k},y_{k}$ is due to Lemma 1. This is contradicting the $P_{5}$ -freeness of $G$ . Similarly, $\forall y\in B_{2}$ , $N(y)\subset A_{1}$ , can be proved. ∎

Lemma 3

Let $G$ be a $P_{5}$ -free chordal bipartite graph. For $x_{i},x_{j}\in A_{2}$ , $i\not=j$ , if $d(x_{i})\leq d(x_{j})$ , then $N(x_{i})\subseteq N(x_{j})$ . Similarly, for $y_{i},y_{j}\in B_{2}$ , if $d(y_{i})\leq d(y_{j})$ , $N(y_{i})\subseteq N(y_{j})$ .

Proof

Let us assume to the contrary that $N(x_{i})\not\subseteq N(x_{j})$ . I.e., $N(x_{i})\setminus N(x_{j})\neq\emptyset$ .
Case 1: $N(x_{i})\cap N(x_{j})\neq\emptyset$ . I.e., $\exists y_{a}\in B$ such that $y_{a}\in N(x_{i})\cap N(x_{j})$ . Since $N(x_{i})\not\subseteq N(x_{j})$ , $\exists y_{b}\in B$ such that $y_{b}\not\in N(x_{i})\cap N(x_{j})$ and $y_{b}\in N(x_{i})$ . Since $d(x_{j})\geq d(x_{i})$ , vertex $x_{j}$ is adjacent to at least one more vertex $y_{c}\in B$ such that $y_{c}\not\in N(x_{i})$ . The path $P(y_{c},y_{b})=(y_{c},x_{j},y_{a},x_{i},y_{b}$ ) is an induced $P_{5}$ . This is a contradiction.
Case 2: $N(x_{i})\cap N(x_{j})=\emptyset$ , $|N(x_{i})|\geq 1$ and $|N(x_{j})|\geq 1$ . I.e., $\exists y_{a},y_{b}\in B$ such that $y_{a}\in N(x_{i})$ , $y_{a}\not\in N(x_{j})$ and $y_{b}\in N(x_{j})$ , $y_{b}\not\in N(x_{i})$ . Since $G$ is a connected graph, $|P(y_{a},y_{b})|\geq 3$ , an induced path of length at least 3. The path $P(x_{i},x_{j})=(x_{i},P(y_{a},y_{b}),x_{j}$ ) has an induced path of length at least 5. This is a contradiction. Similarly, for all pairs of distinct vertices $y_{i},y_{j}\in B_{2}$ with $d(y_{i})\leq d(y_{j})$ , $N(y_{i})\subseteq N(y_{j})$ can be proved. ∎

Theorem 2.1

Let $G$ be a $P_{5}$ -free chordal bipartite graphs with $(A_{1},B_{1})$ being the maximum biclique. Let $A_{2}=(u_{1},u_{2},...,u_{p})$ and $B_{2}=(v_{1},v_{2},...,v_{q})$ are orderings of vertices. If $d_{G}(u_{1})\leq d_{G}(u_{2})\leq d_{G}(u_{3})\leq\ldots\leq d_{G}(u_{p})$ , then $N(u_{1})\subseteq N(u_{2})\subseteq N(u_{3})\subseteq\ldots\subseteq N(u_{p})$ . Further, if $d_{G}(v_{1})\leq d_{G}(v_{2})\leq d_{G}(v_{3})\leq\ldots\leq d_{G}(v_{q})$ , then $N(v_{1})\subseteq N(v_{2})\subseteq N(v_{3})\subseteq\ldots\subseteq N(v_{q})$ .

Proof

We shall prove by mathematical induction on $|A_{2}|$ . Base Case: $|A_{2}|=2,A_{2}=(u_{1},u_{2})$ such that $d(u_{1})\leq d(u_{2})$ . By Lemma 3, $N(u_{1})\subseteq N(u_{2})$ . Induction step: Consider $A_{2}=(u_{1},u_{2},u_{3},\ldots,u_{p}),p\geq 3$ . Consider the vertex $u_{p}\in A_{2}$ such that $d(u_{p})\geq d(u_{p-1})$ . By Lemma 3, $N(u_{p-1})\subseteq N(u_{p})$ is true. By the hypothesis, $N(u_{1})\subseteq N(u_{2})\subseteq N(u_{3})\subseteq\ldots\subseteq N(u_{p-1})$ . By combining the hypothesis and the fact that $N(u_{p-1})\subseteq N(u_{p})$ , our claim follows. Similarly for $B_{2}$ as well.∎

We refer to the above ordering of vertices as Nested Neighbourhood Ordering (NNO) of $G$ . From now on, we shall arrange the vertices in $A_{2}$ in non-decreasing order of their degrees so that we can work with NNO of $G$ .

Lemma 4

Let $G$ be a $P_{5}$ -free chordal bipartite graph. Then, $G$ is bisplit.

Proof

By our structural result, we know that $G$ is partitioned into four stable sets namely $A_{1}$ , $B_{1}$ , $A_{2}$ , and $B_{2}$ . We observe that $A_{1}\cup B_{1}$ induces a maximum biclique and $A_{2}$ , $B_{2}$ is an independent set. Therefore, by definition, $G$ is bisplit. ∎

3 Hamiltonicity in $P_{5}$ -free Chordal Bipartite graphs

In this section, we shall present polynomial-time algorithms for the Hamiltonian cycle (path) problem in $P_{5}$ -free chordal bipartite graphs. For a connected graph $G$ and set $S\subset V(G)$ , $c(G-S)$ denotes the number of connected components in the graph induced on the set $V(G)\setminus S$ . It is well-known, due to, Chvatal [31] that if a graph $G$ has a Hamiltonian cycle, then for every $S\subset V(G),c(G-S)\leq|S|$ . Similarly, if a graph $G$ has a Hamiltonian path, then for every $S\subset V(G),c(G-S)\leq|S|+1$ .

Theorem 3.1

For a $P_{5}$ -free chordal bipartite graph $G$ , $G$ has a Hamiltonian cycle if and only if (i) $|A|=|B|$ and (ii) $A_{2}$ has an ordering $(u_{1},u_{2},\ldots,u_{p})$ , such that $\forall u_{g},d(u_{g})>g$ , $1\leq g\leq p$ and $B_{2}$ has an ordering $(v_{1},v_{2},\ldots,v_{q})$ , $\forall v_{h},d(v_{h})>h$ , $1\leq h\leq q$ .

Proof

Necessity: (i) Any cycle in a bipartite graph is even and alternates between vertices of $A$ and $B$ . Since the Hamilton cycle visits all the vertices in $A$ and $B$ , it must have $|A|=|B|$ . (ii) On the contrary, $\exists u_{g}\in A_{2}$ such that $u_{g}$ is the first vertex in the ordering with $d(u_{g})\leq g$ . That is, for $u_{k}\in\{u_{1},\ldots,u_{g-1}\}$ , $d_{G}(u_{k})>k$ and $d(u_{g})\leq g$ . Since $G$ follows NNO, $d_{G}(u_{g})=g$ . From Theorem 2.1, we know that $N(u_{1})\subseteq N(u_{2})\subseteq\ldots\subseteq N(u_{g-1})\subseteq N(u_{g})$ . This implies that $c(G-N(u_{g}))=g+1>g$ . This is a contradiction to Chvatal’s necessary condition for the Hamiltonian cycle. Similarly, in $B_{2}$ , $\forall v_{h},$ $d(v_{h})>h$ can be proved.
Sufficiency: Let $i=|A_{1}|$ and $j=|B_{1}|$ . Since $A_{2}$ has an ordering such that $\forall u_{g}\in A_{2}$ , $d(u_{g})>g$ , for clarity purpose, we define $N_{G}(u_{g})$ as follows; $N(u_{g})=\{y_{1},y_{2},\ldots,y_{l}\}$ , $g<l<j$ , that is, $u_{1}$ is adjacent to at least two vertices $\{y_{1},y_{2}\}$ and at most $j-1$ vertices $\{y_{1},y_{2},\ldots,y_{j-1}\}$ , $u_{2}$ is adjacent to at least three vertices $\{y_{1},y_{2},y_{3}\}$ and at most $j-1$ vertices $\{y_{1},y_{2},\ldots,y_{j-1}\}$ and similarly $u_{p}$ is adjacent to at least $p+1$ vertices $\{y_{1},y_{2},\ldots,y_{p+1}\}$ and at most $j-1$ vertices $\{y_{1},y_{2},\ldots,y_{j-1}\}$ . Observe that, due to the maximality of $(A_{1},B_{1})$ , any $u_{g}$ of $A_{2}$ can be adjacent to at most $j-1$ vertices of $B_{1}$ . Similarly, in $B_{2}$ , for all $v_{h}\in B_{2}$ , $N(v_{h})=\{x_{1},x_{2},\ldots,x_{l}\},$ $h<l<i$ .
Let $d(u_{p})=r,p+1\leq r\leq j-1$ and $d(v_{q})=s,q+1\leq s\leq i-1$ . The vertices in $A_{1}$ can be ordered as $(x_{1},x_{2},\ldots,x_{q},x_{q+1},\ldots,x_{i})$ and the vertices in $B_{1}$ can be ordered as $(y_{1},y_{2},\ldots,y_{p},y_{p+1},\ldots,y_{j})$ . Note that $A_{3}=A_{1}{\setminus}\{x_{1},x_{2},\ldots,x_{q+1}\}=\{x_{q+2},\ldots,x_{i-1},x_{i}\}$ and $B_{3}=B_{1}{\setminus}\{y_{1},y_{2},\ldots,y_{p+1}\}=\{y_{p+2},\ldots,y_{j-1},y_{j}\}$ . Further, $|A_{3}|=|A|-(|A_{2}|+q+1)=|A|-(p+q+1)$ and $|B_{3}|=|B|-(|B_{2}|+p+1)=|B|-(q+p+1)$ . Since $|A|=|B|$ , it follows that $|A_{3}|=|B_{3}|$ . In $G$ , $(y_{1},u_{1},y_{2},u_{2},\ldots,y_{p},u_{p},y_{p+1},x_{1},v_{1},x_{2},v_{2},\ldots,x_{q},v_{q},x_{q+1},y_{p+2},x_{q+2},$ $\ldots,y_{j},x_{i},y_{1})$ is a Hamiltonian cycle. ∎

Theorem 3.2

For a $P_{5}$ -free chordal bipartite graph $G$ , $G$ has a Hamiltonian path if and only if one of the following is true
(i) $|A|=|B|$ and $A_{2}$ has an ordering, $\forall u_{g},d(u_{g})\geq g$ , $1\leq g\leq p$ and $B_{2}$ has an ordering, $\forall v_{h},d(v_{h})\geq h$ , $1\leq h\leq q$ .
(ii) $|A|=|B|+1$ and $A_{2}$ has an ordering, $\forall u_{g},d(u_{g})\geq g$ , $1\leq g\leq p$ and $B_{2}$ has an ordering, $\forall v_{h},d(v_{h})>h$ , $1\leq h\leq q$ .

Proof

Necessity: (i) Without loss of generality, we assume $A\geq B$ . Any Hamiltonian path starting at $A$ and alternates between $A$ and $B$ can end at $A$ or $B$ . Therefore $|A|=|B|$ or $|A|=|B|+1$ . To prove that $A_{2}$ satisfies the ordering, we assume to the contrary that $\exists u_{g}\in A_{2}$ such that $u_{g}$ is the first vertex in the ordering such that $d(u_{g})<g$ . Since $G$ follows NNO, $d_{G}(u_{g})=g-1$ . From Theorem 2.1, we know that $N(u_{1})\subseteq N(u_{2})\subseteq\ldots\subseteq N(u_{g-1})\subseteq N(u_{g})$ . Note that, as per the ordering of $A_{2}$ , $N(u_{g-1})=N(u_{g})$ . On removing $N(u_{g})$ from $G$ we have $g$ components in $A_{2}$ and $A_{1}\cup B_{2}\cup(B_{1}-N(u_{g}))$ forms another component. This implies that $c(G-N(u_{g}))=g+1$ . Clearly, $g+1\not\leq g-1$ . Thus we contradict the Chvatal’s necessary condition for the Hamiltonian path. Similarly $B_{2}$ has an ordering such that $\forall v_{h},d(v_{h})\geq h$ , $1\leq h\leq q$ .
(ii) For $A_{2}$ , the argument is similar to the above. Suppose ${\exists}v_{r}{\in}B_{2}$ such that $v_{r}$ is the first vertex in the ordering such that $d(v_{r}){\leq}r$ . From Theorem 2.1, $N(v_{1}){\subseteq}N(v_{2}){\subseteq}\ldots{\subseteq}N(v_{r-1}){\subseteq}N(v_{r})$ . Consider the set $S=B_{1}{\cup}\{v_{r+1},v_{r+2},\ldots,v_{q}\}$ and $|S|=j+q-r-1+1=j+q-r$ . Further, $c(G-S){\geq}p+1+i-r$ . Note that $|A|=i+p$ and $|B|=j+q$ . Since $|A|=|B|+1$ , $c(G-S){\geq}p+1+i-r=j+q+1+1-r=j+q-r+2$ . Clearly, $c(G-S)\not\leq|S|+1$ , contradicting the Chvatal’s condition for the Hamiltonian path.
Sufficiency: (i) Let $N(u_{g})=\{y_{1},\ldots,y_{l}\}$ , $g\leq l<j$ and $N(v_{h})=\{x_{1},\ldots,x_{l}\},$ $h{\leq}l<i$ . Consider $A_{3}=A_{1}{\setminus}\{x_{1},x_{2},\ldots,x_{q}\}=\{x_{q+1},x_{q+2},\ldots,x_{i-1},x_{i}\}$ . $B_{3}=B_{1}{\setminus}\{y_{1},y_{2},\ldots,y_{p}\}=\{y_{p+1},x_{p+2},\ldots,y_{j-1},y_{j}\}$ . Note that $|A_{3}|=|A|-(p+q)$ and $|B_{3}|=|B|-(p+q)$ . In $G$ ,
$P(u_{1},y_{1},u_{2},y_{2},\ldots,u_{p},y_{p},x_{q+1},y_{p+1},x_{q+2},y_{p+2},\ldots,x_{i},y_{j},x_{q},v_{q},\ldots,x_{1},v_{1})$ is a Hamiltonian path.
(ii) Consider $A_{3}=A_{1}{\setminus}\{x_{1},x_{2},\ldots,x_{q+1}\}=\{x_{q+2},x_{q+3},\ldots,x_{i-1},x_{i}\}$ and $B_{3}=B_{1}{\setminus}\{y_{1},y_{2},\ldots,y_{p}\}=\{y_{p+1},x_{p+2},\ldots,y_{j-1},y_{j}\}$ . In $G$ , $P(u_{1},y_{1},u_{2},y_{2},\ldots,u_{p},y_{p},x_{q+2},y_{p+1},x_{q+3},y_{p+2},\ldots,x_{i},y_{j},x_{q+1},v_{q},\ldots,x_{2},$ $v_{1},x_{1})$ is a Hamiltonian path. This completes the proof of this claim. ∎

Theorem 3.3

Let $G$ be a $P_{5}$ -free chordal bipartite graph. Finding a Hamiltonian path and cycle in $G$ are polynomial-time solvable.

Proof

Follows from the characterizations presented in Theorems 3.1 and 3.2 as the proofs are constructive. ∎

4 Chvátal’s Necessary condition is Sufficient on $P_{5}$ -free chordal bipartite graphs

For the Hamiltonian cycle (path) problem, it is well-known from the literature that there are no necessary and sufficient conditions. However, we know the condition due to Chvátal is necessary but not sufficient and results due to Ore and Dirac are sufficient but not necessary. In this section, we show that Chvátal’s necessary condition is sufficient for $P_{5}$ -free chordal bipartite graphs.

Theorem 4.1

Let $G$ be a $P_{5}$ -free chordal bipartite graph with $|A|=|B|$ . If $G$ satisfies $c(G-S)\leq|S|$ , for every non-empty subset $S$ $\subseteq V(G)$ , then $G$ has the Hamiltonian cycle.

Proof

Assume on the contrary, that $G$ has no Hamiltonian cycle, then there exists $u_{g}$ or $v_{h}$ in $A_{2}(B_{2})$ that violates the degree conditions mentioned in Theorem 2. Let $u_{g}$ be the first vertex in the ordering with $d(u_{g})\leq g$ . By Theorem 2.1, we know that $G$ follows NNO, $d_{G}(u_{g})=g$ . This implies that $c(G-N(u_{g}))=g+1>g$ , which is a contradiction to the premise of the theorem. Similarly, $v_{h}$ in $B_{2}$ can be proved. ∎

Theorem 4.2

Let $G$ be a $P_{5}$ -free chordal bipartite graph with $|A|=|B|$ or $|A|=|B|+1$ . If $G$ satisfies $c(G-S)\leq|S|+1$ , for every non-empty subset $S$ $\subseteq V(G)$ , then $G$ has the Hamiltonian path.

Proof

Case 1: $|A|=|B|$ . Assume on the contrary that $G$ has no Hamiltonian path, then there exists $u_{g}$ or $v_{h}$ in $A_{2}(B_{2})$ that violates degree conditions $(i)$ mentioned in Theorem 3.2. Let $u_{g}$ be the first vertex in the ordering with $d(u_{g})<g$ . By Theorem 2.1, we know that $G$ has NNO and hence $d_{G}(u_{g})=g-1$ . On removing $N(u_{g})$ from $G$ , we have $g$ components in $A_{2}$ and $A_{1}\cup B_{2}\cup(B_{1}-N(u_{g}))$ forms another component. This implies that $c(G-N(u_{g}))=g+1$ . Clearly, $g+1\not\leq g-1$ , a contradiction.

Case 2: $|A|=|B|+1$ . Assume on the contrary that $G$ has no Hamiltonian path. Let $v_{h}$ be the first vertex in $B_{2}$ in the ordering such that $d(v_{h}){\leq}h$ . By Theorem 2.1, $G$ satisfies NNO. Consider the set $S=B_{1}{\cup}\{v_{h+1},v_{h+2},\ldots,v_{q}\}$ and $|S|=j+q-h-1+1=j+q-h$ . Further, $c(G-S){\geq}p+1+i-h$ . Note that $|A|=i+p$ and $|B|=j+q$ . Since $|A|=|B|+1$ , $c(G-S){\geq}p+1+i-h=j+q+1+1-h=j+q-h+2$ , contradicting the premise. ∎

5 Hamiltonicity variants in $P_{5}$ -free chordal bipartite graphs

The variants of Hamiltonicity reported in the literature are bipancyclic, homogeneously traceable, EXACTLY 2 SIMPLE PATH COVER, Hamiltonian connected, and hypohamitonian. Interestingly, for all of them, similar to the Hamiltonian cycle we do not know necessary and sufficient conditions. In this paper, we establish necessary and sufficient conditions for a few of the variants restricted to $P_{5}$ -free chordal bipartite graphs.

5.1 Bipancyclic $P_{5}$ -free chordal bipartite graphs

Bondy [20] has given a sufficient condition for a graph to be pancyclic. Similarly, Amar [22] has given a sufficient condition for a graph to be bipancyclic in terms of vertex degree along with Hamiltonicity. It is important to highlight that for $P_{5}$ -free chordal bipartite graphs, being a Hamiltonian is necessary and sufficient to be bipancyclic.

Theorem 5.1

For a $P_{5}$ -free chordal bipartite graph $G$ of order $2n$ , $G$ is Hamiltonian if and only if $G$ is bipancyclic.

Proof

Necessity: We know that the graph $G$ satisfies Theorem 3.1. From the structural results, it is clear that the graph induced on $A_{1}\cup B_{1}$ , say $H$ is a complete bipartite subgraph and $A_{2}(B_{2})$ follows NNO. Let $p=|A_{2}|$ . We obtain the cycles of length $2l$ , $2\leq l\leq|A_{2}|$ , by following the Hamiltonian cycle procedure given in Theorem 3.1.
$C_{4}=(y_{1},u_{1},y_{2},u_{2},y_{1})$
$C_{6}=(y_{1},u_{1},y_{2},u_{2},y_{3},u_{3},y_{1})$
⋮
$C_{2p}=(y_{1},u_{1},y_{2},u_{2},\ldots,u_{p},y_{1})$
For the cycles, $C_{2l}$ , $p+1\leq l\leq n$ , the following procedure is used.
$C_{2(p+1)}=(y_{1},u_{1},y_{2},u_{2},\ldots,u_{p},y_{p+1},x_{1},y_{1})$
$C_{2(p+2)}=(y_{1},u_{1},y_{2},u_{2},\ldots,u_{p},y_{p+1},x_{1},v_{1},x_{2},y_{1})$
⋮
$C_{2n}=(y_{1},u_{1},y_{2},u_{2},\ldots,y_{p},u_{p},y_{p+1},x_{1},v_{1},x_{2},v_{2},\ldots,x_{q},v_{q},x_{q+1},y_{p+2},x_{q+2},$ $\ldots,y_{j},x_{i},y_{1})$
Thus we obtain the cycles $C_{2l}$ , $2\leq l\leq n$ in $G$ . Hence $G$ is a bipancyclic graph.
Sufficiency: Since $G$ is a $P_{5}$ -free chordal bipartite bipancyclic graph, we have the cycles of length $2l$ , $2\leq l\leq n$ . It is easy to see that the cycle $C_{2n}$ contains all the vertices of $G$ , which is a Hamiltonian cycle. ∎

Remark : The above proof is constructive and we can get all these cycles in polynomial time.

5.2 Homogeneously traceable $P_{5}$ -free chordal bipartite graphs

A graph $G$ is said to be homogeneously traceable if there exists a Hamiltonian path beginning at every vertex of $G$ . It is obvious that every Hamiltonian is homogeneously traceable. On the other hand, there exist homogeneously traceable non-Hamiltonian graphs. The Petersen graph is an example of a homogeneously traceable non-Hamiltonian graph. A graph is semi-Hamiltonian if it has a Hamiltonian path and does not have a Hamiltonian cycle. We denote the semi-Hamiltonian problem as ONE ENDPOINT SPECIFIED SEMI-HAMILTONIAN if one endpoint is specified in the input. ONE ENDPOINT SPECIFIED SEMI-HAMILTONIAN [32] problem is NP-complete on general graphs as there is a polynomial-time reduction from satisfiability problem. The Homogeneously traceable problem is a generalization of ONE ENDPOINT SPECIFIED SEMI-HAMILTONIAN problem. Chartrand et al.[26] has given a construction of homogeneously traceable non-Hamiltonian graph with $n$ vertices, $n\geq 9$ . Interestingly, every homogeneously traceable $P_{5}$ -free chordal bipartite graphs are Hamiltonian graphs.

Theorem 5.2

For a $P_{5}$ -free chordal bipartite graph $G$ , $G$ is Hamiltonian if and only if $G$ is homogeneously traceable.

Proof

Necessity: It is easy to see that the Hamiltonian graphs are homogeneously traceable.
Sufficiency: Let $G$ be homogeneously traceable. Case 1: $|A|=|B|$ . By Theorem 2.1, the vertices of $A_{2}(B_{2})$ follows NNO property. Since $G$ is homogeneously traceable, we have Hamiltonian path beginning at every vertex of $G$ . Without out loss of generality, we begin the Hamiltonian path at vertex $y_{1}\in B_{1}$ . We observe that the degree of $u_{1}$ is at least two. In general, $\forall u_{g},d(u_{g})>g$ , $1\leq g\leq p$ . Similarly, if we begin at $x_{1}\in A_{1}$ , then the vertices of $B_{2}$ satisfies the following property, $\forall v_{h},d(v_{h})>h$ , $1\leq h\leq q$ . Now we observe that the graph $G$ follows Theorem 3.1. Therefore, $G$ is Hamiltonian.
Case 2: $|A|=|B|+1$ . We now show that this case is not possible. Assume on the contrary that this case is possible. Suppose we begin constructing the path $P$ at vertex $y_{1}\in B_{1}$ and visit all of $A_{2}$ . Let $B^{\prime}_{1}=\{y_{1},y_{2},\ldots,y_{p+1}\}$ be the set of vertices that helps to visit $A_{2}$ . Note that $B_{3}=\{y_{p+2},\ldots,y_{j-1},y_{j}\}=B_{1}{\setminus}\{y_{1},y_{2},\ldots,y_{p+1}\}$ . Similarly, $A_{3}=\{x_{q+2},\ldots,x_{i-1},x_{i}\}=A_{1}{\setminus}\{x_{1},x_{2},\ldots,x_{q+1}\}$ . Further, $|A_{3}|=|A|-(|A_{2}|+q+1)=|A|-(p+q+1)$ and $|B_{3}|=|B|-(|B_{2}|+p+1)=|B|-(q+p+1)$ . This implies that $|A_{3}|>|B_{3}|$ . It is clear that some vertices of $A_{3}$ are left out in the path $P$ . Therefore, the constructed path $P$ is not a Hamiltonian path. Hence this case is not possible. ∎

Corollary 1

Let $G$ be a $P_{5}$ -free chordal bipartite graph with $|A|=|B|+1$ . Then, $G$ is non-Hamiltonian connected.

Proof

Follows from the definition of Hamiltonian connected and Theorem 5.2.∎

5.3 EXACTLY 2 SIMPLE PATH COVER in $P_{5}$ -free chordal bipartite graphs

Simple path cover is a simple path that covers all the vertices of $G$ . By EXACTLY 2 SIMPLE PATH COVER [32], we denote the set of graphs that can be covered by two simple paths, but cannot be covered by one simple path. A Hamiltonian path can be viewed as one simple path that covers all the vertices of $G$ . These problems are NP-complete on general graphs. Since the Hamiltonian path problem is polynomial-time solvable in $P_{5}$ -free chordal bipartite graphs, it is natural to look at the complexity of EXACTLY 2 SIMPLE PATH COVER in this graph class. The notation $\exists!z$ refers to there exists unique $z$ .

Theorem 5.3

For a $P_{5}$ -free chordal bipartite graph $G$ , $G$ has Exactly 2 Simple Path Cover if and only if one of the following is true
(i) $|A|=|B|$ and $A_{2}$ has an ordering, $\exists!z_{r},~{}d(z_{r})<r$ and $\forall u_{g}\neq z_{r},d(u_{g})\geq g$ , $1\leq g\leq p$ and $B_{2}$ has an ordering, $\forall v_{h},d(v_{h})\geq h$ , $1\leq h\leq q$ .
(ii) $|A|=|B|$ and $A_{2}$ has an ordering, $\forall u_{g}\,d(u_{g})\geq g$ , $1\leq g\leq p$ and $B_{2}$ has an ordering, $\exists!z_{r},~{}d(z_{r})<r$ and $\forall v_{h}\neq z_{r},d(v_{h})\geq h$ , $1\leq h\leq q$ .
(iii) $|A|=|B|+1$ and $A_{2}$ has an ordering, $\exists!z_{r},~{}d(z_{r})<r$ and $\forall u_{g}\neq z_{r},d(u_{g})\geq g$ , $1\leq g\leq p$ and $B_{2}$ has an ordering, $\forall v_{h},d(v_{h})>h$ , $1\leq h\leq q$ .
(iv) $|A|=|B|+1$ and $A_{2}$ has an ordering, $\forall u_{g},,d(u_{g})\geq g$ , $1\leq g\leq p$ and $B_{2}$ has an ordering, $\exists!z_{r},~{}d(z_{r})\leq r$ and $\forall v_{h}\neq z_{r},d(v_{h})>h$ , $1\leq h\leq q$ .

Proof

Necessity: (i) Without loss of generality, on the contrary, assume that a vertex $z_{r}\in A_{2}$ such that $d(z_{r})<r$ or there exist at least two vertices $z_{r},z_{s}\in A_{2}$ such that $d(z_{r})<r$ and $d(z_{s})<s$ .
Case 1: There does not exist $z_{r}$ such that $d(z_{r})<r$ . By Theorem 3.2, we observe that $G$ is an yes instance of the Hamiltonian path problem, which is a one simple path cover. A contradiction.
Case 2: There exist at least two such vertices $z_{r}$ and $z_{s}$ . Without loss of generality, assume that $d(z_{r})\leq d(z_{s})$ . By following the procedure given in Theorem 3.2, we obtain three simple paths $P_{1}$ , $P_{2}$ , and $P_{3}$ that cover $V(G)$ .
$P_{1}=(u_{1},y_{1},u_{2},y_{2},\ldots,u_{r-1},y_{r-1},u_{r}=z_{r})$ , $1<r<s$
$P_{2}=(y_{r},u_{r+1},y_{r+1},u_{r+2},\ldots,y_{s-2},u_{s-1},y_{s-1},u_{s}=z_{s})$ , $1<s\leq p$
$P_{3}=(y_{s},u_{s+1},\dots,y_{p-1},u_{p},y_{p},x_{q+1},y_{p+1},x_{q+2},y_{p+2},\ldots,x_{i},y_{j},x_{q},v_{q},\ldots,x_{2},$ $v_{2},x_{1},v_{1})$ ,
A similar argument can be given for (ii), (iii) and (iv)
Sufficiency: There exists exactly one vertex $z_{r}$ , such that $~{}d(z_{r})<r$ . By Theorem 3.2, $G$ is a no instance of the Hamiltonian path problem and thus $G$ cannot be covered by one simple path. By following the procedure given in Theorem 3.2, we obtain the following two simple paths $P_{1}$ , and $P_{2}$ that cover $V(G)$ .
$P_{1}=(u_{1},y_{1},u_{2},y_{2},\ldots,u_{r-1},y_{r-1},u_{r}=z_{r})$ , $1<r\leq p$
$P_{2}=(y_{r},u_{r+1},y_{r+1},u_{r+2}\ldots,y_{p-1},u_{p},y_{p},x_{q+1},y_{p+1},x_{q+2},y_{p+2},\ldots,x_{i},y_{j},x_{q},v_{q},\ldots,x_{2},$ $v_{2},x_{1},v_{1})$
Similarly (ii), (iii) and (iv) can be proved.
∎

5.4 Hamiltonian connected $P_{5}$ -free chordal bipartite graphs

A graph $G$ is said to be Hamiltonian connected if there exists a Hamiltonian path between every pair of vertices. Some of the related problems studied in the literature are TWO ENDPOINT SPECIFIED-SEMI-HAMILTONIAN [32], where both the endpoints are specified. This problem is NP-complete on chordal bipartite graphs. Hamiltonian connected is a generalization of this problem. In this paper, we investigate the Hamiltonian connectedness of $G$ . If $G$ has a Hamiltonian path, then $G$ satisfies Theorem 3.2. It is clear from Corollary 1 that if $|A|=|B|+1$ , then $G$ is non-Hamiltonian connected. We shall now look at the case where $|A|=|B|$ .

Theorem 5.4

Let $G$ be a $P_{5}$ -free chordal bipartite graph with $|A|=|B|$ . Then, $G$ is non-Hamiltonian connected.

Proof

Assume on the contrary, that $G$ is Hamiltonian connected. By the definition, there exists a Hamiltonian path between every pair of vertices. Without loss of generality, we choose a pair $u_{1}$ and $u_{2}$ from $A_{2}$ . Suppose, if we begin constructing the path $P$ at $u_{1}$ and visit the vertices of $A_{2}$ using $B_{1}$ except the vertex $u_{2}$ . Note that $B_{3}=\{y_{p},\ldots,y_{j-1},y_{j}\}=B_{1}{\setminus}\{y_{1},y_{2},\ldots,y_{p-1}\}$ and $A_{3}=\{x_{q+2},\ldots,x_{i-1},x_{i}\}=A_{1}{\setminus}\{x_{1},x_{2},\ldots,x_{q+1}\}$ . Further, $|A_{3}|=|A|-(|A_{2}|+q+1)=|A|-(p+q+1)$ and $|B_{3}|=|B|-(|B_{2}|+p-1)=|B|-(q+p-1)$ . Since $|A|=|B|$ , it follows that $|A_{3}|<|B_{3}|$ , in particular, $|B_{3}|=|A_{3}|+2$ . Now, we are left with two vertices in $B_{1}$ , say $w$ and $z$ , and a vertex $u_{2}$ . We observer that either $P$ ends in $w$ $(z)$ leaving $u_{2}$ or $P$ ends in $u_{2}$ leaving $w$ $(z)$ . Clearly, $P$ is not a Hamiltonian path, which is a contradiction. Hence $G$ is non-Hamiltonian connected. ∎

5.5 Path-hypohamitonian $P_{5}$ -free chordal bipartite graphs

We know that bipartite graphs are non-hypohamiltonian graphs. So it is natural to ask for the variants of hypohamiltonian, one such variant is path-hypohamiltonian. A graph $G$ is called path-hypohamiltonian, if $G$ has no Hamiltonian path and $\forall v\in V(G)$ , $G-v$ has a Hamiltonian path. In this section, we show that $P_{5}$ -free chordal bipartite graphs are non-path-hypohamiltonian.

Theorem 5.5

Let $G$ be a $P_{5}$ -free chordal bipartite graph and has no Hamiltonian path. Then, $G$ is non-path-hypohamiltonian.

Proof

We now exhibit a vertex $u$ such that $G-u$ has no Hamiltonian path. Since $G$ is a no instance of Hamiltonian path problem, by Theorem 3.2, either (i) or (ii) is true. (i) $|A|=|B|$ and there exists a vertex $u_{g}\in A_{2}$ such that $d(u_{g})<g$ or $v_{r}\in B_{2}$ such that $d(v_{r})<r$ (ii) $|A|=|B|+1$ there exists a vertex $u_{g}\in A_{2}$ such that $d(u_{g})<g$ or $v_{r}\in B_{2}$ such that $d(v_{r})\leq r$ .
(i) We observe that $G-u_{g}$ is an yes instance of the Hamiltonian path problem and thus we get a Hamiltonian path in $G-u_{g}$ . Now we choose $v\in B_{2}$ . In $G-v$ , the degree $d_{G}(u_{g})=d_{G-v}(u_{g})$ . By Theorem 3.2, $G-v$ is a no instance of the Hamiltonian path problem. Therefore, $G$ is non-path-hypohamiltonian.
(ii) We choose $v\in B_{1}(B_{2})$ . In $G-v$ , It is easy to see that $|A|>|B|+1$ . By Theorem 3.2, $G-v$ is a no instance of Hamiltonian path problem. Therefore, $G$ is non-path-hypohamiltonian.

Remark: The problems discussed in this section and their proofs are constructive in nature, therefore we obtain a polynomial-time algorithm for Hamiltonicity variants.

6 Generalizations of Hamiltonian path (cycle) in $P_{5}$ -free chordal bipartite graphs

We know that, if a problem $X$ is NP-complete for a graph class under study, then the problem $X$ is also NP-complete in all its superclasses. Further, the generalization of the problem under study is also NP-complete in that graph class. For example, the Hamiltonian path is NP-complete on split graphs therefore it is NP-complete in chordal graphs. The longest path problem which is a generalization of the Hamiltonian path problem is NP-complete in split graphs. If a problem is polynomial-time solvable in a graph class, then it is appropriate to investigate the complexity of its generalization in that graph class. Interestingly, in $P_{5}$ -free chordal bipartite graphs, Hamiltonian path (cycle) problems are polynomial-time solvable. So it is natural to look at the generalization of the Hamiltonian path (cycle) problems and their complexity study in $P_{5}$ -free chordal bipartite graphs. In this section, we use the Hamiltonian cycle (path) problem as a framework to solve other combinatorial problems. For all other problems, we modify the input graph to obtain $G^{*}$ . The challenge lies in identifying $G^{*}$ for each combinatorial problem such as longest cycle (path), Steiner cycle (path). By calling the appropriate algorithm (Hamiltonian cycle, or Hamiltonian path Algorithm) on $G^{*}$ , we obtain a result. A suitable modification to the result will give the longest cycle (path), Steiner cycle (path) for $G$ . We shall see some of the generalizations of Hamiltonicity.

6.1 Longest paths in $P_{5}$ -free chordal bipartite graphs

For a connected graph $G$ , the longest path is an induced path of maximum length in $G$ . Since the Hamiltonian path is a path of maximum length, finding the longest path is trivially solvable if the input instance is an yes instance of the Hamiltonian path problem. Thus the longest path problem is a generalization of the Hamiltonian path problem, and hence the longest path problem is NP-complete if the Hamiltonian path problem is NP-complete on the graph class under study. On the other hand, it is interesting to investigate the complexity of the longest path problem in graphs where the Hamiltonian path problem is polynomial-time solvable. Since, the Hamiltonian path problem in $P_{5}$ -free chordal bipartite graphs is polynomial-time solvable, in this section, we shall investigate the complexity of the longest path problem in $P_{5}$ -free chordal bipartite graphs.

Pruning: We shall now prune $G$ by removing vertices that will not be part of any longest path in $G$ . Without loss of generality, we assume that $G$ has no Hamiltonian path, and hence $A=B+1+f$ , $f\geq 1$ or there must exists a vertex in $A_{2}$ ( $B_{2}$ ) that does not satisfies the conditions mentioned in Theorem 3.2. As part of pruning, we prune such vertices from $G$ . Recall that $A_{2}=(u_{1},u_{2},\ldots,u_{p})$ . Let $u_{r}$ be the first vertex in $A_{2}$ with $d(u_{r})<r$ . Remove $u_{r}$ and relabel the vertices of $A_{2}$ so that the sequence is reduced to $(u_{1},u_{2},\ldots,u_{p-1})$ . With respect to the modified sequence, if we find $u_{i}$ such that $d(u_{i})<i$ , then prune $u_{i}$ and update the sequence. If there are no such $u_{r}$ , then $c=0$ . After, say $c$ iterations, $A_{2}$ becomes $(u_{1},u_{2},\ldots,u_{p-c})$ such that for $\forall u_{g},1\leq g\leq(p-c),d(u_{g})\geq g$ . Similarly, after $d$ iterations, $B_{2}$ becomes $(v_{1},v_{2},\ldots,v_{q-d})$ such that for $\forall v_{h},1\leq h\leq(q-d),d(v_{h})\geq h$ . After pruning the vertices in $A$ is reduced to the set $A^{\prime}$ , $|A^{\prime}|=|A|-c$ ,, similarly, $B$ reduced to the set $B^{\prime}$ , $|B^{\prime}|=|B|-d$ . From now on, when we refer to $A_{2}$ ( $B_{2}$ ), it refers to the modified $A_{2}$ ( $B_{2}$ ). Let $G^{*}$ be the modified graph of $G$ . $V(G^{*})=V(A^{\prime})\cup V(B^{\prime})$ .

Case 1: $|A^{\prime}|=|B^{\prime}|$
We observe that $G^{*}$ satisfies NNO and as per Theorem 3.2, $G^{*}$ has a Hamiltonian path, which is $P=(u_{1},y_{1},u_{2},y_{2},\ldots,u_{p-c},y_{p-c},x_{(q-d)+1},y_{(p-c)+1},$ $x_{(q-d)+2},y_{(p-c)+2},\ldots,x_{i},y_{j},x_{q-d},v_{q-d},$ $x_{(q-d)-1},$ $v_{(q-d)-1},$ $\ldots,x_{1},v_{1})$
Case 2: $|A^{\prime}|=|B^{\prime}|+1+f$ , $f\geq 0$
If $f>0$ , By Theorem 3.2, $G^{*}$ is not an yes instance of the Hamiltonian path problem. We remove $f$ vertices from $A^{\prime}_{2}$ . Let $G^{*}_{1}(A^{\prime}\setminus\{u_{(p-c)-1},u_{(p-c)-2},\ldots,u_{(p-c)-f}\},B^{\prime})$ be the modified graph. If $f=0$ , then $G^{*}_{1}(A^{\prime},B^{\prime})$ be same as $G^{*}$ .
Case 2.1: $\exists v_{r}$ $\in B^{\prime}_{2}$ in $G^{*}_{1}$ such that $d_{G^{*}_{1}}(v_{r})=r$
Since $d_{G^{*}_{1}}(v_{r})=r$ , $G^{*}_{1}$ is not an yes instance of the Hamiltonian path problem as per Theorem 3.2. However $G^{*}_{1}(A^{\prime}\setminus\{u_{(p-c)-1},u_{(p-c)-2},\ldots,u_{(p-c)-f},u_{(p-c)-(f+1)}\},B^{\prime})$ has a Hamiltonian path as per Theorem 3.2.
$P=(u_{1},y_{1},u_{2},y_{2},\ldots,u_{(p-c)-(f+1)},y_{(p-c)-(f+1)},x_{(q-d)+1},y_{((p-c)-(f+1))+1},x_{(q-d)+2},y_{((p-c)-(f+1))+2},\ldots,x_{i},$ $y_{j},x_{q-d},v_{q-d},$ $x_{(q-d)-1},$ $v_{(q-d)-1},\ldots,$ $x_{1},v_{1})$
Case 2.2: $\nexists v_{r}$ $\in B^{\prime}_{2}$ in $G^{*}_{1}$ such that $d_{G^{*}_{1}}(v_{r})=r$
By Theorem 3.2, $G^{*}_{1}$ is an yes instance of the Hamiltonian path problem.
$P=(u_{1},y_{1},u_{2},y_{2},\ldots,u_{(p-c)-f},y_{(p-c)-f},x_{(q-d)+1},y_{((p-c)-f)+1},x_{(q-d)+2},y_{((p-c)-f)+2},\ldots,x_{i},y_{j},x_{q-d},v_{q-d},$ $x_{(q-d)-1},$ $v_{(q-d)-1},\ldots,$ $x_{1},v_{1})$

Claim 1: $P$ is a longest path in $G^{*}$ .

Proof

$G^{*}$ be the graph obtained by pruning the vertices from $A_{2}$ and $B_{2}$ in $G$ and thus $G^{*}$ becomes an yes instance of the Hamiltonian path problem. Since $G^{*}$ satisfies (NNO), for all the pruned vertices of $A_{2}$ and $B_{2}$ , their neighborhood is a subset of $\{y_{1},\ldots,y_{p-c}\}$ and $\{x_{1},\ldots,x_{q-d}\}$ respectively. This shows that the pruned vertices of $A_{2}$ and $B_{2}$ cannot be augmented to $P$ to get a longer path in $G$ . This proves that $P$ is a longest path in $G$ . ∎

Trace of the longest path algorithm:

Refer to caption — Figure 1: An illustration for the proof of Longest path (Case 1).

For Figure 1, we shall trace the longest path algorithm. Consider the vertices of $A_{2}$ , $d(u_{2})=1$ , $u_{2}$ violates the degree constraint, so we prune $u_{2}$ and relabel the vertices $u_{3}$ as $u_{2}$ , $u_{4}$ as $u_{3}$ , and $u_{5}$ as $u_{4}$ . The updated sequence of $A_{2}$ is $(u_{1},u_{2},u_{3},u_{4})$ . With respect to the modified sequence, $d_{G^{*}}(u_{3})=2$ , prune $u_{3}$ and relabel the vertex $u_{4}$ as $u_{3}$ . Now all the vertices of $A^{\prime}_{2}$ satisfies the degree constraint and the sequence is $(u_{1},u_{2},u_{3})$ . By applying the procedure to the vertices of $B_{2}$ , we get $B^{\prime}_{2}$ as $(v_{1},v_{2},v_{3})$ . The resultant graph $G^{*}$ falls under Case 1. We obtain the longest path $P=(u_{1},y_{1},u_{2},y_{2},u_{3},y_{3},x_{4},y_{4},x_{5},y_{5},x_{3},v_{3},x_{2},v_{2},x_{1},v_{1})$

Consider Figure 2. The vertex $u_{6}$ violates the degree constrains, prune $u_{6}$ and we obtain $A^{\prime}_{2}$ , whose sequence reduced to $(u_{1},u_{2},u_{3},u_{4},u_{5})$ . Similarly $v_{3}$ and $v_{4}$ violates the constraint and thus the sequence of $B^{\prime}_{2}$ is reduced to $(v_{1},v_{2})$ . $G^{*}$ follows Case 2 of the procedure. Let $G^{*}_{1}$ be the graph obtained by removing $f$ , $f=\{u_{4},u_{5}\}$ vertices from $G^{*}$ . We observe that $d_{G^{*}}(v_{1})=1$ , by Case 2.1, remove $u_{3}$ and the longest path is $P=(u_{1},y_{1},u_{2},y_{2},x_{3},y_{3},x_{4},y_{4},x_{5},y_{5},x_{6},y_{6},x_{2},v_{2},x_{1},v_{1})$

Theorem 6.1

Let $G$ be a $P_{5}$ -free chordal bipartite graph. Finding the longest path in $G$ is polynomial-time solvable.

Proof

Follows from the above discussion on pruning and Claim 1. ∎

Remarks: As an extension of longest path problem, we naturally obtain a minimum leaf spanning tree of $G$ , which is a spanning tree of $G$ with the minimum number of leaves, in polynomial-time. Since $G$ satisfies NNO, the vertices pruned while constructing $G^{*}$ , cannot be included as internal vertices of $P$ . We shall now construct a minimum leaf spanning tree $T$ with $P$ as a subtree. (i) the pruned vertices are augmented to $P$ as leaves to obtain $T$ . (ii) if $|A_{1}^{\prime}|>|B_{1}^{\prime}|$ , then the vertices in $A_{1}^{\prime}$ not included in $P$ are added to $P$ as leaves to obtain $T$ . Similarly, if $|B_{1}^{\prime}|>|A_{1}^{\prime}|$ , then the vertices in $B_{1}^{\prime}$ not included in $P$ are added to $P$ as leaves to obtain $T$ . This shows that $T$ has $|V(G)\setminus V(P)|+2$ leaves. Maximum leaf spanning tree of $G$ can be constructed by choosing $x_{1}y_{1}$ edge and augment all other vertices of $A_{1},A_{2}$ to the vertex $y_{1}$ , similarly $B_{1},B_{2}$ to $x_{1}$ .

Corollary 2

Minimum connected dominating set in $P_{5}$ -free chordal bipartite graph is polynomial-time solvable.

Proof

Follows from Theorem 6.1.

6.2 Longest cycles in $P_{5}$ -free chordal bipartite graphs

Similar to the longest path, the longest cycle is an induced cycle of maximum length in $G$ . It is natural to ask for the longest cycle in a graph if $G$ has no Hamiltonian cycle because it is trivially solvable when $G$ has a Hamiltonian cycle. Since, the Hamiltonian cycle problem in $P_{5}$ -free chordal bipartite graphs is polynomial-time solvable, in this section, we shall investigate the complexity of the longest cycle problem.
Pruning: Without loss of generality, we assume that $G$ has no Hamiltonian cycle, and hence $A\neq B$ or there must exist a vertex in $A_{2}~{}(B_{2})$ that does not satisfies the condition mentioned in Theorem 2. The violated vertices cannot be a part of the longest cycle, so we prune such vertices from $G$ . Let $u_{r}$ be the first vertex in $A_{2}$ with $d(u_{r})\leq r$ . Remove $u_{r}$ and relabel the vertices of $A_{2}$ until there are no such $u_{r}$ . After say $c$ iterations, $A_{2}$ becomes $(u_{1},u_{2},\ldots,u_{p-c})$ such that for $\forall$ $u_{g}$ , 1 $\leq g\leq(p-c)$ , $d(u_{g})>g$ . Similarly, after say $d$ iterations, $B_{2}$ becomes $(v_{1},v_{2},\ldots,v_{q-d})$ such that for $\forall$ $v_{h}$ , 1 $\leq h\leq(q-d)$ , $d(u_{h})>h$ . After pruning, $A$ reduced to the set $A^{\prime}$ , $|A^{\prime}|=|A|-c$ and $B$ reduced to the set $B^{\prime}$ , $|B^{\prime}|=|B|-d$ . Let the modified graph be $G^{*}$ .

Case 1: $|A^{\prime}|=|B^{\prime}|$
$G^{*}$ satisfies NNO and by Theorem 3.1, $G^{*}$ is an yes instance of the Hamiltonian cycle problem.
$C=(y_{1},u_{1},y_{2},u_{2},\ldots,y_{p-c},u_{p-c},y_{(p-c)+1},x_{1},v_{1},x_{2},v_{2},\ldots,$ $x_{q-d},$ $v_{q-d},x_{(q-d)+1},y_{(p-c)+2},x_{(q-d)+2},\ldots,$ $y_{j},$ $x_{i},y_{1})$
Case 2: $|A^{\prime}|=|B^{\prime}|+f$ , $f\geq 1$
By Theorem 3.1, $|A^{\prime}|=|B^{\prime}|$ and hence $G^{*}$ is an yes instance of the Hamiltonian cycle problem. We Remove $f$ , $\{u_{(p-c)-1},u_{(p-c)-2},\ldots,u_{(p-c)-f}\}$ vertices from $A^{\prime}_{2}$ in $G^{*}$ results $|A^{\prime}|=|B^{\prime}|$ and by Theorem 3.1, $G^{*}$ has a Hamiltonian cycle.
$C=(y_{1},u_{1},y_{2},u_{2},\ldots,y_{(p-c)-f},u_{(p-c)-f},y_{((p-c)-f)+1},$ $x_{1},v_{1},x_{2},v_{2},$ $\ldots,x_{q-d},$ $v_{q-d},x_{(q-d)+1},y_{((p-c)-f)+2},$ $x_{(q-d)+2},\ldots,$ $y_{j},x_{i},y_{1})$

Claim 2: $C$ is a longest cycle in $G^{*}$ .

Proof

We prune the vertices from $A_{2}$ and $B_{2}$ in $G$ and let the modified graph be $G^{*}$ . We observe that $G^{*}$ satisfies the condition mentioned in Theorem 2. Since $G^{*}$ satisfies (NNO), the neighborhood of pruned vertices of $A_{2}$ and $B_{2}$ is a subset of $\{y_{1},\ldots,y_{p-c}\}$ and $\{x_{1},\ldots,x_{q-d}\}$ respectively. Therefore the pruned vertices cannot be augmented to $C$ to get a longer cycle in $G^{*}$ . Hence $C$ is a longest cycle in $G^{*}$ . ∎

Trace of the Algorithm: Consider the graph $G$ given in Figure 1, $u_{1}$ and $u_{2}$ violates the degree constraint, we prune the vertices and the sequence becomes $(u_{1},u_{2},u_{3})$ . With respect to the modified sequence $d_{G^{*}}(u_{3})=3$ , prune $u_{3}$ and the sequence becomes $(u_{1},u_{2})$ . Similarly, in $B_{2}$ , $v_{1}$ is pruned, $(v_{1},v_{2},v_{3})$ . We find $v_{3}$ such that $d_{G^{*}}(v_{3})=3$ , prune $v_{3}$ , $(v_{1},v_{2})$ . Graph $G^{*}$ satisfies case 1, $|A^{\prime}|=|B^{\prime}|$ and the longest cycle $C=(y_{1},u_{1},y_{2},u_{2},y_{3},x_{1},v_{1},x_{2},v_{2},x_{3},y_{4},x_{4},y_{5},x_{5},y_{1})$ .
Case 2: Consider the graph $G$ given in Figure 2, vertices $u_{5}$ and $u_{6}$ are pruned and $A^{\prime}$ becomes $(u_{1},u_{2},u_{3},u_{4})$ . Similarly, $v_{1}$ is pruned and the sequence becomes $(v_{1},v_{2},v_{3})$ . In the modified graph, $v_{2}$ and $v_{3}$ violates degree constraint and thus $B^{\prime}_{2}$ has a vertex $v_{1}$ . $G^{*}$ satisfies case 2 $|A^{\prime}|=|B^{\prime}|+f$ , $f=(u_{2},u_{3},u_{4})$ . Let $G^{*}_{1}$ be the graph obtained by removing $(u_{2},u_{3},u_{4})$ . The longest cycle $C=(y_{1},u_{1},y_{2},x_{1},v_{1},x_{2},y_{3},x_{3},y_{4},x_{4},y_{5},x_{5},y_{1})$ .

6.3 Steiner paths in $P_{5}$ -free chordal bipartite graphs

The Steiner path problem is introduced in [33] which is a variant of the Steiner tree and a generalization of the Hamiltonian path problem. Given $G,R\subseteq V(G)$ , find a path containing all of $R$ minimizing $V(G)\setminus R$ , if exists. Note that, this constrained path problem is precisely the Hamiltonian path problem when $R=V(G)$ . This has another motivation as well. The Steiner tree problem [11] is the problem of connecting a given set $R$ of vertices (known as terminal vertices) by adding a minimum number of vertices from $V(G)\setminus R$ (known as Steiner vertices). The Steiner tree problem is trivially solvable in $P_{5}$ -free chordal bipartite graphs. It is natural to ask for a variant, namely the Steiner path. It is important to highlight that not all input graphs have Steiner paths. We shall present constructive proof for the existence of the Steiner path in a $P_{5}$ -free chordal bipartite graph.

Lemma 5

For a $P_{5}$ -free chordal bipartite graph and $R=\{u_{1},\ldots,u_{r}\}\subseteq A_{2}$ , $G$ has Steiner path $P$ if and only if the vertices of $R$ has an ordering $(u_{1},\ldots,u_{r})$ such that $\forall u_{g},d(u_{g})\geq g$ , $1\leq g\leq r-1$ and $d(u_{r})\geq d(u_{r-1})$ .

Proof

We modify the instance of Steiner path problem of $G$ to the instance of Hamiltonian path problem of $G^{*}$ , where $G^{*}$ is the graph induced on the set $R\cup\{y_{1},y_{2},\ldots,y_{r-1}\}$ .
Necessity : Assume on the contrary, there exists a vertex $u_{g}\in R$ such that $d(u_{g})<g$ . Since $G^{*}$ is a no instance of the Hamiltonian path problem, the path $P$ obtained from $G^{*}$ is not a Steiner path, a contradiction.
Sufficiency: Since $R$ has an ordering $(u_{1},\ldots,u_{r})$ and $\forall u_{g},d(u_{g})\geq g$ , $1\leq g\leq r-1$ , $R$ satisfies NNO in $G^{*}$ . By passing $G^{*}$ to the Hamiltonian path algorithm we obtain a path $P$ . Since the path $P$ spans all of $R$ , $P$ is a Steiner path in $G$ . Therefore, $P=(u_{1},y_{1},\ldots,y_{r-1},u_{r})$ is a Steiner path. Since $R$ is an independent set of size $r$ , any path containing $R$ must have $r-1$ additional vertices and hence $P$ is a minimum Steiner path. ∎

Lemma 6

For a $P_{5}$ -free chordal bipartite graph and $R=\{x_{1},\ldots,x_{r}\}\subseteq A_{1}$ , $G$ has Steiner path $P$ if and only if there exists $(v_{1},\ldots,v_{r-(j+1)})$ in $B_{2}$ such that $\forall v_{h},d(v_{h})\geq h$ , $1\leq h\leq|A_{1}|-|B_{1}|$ .

Proof

Let $G^{*}$ be the graph induced on $R\cup B_{1}\cup\{v_{1},\ldots,v_{r-(j+1)}\}$ .
Necessity : It is easy to see that if $|R|\leq|B_{1}|+1$ , then $P=(x_{1},y_{1},\ldots,x_{r-1},y_{r-1},x_{r})$ is a minimum Steiner path. We shall now see the case where, $|R|>|B_{1}|+1$ . Assume on the contrary, there exists a vertex $v_{h}\in B_{2}$ such that $d(v_{h})<h$ . We observe that $G^{*}$ is a no instance of Hamiltonian path problem, a contradiction.
Sufficiency: We observe that $G^{*}$ has a Hamiltonian path which is a Steiner path in $G$ . Note that the path $P=(x_{r},y_{j},x_{r-1},y_{j-1},\ldots,x_{r-(j+1)},v_{r-(j+1)},\ldots,v_{2},x_{2},v_{1},x_{1})$ is a Steiner path of minimum cardinality. ∎

Lemma 7

For a $P_{5}$ -free chordal bipartite graph and $R=\{x_{1},\ldots,x_{r}\}\subseteq(A_{1}\cap B_{2}$ ), $G$ has Steiner path $P$ if and only if $R\cap B_{2}=(z_{1},\ldots,z_{l})$ has NNO with $(w_{1},\ldots,w_{l})$ , $1\leq l<r$ , of $A_{1}$ .

Proof

Let $G^{*}$ be the graph induced on the set $R\cup\{z_{1},\ldots,z_{l}\}\cup\{w_{1},\ldots,w_{l}\}.$
Necessity : Proof is similar to the necessity of Lemma 6.
Sufficiency: The modified graph $G^{*}$ has a Hamiltonian path. We obtain the path $P=(z_{1},w_{1},\ldots,z_{l},w_{l},y_{1},x_{1},$ $\ldots,y_{r-l-1},x_{r-l})$ which is a minimum Steiner path in $G$ . ∎

On the similar line, other cases $(a)$ $R\subseteq B_{1}$ , $(b)$ $R\subseteq B_{2}$ , $(c)$ $R\cap A_{1}\not=\emptyset$ and $R\cap A_{2}\not=\emptyset$ , $(d)$ $R\cap A_{2}\not=\emptyset$ and $R\cap B_{1}\not=\emptyset$ , $(e)$ $R\cap B_{1}\not=\emptyset$ and $R\cap B_{2}\not=\emptyset$ , and $(f)$ $R\cap A_{1}\not=\emptyset$ and $R\cap B_{2}\not=\emptyset$ and $R\cap A_{2}\not=\emptyset$ can be proved.

Trace: Let us consider the set, $R=\{u_{2},u_{3},u_{5}\}$ in Figure 3 (a). It is clear that all the vertices in set $R$ satisfies the above given degree constrains and hence there exists a Steiner path, $P=\{u_{2},y_{1},u_{3},y_{2},u_{5}\}$ . Suppose, if $R=\{u_{1},u_{2},u_{3}\}$ , then we observe that the vertex $u_{2}$ violates the degree constraint and hence there does not exist Steiner path in Figure 3 (b).

6.4 Steiner cycles in $P_{5}$ -free chordal bipartite graphs

Similar to the Steiner path, given a graph $G,R\subseteq V(G)$ , the Steiner cycle problem asks for a simple cycle containing all of $R$ minimizing $V(G)\setminus R$ . Suppose, if $R=V(G)$ , then this problem is precisely the Hamiltonian cycle problem. If $G$ is an yes instance of the Hamiltonian cycle problem, then this problem is trivially solvable. We observe that not all input graphs have a solution to the Steiner cycle problem. We shall present constructive proof for the existence of a Steiner cycle in a $P_{5}$ -free chordal bipartite graph.

Lemma 8

For a $P_{5}$ -free chordal bipartite graph and $R=\{u_{1},\ldots,u_{r}\}\subseteq A_{2}$ , $G$ has Steiner cycle $P$ if and only if the vertices of $R$ has an ordering $(u_{1},\ldots,u_{r})$ such that $\forall u_{g},d(u_{g})>g$ , $1\leq g\leq r-1$ and $d(u_{r})\geq d(u_{r-1})$ .

Proof

Let $G^{*}$ be the graph induced on the set $R\cup(u_{1},\ldots,u_{r})$ .
Necessity : Assume on the contrary, there exists a vertex $u_{g}\in R$ such that $d(u_{g})\leq g$ . Since $G^{*}$ is a no instance of the Hamiltonian cycle problem, the cycle $C$ obtained from $G^{*}$ is not a Steiner path, a contradiction.
Sufficiency: Since $R$ has an ordering $(u_{1},\ldots,u_{r})$ and $\forall u_{g},d(u_{g})>g$ , $1\leq g\leq r-1$ , $R$ satisfies NNO in $G^{*}$ . We call our Hamiltonian cycle algorithm on $G^{*}$ which outputs a cycle $C$ . Since the cycle $C$ spans all of $R$ , $C$ is a Steiner cycle in $G$ . Therefore, $C=(y_{1},u_{1},\ldots,y_{r},u_{r},y_{1}\}$ is a Steiner cycle. Any cycle containing $R$ must have $r$ additional vertices and hence $C$ is a minimum Steiner cycle. ∎

Lemma 9

For a $P_{5}$ -free chordal bipartite graph and $R=\{x_{1},\ldots,x_{r}\}\subseteq A_{1}$ , $G$ has Steiner cycle $C$ if and only if there exists $(v_{1},\ldots,v_{r-j})$ in $B_{2}$ such that $\forall v_{h},d(v_{h})>h$ , $1\leq h\leq r-j$ .

Proof

Let $G^{*}$ be the graph induced on $R\cup B_{1}\cup\{v_{1},\ldots,v_{r-j}\}$ .
Necessity : If $|R|\leq|B_{1}|$ , then the Steiner cycle problem is trivially solvable. We obtain the Steiner cycle $C=(x_{1},y_{1},\ldots,x_{r-1},$ $y_{r-1},x_{r},y_{r},x_{1})$ . We assume that $|R|>|B_{1}|$ . Assume on the contrary, there exists a vertex $v_{h}\in B_{2}$ such that $d(v_{h})\leq h$ . We observe that $G^{*}$ is a no instance of Hamiltonian cycle problem, a contradiction.
Sufficiency: We observe that $G^{*}$ has a Hamiltonian cycle which is a Steiner cycle in $G$ . The cycle $C=(x_{1},v_{1},x_{2},v_{2},\ldots,x_{r-j},v_{r-j},x_{(r-j)+1},y_{j},x_{(r-j)+2},y_{j-1},\ldots,x_{r-1},y_{2},x_{r},y_{1},x_{1})$ .
is a Steiner cycle of minimum cardinality. ∎

Lemma 10

For a $P_{5}$ -free chordal bipartite graph and $R=\{x_{1},\ldots,x_{r}\}\subseteq A_{1}\cap B_{2}$ , $G$ has Steiner cycle $C$ if and only if $R\cap B_{2}=(z_{1},\ldots,z_{l})$ has NNO with $(w_{1},\ldots,w_{l})$ , $1\leq l<r$ , of $A_{1}$ .

Proof

Let $G^{*}$ be the graph induced on the set $R\cup\{z_{1},\ldots,z_{l}\}\cup\{w_{1},\ldots,w_{l}\}.$
Necessity : Proof is similar to the necessity of Lemma 9
Sufficiency: We observe that $G^{*}$ has a Hamiltonian cycle. The cycle $C=(w_{1},z_{1},\ldots,w_{l},z_{l},x_{l+1},y_{1},\ldots x_{r-l},$ $y_{r-l},w_{1})$ is a minimum Steiner cycle in $G$ . ∎

For other cases such as $(a)$ $R\subseteq B_{1}$ , $(b)$ $R\subseteq B_{2}$ , $(c)$ $R\cap A_{1}\not=\emptyset$ and $R\cap A_{2}\not=\emptyset$ , $(d)$ $R\cap A_{2}\not=\emptyset$ and $R\cap B_{1}\not=\emptyset$ , $(e)$ $R\cap A_{1}\not=\emptyset$ and $R\cap A_{2}\not=\emptyset$ , and $(f)$ $R\cap A_{1}\not=\emptyset$ and $R\cap B_{2}\not=\emptyset$ and $R\cap A_{2}\not=\emptyset$ , a similar argument can be given.
Trace: Consider the illustration given in Figure 4. We trace $(a)$ and $(b)$ of Figure 4 for the set $R=\{x_{1},x_{2},x_{3},x_{4},x_{5}\}$ . In Figure 4 (a), $|B_{1}|=3$ , so there must exist at least two vertices, $\{z_{1},z_{2}\}$ in $B_{2}$ such that $d(z_{r})>r$ . We consider $v_{2}$ as $z_{1}$ and $v_{3}$ as $z_{2}$ . We observe that $d(z_{1})>1$ and $d(z_{2})>2$ . The Steiner cycle, $C=\{x_{1},v_{2},x_{2},v_{3},x_{3},y_{1},x_{4},y_{2},x_{5},y_{3},x_{1}\}$ . In Figure 4 (b), there does not exist at least two vertices satisfying the degree constraint and hence it is a no instance of a Steiner cycle.

Remark: Proofs of the problems discussed in this section are constructive in nature and thus we obtain a polynomial-time algorithm for generalization of the Hamiltonian cycle (path).

7 Treewidth and Pathwidth of $P_{5}$ -free chordal bipartite graphs

In general, many graph-theoretic problems have linear-time algorithms in trees. This motivates us to investigate the tree-like representation of graphs so that algorithmic techniques used in trees can be used to study the computational complexity of those problems in trees. The study of treewidth investigates this line of study. This problem was introduced by Robertson and Seymour [34]. This problem is NP-complete for bipartite graphs [35] and planar graphs. Treewidth can be obtained for cographs in $\mathit{O(n)}$ time and for chordal bipartite graphs in $\mathit{O(n^{6})}$ time [36]. We have the following result in [36] for chordal bipartite graphs. Given a chordal bipartite graph $G$ , and a positive integer $k$ , if the treewidth of $G$ is at most $k$ then it returns yes with the underlying chordal embedding of $G$ , otherwise, it says no. However, the exact value of treewidth is not explicitly mentioned due to the inherent complex structure of chordal bipartite graphs. Interestingly, for $P_{5}$ -free chordal bipartite graphs, we present an exact value for treewidth as well as the underlying chordal embedding in linear time. In this section, we present a polynomial-time algorithm to find a tree decomposition of a $P_{5}$ -free chordal bipartite graph, and hence the treewidth can be computed in polynomial time.
Definition :
A tree decomposition of a graph $G$ is a pair $(T,Z)$ where $T$ is a tree and $V(T)=Z=\{z_{1},z_{2},\ldots,z_{k}\}$ , $z_{t}$ is a vertex in $T$ such that $z_{t}\subseteq V(G)$ for each $t$ , $1\leq t\leq k$ . Further,

(i)

$V(G)=\bigcup_{z_{t}\in V(T)}z_{t}$ ,
(ii)

For every edge $\{x,y\}\in E(G)$ , there exists some $z_{t}\in V(T)$ such that $\{x,y\}\subseteq z_{t}$ and
(iii)

For every vertex $u\in V(G)$ the set $\{z_{t}\in V(T)|u\in z_{t}\}$ induces a subtree in the tree $T$ .

The width of a tree decomposition $(T,Z)$ is $\max_{z_{t}\in V(T)}~{}|~{}z_{t}|$ . The treewidth of a graph $G$ , denoted by $tw(G)$ , is the least possible width of a tree decomposition of $G$ minus one. The vertex set $z_{t}$ is also referred to as $label(t)$ . In this section, we shall present an algorithm that outputs a tree decomposition of $G$ .

Input: A

P_{5}

-free chordal bipartite graph

G

Output: A tree decomposition of

G

1 Let

A_{1}=(x_{1},\ldots,x_{i})

B_{1}(y_{1},\ldots,y_{j})

A_{2}(u_{1},\ldots,u_{p})

, and

B_{2}(v_{1},\ldots,v_{q})

be the vertices of

G

and

t=2

2 Let

\{z_{1},\ldots,z_{k}\}

be the vertices of

V(T)

3 if $(i+d(u_{p}))\leq(j+d(v_{q}))$ then

4 Create a vertex

z_{1}

T

whose label, label

(z_{1})=\{x_{1},x_{2},\ldots,x_{i},y_{1},y_{2},\ldots,y_{d(u_{p})}\}

5 for $k=d(u_{p})+1$ to $j$ do

6 Create a label,

(z_{t})=\{x_{1},x_{2},\ldots,x_{i},y_{k}\}

and add an edge

\{z_{t-1},z_{t}\}

E(T)

t++

8 end for

9 for $k=q$ to 1 do

10 Create a label,

(z_{t})=\{v_{k},N_{G}(v_{k})\}

and add an edge

\{z_{t},z_{t-1}\}

E(T)

t++

12 end for

13 for $k=p$ to 1 do

14 if $k=p$ then

15 Create a label,

(z_{t})=\{u_{k},N(u_{k})\}

and add an edge

\{z_{t},z_{1}\}

E(T)

t++

17 else

18 Create a label

(z_{t})=\{u_{K},N(u_{k})\}

and add an edge

\{z_{t},z_{t-1}\}

E(T)

t++

20 end if

22 end for

24else

25 Create a vertex

z_{1}

T

whose label, label

(z_{1})=\{y_{1},y_{2},\ldots,y_{j},x_{1},x_{2},\ldots,x_{d(v_{q})}\}

26 for $k=d(v_{q})+1$ to $i$ do

27 Create a label,

(z_{t})=\{y_{1},y_{2},\ldots,y_{j},x_{k}\}

and add an edge

\{z_{t-1},z_{t}\}

E(T)

t++

29 end for

30 for $k=p$ to 1 do

31 Create a label,

(z_{t})=\{u_{k},N_{G}(u_{k})\}

and add an edge

\{z_{t},z_{t-1}\}

E(T)

t++

33 end for

34 for $k=q$ to 1 do

35 if $k=q$ then

36 Create a label,

(z_{t})=\{v_{k},N(v_{k})\}

and add an edge

\{z_{t},z_{1}\}

E(T)

t++

38 else

39 Create a label

(z_{t})=\{v_{k},N(v_{k})\}

and add an edge

\{z_{t},z_{t-1}\}

E(T)

t++

41 end if

43 end for

45 end if

Algorithm 1 Tree Decomposition for

P_{5}

-free chordal bipartite graphs

Correctness of Algorithm 1

Lemma 11

The graph $T$ obtained by Algorithm 1 is a tree and it satisfies all the three properties of tree decomposition mentioned in the definition.

Proof

(i)

$T$ is a Tree
Let $V(T)=\{z_{1},z_{2},\ldots,z_{k}\}$ , and $E(T)=\{\{z_{r},z_{t}\}|z_{t}$ is adjacent to $z_{r}$ by steps 6, 10, 15, 18 of Algorithm 1 $\}$ . From the construction, it is clear that the invariant maintained by Algorithm 1 is connectedness. We observe that at each step, $(z_{t})$ , $t>1$ is created and an edge $\{z_{t},z_{t-1}\}$ is added to $E(T)$ corresponding to sets $z_{t}$ and $z_{t-1}$ which shows that $T$ is acyclic. This implies that $T$ is connected and acyclic. Hence $T$ is a tree.
(ii)

For every edge $\{x,y\}\in E(G)$ , there exist some $z_{t}\in V(T)$ such that $\{x,y\}\in label(z_{t}).$
By our construction, at each step a vertex $x$ and $N_{G}(x)$ is added to $label(z_{t})$ for some $t$ . Hence there exist some $z_{t}\in V(T)$ such that $\{x,y\}\in label(z_{t})$ . This shows that $V(G)=\bigcup_{z_{t}\in V(T)}label(z_{t})$ .
(iii)

For every vertex $u\in V(G)$ the set $\{z_{t}\in V(T)|u\in label(z_{t})\}$ induces subtree of the tree $T$ .
As per the construction, the vertices $\{x_{1},\ldots,x_{i},y_{1},\ldots,y_{d(u_{p})}\}$ are added to the label $z_{1}$ . It is clear from Steps (5-20), the vertices $\{y_{d(u_{p})},\ldots,y_{j}\}$ of $B_{1}$ and $A_{2}$ are included based on NNO and an edge $\{z_{t},z_{t-1})\}$ is added to $E(T)$ . Similarly, from Steps (24-40), the vertices of $A_{1}$ and $B_{2}$ are included. Observe that for each $u\in V(G)$ , the set $\{z_{t}|u\in label(z_{t})\}$ induces a subtree in $T$ .

Theorem 7.1

The treewidth of a $P_{5}$ -free chordal bipartite graph is $tw(G)\geq\min\{(i+d(u_{p})),(j+d(v_{q}))\}-1$ .

Proof

We observe that in any tree decomposition there exists a label, $z_{t}$ whose cardinality is at least $i+d(u_{p})$ . On the contrary, suppose there exists a tree decomposition such that $|label(z_{t})|\leq i+d(u_{p})-1$ . Without loss of generality, we assume that $z_{t}<i+d(u_{p})$ and label $(z_{t})=\{x_{1},\ldots,x_{i},y_{1},\ldots,y_{d(u_{p})-1}\}$ . By the property of NNO, the vertex $u_{p}$ is adjacent to $\{y_{1},\ldots,y_{d(u_{p})\}}$ . Clearly, either the set $\{z~{}|~{}y_{d(u_{p})}\in$ label $(z)\}$ or $\{z~{}|~{}u_{p}\}\in$ label $(z)\}$ does not form a subtree in $T$ . Therefore, $y_{d(u_{p})}\in$ label $(z_{1})$ . Similarly, each $y_{r}\in\{y_{1},\ldots,y_{d(u_{p})-1}\}$ must be part of label $(z_{1})$ . ∎

Lemma 12

The tree $T$ obtained from Algorithm 1 is a tree decomposition of $G$ such that the treewidth, $tw(G)=\min\{(i+d(u_{p})),(j+d(v_{q}))\}-1$ .

Proof

By our construction, we see that the cardinality of each label $(z_{t})$ is at most $\min\{(i+d(u_{p})),(j+d(v_{q}))\}-1$ , in particular, $|label(z_{1})|=\min\{(i+d(u_{p})),(j+d(v_{q}))\}-1$ . ∎

Corollary 3

Let $G$ be a $P_{5}$ -free chordal bipartite graph. Then, the pathwidth of $G$ is $min\{(i+d(u_{p})),(j+d(v_{q}))\}-1$ .

Proof

We know that for any graph $G$ , the pathwidth of $G$ is at least the treewidth of $G$ . By Theorem 7.1, the treewidth of a $P_{5}$ -free chordal bipartite graph is $\min\{(i+d(u_{p})),(j+d(v_{q}))\}-1$ . We observe that the tree decomposition of $G$ output by Algorithm 1 is a also a path decomposition of $G$ . Hence the pathwidth of $G$ is same as the treewidth of $G$ which is $min\{(i+d(u_{p})),(j+d(v_{q}))\}-1$ . ∎

Trace of the Treewidth (Pathwidth) Algorithm (Algorithm 1):
Consider the illustration given in Figure 1. We shall trace the treewidth algorithm for Figure. 1. By Step 3, we create a label $z_{1}=\{x_{1},x_{2},x_{3},x_{4},x_{5},y_{1},y_{2},y_{3}\}$ . The trace of other steps are included in Figure 6 and Figure 7.

8 Minimum Fill-in in $P_{5}$ -free chordal bipartite graphs

Having studied treewidth, we focus on problems that are related to treewidth. We know that a graph $G$ has treewidth at most $k$ if and only if $G$ has a chordal completion whose maximum clique size is at most $k+1$ . This motivates us to study the complexity of the chordal completion problem in $P_{5}$ -free chordal bipartite graphs. For a graph $G$ , the minimum fill-in (chordal completion) [38] problem is the problem of finding a chordal embedding of $G$ which is a graph $G^{*}$ obtained by an augmenting minimum number of edges to $G$ so that $G^{*}$ is chordal. The minimum fill-in problem is NP-complete on general graphs [37]. In [38] an $\mathit{O(n^{5})}$ time algorithm is presented for chordal bipartite graphs. Subsequently, in [39] it is improved to $\mathit{O(n^{4})}$ . Interestingly, a chordal embedding of a $P_{5}$ -free chordal bipartite graph is a split graph. In this section, we present a linear-time algorithm to find the minimum fill-in for $P_{5}$ -free chordal bipartite graphs.

Input: A

P_{5}

-free chordal bipartite graph

G

Output: A minimum fill-in of

G

1 Let

A_{1}=(x_{1},\ldots,x_{i})

B_{1}=(y_{1},\ldots,y_{j})

A_{2}=(u_{1},\ldots,u_{p})

, and

B_{2}=(v_{1},\ldots,v_{q})

be the vertices of

G

2 Let

k=(i-d(v_{q}))

and

l=(j-d(u_{p}))

3 for $r=d(u_{p})$ to 1 do

4 for $z=r-1$ to 1 do

5 Add an edge

\{y_{r},y_{z}\}

E(G)

6 end for

8 end for

9for $r=d(v_{q})$ to 1 do

10 for $z=r-1$ to 1 do

11 Add an edge

\{x_{r},x_{z}\}

E(G)

12 end for

14 end for

15if $(k*(i-k))\leq(l*(j-l))$ and $(k\leq l)$ then

16 for $r=i$ to $(i-k)$ do

17 for $z=r-1$ to 1 do

18 Add an edge

\{x_{r},x_{z}\}

E(G)

19 end for

21 end for

23else

24 for $r=j$ to $(j-l)$ do

25 for $z=r-1$ to 1 do

26 Add an edge

\{y_{r},y_{z}\}

E(G)

27 end for

29 end for

31 end if

Algorithm 2 Minimum Fill-in of

P_{5}

-free chordal bipartite graphs

Lemma 13

Let $G$ be a $P_{5}$ -free chordal bipartite graph. The number of edges augmented to find a chordal embedding of $G$ is min{ $(\frac{i(i-1)}{2}+\frac{d(u_{p})(d(u_{p})-1)}{2}),(\frac{j(j-1)}{2}+\frac{d(v_{q})(d(v_{q})-1)}{2})\}$

Proof

Let $G^{*}$ be a chordal embedding of $G$ with $V(G^{*})=V(G)$ and $E(G^{*})=E(G^{*})\cup S$ , where $S$ is the set of augmented edges. We know that $A_{1}\cup B_{1}$ is a maximal biclique in $G$ . So, one of the partitions $A_{1}~{}(B_{1})$ of $G$ must be a clique $K$ in $G^{*}$ . We consider the followings cases to find the edges added from $A_{2}$ $(B_{2})$ to $K$ .
Case 1: $A_{1}$ is a clique. Then, in any $G^{*}$ , $\{y_{1},y_{2},\ldots,y_{d(u_{p})}\}$ must be a clique. On the contrary, there exist a pair of vertices, say $y_{r}$ , $y_{s}$ $\in$ $B_{1}$ , $1\leq r\leq d(u_{p})$ , $1\leq s\leq d(u_{p})$ such that $\{y_{r},y_{s}\}\notin E(G^{*})$ . Due to NNO property in $G^{*}$ , we get an induced cycle $C=(y_{r},u_{p},y_{s},x_{1},y_{r})$ of length four. This contradicts the fact that $G^{*}$ is chordal. Therefore, $\{y_{1},y_{2},\ldots,y_{d(u_{p})}\}$ induces a clique and the number of edges augmented is $\frac{d(u_{p})(d(u_{p})-1)}{2}$ .
Case 2: $B_{1}$ is a clique. Then, $\{x_{1},x_{2},\ldots,x_{d(v_{p})}\}$ must be a clique. Suppose not, then there exist a pair of vertices, say $x_{r}$ , $x_{s}$ $\in$ $A_{1}$ , $1\leq r\leq d(v_{q})$ , $1\leq s\leq d(v_{q})$ that are not adjacent in $G^{*}$ . Similar to Case 1, we get an induced cycle $C=(x_{r},v_{q},x_{s},y_{1},x_{r})$ of length four, which is a contradiction. Therefore, we augment $\frac{d(v_{q})(d(v_{q})-1)}{2})\}$ edges to $A_{1}$ .
From the above case analysis, Lemma 13 follows. ∎

Correctness of Algorithm 2

Lemma 14

For a $P_{5}$ -free chordal bipartite graph $G$ , Algorithm 2 outputs a minimum fill-in of $G$ . Besides, Algorithm 2 outputs a chordal embedding of $G$ .

Proof

By our construction, the graph induced on $A_{1}$ ( $B_{1}$ ) is a complete graph. This implies that the graph induced on $A_{1}\cup B_{1}$ is a split graph, which is a chordal graph. We know that the pendant vertices of $A_{2}$ cannot be a part of a cycle. It is clear from the Steps (3-7) and the fact that $A_{2}$ follows NNO in $G$ , $\{u_{r}\}\cup N_{G}(u_{r})$ , $1\leq r\leq p$ , forms a clique. Similarly, for $B_{2}$ as well. We observe that there does not exist an induced cycle of length at least four in $G^{*}$ . Therefore, the graph constructed by Algorithm 2 is a chordal graph. From Steps (3-7) and Steps (14-18), it is clear that the number of edges added is the number mentioned in Lemma 13, which is min{ $(\frac{i(i-1)}{2}+\frac{d(u_{p})(d(u_{p})-1)}{2}),(\frac{j(j-1)}{2}+\frac{d(v_{q})(d(v_{q})-1)}{2})\}$ . ∎

Trace of Algorithm 2: Consider the illustration given in Figure 8. We trace Algorithm 2 for Figure 8. The degree of $u_{p}$ , $d(u_{p})=3$ , Steps (3-5) of Algorithm 2 make $\{y_{1},y_{2},y_{3}\}$ a clique. Similarly, $d(v_{q})=3$ , $\{x_{1},x_{2},x_{3}\}$ forms a clique. Here, $k=l=3$ , $(k*(i-k))\leq(l*(j-l))$ = 6 $\leq$ 6. Steps (14-18), initially chooses $u_{5}$ and add edges to $\{u_{4},u_{3},u_{2},u_{1}\}$ . At Iteration 2, $u_{4}$ is connected to $\{u_{3},u_{2},u_{1}\}$ . The resultant graph $H$ is a chordal graph.

Theorem 8.1

The chordal embedding of a $P_{5}$ -free chordal bipartite graph is a split graph.

Proof

By construction, it is clear that $A_{1}\cup B_{1}$ is a maximal biclique, and $A_{2}$ , $B_{2}$ are independent sets. Let $G^{*}$ be a chordal embedding of $G$ . Algorithm 2 makes $A_{1}\cup\{y_{1},y_{2},\ldots,y_{d(u_{p})}\}$ as a clique. The set $A_{2}\cup B_{2}\cup\{y_{d(u_{p})},y_{d(u_{p})+1},\ldots,y_{j}\}$ forms an independent set. We see that the graph $G^{*}$ is partitioned into an independent and a clique. Therefore, $G^{*}$ is a split graph.

9 Results on Complement graphs of $P_{5}$ -free chordal bipartite graphs

The generalization of the minimum fill-in problem is cluster editing problem [40] where we modify the input graph by adding/removing at most $k$ edges. Note that finding the complement of a graph is an example of a cluster editing problem. Interestingly, the complement of $P_{5}$ -free chordal bipartite graph is chordal. We now present some results on complement graphs of $P_{5}$ -free chordal bipartite graphs.
We use the following notation, definition and results to prove our results. Let $\overline{G}$ denote the complement of the graph $G$ , where $V(\overline{G})=V(G)$ , and $E(\overline{G})=\{\{u,v\}|\{u,v\}\notin E(G)\}$ . Since $V(G)=V(\overline{G})$ , the notation we follow for $G$ is applicable for $\overline{G}$ also.

Definition 1

A vertex $x$ of $G$ is called simplicial if $N(x)$ induces a complete subgraph of $G$ .

Definition 2

Let $G=(V,E)$ be an undirected graph and let $\sigma=[v_{1},v_{2},\ldots,v_{n}]$ be an ordering of the vertices. We say that $\sigma$ is a perfect vertex elimination scheme (or perfect elimination ordering) if each $v_{i}$ is a simplicial vertex of the induced subgraph $G_{\{v_{i},v_{i+1},\ldots,v_{n}\}}$ .

Theorem 9.1

(Dirac 1961, Fulkerson and Gross, 1965, Rose 1970). A graph $G$ is chordal if and only if $G$ has a PEO.

Theorem 9.2

If $G$ is a $P_{5}$ -free chordal bipartite graph, then $\overline{G}$ is a chordal graph.

Proof

To show that $\overline{G}$ is chordal, we now exhibit a Perfect Elimination Ordering (PEO) in $\overline{G}$ . Considering an ordering $\sigma$ of $V(\overline{G})$ , $\sigma=(z_{1}=y_{1},y_{2},\ldots y_{j},v_{1},v_{2},\ldots,v_{q},u_{p},u_{p-1},\ldots,u_{1},x_{i},$ $x_{i-1},\ldots,x_{1}=z_{n})$ . We now show that $\sigma$ is a PEO. On the contrary, assume that $\sigma$ is not a PEO. Let $z_{r}$ be the first vertex in $\sigma$ whose neighborhood is not a clique in the graph induced on $\{z_{r},z_{r+1},\ldots,z_{n}\}$ .

Case 1: $z_{r}\in A(\overline{G})$
We claim that $A(\overline{G})$ is a clique. Suppose not, then there exist $u,v$ such that $\{u,v\}\notin E(\overline{G})$ . This shows that in $A(G)$ , $\{u,v\}\in E(G)$ , a contradiction to the independent set property of $A(G)$ . Note that $N_{\overline{G}}(z_{r})=\{z_{r},z_{r+1},\ldots,z_{n}\}$ is a subset of $A(\overline{G})$ . Therefore, $z_{r}$ is a simplicial vertex.

Case 2: $z_{r}\in B_{1}(\overline{G})$ .
Let $s=|N(z_{r})\cap A_{2}(G)|$ . This implies that $w=p-s=|N_{\overline{G}}(z_{r})\cap A_{2}(\overline{G})|$ . Since $A_{2}(G)$ satisfies NNO, $u_{w}$ to $u_{p}$ vertices of $A_{2}(\overline{G})$ are adjacent to the vertices of the set $\{y_{r+1},y_{r+2},\ldots,y_{j}\}$ , and $A_{2}(\overline{G})\cup B_{2}(\overline{G})$ is a clique. Let $H=A_{2}(\overline{G})\cup B_{2}(\overline{G})\cup\{y_{r},y_{r+1},\ldots,y_{n}\}$ . We now claim that the graph induced on $H$ is a clique. Suppose not, we obtain a contradiction to the independent set property of $G$ similar to Case 1. Note that $N_{\overline{G}}(z_{r})=\{z_{r},z_{r+1},\ldots,z_{n}\}$ is a subset of $H$ . Therefore, $z_{r}$ is a simplicial vertex. Similar argument is true for $z_{r}\in B_{2}(\overline{G})$ .

From the above two cases, we conclude that $\sigma$ is a PEO. Hence by Theorem 9.1, $\overline{G}$ is a chordal graph.
Suppose $A_{2}(G)=\emptyset$ or $B_{2}(G)=\emptyset$ , then $A_{1}$ and $B_{1}$ are clique in $\overline{G}$ . Therefore, $\overline{G}$ is chordal. ∎

Lemma 15

For a graph $G$ , if the vertex connectivity is at least the independence number then $G$ is Hamiltonian [41].

Theorem 9.3

Let $G(A_{1},B_{1},A_{2},B_{2})$ be a $P_{5}$ -free chordal bipartite graph such that $A_{2}$ and $B_{2}$ are non empty. If $G$ is Hamiltonian, then $\overline{G}$ is Hamiltonian.

Proof

Since $A_{1}$ $(B_{1})$ is an independent set in $G$ , it is clique in $\overline{G}$ . Similarly, $A_{2}\cup B_{2}$ is a clique in $\overline{G}$ . We observe that any independent set in $\overline{G}$ contains at most two vertices, in particular one vertex from $A(\overline{G})$ and other from $B(\overline{G})$ . Therefore, the independence number is at most two. We observer that $\overline{G}$ is connected and now we show that there does not exist a cut vertex in $\overline{G}$ . On the contrary, assume that there exists a cut vertex $z$ . W.l.o.g. assume that $x$ and $y$ be the neighbors of $z$ in $\overline{G}$ .

Case 1: $x,y\in A(\overline{G})$ . Since the graph induced on $A(\overline{G})$ is a clique, there exists a path $P(x,y)$ in $\overline{G}-z$ . This shows that $\overline{G}-z$ is connected. Similar argument is true for $x,y\in B(\overline{G})$ , and $x,y\in A_{2}\cup B_{2}$ in $\overline{G}$ .

Case 2: $x\in A(\overline{G})$ , and $y\in B(\overline{G})$ . Since $A_{1}$ $(B_{1})$ , and the set $A_{2}\cup B_{2}$ induces a clique, we obtain a path $P(x,y)=(x,u_{1},y_{j},y)$ , where $u_{1}\in A_{2}$ , and $y_{j}\in B_{2}$ in $G-z$ . This shows that $z$ is not a cut vertex. Therefore, the vertex connectivity of $\overline{G}$ is at least two. From Lemma 15, we conclude that $\overline{G}$ is Hamiltonian.

Time Complexity Analysis :
The Nested Neighbourhood Ordering (NNO) of $P_{5}$ -free chordal bipartite graphs can be obtained in linear time by using perfect edge elimination ordering proposed by Fulkerson and Gross. Further, the Hamiltonian cycle (path) can be obtained in linear time. Since bipancyclic, and homogeneously traceable involves order $n$ call to Hamiltonian cycle (path) algorithm, these two incurs $\mathit{O(n^{2})}$ time. All other algorithmic results run in linear time.

Conclusions and Further Research
In this paper, we have presented structural results on $P_{5}$ -free chordal bipartite graphs. Subsequently, using these results, we have presented polynomial-time algorithms for the Hamiltonian cycle (path), also its variants and generalizations. We also presented polynomial-time algorithms for combinatorial problems such as treewidth (pathwidth), and minimum fill-in. We have also shown that Chvátal’s necessary condition is sufficient for this graph class. Further, we have presented some results on complement graphs of $P_{5}$ -free chordal bipartite graphs. These results exploit the nested neighborhood ordering of $P_{5}$ -free chordal bipartite graphs which is an important contribution of this paper. A natural direction for further research is to study $P_{6}$ -free chordal bipartite graphs and $P_{7}$ -free chordal bipartite graphs as the complexity of most of these problems are open in these graph classes.

References

[1] Gabriel Andrew Dirac.: On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25, 71–76 (1961)
[2] Delbert Fulkerson and Oliver Gross.: Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15(3), 835–855 (1965)
[3] Martin Charles Golumbic.: Algorithmic Graph Theory and Perfect Graphs. Elsevier, (1980)
[4] Yi-Ming Wang, Shi-Hao Chen, and Mango C-T Chao.: An Efficient Hamiltonian-cycle power-switch routing for MTCMOS designs. In Design Automation Conference (ASP-DAC), 17th Asia and SouthPacific, 59–65 (2012)
[5] Malakis, A.: Hamiltonian walks and polymer configurations. Physica A: Statistical Mechanics and its Applications, 84(2), 256–284 (1976)
[6] Dorninger.D: Hamiltonian circuits determining the order of chromosomes. Discrete Applied Mathematics, 50(2), 159–168 (1994)
[7] Deogun, J.S and Steiner, G.: Polynomial algorithms for Hamiltonian cycle in cocomparability graphs. SIAM Journal on Computing, 23(3), 520–552 (1994)
[8] Alan A Bertossi and Maurizio A Bonuccelli.: Hamiltonian circuits in interval graph generalizations. Information Processing Letters, 23(4), 195–200 (1986)
[9] Krishnamoorthy, M. S.: An NP-hard problem in bipartite graphs. SIGACT News, 7(1), 26–26 (1975)
[10] M $\ddot{\rm u}$ ller.: Hamiltonian circuits in chordal bipartite graphs. Discrete Mathematics, 156(1-3), 291–298 (1996)
[11] M $\ddot{\rm u}$ ller and Andreas Brandst $\ddot{\rm a}$ dt.: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theoretical Computer Science, 53(2-3), 257–265 (1987)
[12] Brandstädt, Andreas and Hammer, Peter L and Lozin, Vadim V.: Bisplit graphs. Discrete Mathematics, 299, (1-3), 11–32 (2005)
[13] Abueida, Atif and Sritharan, R.: A note on the recognition of bisplit graphs. Discrete mathematics, 306(17), 2108–2110 (2006)
[14] Daniel Lokshantov, Martin Vatshelle, and Yngve Villanger.: Independent set in $P_{5}$ -free graphs in polynomial time. In Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, PP. 570–581 (2014)
[15] Hoàng, Chính T and Kamiński, Marcin and Lozin, Vadim and Sawada, Joe and Shu, Xiao. Deciding $k-$ colorability of $P_{5}$ -free graphs in polynomial-time. Algorithmica, 8, 85–89 (2001)
[16] Abrishami, Tara and Chudnovsky, Maria and Pilipczuk, Marcin and Rzążewski, Paweł and Seymour, Paul.: Induced subgraphs of bounded treewidth and the container method. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), PP. 1948–1964, (2021)
[17] Ioannidou, Kyriaki and Mertzios, George B and Nikolopoulos, Stavros D.: The longest path problem is polynomial on interval graphs. International Symposium on Mathematical Foundations of Computer Science, Springer, pp. 403–414 (2009)
[18] Ghosh, Esha and Narayanaswamy, NS and Rangan, C Pandu.: A polynomial-time algorithm for longest paths in biconvex graphs. International Workshop on Algorithms and Computation, Springer, pp. 191–201 (2011)
[19] Kona, Harshita and Sadagopan, N.: On some combinatorial problems in cographs. International Journal of Advances in Engineering Sciences and Applied Mathematics, 11(1), 25–39 (2019)
[20] Bondy, Adrian J.: Pancyclic graphs I. Journal of Combinatorial Theory, Series B, 11(1), 80–84 (1971)
[21] Zamfirescu, Carol T.: (2)-pancyclic graphs. Discrete Applied Mathematics, 161(7-8), 1128–1136 (2013)
[22] Amar, D.: A condition for a Hamiltonian bipartite graph to be bipancyclic. Discrete mathematics, 102(3), 221–227 (1992)
[23] Asratian, Armen S.: A criterion for some Hamiltonian graphs to be Hamilton-connected. Faculty of Applied Mathematics, University of Twente, (1993)
[24] Kewen, Zhao and Lai, Hong-Jian and Zhou, Ju.: Hamiltonian-connected graphs. Computers & Mathematics with Applications, 55(12), 2707–2714 (2008)
[25] Skupień, Zdzislaw.: Homogeneously traceable and Hamiltonian connected graphs. Demonstratio Mathematica, 17(4), 1051–1068 (1984)
[26] Chartrand, Gary and Gould, Ronald J and Kapoor, SF.: On homogeneously traceable nonhamiltonian graphs. Annals of the New York Academy of Sciences, 319(1), 130–135 (1979)
[27] Faudree, Ralph J and Gould, Ronald J and Kostochka, Alexandr V and Lesniak, Linda and Schiermeyer, Ingo and Saito, Akira.: Degree conditions for $k$ -ordered Hamiltonian graphs. Journal of Graph Theory, 42(3), 199–210 (2003)
[28] Hammer, Peled, Sun.: Difference graphs. Discrete Applied Mathematics, 28(1), 35–44 (1990)
[29] Maffray, Morel.: On 3-colorable $P_{5}$ -free graphs. SIAM J. Discrete Mathematics, 26(4), 1682–1708 (2012)
[30] Fouquet, Jean-Luc.: A decomposition for a class of $(P_{5},\overline{P_{5}})$ -free graphs. Discrete Mathematics, 121, 75–83 (1993)
[31] Douglas Brent West. Introduction to Graph Theory. 2nd Edition. Prentice hall Upper Saddle River, (2003)
[32] Nguyen, Thinh D., Various variants of Hamiltonian problems.: Moscow State University, OSF Preprints (2018)
[33] Kona Harshita and Sadagopan. N.: On some combinatorial problems in cographs. International Journal of Advances in Engineering Sciences and Applied Mathematics, 11(1), 25–39 (2019)
[34] Robertson, N., Seymour, P. D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of algorithms, 7(3), 309–322 (1986)
[35] Hans L. Bodlaender.: A tourist guide through treewidth. Acta Cybernetica, 92, 1–21 (1992)
[36] Ton Kloks, Dieter Kratsch.: Treewidth of chordal bipartite graphs. Journal of Algorithms, 19(2), 266–281 (1995)
[37] Yannakakis, M.: Computing the minimum fill-in is NP-complete, SIAM Journal on Algebraic and Discrete Methods, 2, 77–79 (1981)
[38] Ton Kloks, Antonius Jacobus Johannes.: Minimum fill-in for chordal bipartite graphs, Universiteit Utrecht. UU-CS, Utrecht University, 93 (1993)
[39] Chang, Maw-Shang.: Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs. International Symposium on Algorithms and Computation, Springer, PP. 146–155, (1996)
[40] Fomin, Fedor V and Golovach, Petr A and Strømme, Torstein JF and Thilikos, Dimitrios M.: Subgraph Complementation. Algorithmica, 82(7), 1859–1880 (2020)
[41] Chvátal, Vasek and Erdös, Paul. A note on Hamiltonian circuits. Journal Discrete Mathematics, 2, 111–113 (1972)

Hamiltonicity: Variants and Generalization in P5P_{5}-free Chordal Bipartite graphs††thanks: This work is partially supported by DAE-NBHM project, NBHM/ 02011/37/2017/RD II/16646

Abstract

Keywords:

1 Introduction

1.1 Preliminaries

2 Structural Results

Lemma 1

Proof

Lemma 2

Proof

Lemma 3

Proof

Theorem 2.1

Proof

Lemma 4

Proof

3 Hamiltonicity in P5P_{5}-free Chordal Bipartite graphs

Theorem 3.1

Proof

Theorem 3.2

Proof

Theorem 3.3

Proof

4 Chvátal’s Necessary condition is Sufficient on P5P_{5}-free chordal bipartite graphs

Theorem 4.1

Proof

Theorem 4.2

Proof

5 Hamiltonicity variants in P5P_{5}-free chordal bipartite graphs

5.1 Bipancyclic P5P_{5}-free chordal bipartite graphs

Theorem 5.1

Proof

5.2 Homogeneously traceable P5P_{5}-free chordal bipartite graphs

Theorem 5.2

Proof

Corollary 1

Proof

5.3 EXACTLY 2 SIMPLE PATH COVER in P5P_{5}-free chordal bipartite graphs

Theorem 5.3

Proof

5.4 Hamiltonian connected P5P_{5}-free chordal bipartite graphs

Theorem 5.4

Proof

5.5 Path-hypohamitonian P5P_{5}-free chordal bipartite graphs

Theorem 5.5

Proof

6 Generalizations of Hamiltonian path (cycle) in P5P_{5}-free chordal bipartite graphs

6.1 Longest paths in P5P_{5}-free chordal bipartite graphs

Proof

Theorem 6.1

Proof

Corollary 2

Proof

6.2 Longest cycles in P5P_{5}-free chordal bipartite graphs

Proof

6.3 Steiner paths in P5P_{5}-free chordal bipartite graphs

Lemma 5

Proof

Lemma 6

Proof

Lemma 7

Proof

6.4 Steiner cycles in P5P_{5}-free chordal bipartite graphs

Lemma 8

Proof

Lemma 9

Proof

Lemma 10

Proof

7 Treewidth and Pathwidth of P5P_{5}-free chordal bipartite graphs

Lemma 11

Proof

Theorem 7.1

Proof

Lemma 12

Proof

Corollary 3

Proof

8 Minimum Fill-in in P5P_{5}-free chordal bipartite graphs

Lemma 13

Hamiltonicity: Variants and Generalization in $P_{5}$ -free Chordal Bipartite graphs^†^†thanks: This work is partially supported by DAE-NBHM project, NBHM/ 02011/37/2017/RD II/16646

3 Hamiltonicity in $P_{5}$ -free Chordal Bipartite graphs

4 Chvátal’s Necessary condition is Sufficient on $P_{5}$ -free chordal bipartite graphs

5 Hamiltonicity variants in $P_{5}$ -free chordal bipartite graphs

5.1 Bipancyclic $P_{5}$ -free chordal bipartite graphs

5.2 Homogeneously traceable $P_{5}$ -free chordal bipartite graphs

5.3 EXACTLY 2 SIMPLE PATH COVER in $P_{5}$ -free chordal bipartite graphs

5.4 Hamiltonian connected $P_{5}$ -free chordal bipartite graphs

5.5 Path-hypohamitonian $P_{5}$ -free chordal bipartite graphs

6 Generalizations of Hamiltonian path (cycle) in $P_{5}$ -free chordal bipartite graphs

6.1 Longest paths in $P_{5}$ -free chordal bipartite graphs

6.2 Longest cycles in $P_{5}$ -free chordal bipartite graphs

6.3 Steiner paths in $P_{5}$ -free chordal bipartite graphs

6.4 Steiner cycles in $P_{5}$ -free chordal bipartite graphs

7 Treewidth and Pathwidth of $P_{5}$ -free chordal bipartite graphs

8 Minimum Fill-in in $P_{5}$ -free chordal bipartite graphs

9 Results on Complement graphs of $P_{5}$ -free chordal bipartite graphs