Spectral conditions for the Bipancyclic Bipartite graphs

1. Introduction

We consider only finite undirected graphs without loops or multiple edges. Notation and terminology not defined here follow that in [1]. Let \(G = (V(G), \, E(G))\) be a graph. The graph \(G\) is said to be Hamiltonian if it contains a cycle of length \(|V(G)|\). The graph \(G\) is said to be pancyclic if it contains cycles of every length from \(3\) to \(|V(G)|\). Let \(G = (V_1(G), V_2(G); \, E(G))\) be a bipartite graph with two vertex partition subsets \(V_1(G)\) and \(V_2(G)\). The bipartite graph \(G\) is said to be semiregular bipartite if all the vertices in \(V_1(G)\) have the same degree and all the vertices in \(V_2(G)\) have the same degree. The bipartite graph \(G\) is said to be balanced if \(|V_1| = |V_2|\). Clearly, if a bipartite graph is Hamiltonian, then it must be balanced. The bipartite graph \(G\) is said to be bipancyclic if it contains cycles of every even length from \(4\) to \(|V(G)|\). The balanced bipartite graph \(G_1 = (A, B; E)\) of order \(2n\) with \(n \geq 4\) is defined as follows: \(A = \{a_1, a_2, ... , a_n\}\), \(B = \{b_1, b_2, ... , b_n\}\), and \(E = \{a_ib_j : 1 \leq i \leq 2, (n - 1) \leq j \leq n \} \cup \{a_ib_j : 3 \leq i \leq n, 1 \leq j \leq n \}\). Notice that \(G_1\) is not Hamiltonian.

The eigenvalues of a graph \(G\), denoted \(\lambda_1(G) \geq \lambda_2(G) \geq \cdots \geq \lambda_n(G)\), are defined as the eigenvalues of its adjacency matrix \(A(G)\). Let \(D(G)\) be a diagonal matrix such that its diagonal entries are the degrees of vertices in a graph \(G\). The Laplacian matrix of a graph \(G\), denoted \(L(G)\), is defined as \(D(G) - A(G)\), where \(A(G)\) is the adjacency matrix of \(G\). The eigenvalues \(\mu_1(G) \geq \mu_2(G) \geq \cdots \geq \mu_{n - 1}(G) \geq \mu_{n}(G) = 0\) of \(L(G)\) are called the Laplacian eigenvalues of \(G\). The second smallest Laplacian eigenvalue \(\mu_{n - 1}(G)\) is also called the algebraic connectivity of the graph \(G\) (see [2]). The signless Laplacian matrix of a graph \(G\), denoted \(Q(G)\), is defined as \(D(G) + A(G)\), where \(A(G)\) is the adjacency matrix of \(G\). The eigenvalues \(q_1(G) \geq q_2(G) \geq \cdots \geq q_n(G)\) of \(Q(G)\) are called the signless Laplacian eigenvalues of \(G\).

Yu et al., in [3] obtained some spectral conditions for the pancyclic graphs. Motivated by the results in [3], we present spectral conditions for the bipancyclic bipartite graphs. The main results are as follows:

Theorem 1. Let \(G = (X, Y; E)\) be a connected balanced bipartite graph of order \(2n\) with \(n \geq 4\), \(e\) edges, and \(\delta \geq 2\). If \(\lambda_1 \geq \sqrt{n^2 - 2n + 4}\), then \(G\) is bipancyclic.

Theorem 2. Let \(G = (X, Y; E)\) be a connected balanced bipartite graph of order \(2n\) with \(n \geq 4\), \(e\) edges, and \(\delta \geq 2\). If \[\mu_{n - 1} \geq \frac{2(n^2 - 2n + 4)}{n},\] then \(G\) is bipancyclic.

Theorem 3. Let \(G = (X, Y; E)\) be a connected balanced bipartite graph of order \(2n\) with \(n \geq 4\), \(e\) edges, and \(\delta \geq 2\). If \[q_1 \geq \frac{2(n^2 - n + 2)}{n},\] then \(G\) is bipancyclic.

2. Lemmas

In order to prove the theorems above, we need the following results as our lemmas:

Lemma 1 is the main result in [4].

Lemma 1. Let \(G = (X, Y; E)\) be a balanced bipartite graph of order \(2n\) with \(n \geq 4\). Suppose that \(X = \{x_1, x_2, ... , x_n\}\), \(Y = \{y_1, y_2, ... , y_n\}\), \(d(x_1) \leq d(x_2) \leq \cdots \leq d(x_n)\), and \(d(y_1) \leq d(y_2) \leq \cdots \leq d(y_n)\). If \[d(x_k) \leq k < n \Longrightarrow d(y_{n - k}) \geq n - k + 1,\] then \(G\) is bipancyclic.

Lemma 2 below follows from Proposition 2.1 in [5]:

Lemma 2. Let \(G\) be a connected bipartite graph of order \(n \geq 2\) and \(e \geq 1\) edges. Then \(\lambda_1 \leq \sqrt{e}\). If \(\lambda_1 = \sqrt{e}\), then \(G\) is a complete bipartite graph \(K_{s, \, t}\), where \(e = s \, t\).

Lemma 3 below is Lemma 4.1 in [2]:

Lemma 3. Let \(G\) be a noncomplete graph. Then \(\mu_{n - 1} \leq \kappa\), where \(\kappa\) is the vertex connectivity of \(G\).

Lemma 4 below is Theorem 2.9 in [6]:

Lemma 4. Let G be a balanced bipartite graph of order \(2n\) and \(e\) edges. Then \(q(G) \leq \frac{e}{n} + n\).

Lemma 5 below is Lemma 2.3 in [7]:

Lemma 5. Let \(G\) be a connected graph. Then \[q_1 \leq \max\{ d(u) + \frac{\sum_{v \in N(u)} d(v)} {d(u)} : u \in V \},\] with equality holding if and only if \(G\) is either semiregular bipartite or regular.

Lemma 6. Let \(G = (X, Y; E)\) be a balanced bipartite graph of order \(2n\) with \(n \geq 4\), \(e\) edges, and \(\delta \geq 2\). If \(e \geq n^2 - 2n + 4\), then \(G\) is bipancyclic or \(G = G_1\).

Proof. Without loss of generality, we assume that \(X = \{x_1, x_2, ... , x_n\}\), \(Y = \{y_1, y_2, ... , y_n\}\), \(d(x_1) \leq d(x_2) \leq \cdots \leq d(x_n)\), and \(d(y_1) \leq d(y_2) \leq \cdots \leq d(y_n)\). Suppose \(G\) is not bipancyclic. Then Lemma 1 implies that there exists an integer \(k\) such that \(1 \leq k < n\), \(d(x_k) \leq k\), and \(d(y_{n - k}) \leq n - k\). Thus \begin{align*} 2n^2 - 4n + 8 &\leq 2 e\\& = \sum_{i = 1}^n d(x_i) + \sum_{i = 1}^n d(y_i)\\ &\leq k^2 + (n - k) n + (n - k)^2 + k n\\ &= 2n^2 - 4n + 8 - (k - 2)(2n - 2k - 4). \end{align*} Since \(\delta \geq 2\), we have that \(k \neq 1\). Therefore we have the following possible cases.

Case \(1\). \(k = 2\).

In this case, all the inequalities in the above arguments now become equalities. Thus \(d(x_1) = d(x_2) = 2\), \(d(x_3) = \cdots = d(x_n) = n\), \(d(y_1) = \cdots = d(y_{n - 2}) = n - 2\), and \(d(y_{n - 1}) = d(y_{n - 2}) = n\). Hence \(G = G_1\).

Case \(2\). \((2n - 2k - 4) = 0\).

In this case, we have \(n = k + 2\) and all the inequalities in the above arguments now become equalities. Thus \(d(x_1) = \cdots = d(x_{n - 2}) = n - 2\), \(d(x_{n - 1}) = d(x_n) = n\), \(d(y_1) = d(y_{2}) = n - 2\), and \(d(y_{3}) = \cdots = d(y_{n - 2}) = n\). Hence \(G = G_1\).

Case \(3\). \(k \geq 3\) and \(2n - 2k - 4 < 0\).

In this case, we have that \(n < k + 2\), namely, \(n \leq k + 1\). Since \(k < n\), we have \(k = n - 1\). This implies that \(d(y_1) \leq 1\), contradicting to the assumption of \(\delta \geq 2\).

This completes the proof of Lemma 6.

3. Proofs

Proof of Theorem 1. Let \(G\) be a graph satisfying the conditions in Theorem 1. Then we, from Lemma 2, we have \[\sqrt{n^2 - 2n + 4} \leq \lambda_1 \leq \sqrt{e}.\] Thus \(e \geq n^2 - 2n + 4\). Therefore by Lemma 6 we have that \(G\) is bipancyclic or \(G = G_1\).

If \(G = G_1\), then \(e = n^2 - 2n + 4\). Hence \[\sqrt{n^2 - 2n + 4} \leq \lambda_1 \leq \sqrt{e} = \sqrt{n^2 - 2n + 4}.\] So \(\lambda_1 = \sqrt{e}\). Lemma 2 implies that \(G_1\) is a complete bipartite graph, a contradiction.

This completes the proof of Theorem 1.

Proof of Theorem 2. Let \(G\) be a graph satisfying the conditions in Theorem 2. Then we, from Lemma 3, we have \[\frac{2(n^2 - 2n + 4)}{n} \leq \mu_{n - 1} \leq \kappa \leq \delta \leq \frac{2e}{n}.\] Thus \(e \geq n^2 - 2n + 4\). Therefore by Lemma 6 we have that \(G\) is bipancyclic or \(G = G_1\).

If \(G = G_1\), then \(e = n^2 - 2n + 4\). Hence

\[\frac{2(n^2 - 2n + 4)}{n} \leq \mu_{n - 1} \leq \kappa \leq \delta \leq \frac{2e}{n} = \frac{2(n^2 - 2n + 4)}{n}.\] This implies that \(G_1\) is a regular graph, a contradiction.

This completes the proof of Theorem 2.

Proof of Theorem 3. Let \(G\) be a graph satisfying the conditions in Theorem 3. Then we, from Lemma 4, we have \[\frac{2(n^2 - n + 2)}{n} \leq q_1 \leq \frac{e}{n} + n.\] Thus \(e \geq n^2 - 2n + 4\). Therefore by Lemma 6 we have that \(G\) is bipancyclic or \(G = G_1\).

If \(G = G_1\), then \(e = n^2 - 2n + 4\). Therefore

\[\frac{2(n^2 - n + 2)}{n} \leq q_1 \leq \frac{e}{n} + n = \frac{ n^2 - 2n + 4}{n} + n = \frac{2(n^2 - n + 2)}{n}.\] Hence \[q_1 = \frac{2(n^2 - n + 2)}{n}.\] It can be verified that \[\max\{ d(u) + \frac{\sum_{v \in N(u)} d(v)} {d(u)} : u \in V \} = \frac{2(n^2 - n + 2)}{n} = q_1.\] Thus Lemma 5 implies that \(G_1\) is semiregular or regular, a contradiction.

This completes the proof of Theorem 3.

Conflicts of Interest

The author declares no conflict of interest.