Chromatic spectrum of some classes of 2-regular bipartite colored graphs

Abstract

Chromatic spectrum of a colored graph G is a multiset of eigenvalues of colored adjacency matrix of G. The nullity of a disconnected graph is equal to sum of nullities of its components but we show that this result does not hold for colored graphs. In this paper, we investigate the chromatic spectrum of three different classes of 2-regular bipartite colored graphs. In these classes of graphs, it is proved that the nullity of G is not sum of nullities of components of G. We also highlight some important properties and conjectures to extend this problem to general graphs.

Keywords

Spectrum of graph nullity of graph graph coloring

1 Introduction

Graph spectra is study of eigenvalues of different types of matrices associated with graphs. These types include adjacency matrix, L-matrix and some other matrices. Graph isomorphism testing is related to eigenvalues of graph. Graph spectra is playing a vital role in analyzing graph isomorphism problem which is in low hierarchy of class NP. Now graph isomorphism problem can be solved in polynomial time for some special classes of graphs. Some recent studies can be found in [5]-[2]. Spectral graph theory also includes the study of nullity and energy of graphs. Nullity and energy of graph has diverse applications in fields like dimer problem, road networks and most importantly interaction between components and smart cities and design optimization of outdoor lighting, see for example [14] and [9]. The study of the nullity of graphs is one of the most celebrated problems in spectral graph theory. In chemistry, molecular graphs of conjugated hydrocarbons can be drawn by considering carbon atoms as vertices and their chemical bonds by edges. The nullity of such graphs predicts reactivity of the respective molecules. If for a molecular graph G, η (G) >0, then the respective compound is highly reactive and if η (G) =0, then the compound is stable. Let G = (V, E) be a simple graph with vertex set V and edge set E and let |V| = n. A graph is called simple if it does not contain any loops or multiple edges. The degree d (v) of a vertex v in G is the number of edges incident on v. The graph G is called r-regular if d (v) = r (r ≥ 0) for all v ∈ V. The adjacency matrix A (G) = [a_i,j] _n×n, 1 ≤ i, j ≤ n, of graph G is a (0, 1)-matrix with a_i,j = 1 whenever v_iv_j ∈ E and a_i,j = 0 otherwise. The characteristic polynomial P (G, λ) of G is the polynomial defined by det (A - λI_n), where I_n is the identity matrix of order n and $λ \in ℝ$ . The roots of P (G, λ) are called the eigenvalues of graph G. Since A (G) is real and symmetric so all eigenvalues of A, and thus G, are real. The spectrum Spec (G) of G is the multiset of its eigenvalues. The nullity η (G) of G is the number of zeros in Spec (G). Let C_n denote a cycle of length n. Then C_n is an odd cycle if n is odd. A graph G is bipartite if it does not contain any odd cycle. The components of a graph G are its maximal connected subgraphs. Two graphs are said to be isomorphic if one graph can be obtained by a redrawing of the other graph. The energy of a graph G is defined as the sum of the absolute of eigenvalues of the adjacency matrix of G. The energy of a graph is denoted by $\hat{E} (G)$ and given as follows: $\hat{E} (G) = \sum_{i = 1}^{n} | λ_{i} | .$

In 1957, Collatz and Sinogowitz [4] for the first time, investigated the problem of characterizing graphs on the basis of their nullity. Many results regarding spectrum and nullity of different graph classes (e.g. paths, cycles, bipartite graphs, trees, unicyclic and bicyclic graphs etc.) have been derived so far in papers like [3 , 13]. Fan and Qian [6] characterized the bipartite graphs with nullity n - 4 and regular bipartite graphs with nullity n - 6. Research in this field has also extended to spectrum of colored graphs.

Consider a mapping c : V → {1, 2, …, n}, where the co-domain of c is the set of colors. A coloring of graph G is the existence of a coloring function c which colors vertices of G in such a way that no two adjacent vertices receive the same color. A graph with such a coloring function is called a colored graph. The minimum colors required to color G is called chromatic number of G and is denoted by χ (G). For a graph G, let c (v) denotes the color of v ∈ V. The matrix of a colored graph having minimum number of colors is denoted by A_χ (G) = [a_i,j] _n×n, 1 ≤ i, j ≤ n, where $a_{i, j} = {\begin{matrix} 1 & if v_{i} v_{j} \in E, \\ - 1 & if v_{i} v_{j} \notin E and c (v_{i}) =c (v_{j}), \\ 0 & otherwise . \end{matrix}$ (1) The characteristic polynomial P_χ (G) of the matrix A_χ (G) is determined by det (A_χ - λ_χI_n), where λ_χ’s denote the eigenvalues of A_χ (G). The eigenvalues of A_χ (G) are called chromatic eigenvalues of G. In a similar fashion, the chromatic spectrum of G is the multiset of n chromatic eigenvalues of G and is denoted by Spec_χ (G). It is obvious form (1) Achi that A_χ (G) is real and symmetric, so all chromatic eigenvalues of G are real. The chromatic nullity η_χ (G) is the multiplicity of 0 in Spec_χ (G). If a graph G has chromatic eigenvalues λ_χ1, λ_χ2, …, λ_χr (where r ≤ n), with respective multiplicities m₁, m₂, …, m_r, then we will use the following notation for its chromatic spectrum. ${Spec}_{χ} (G) = (\begin{matrix} λ_{χ 1} & λ_{χ 2} & \dots & λ_{χ r} \\ m_{1} & m_{2} & \dots & m_{r} \end{matrix}),$ where $\sum_{i = 1}^{r} m_{i} = n$ . It should be noted that the colored energy of a graph is denoted by ${\hat{E}}_{χ} (G)$ and given as follows: ${\hat{E}}_{χ} (G) = \sum_{i = 1}^{n} | λ_{χ i} | .$ In 2013, Adiga and Shrikanth [1] presented results about chromatic spectrum of some graphs and their complements. They established upper and lower bound for energy of some colored graphs. Recently, Shigehalli and Kenchappa [12] have estimated the number of colored graphs of order 6 whose energy does not exceed 10. The chromatic spectrum of many graph classes (e.g., bipartite, unicyclic, bicyclic graphs, etc.) is still unknown. In this paper, we consider 2-regular bipartite colored graphs and investigate their chromatic spectrum.

It is important to note that we use the following notations in the column operations while computing the determinants:

c_k is the k^th column.

is the new k^th column obtained by a column operation.

Furthermore, we reserve notations O_n and J_n to denote n × n matrices with all entires 0 and 1, respectively.

2 Chromatic spectrum of 2-regular bipartite colored graphs

In this section, we study the chromatic spectrum of 2-regular bipartite colored graphs. Isomorphism and disjoint union are important definitions that we use in this work. We use G ≃ H to denote that G and H are isomorphic. 1 A disjoint union of k graphs G₁, G₂, ⋯ , G_k is a graph G ≃ G₁ ∪ G₂ ∪ ⋯ ∪ G_k with vertex set $V (G) = \underset{i}{\cup^{k}} V (G_{i})$ and $E (G) = \underset{i}{\cup^{k}} E (G_{i})$ , when G_i ≃ H for 1 ≤ i ≤ k, then $G = \underset{i}{\cup^{k}} (G_{i}) = kH$ . 2-regular bipartite colored graphs in this paper are isomorphic to union of cycles of length 4 or/and 6.

It is well-known that the chromatic number of a bipartite graph(with non-zero edges) is 2. It is important note that throughout the paper 2-regular bipartite colored graph G has n vertices and n = 2s where s is the number of vertices in each partite set of G. We computed the chromatic eigenvalues for three classes of 2-regular bipartite colored graphs.

Theorem 1. Let G be a 2-regular bipartite colored graph with n vertices such that $G ≃ \frac{s}{2} C_{4}$ . Then the chromatic spectrum of G is given as follows ${Spec}_{χ} (G) = (\begin{matrix} 3 - s & - s - 1 & 1 & - 1 & 3 \\ 1 & 1 & s & \frac{s - 2}{2} & \frac{s - 2}{2} \end{matrix}) .$

Proof. Consider a 2-regular bipartite colored graph G of order n, with $G ≃ \frac{s}{2} C_{4}$ , here n = 2s, where s is the number of vertices in each partite set of G. Clearly, G contains $\frac{s}{2}$ number of cycles C₄. Using Equation (1) Achi, we obtain matrix $A_{χ}^{1} (G)$ for G as follows. $A_{χ}^{1} (G) = {[\begin{matrix} - B & C \\ C & - B \end{matrix}]}_{2 s \times 2 s},$ (2) where $B = {[\begin{matrix} 0 & 1 & \dots & 1 & 1 \\ 1 & 0 & \dots & 1 & 1 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 1 & 1 & \dots & 0 & 1 \\ 1 & 1 & \dots & 1 & 0 \end{matrix}]}_{s \times s} and C = {[\begin{matrix} 1 & 1 & 0 & 0 & \dots & 0 & 0 \\ 1 & 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & 1 & \dots & 0 & 0 \\ 0 & 0 & 1 & 1 & \dots & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & \dots & 1 & 1 \\ 0 & 0 & 0 & 0 & \dots & 1 & 1 \end{matrix}]}_{s \times s} .$ (3) To find the characteristic polynomial of $A_{χ}^{1} (G)$ , consider $\det (A_{χ}^{1} (G) - λ_{χ} I_{2 s}) = {| \begin{matrix} - B - λ_{χ} I_{s} & C \\ C & - B - λ_{χ} I_{s} \end{matrix} |}_{2 s \times 2 s} .$ As C (- B - λ_χI_s) = (- B - λ_χI_s) C, by using the property of block matrix we obtain $\det (A_{χ}^{1} (G) - λ_{χ} I_{2 s}) = \det (A^{1}),$ (4) where $A^{1} = (- B - λ_{χ} I_{s})^{2} - C^{2}$ . Using B and C from Equation (3), we have $A^{1} = {[\begin{matrix} λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 4 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 2 \\ 2 λ_{χ} + s - 4 & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 2 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 4 \\ 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 4 & λ_{χ}^{2} + s - 3 \end{matrix}]}_{s \times s} .$ Replacing c₁ by $c_{1}^{'} = c_{1} + c_{2} + \dots + c_{s}$ , it gives $[λ_{χ}^{2} + 2 (s - 1) λ_{χ} + (s + 1) (s - 3)]$ value in first column which can be taken common. After simplifying it, we get characteristic polynomial as $[λ_{χ}^{2} + 2 (s - 1) λ_{χ} + (s + 1) (s - 3)] \det (P_{s}) = 0,$ (5) where $\det (P_{s}) = {| \begin{matrix} 1 & 2 λ_{χ} + s - 4 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 2 \\ 1 & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 2 \\ ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 1 & 2 λ_{χ} + s - 2 & \dots & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 4 \\ 1 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 4 & λ_{χ}^{2} + s - 3 \end{matrix} |}_{s \times s} .$ (6) Replacing c₂ by $c_{2}^{'} = c_{2} - (2 λ_{χ} + s - 4) c_{1}$ and c_m by $c_{m}^{'} = c_{m} - (2 λ_{χ} + s - 2) c_{1}$ in equation (6) for m = 3, 4, ⋯ , s, we get $\det (P_{s}) = {| \begin{matrix} 1 & 0 & 0 & 0 & 0 & \dots & 0 \\ 1 & λ_{χ}^{2} - 2 λ_{χ} + 1 & 0 & 0 & 0 & \dots & 0 \\ 1 & 2 & λ_{χ}^{2} - 2 λ_{χ} - 1 & - 2 & 0 & \dots & 0 \\ 1 & 2 & - 2 & λ_{χ}^{2} - 2 λ_{χ} - 1 & 0 & \dots & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 1 & 2 & 0 & 0 & \dots & λ_{χ}^{2} - 2 λ_{χ} - 1 & - 2 \\ 1 & 2 & 0 & 0 & \dots & - 2 & λ_{χ}^{2} - 2 λ_{χ} - 1 \end{matrix} |}_{s \times s} .$ Simplifying above equation, we obtain $\det (P_{s}) = (λ_{χ}^{2} - 2 λ_{χ} + 1) \det (P_{s - 2}) .$ (7)det (P_s-2) can be defined in the following way: $\det (P_{s - 2}) = {| \begin{matrix} M_{2} & O_{2} & \dots & O_{2} \\ O_{2} & M_{2} & \dots & O_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ O_{2} & O_{2} & \dots & M_{2} \end{matrix} |}_{(s - 2) \times (s - 2)},$ where $M_{2} = [\begin{matrix} λ_{χ}^{2} - 2 λ_{χ} - 1 & - 2 \\ - 2 & λ_{χ}^{2} - 2 λ_{χ} - 1 \end{matrix}] .$ The determinant of the above matrix is given as follows: $\begin{matrix} | M_{2} | = (λ_{χ}^{2} - 2 λ_{χ} - 1)^{2} - 4 \\ = (λ_{χ}^{2} - 2 λ_{χ} + 1) (λ_{χ}^{2} - 2 λ_{χ} - 3) . \end{matrix}$ (8) Using the properties of block matrices, we get $\det (P_{s - 2}) = (λ_{χ}^{2} - 2 λ_{χ} + 1)^{\frac{s - 2}{2}} (λ_{χ}^{2} - 2 λ_{χ} - 3)^{\frac{s - 2}{2}} .$ (9) Thus substituting Equation (9) into Equation (7), we obtain $\begin{matrix} \det (P_{s}) & = & (λ_{χ}^{2} - 2 λ_{χ} + 1) (λ_{χ}^{2} - 2 λ_{χ} + 1)^{\frac{s - 2}{2}} \times \\ (λ_{χ}^{2} - 2 λ_{χ} - 3)^{\frac{s - 2}{2}}, \\ \det (P_{s}) & = & (λ_{χ}^{2} - 2 λ_{χ} + 1)^{\frac{s}{2}} (λ_{χ}^{2} - 2 λ_{χ} - 3)^{\frac{s - 2}{2}} . \end{matrix}$ Using Eqs. (5) and (10), we can write chromatic characteristic polynomial as $\begin{matrix} (λ_{χ}^{2} - 2 λ_{χ} + 1)^{\frac{s}{2}} (λ_{χ}^{2} - 2 λ_{χ} - 3)^{\frac{s - 2}{2}} \\ \times [λ_{χ}^{2} + 2 (s - 1) λ_{χ} + (s + 1) (s - 3)] = 0 . \end{matrix}$ (10) Hence, ${Spec}_{χ} (G) = (\begin{matrix} 3 - s & - s - 1 & 1 & - 1 & 3 \\ 1 & 1 & s & \frac{s - 2}{2} & \frac{s - 2}{2} \end{matrix}) .$ (11) ■

Corollary 2. The chromatic nullity of graph G, where $G ≃ \frac{s}{2} C_{4}$ , is zero.

Proof. By definition, chromatic nullity η_χ (G) of G is the number of zeros in Spec_χ (G). By Equation (1) Sp-c4, there is no zero eigenvalue in Spec_χ (G) therefore, η_χ (G) =0. ■

Theorem 3. Let G be a 2-regular bipartite colored graph with n vertices such that $G ≃ \frac{s}{3} C_{6}$ . Then the chromatic spectrum of G is given as follows ${Spec}_{χ} (G) = (\begin{matrix} 3 - s & - s - 1 & 0 & 2 & - 1 & 3 \\ 1 & 1 & \frac{2 s}{3} & \frac{2 s}{3} & \frac{s - 3}{3} & \frac{s - 3}{3} \end{matrix}) .$

Proof. Let G be a 2-regular bipartite colored graph such that G ≃ C₆. Let n = 2s be the order of graph G with s vertices in each partite set. Then there will be $\frac{s}{3}$ components of C₆. We denote $A_{χ}^{2} (G)$ to represent the matrix obtained by using Equation (1) Achi for G and it is written as $A_{χ}^{2} (G) = [\begin{matrix} - B & C \\ C & - B \end{matrix}],$ (12) where $B = {[\begin{matrix} N_{3} & J_{3} & \dots & J_{3} \\ J_{3} & N_{3} & \dots & J_{3} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ J_{3} & \dots & J_{3} & N_{3} \end{matrix}]}_{s \times s}$ (13) and $C = {[\begin{matrix} N_{3}^{T} & O_{3} & \dots & O_{3} \\ O_{3} & N_{3}^{T} & \dots & O_{3} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ O_{3} & \dots & O_{3} & N_{3}^{T} \end{matrix}]}_{s \times s}$ (14) also N₃ = J₃ - I₃ and exponent T represents the transpose of a matrix. To find the characteristic polynomial for $A_{χ}^{2} (G)$ by using B and C defined in Eq (1) 19, we apply the similar procedure as done in Theorem 1, we have $\det (A_{χ}^{2} (G) - λ_{χ} I_{2 s}) = \det (A^{2}),$ (15) where $A^{2} = (- B - λ_{χ} I_{s})^{2} - C^{2}$ . Replacing c₁ by $c_{1}^{'} = c_{1} + c_{2} + \dots + c_{s}$ , it gives $[λ_{χ}^{2} + 2 (s - 1) λ_{χ} + (s + 1) (s - 3)]$ value in first column which can be taken common. After simplifying it, we get $[λ_{χ}^{2} + 2 (s - 1) λ_{χ} + (s + 1) (s - 3)] \det (Q_{s}) = 0,$ (16) where $\det (Q_{s}) = {| \begin{matrix} 1 & 2 λ_{χ} + s - 3 & 2 λ_{χ} + s - 3 & \dots & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 \\ 1 & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 3 & \dots & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 \\ 1 & 2 λ_{χ} + s - 3 & λ_{χ}^{2} + s - 3 & \dots & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ 1 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 3 & 2 λ_{χ} + s - 3 \\ 1 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 3 & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 3 \\ 1 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 3 & 2 λ_{χ} + s - 3 & λ_{χ}^{2} + s - 3 \end{matrix} |}_{s \times s} .$ (17)

Replacing c₂ by $c_{2}^{'} = c_{2} - (2 λ_{χ} + s - 3) c_{1}$ , c₃ by $c_{3}^{'} = c_{3} - (2 λ_{χ} + s - 3) c_{1}$ and c_m by $c_{m}^{'} = c_{m} - (2 λ_{χ} + s - 2) c_{1}$ in equation (32) for m = 4, 5, ⋯ , s. Further simplification gives $\det (Q_{s}) = (λ_{χ}^{2} - 2 λ_{χ})^{2} \det (Q_{s - 3}),$ (18) where $Q_{s - 3} = [\begin{matrix} M_{3} & O_{3} & \dots & O_{3} \\ O_{3} & M_{3} & \dots & O_{3} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ O_{3} & O_{3} & \dots & M_{3} \end{matrix}]$ with $M_{3} = [\begin{matrix} λ_{χ}^{2} - 2 λ_{χ} - 1 & - 1 & - 1 \\ - 1 & λ_{χ}^{2} - 2 λ_{χ} - 1 & - 1 \\ - 1 & - 1 & λ_{χ}^{2} - 2 λ_{χ} - 1 \end{matrix}] .$ Here Q_s-3 is of order (s - 3) × (s - 3) and $| M_{3} | = (λ_{χ}^{2} - 2 λ_{χ} - 3) (λ_{χ}^{2} - 2 λ_{χ})^{2}$ . Thus $\begin{matrix} \det (Q_{s - 3}) = [\det (M_{3 \times 3})]^{\frac{s - 3}{3}} \\ = (λ_{χ}^{2} - 2 λ_{χ} - 3)^{\frac{s - 3}{3}} (λ_{χ}^{2} - 2 λ_{χ})^{2 (\frac{s - 3}{3})} . \end{matrix}$ (19) From Eqs. (18) into equation (19), we obtain $\det (Q_{s}) = (λ_{χ}^{2} - 2 λ_{χ})^{(\frac{2 s}{3})} (λ_{χ}^{2} - 2 λ_{χ} - 3)^{\frac{s - 3}{3}} .$ (20) Using Eqs. (16) and (20), we can write chromatic characteristic polynomial as $\begin{matrix} (λ_{χ}^{2} - 2 λ_{χ})^{\frac{2 s}{3}} (λ_{χ}^{2} - 2 λ_{χ} - 3)^{\frac{s - 3}{3}} \\ \times [λ_{χ}^{2} + 2 (s - 1) λ_{χ} + (s + 1) (s - 3)] = 0 . \end{matrix}$ (21) Therefore, ${Spec}_{χ} (G) = (\begin{matrix} 3 - s & - s - 1 & 0 & 2 & - 1 & 3 \\ 1 & 1 & \frac{2 s}{3} & \frac{2 s}{3} & \frac{s - 3}{3} & \frac{s - 3}{3} \end{matrix}) .$ (22) ■

Corollary 4. The chromatic nullity of G where $G ≃ \frac{s}{3} C_{6}$ is given by $η_{χ} = {\begin{matrix} 3 & if s = 3 \\ \frac{2}{3} s & otherwise . \end{matrix}$

Proof. For s = 3 in Equation (1) Sp-c6, we have zero eigenvalue with multiplicity. Whereas we have s - 3 =0 which is an additional zero eigenvalue in this case. When s ≠ 3, the result holds trivially by (1) Sp-c6. ■

Theorem 5. Let G be a 2-regular bipartite colored graph with n vertices such that G ≃ pC₄ ∪ qC₆, where s = 2p + 3q, both p and q are nonzero positive integers. Then the chromatic spectrum of G, Spec_χ (G), is given as follows $(\begin{matrix} 3 - s & - s - 1 & 1 & 0 & 2 & - 1 & 3 \\ 1 & 1 & 2 p & 2 q & 2 q & (p + q - 1) & (p + q - 1) \end{matrix}) .$

Proof. Let G be a 2 regular bipartite colored graph which is composed of p components of C₄ and q components of C₆. Let n = 2s be the order of graph G with s vertices in each partite set. Obviously, s = 2p + 3q, in this case the adjacency matrix is denoted by $A_{χ}^{3} (G)$ and can be written as $A_{χ}^{3} (G) = [\begin{matrix} - B & C \\ C & - B \end{matrix}],$ (23) where B and C, both have size s × s, are defined as $B = [\begin{matrix} N_{3} & J_{3} & \dots & J_{3} \\ J_{3} & N_{3} & \dots & J_{3} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ J_{3} & \dots & J_{3} & N_{3} \end{matrix}] and C = [\begin{matrix} P_{2 p \times 2 p} & O_{2 p \times 3 q} \\ O_{3 q \times 2 p} & Q_{3 q \times 3 q} \end{matrix}],$ (24) where J₃ and O₃ are 3 × 3 matrices with all entries 1 and 0, respectively, and N₃ = J₃ - I₃. Also O_2p×3q and O_3q×2p represent a zero matrix of order 2p × 3q. and 3q × 2p, respectively. In the above expression, P_2p×2p and Q_3q×3q are given as follows: $P_{2 p \times 2 p} = [\begin{matrix} J_{2} & O_{2} & \dots & O_{2} \\ O_{2} & J_{2} & \dots & O_{2} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ O_{2} & O_{2} & \dots & J_{2} \end{matrix}]$ (25) and $Q_{3 q \times 3 q} = [\begin{matrix} N_{3}^{T} & O_{3} & \dots & O_{3} \\ O_{3} & N_{3}^{T} & \dots & O_{3} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ O_{3} & \dots & O_{3} & N_{3}^{T} \end{matrix}],$ (26) where N₃ = J₃ - I₃.

To find the characteristic polynomial of A_χ (G), applying the similar procedure as in previous theorems, we have $\det (A_{χ}^{3} (G) - λ_{χ} I_{2 s})$ of following form: $\det (A_{χ}^{3} (G) - λ_{χ} I_{2 s}) = \det ((- B - λ_{χ} I_{s})^{2} - C^{2}) = \det (A^{3}),$ (27) where $A^{3} = {[\begin{matrix} D_{2 p \times 2 p}^{'} & D_{2 p \times 3 q} \\ D_{3 q \times 2 p} & D_{3 q \times 3 q}^{″} \end{matrix}]}_{s \times s} .$ (28)D_2p×3q and D_3q×2p have entries a_ij, where $a_{ij} = 2 λ_{χ} + s - 2 \forall i, j,$ $D_{2 p \times 2 p}^{'}$ and $D_{3 q \times 3 q}^{″}$ are give by $D_{2 p \times 2 p}^{'} = [\begin{matrix} λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 4 & 2 λ_{χ} + s - 2 & \dots & \dots & \dots & 2 λ_{χ} + s - 2 \\ 2 λ_{χ} + s - 4 & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 2 & \dots & \dots & \dots & 2 λ_{χ} + s - 2 \\ 2 λ_{χ} + s - 2 & \dots & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 4 & \dots & \dots & 2 λ_{χ} + s - 2 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ & \dots & \dots \\ 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & \dots & \dots & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 4 \\ 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & \dots & \dots & 2 λ_{χ} + s - 4 & λ_{χ}^{2} + s - 3 \end{matrix}],$ (29) $D_{3 q \times 3 q}^{″} = [\begin{matrix} λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 3 & 2 λ_{χ} + s - 3 & \dots & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 \\ 2 λ_{χ} + s - 3 & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 3 & \dots & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 \\ 2 λ_{χ} + s - 3 & 2 λ_{χ} + s - 3 & λ_{χ}^{2} + s - 3 & \dots & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ & ⋮ \\ 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 3 & 2 λ_{χ} + s - 3 \\ 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 3 & λ_{χ}^{2} + s - 3 & 2 λ_{χ} + s - 3 \\ 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & 2 λ_{χ} + s - 2 & \dots & 2 λ_{χ} + s - 3 & 2 λ_{χ} + s - 3 & λ_{χ}^{2} + s - 3 \end{matrix}] .$ (30) Proceeding as in previous sections, we obtain $\begin{matrix} [λ_{χ}^{2} + 2 (s - 1) λ_{χ} + (s + 1) (s - 3)] \\ \times (λ_{χ}^{2} - 2 λ_{χ} + 1) \det (R_{s - 2}) = 0 . \end{matrix}$ (31) Here R_s-2 is a (s - 2) × (s - 2) matrix given by $R_{s - 2} = [\begin{matrix} M_{(2 p - 2) \times (2 p - 2)} & O_{(2 p - 2) \times 3 q} \\ O_{3 q \times (2 p - 2)} & M_{3 q \times 3 q} \end{matrix}],$ (32) and M_{(2p-2)×(2p-2)} is of size (2p - 2) × (2p - 2) $M_{(2 p - 2) \times (2 p - 2)} = [\begin{matrix} M_{2} & O_{2} & \dots & O_{2} \\ O_{2} & M_{2} & \dots & O_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ O_{2} & O_{2} & \dots & M_{2} \end{matrix}],$ (33) with $M_{2} = [\begin{matrix} λ_{χ}^{2} - 2 λ_{χ} - 1 & - 2 \\ - 2 & λ_{χ}^{2} - 2 λ_{χ} - 1 \end{matrix}] .$ (34) Similarly $M_{3 q \times 3 q} = {[\begin{matrix} M_{3} & O_{3} & \dots & O_{3 \times 3} \\ O_{3} & M_{3} & \dots & O_{3} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ O_{3} & O_{3} & \dots & M_{3} \end{matrix}]}_{3 q \times 3 q},$ (35) with $M_{3} = [\begin{matrix} λ_{χ}^{2} - 2 λ_{χ} - 1 & - 1 & - 1 \\ - 1 & λ_{χ}^{2} - 2 λ_{χ} - 1 & - 1 \\ - 1 & - 1 & λ_{χ}^{2} - 2 λ_{χ} - 1 \end{matrix}],$ (36) Using property of block matrices, we have $\det (R_{s - 2}) = \det (M_{(2 p - 2) \times (2 p - 2)}) \det (M_{3 q \times 3 q}),$ (37) $\det (M_{(2 p - 2) \times (2 p - 2)}) = [\det (M_{2})]^{\frac{2 p - 2}{2}}$ (38) and $\det (M_{3 q \times 3 q}) = [\det (M_{3})]^{q} .$ (39) We find out that $| M_{2} | = (λ_{χ}^{2} - 2 λ_{χ} + 1) (λ_{χ}^{2} - 2 λ_{χ} - 3)$ (40) and $| M_{3} | = (λ_{χ}^{2} - 2 λ_{χ} - 3) (λ_{χ}^{2} - 2 λ_{χ})^{2} .$ (41) Using eqs. (37)-(41), we get $\begin{matrix} \det (R_{s - 2}) & = [(λ_{χ}^{2} - 2 λ_{χ} + 1) (λ_{χ}^{2} - 2 λ_{χ} - 3)]^{\frac{2 p - 2}{2}} \\ \times [(λ_{χ}^{2} - 2 λ_{χ} - 3) (λ_{χ}^{2} - 2 λ_{χ})^{2}]^{q} . \end{matrix}$ (42) From eqs. (42) and (31), finally we obtain $\begin{matrix} [λ_{χ}^{2} + 2 (s - 1) λ_{χ} + (s + 1) (s - 3)] (λ_{χ}^{2} - 2 λ_{χ} + 1) \\ \times [(λ_{χ}^{2} - 2 λ_{χ} + 1) (λ_{χ}^{2} - 2 λ_{χ} - 3)]^{(2 p - 2) / 2} \\ \times [(λ_{χ}^{2} - 2 λ_{χ})^{2} (λ_{χ}^{2} - 2 λ_{χ} - 3)]^{q} = 0, \end{matrix}$ which can be rewritten as $\begin{matrix} [λ_{χ}^{2} + 2 (s - 1) λ_{χ} + (s + 1) (s - 3)] (λ_{χ}^{2} - 2 λ_{χ} + 1)^{p} \\ \times (λ_{χ}^{2} - 2 λ_{χ})^{2 q} (λ_{χ}^{2} - 2 λ_{χ} - 3)^{p + q - 1} = 0 . \end{matrix}$ (43) Therefore, Spec_χ (G) is given as follows $= (\begin{matrix} 3 - s & - s - 1 & 1 & 0 & 2 & - 1 & 3 \\ 1 & 1 & 2 p & 2 q & 2 q & (p + q - 1) & (p + q - 1) \end{matrix}) .$ (44) ■

It can be observed by using q = 0 and s = 2p equation (1) Sp-c46 takes the form of equation (1) Sp-c4. Similarly, using p = 0 and s = 3q in equation (1) Sp-c46 resumes to equation (1) Sp-c6. From eqs. (1) Sp-c4, (1) Sp-c6 and (1) Sp-c46, it can be deduced that Theorem 1 and Theorem 3 are special cases of Theorem 5.

Corollary 6. Let G be a 2-regular bipartite colored graph with n vertices such that G ≃ pC₄ ∪ qC₆, where s = 2p + 3q. Then the chromatic nullity of G is 2q.

Proof. In this case s ≠ 3 therefore, result follows from Equation (1) Sp-c46.■

3 Conclusion

We computed chromatic spectrum of three types of 2-regular bipartite graphs. We also observed pattern of nullity in these kind of graphs. According to [3], nullity of a disconnected graph is equal to sum of nullities of its components but this result does not hold for colored graphs. For example, η (C₆ ∪ C₆ ∪ C₆) =3η (C₆). Now consider chromatic nullity of these graphs, that is, η_χ (C₆ ∪ C₆ ∪ C₆) =6 but η_χ (C₆) =3. Clearly, η_χ (C₆ ∪ C₆ ∪ C₆) ≠3η_χ (C₆).

We also noticed that if a 2-regular bipartite graph has a component C₄, then it would not contribute in the chromatic nullity of that graph and it seems that a C₆ component would increase chromatic nullity of a disconnected 2-regular bipartite graph by 2. For example, η_χ (C₄) =0 and chromatic nullity of a graph all of whose components are C₄ (Theorem 1) is also 0. If G has three C₆ components, then η_χ (G) =6. This pattern can also be seen in Theorem 5, where chromatic nullity of G is depends upon the number of components that are C₆.

As mentioned earlier, chromatic eigenvalues of a disconnected graph is not necessarily equal to chromatic eigenvalues of its components. To analyse these properties, consider characteristic polynomial and chromatic characteristic polynomial of C₄ and a graph having C₄ as a component. P_{C
₄} (λ) = λ² (λ² - 4) and P_C₄∪C₄ (λ) = [λ² (λ² - 4)] ². Moreover, $P_{C_{4}} (λ_{χ}) = (λ_{χ}^{2} + 2 λ_{χ} - 3) (λ_{χ}^{2} - 2 λ_{χ} + 1)$ and $P_{C_{4} \cup C_{4}} (λ_{χ}) = (λ_{χ}^{2} + 6 λ_{χ} + 5) (λ_{χ}^{2} - 2 λ_{χ} - 3) (λ_{χ}^{2} - 2 λ_{χ} + 1)^{2}$ Clearly, $P_{C_{4} \cup C_{4}} (λ) = P_{C_{4}} (λ) . P_{C_{4}} (λ),$ but $P_{C_{4} \cup C_{4}} (λ_{χ}) \neq P_{C_{4}} (λ_{χ}) . P_{C_{4}} (λ_{χ}) .$

The irreducible factors of P_G (λ_χ) when all components of G are C₄ and C₆ are given in (1) 16 and (1) 32, respectively. We noticed that chromatic characteristic polynomial of all 2-regular bipartite colored graphs are of this form $[λ_{χ}^{2} + 2 (s - 1) λ_{χ} + s^{2} - 2 s - 3] ξ_{G} (λ_{χ}),$ (45) with s vertices in each partite set, where ξ_G (λ_χ) is a factor which varies uncertainly for different graphs. We believe that there is a pattern followed by ξ_G (λ_χ) when we consider cycles of greater lengths than 4 and 6 but we could not find that generally. Here we are listing some examples that may be helpful in generalization of this problem. Note that we are only considering ξ_G (λ_χ). We know that for a single component of C₄, $ξ_{C_{4}} (λ_{χ}) = (λ_{χ} - 1)^{2}$ For a single component of C₈, $ξ_{C_{8}} (λ_{χ}) = ξ_{C_{4}} (λ_{χ}) (λ_{χ}^{2} - 2 λ_{χ} - 1)$ . For C₁₆, ξ (λ_χ) is given as $ξ_{C_{16}} (λ_{χ}) = ξ_{C_{8}} (λ_{χ}) (λ_{χ}^{8} - 8 λ_{χ}^{7} + 20 λ_{χ}^{6} - 8 λ_{χ}^{5} - 30 λ_{χ}^{4} + 24 λ_{χ}^{3} + 12 λ_{χ}^{2} - 8 λ_{χ} - 1)^{2}$ . The pattern of ξ_{C
_k} (λ_χ) depends upon its highest factor with some new polynomial. Determination of ξ_G (λ_χ) for general chromatic characteristic polynomials of all 2-regular bipartite graphs is still in progress.

Data availability

The data used to support the findings of this study are included within the article.

Conflicts of interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Footnotes

Acknowledgments

This research is supported by UPAR Grant of United Arab Emirates University (UAEU), Al Ain, UAE via Grants No. G00003271 and AUA Grant of UAEU via Grant No. G00003461.

Two graphs G and H are said to isomorphic if there exits a mapping φ : V (G) → V (H) such that for each edge uv ∈ E (G) we have φ (u) φ (v) ∈ E (H).

References

Adiga

, Sampathkumar

, Sriraj

and Shrikanth

, Colorergy of a graph, Proc Jangjeon Math Soc 16 (2013), 335–351.

Babai

, Graph isomorphism in quasipolynomial time, Preprint at https://arxiv.org/abs/1512.03547v2, 2016.

Borovićanin

and Gutman

, Nullity of graphs, Applications ofGraph Spectra, Zbornik Radova 13(21) (2009), 107–122.

Collatz

and Sinogowitz

, Spektren endlicher grafen, AbhMath Sere Univ Hamburg 21 (1957), 63–77.

Elsaesser

and Trinker

, On the isomorphism of graphs havingsome eigenvalues of moderate multiplicity, Lin Algebra Appl 488 (2016), 377–395.

Fan

and Qian

, On the nullity of bipartite graphs, LinAlgebra Appl 430 (2009), 2943–2949.

Fiorini

, Gutman

and Sciriha

, Trees with maximum nullity, Lin Algebra Appl 397 (2005), 245–251.

Gong

, Fan

and Yin

, On the nullity of graphs with pendanttrees, Lin Algebra Appl 433 (2010), 1374–1380.

Kotulski

, Sedziwy

, Strug

, Wojnicki

and ErnstSynchronisation

, methods in graph-based knowledge representation forlarge-scale design process, Int J Des Eng 7 (2017), 17–32.

10.

and Chang

, On the trees with maximum nullity, MATCHCommun Math Comput Chem 56 (2006), 501–508.

11.

Miyazakim

, On Testing Isomorphism of Graphs of Bounded Eigenvalue Multiplicity, in: Mathematical Aspects of Computer and Information Sciences, Springer, 1^st ed., 2017, pp. 325–329.

12.

Shigehalli

and Kenchappa

, A note on color energy of graphs, BOMSR 4(4) (2016).

13.

Tan

and Liu

, On the nullity of unicyclic graphs, LinAlgebra Appl 408 (2005), 212–220.

14.

Wojnicki

, Kotulski

, Sedziwy

and Ernst

, Application ofDistributed Graph Transformations to Automated Generation of ControlPatterns for Intelligent Lighting Systems, J Comput Sci 23 (2017), 20–30.