On the Spectral Properties of Graphs with Rank 4

Jianxuan Luo

School of Mathematics and Statistics, Qinghai Minzu University, Xining, China.

DOI: 10.4236/am.2023.1411045                

Abstract

Let G be a graph and A(G) the adjacency matrix of G. The spectrum of G is the eigenvalues together with their multiplicities of A(G). Chang et al. (2011) characterized the structures of all graphs with rank 4. Monsalve and Rada (2021) gave the bound of spectral radius of all graphs with rank 4. Based on these results as above, we further investigate the spectral properties of graphs with rank 4. And we give the expressions of the spectral radius and energy of all graphs with rank 4. In particular, we show that some graphs with rank 4 are determined by their spectra.

Keywords

Spectral Radius, Energy, Cospectral Graphs, Rank

1. Introduction

All graphs considered in this paper are undirected, finite and simple. Let $G=\left(V\left(G\right)\mathrm{,}E\left(G\right)\right)$ be a graph with n vertices and m edges. For convenience, the path, cycle and complete graph of order n are denoted by $P_n$ , $C_n$ and $K_n$ , respectively. Let C be a set, and the number of elements in C is denoted by $\left|C\right|$ , let $c_i\left(G\right)$ denote the number of cycles of length i.

The adjacency matrix of G is denoted by $A\left(G\right)$ . The polynomial $\varphi \left(G,x\right)=\det \left|xI-A\left(G\right)\right|$ is called the characteristic polynomial of a graph G, where I is the identity matrix of order n. The spectrum of G consists of the eigenvalues together with their multiplicities of $A\left(G\right)$ . The spectral radius of G, denoted by $\rho \left(G\right)$ , is the maximum eigenvalue of graph G. The nullity of G, denoted by $\eta \left(G\right)$ , is the multiplicity of zeros in the spectrum of G. Let $r\left(G\right)$ be the rank of $A\left(G\right)$ . Obviously, $\eta \left(G\right)=n-r\left(G\right)$ . Two graphs G and H are said to be cospectral (denoted by $G~H$ ) if they share the same spectrum. A graph G is said to be determined by its spectrum (DS for short) if for any graph H, $\varphi \left(G\mathrm{,}x\right)=\varphi \left(H\mathrm{,}x\right)$ implies that H is isomorphic to G.

The energy of G first is defined by Gutman in 1978 as the sum of the absolute values of its eigenvalues. That is,

$E\left(G\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left|{\lambda }_i\right|.$

The theory of graph energy is well developed nowadays; its details can be found in the book [1] and reviews [2] [3] .

Definition 1.1. ( [4] ) Given a graph G with the set of vertices $V\left(G\right)=\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_p\right\}$ and a vector of positive integers $m=\left(m_1\mathrm{,}{m}_2\mathrm{,}\cdots \mathrm{,}{m}_p\right)$ , denote by $Gom\left(m_1\mathrm{,}{m}_2\mathrm{,}\cdots \mathrm{,}{m}_p\right)$ (Gom for short) the graph obtained from G by replacing each vertex $v_i$ of G with an independent set of $m_i$ vertices $v_i^1\mathrm{,}{v}_i^2\mathrm{,}\cdots \mathrm{,}{v}_i^{m_i}$ and joining $v_i^s$ with $v_j^t$ if and only if $v_i$ and $v_j$ are adjacent in G. The resulting graph Gom is said to be obtained from G by multiplication of vertices. For graph $G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_k$ , we denote by $N\left(G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_k\right)$ the class of all graphs that can be obtained from one of the graphs in $\left\{G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_k\right\}$ by multiplication of vertices.

By Definition 2.1, Chang et al. [4] characterized all connected graphs with rank 4. That is, if G is a connected graph with rank 4, then $G\in N\left(G_2\mathrm{,}\cdots \mathrm{,}{G}_9\right)$ , the resulting graph, see Figure 1. Wu et al. [5] studied further the spectral properties of graphs with rank 4. They computed the characteristic polynomials of all graphs with rank 4. And they showed that some graphs with rank 4 are determined by their spectra. In particular, they proposed a problem: Which graphs with rank 4 are determined by their spectra? Recently, Monsalve and Rada [6] characterized spectral radius of all connected graphs with rank 4. A natural problem is: How to characterize the spectral radius of all graphs with rank 4?

In this paper, we intend to solve these two problems. Preliminaries are presented in Section 2. And we give the expressions of the spectral radius and energy of all graphs with rank 4 in Section 3. In Section 4, we consider which graphs

Figure 1. $G_1\mathrm{,}{G}_2\mathrm{,}{G}_3\mathrm{,}{G}_4\mathrm{,}{G}_5\mathrm{,}{G}_6\mathrm{,}{G}_7\mathrm{,}{G}_8\mathrm{,}{G}_9$ .

with rank 4 are DS. More precisely, we prove that two classes of graphs with rank 4 are DS. And some cospectral graphs with rank 4 are presented.

2. Some Lemmas

Several lemmas are of importance to the description and proof of our results later, and we list them below.

By the properties of vertex multiplication, Wu et al. [5] computed the characteristic polynomials with rank 4 as follows.

Lemma 2.1. ( [5] ) Let G be a simple graph on n vertices and $n\ge 4$ . Then $r\left(G\right)=4$ if an only if $G\in \left(G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_9\right)$ , where the graphs $G_1\mathrm{,}\cdots \mathrm{,}{G}_9$ are depicted in Figure 1.

Lemma 2.2. ( [7] ) Let G be a graph. For the adjacency matrix the following can be deduced from the spectrum:

(i) The number of vertices.

(ii) The number of edges.

(iii) Whether G is regular.

(iv) Whether G is regular with any fixed girth.

(v) The number of closed walk of any length.

(vi) Whether G is bipartite.

Lemma 2.3. ( [8] ) Let G be a simple bipartite graph with e edges. Then

$\rho \left(G\right)\le \sqrt{e}$

with equality if G is a disjoint union of a complete bipartite graph and isolated vertices.

Lemma 2.4. ( [5] ) Suppose that ${G^{\prime }}_i=G_{i}om\left[m_1\mathrm{,}{m}_2\mathrm{,}\cdots \mathrm{,}{m}_p\right]$ , where $G_i$ is depicted in Figure 1, $i=\mathrm{1,2,}\cdots \mathrm{,9}$ , $p=\left|V\left(G_i\right)\le 6\right|$ , $\left|m_1\right|=a$ , $\left|m_2\right|=b$ , $\left|m_3\right|=c$ , $\left|m_4\right|=d$ , $\left|m_5\right|=e$ , $\left|m_6\right|=f$ . Then each of the following holds.

(i) $\varphi \left({G^{\prime }}_1\mathrm{,}x\right)=x^{a+b+c+d-4}\left[x^4-\left(ab+cd\right)x^2+abcd\right]$ .

(ii) $\varphi \left({G^{\prime }}_2\mathrm{,}x\right)=x^{a+b+c+d-4}\left[x^4-\left(ab+bc+bd+cd\right)x^2-2bcdx+abcd\right]$ .

(iii) $\begin{array}{c}\varphi \left({G^{\prime }}_3\mathrm{,}x\right)=x^{a+b+c+d+e-4}[x^4-\left(ab+ac+bc+bd+ce\right)x^2-2abcx\\ +abdc+abec+dbec]\end{array}$ .

(iv) $\begin{array}{c}\varphi \left({G^{\prime }}_4\mathrm{,}x\right)=x^{a+b+c+d+e-4}[x^4-\left(ab+ae+be+bc+cd+de\right)x^2-2abex\\ +abed+aecd+abcd+abec]\end{array}$ .

(v) $\begin{array}{c}\varphi \left({G^{\prime }}_5\mathrm{,}x\right)=x^{a+b+c+d+e+f-4}[x^4-\left(ab+bc+bf+cf+cd+de+ef\right)x^2-2bcfx\\ +abed+abcd+bdec+abcf+abef+bcef+fbcd+fbed]\end{array}$ .

(vi) $\begin{array}{c}\varphi \left({G^{\prime }}_6\mathrm{,}x\right)=x^{a+b+c+d-4}[x^4-\left(ab+ac+ad+bc+bd+cd\right)x^2\\ -2\left(abc+abd+acd+bcd\right)x-3abcd]\end{array}$ .

(vii) $\begin{array}{c}\varphi \left({G^{\prime }}_7\mathrm{,}x\right)=x^{a+b+c+d+e+f-4}[x^4-\left(ab+ac+af+bc+be+cd+df+de+fe\right)x^2\\ -2\left(abc+def\right)x+abed+abdf+acbe+aced+acef+afed\\ +abcd+fcde+abcf+bcef+fbcd+fbed]\end{array}$ .

(viii) $\varphi \left({G^{\prime }}_8\mathrm{,}x\right)=x^{a+b+c+d-4}\left[x^4-\left(ab+bc+cd\right)x^2+abcd\right]$ .

(ix) $\varphi \left({G^{\prime }}_9\mathrm{,}x\right)=x^{a+b+c+d+e-4}\left[x^4-\left(ab+bc+cd+de\right)x^2+abcd+bcde+abde\right]$ .

3. The Spectral Radii and Energies of Graphs with Rank 4

In this section, we give the spectral radii and energies of graphs with rank 4. All the notation in this paragraph is followed in Lemma 2.4.

Theorem 3.1. Let $G\in N\left(G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_9\right)$ . Then the spectral radius of graph G as follows:

(i) If $G\in N\left(G_1\right)$ . Then

$\rho \left(G\right)={\left(\lfloor \frac{n-2}{2}\rfloor \lceil \frac{n-2}{2}\rceil \right)}^{\frac{1}{2}}\mathrm{.}$

(ii) If $G\in N\left(G_2\right)$ and let $c^{\prime }=ab+bc+bd+cd,d^{\prime }=bcd,e^{\prime }=abcd$ . Then

$\rho \left(G\right)=\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }\mathrm{<mo>\; /\; </mo>}{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right]\mathrm{,}$

where

$\begin{array}{l}\Delta =\left[\sqrt[3]{4}\left({\left(c^{\prime }\right)}^2+12e^{\prime }\right)+{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{2}{3}}\right]\\ \mathrm{<mo>\; /\; </mo>}\left[3\sqrt[3]{2}{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right]\mathrm{,}\end{array}$

where

$\begin{array}{c}A=-432e^{\prime }{\left(c^{\prime }\right)}^4+3456{\left(e^{\prime }\right)}^2{\left(c^{\prime }\right)}^2-432{\left(d^{\prime }\right)}^2{\left(c^{\prime }\right)}^3+15552e^{\prime }{c}^{\prime }{\left(d^{\prime }\right)}^2\\ -6912{\left(e^{\prime }\right)}^3+11664{\left(d^{\prime }\right)}^4\mathrm{.}\end{array}$

(iii) If $G\in N\left(G_3\right)$ and let $c^{\prime }=ab+ac+bc+bd+ce$ , $d^{\prime }=abc$ , $e^{\prime }=abdc+abec+dbec$ . Then

$\rho \left(G\right)=\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }\mathrm{<mo>\; /\; </mo>}{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right]\mathrm{,}$

where

$\begin{array}{l}\Delta =\left[\sqrt[3]{4}\left({\left(c^{\prime }\right)}^2+12e^{\prime }\right)+{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{2}{3}}\right]\\ \mathrm{<mo>\; /\; </mo>}\left[3\sqrt[3]{2}{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right]\mathrm{,}\end{array}$

where

$\begin{array}{c}A=-432e^{\prime }{\left(c^{\prime }\right)}^4+3456{\left(e^{\prime }\right)}^2{\left(c^{\prime }\right)}^2-432{\left(d^{\prime }\right)}^2{\left(c^{\prime }\right)}^3+15552e^{\prime }{c}^{\prime }{\left(d^{\prime }\right)}^2\\ -6912{\left(e^{\prime }\right)}^3+11664{\left(d^{\prime }\right)}^4\mathrm{.}\end{array}$

(iv) If $G\in N\left(G_4\right)$ and let $c^{\prime }=ab+ae+be+bc+cd+de$ , $d^{\prime }=abe$ , $e^{\prime }=abed+aecd+abcd+abec$ . Then

$\rho \left(G\right)=\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }\mathrm{<mo>\; /\; </mo>}{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right]\mathrm{,}$

where

$\begin{array}{l}\Delta =\left[\sqrt[3]{4}\left({\left(c^{\prime }\right)}^2+12e^{\prime }\right)+{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{2}{3}}\right]\\ \mathrm{<mo>\; /\; </mo>}\left[3\sqrt[3]{2}{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right]\mathrm{,}\end{array}$

where

$\begin{array}{c}A=-432e^{\prime }{\left(c^{\prime }\right)}^4+3456{\left(e^{\prime }\right)}^2{\left(c^{\prime }\right)}^2-432{\left(d^{\prime }\right)}^2{\left(c^{\prime }\right)}^3+15552e^{\prime }{c}^{\prime }{\left(d^{\prime }\right)}^2\\ -6912{\left(e^{\prime }\right)}^3+11664{\left(d^{\prime }\right)}^4\mathrm{.}\end{array}$

(v) If $G\in N\left(G_5\right)$ and let $c^{\prime }=ab+bc+bf+cf+cd+de+ef$ , $d^{\prime }=bcf$ , $e^{\prime }=abed+abcd+bdec+abcf+abef+bcef+fbcd+fbed$ . Then

$\rho \left(G\right)=\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }\mathrm{<mo>\; /\; </mo>}{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right]\mathrm{,}$

where

$\begin{array}{l}\Delta =\left[\sqrt[3]{4}\left({\left(c^{\prime }\right)}^2+12e^{\prime }\right)+{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{2}{3}}\right]\\ \mathrm{<mo>\; /\; </mo>}\left[3\sqrt[3]{2}{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right]\mathrm{,}\end{array}$

where

$\begin{array}{c}A=-432e^{\prime }{\left(c^{\prime }\right)}^4+3456{\left(e^{\prime }\right)}^2{\left(c^{\prime }\right)}^2-432{\left(d^{\prime }\right)}^2{\left(c^{\prime }\right)}^3+15552e^{\prime }{c}^{\prime }{\left(d^{\prime }\right)}^2\\ -6912{\left(e^{\prime }\right)}^3+11664{\left(d^{\prime }\right)}^4\mathrm{.}\end{array}$

(vi) If $G\in N\left(G_6\right)$ and let $c^{\prime }=ab+ac+ad+bc+bd+cd$ , $d^{\prime }=abc+abd+acd+bcd$ , $e^{\prime }=abcd$ . Then

$\rho \left(G\right)=\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }\mathrm{<mo>\; /\; </mo>}{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right]\mathrm{,}$

where

$\begin{array}{l}\Delta =\left[\sqrt[3]{4}\left({\left(c^{\prime }\right)}^2-36e^{\prime }\right)+{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2-216e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{2}{3}}\right]\\ \mathrm{<mo>\; /\; </mo>}\left[3\sqrt[3]{2}{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2-216e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right]\mathrm{,}\end{array}$

where

$\begin{array}{c}A=1296e^{\prime }{\left(c^{\prime }\right)}^4+31104{\left(e^{\prime }\right)}^2{\left(c^{\prime }\right)}^2-432{\left(d^{\prime }\right)}^2{\left(c^{\prime }\right)}^3-46656e^{\prime }{c}^{\prime }{\left(d^{\prime }\right)}^2\\ +1886624{\left(e^{\prime }\right)}^3+11664{\left(d^{\prime }\right)}^4\mathrm{.}\end{array}$

(vii) If $G\in N\left(G_7\right)$ and let $c^{\prime }=ab+ac+af+bc+be+cd+df+de+fe$ , $d^{\prime }=abc+def$ , $e^{\prime }=abed+abdf+acbe+aced+acef+afed+abcd+fcde+$ $abcf+bcef+fbcd+fbed$ . Then

$\rho \left(G\right)=\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }\mathrm{<mo>\; /\; </mo>}{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right]\mathrm{,}$

where

$\begin{array}{l}\Delta =\left[\sqrt[3]{4}\left({\left(c^{\prime }\right)}^2+12e^{\prime }\right)+{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{2}{3}}\right]\\ \mathrm{<mo>\; /\; </mo>}\left[3\sqrt[3]{2}{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right]\mathrm{,}\end{array}$

where

$\begin{array}{c}A=-432e^{\prime }{\left(c^{\prime }\right)}^4+3456{\left(e^{\prime }\right)}^2{\left(c^{\prime }\right)}^2-432{\left(d^{\prime }\right)}^2{\left(c^{\prime }\right)}^3+15552e^{\prime }{c}^{\prime }{\left(d^{\prime }\right)}^2\\ -6912{\left(e^{\prime }\right)}^3+11664{\left(d^{\prime }\right)}^4\mathrm{.}\end{array}$

(viii) If $G\in N\left(G_8\right)$ . Then

$\rho \left(G\right)=\frac{1}{2}{\left[2ab+2bc+2cd+2{\left({\left(ab+bc+cd\right)}^2-4abcd\right)}^{\frac{1}{2}}\right]}^{\frac{1}{2}}\mathrm{.}$

(ix) If $G\in N\left(G_9\right)$ . Then

$\rho \left(G\right)=\frac{1}{2}[2ab+2bc+2cd+2de+2({\left(ab+bc+cd+de\right)}^2-{{4\left(abcd+bcde+abde\right))}^{\frac{1}{2}}]}^{\frac{1}{2}}\mathrm{.}$

Proof. Here we only consider the cases $G\in N\left(G_1\right)$ , $G\in N\left(G_2\right)$ . The proof of other cases is quite similar to $G\in N\left(G_2\right)$ and is thus omitted.

Let $G\in N\left(G_1\right)$ . By Lemma 2.3, directly yields $\rho \left(G\right)={\left(\lfloor \frac{n-2}{2}\rfloor \lceil \frac{n-2}{2}\rceil \right)}^{\frac{1}{2}}$ .

Let $G\in N\left(G_2\right)$ . By Theorem 2.4 (ii), there exist 4 nonzero eigenvalues and all other eigenvalues are 0. So we only need to input polynomial $x^4-\left(ab+bc+bd+cd\right)x^2-2bcdx+abcd$ in maple 13.0, we can get the nonzero eigenvalues of the graph G as follows.

$\begin{array}{c}{\lambda }_1=\frac{1}{2}[{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}}\\ +(\frac{4}{3}\left(ab+bc+bd+cd\right)-\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}+3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\\ +4bcd\mathrm{<mo>\; /\; </mo>}{{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}})}^{\frac{1}{2}}]\mathrm{,}\end{array}$

$\begin{array}{c}{\lambda }_2=\frac{1}{2}[{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}}\\ -(\frac{4}{3}\left(ab+bc+bd+cd\right)-\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}+3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\\ +4bcd\mathrm{<mo>\; /\; </mo>}{{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}})}^{\frac{1}{2}}]\mathrm{,}\end{array}$

$\begin{array}{c}{\lambda }_3=-\frac{1}{2}[{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}}\\ +(\frac{4}{3}\left(ab+bc+bd+cd\right)-\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}+3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\\ -4bcd\mathrm{<mo>\; /\; </mo>}{{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}})}^{\frac{1}{2}}]\mathrm{,}\end{array}$

$\begin{array}{c}{\lambda }_4=-\frac{1}{2}[{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}}\\ -(\frac{4}{3}\left(ab+bc+bd+cd\right)-\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}+3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\\ -4bcd\mathrm{<mo>\; /\; </mo>}{{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}})}^{\frac{1}{2}}]\mathrm{.}\end{array}$

where

$\begin{array}{c}D=-a^3{b}^3-b^3{c}^3-b^3{d}^3-c^3{d}^3+33a^2{b}^{2}cd+30a{b}^2{c}^{2}d+30a{b}^{2}c{d}^2\\ +33ab{c}^2{d}^2-6a{b}^{3}cd-3a^2{b}^{3}c-3a^2{b}^{3}d-3a{b}^3{c}^2-3a{b}^3{d}^2\\ -3b^3{c}^{2}d-3b^{3}c{d}^2-3b^2{c}^{3}d-3b^{2}c{d}^3-3b{c}^3{d}^2-3b{c}^2{d}^3+48b^2{c}^2{d}^2,\end{array}$

$\begin{array}{c}E=-3a^5{b}^{5}cd-12a^4{b}^5{c}^{2}d-12a^4{b}^{5}c{d}^2+12a^4{b}^4{c}^2{d}^2-18a^3{b}^5{c}^{3}d\\ -39a^3{b}^5{c}^2{d}^2-18a^3{b}^{5}c{d}^3+12a^3{b}^4{c}^3{d}^2+12a^3{b}^4{c}^2{d}^3-18a^3{b}^3{c}^3{d}^3\\ -12a^2{b}^5{c}^{4}d-45a^2{b}^5{c}^3{d}^2-45a^2{b}^5{c}^2{d}^3-12a^2{b}^{5}c{d}^4-12a^2{b}^4{c}^4{d}^2\\ +75a^2{b}^4{c}^3{d}^3-12a^2{b}^4{c}^2{d}^4+12a^2{b}^3{c}^4{d}^3+12a^2{b}^3{c}^3{d}^4+12a^2{b}^2{c}^4{d}^4\\ -3a{b}^5{c}^{5}d-21a{b}^5{c}^4{d}^2-36a{b}^5{c}^3{d}^3-21a{b}^5{c}^2{d}^4-3a{b}^{5}c{d}^5-12a{b}^4{c}^5{d}^2\end{array}$

$\begin{array}{c}+54a{b}^4{c}^4{d}^3+54a{b}^4{c}^3{d}^4-12a{b}^4{c}^2{d}^5-18a{b}^3{c}^5{d}^3+63a{b}^3{c}^4{d}^4\\ -18a{b}^3{c}^3{d}^5-12a{b}^2{c}^5{d}^4-12a{b}^2{c}^4{d}^5-3ab{c}^5{d}^5-3b^5{c}^5{d}^2-9b^5{c}^4{d}^3\\ -9b^5{c}^3{d}^4-3b^5{c}^2{d}^5-9b^4{c}^5{d}^3+63b^4{c}^4{d}^4-9b^4{c}^3{d}^5-9b^3{c}^5{d}^4\\ -9b^3{c}^4{d}^5-3b^2{c}^5{d}^5\mathrm{,}\end{array}$

$\begin{array}{c}F=-\frac{14}{9}abcd-\frac{1}{9}{a}^2{b}^2-\frac{2}{9}a{b}^{2}d-\frac{1}{9}{b}^2{c}^2-\frac{2}{9}{b}^{2}cd\\ -\frac{1}{9}{b}^2{d}^2-\frac{2}{9}{c}^{2}bd-\frac{2}{9}bc{d}^2-\frac{1}{9}{c}^2{d}^2.\end{array}$

Due to ${\lambda }_3,{\lambda }_4<0$ , ${\lambda }_1,{\lambda }_2>0$ and ${\lambda }_1>{\lambda }_2$ , we can obviously get ${\lambda }_1$ is the spectral radius of graph G. Let $c^{\prime }=ab+bc+bd+cd$ , $d^{\prime }=bcd$ , $e^{\prime }=abcd$ , due to

$\begin{array}{c}D=-a^3{b}^3-b^3{c}^3-b^3{d}^3-c^3{d}^3+33a^2{b}^{2}cd+30a{b}^2{c}^{2}d+30a{b}^{2}c{d}^2\\ +33ab{c}^2{d}^2-6a{b}^{3}cd-3a^2{b}^{3}c-3a^2{b}^{3}d-3a{b}^3{c}^2-3a{b}^3{d}^2\\ -3b^3{c}^{2}d-3b^{3}c{d}^2-3b^2{c}^{3}d-3b^{2}c{d}^3-3b{c}^3{d}^2-3b{c}^2{d}^3+48b^2{c}^2{d}^2\\ =-{\left(ab+bc+bd+cd\right)}^3+54{\left(bcd\right)}^2+36abcd\left(ab+bc+bd+cd\right)\\ =-{\left(c^{\prime }\right)}^3+54{\left(d^{\prime }\right)}^2+36e^{\prime }{c}^{\prime }\end{array}$

$\begin{array}{c}E=-3a^5{b}^{5}cd-12a^4{b}^5{c}^{2}d-12a^4{b}^{5}c{d}^2+12a^4{b}^4{c}^2{d}^2-18a^3{b}^5{c}^{3}d\\ -39a^3{b}^5{c}^2{d}^2-18a^3{b}^{5}c{d}^3+12a^3{b}^4{c}^3{d}^2+12a^3{b}^4{c}^2{d}^3-18a^3{b}^3{c}^3{d}^3\\ -12a^2{b}^5{c}^{4}d-45a^2{b}^5{c}^3{d}^2-45a^2{b}^5{c}^2{d}^3-12a^2{b}^{5}c{d}^4-12a^2{b}^4{c}^4{d}^2\end{array}$

$\begin{array}{c}+75a^2{b}^4{c}^3{d}^3-12a^2{b}^4{c}^2{d}^4+12a^2{b}^3{c}^4{d}^3+12a^2{b}^3{c}^3{d}^4+12a^2{b}^2{c}^4{d}^4\\ -3a{b}^5{c}^{5}d-21a{b}^5{c}^4{d}^2-36a{b}^5{c}^3{d}^3-21a{b}^5{c}^2{d}^4-3a{b}^{5}c{d}^5-12a{b}^4{c}^5{d}^2\end{array}$

$\begin{array}{c}+54a{b}^4{c}^4{d}^3+54a{b}^4{c}^3{d}^4-12a{b}^4{c}^2{d}^5-18a{b}^3{c}^5{d}^3+63a{b}^3{c}^4{d}^4\\ -18a{b}^3{c}^3{d}^5-12a{b}^2{c}^5{d}^4-12a{b}^2{c}^4{d}^5-3ab{c}^5{d}^5-3b^5{c}^5{d}^2-9b^5{c}^4{d}^3\\ -9b^5{c}^3{d}^4-3b^5{c}^2{d}^5-9b^4{c}^5{d}^3+63b^4{c}^4{d}^4-9b^4{c}^3{d}^5-9b^3{c}^5{d}^4\\ -9b^3{c}^4{d}^5-3b^2{c}^5{d}^5\end{array}$

$\begin{array}{c}=-3abcd{\left(ab+bc+bd+cd\right)}^4+24{\left(abcd\right)}^2{\left(ab+bc+bd+cd\right)}^2\\ -3{\left(bcd\right)}^2{\left(ab+bc+bd+cd\right)}^3+108abcd\left(ab+bc+bd+cd\right){\left(bcd\right)}^2\\ -48{\left(abcd\right)}^3+81{\left(bcd\right)}^4\end{array}$

$\begin{array}{c}=-3e^{\prime }{\left(c^{\prime }\right)}^4+24{\left(e^{\prime }\right)}^2{\left(c^{\prime }\right)}^2-3{\left(d^{\prime }\right)}^2{\left(c^{\prime }\right)}^3+108e^{\prime }{c}^{\prime }{\left(d^{\prime }\right)}^2-48{\left(e^{\prime }\right)}^3+81{\left(d^{\prime }\right)}^4\\ =[-432e^{\prime }{\left(c^{\prime }\right)}^4+3456{\left(e^{\prime }\right)}^2{\left(c^{\prime }\right)}^2-432{\left(d^{\prime }\right)}^2{\left(c^{\prime }\right)}^3+15552e^{\prime }{c}^{\prime }{\left(d^{\prime }\right)}^2\\ -6912{\left(e^{\prime }\right)}^3+11664{\left(d^{\prime }\right)}^4]\mathrm{<mo>\; /\; </mo>144}\\ =A\mathrm{<mo>\; /\; </mo>144}\end{array}$

$\begin{array}{c}F=-\frac{14}{9}abcd-\frac{1}{9}{a}^2{b}^2-\frac{2}{9}a{b}^{2}d-\frac{1}{9}{b}^2{c}^2-\frac{2}{9}{b}^{2}cd\\ -\frac{1}{9}{b}^2{d}^2-\frac{2}{9}{c}^{2}bd-\frac{2}{9}bc{d}^2-\frac{1}{9}{c}^2{d}^2\\ =-\frac{1}{9}\left({\left(ab+bc+bd+cd\right)}^2+12abcd\right)\\ =-\frac{1}{9}\left({\left(c^{\prime }\right)}^2+12e^{\prime }\right).\end{array}$

Then we have

$\begin{array}{l}\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\\ =\frac{1}{3}{\left(-{\left(c^{\prime }\right)}^3+54{\left(d^{\prime }\right)}^2+36e^{\prime }{c}^{\prime }+6{\left(A\mathrm{<mo>\; /\; </mo>144}\right)}^{\frac{1}{2}}\right)}^{\frac{1}{3}}\\ -3\left(-\frac{1}{9}\left({\left(c^{\prime }\right)}^2+12e^{\prime }\right)\right)\mathrm{<mo>\; /\; </mo>}{\left(-{\left(c^{\prime }\right)}^3+54{\left(d^{\prime }\right)}^2+36e^{\prime }{c}^{\prime }+6{\left(A\mathrm{<mo>\; /\; </mo>144}\right)}^{\frac{1}{2}}\right)}^{\frac{1}{3}}\\ =\left[\sqrt[3]{4}\left({\left(c^{\prime }\right)}^2+12e^{\prime }\right)+{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{2}{3}}\right]\\ \mathrm{<mo>\; /\; </mo>}\left[3\sqrt[3]{2}{\left(-2{\left(c^{\prime }\right)}^3+108{\left(d^{\prime }\right)}^2+72e^{\prime }{c}^{\prime }+A^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right]\\ =\Delta \end{array}$

So we get

${\lambda }_1=\frac{1}{2}[{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}}$

$\begin{array}{c}+(\frac{4}{3}\left(ab+bc+bd+cd\right)-\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}+3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\\ +4bcd\mathrm{<mo>\; /\; </mo>}{{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\frac{1}{3}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}-3F\mathrm{<mo>\; /\; </mo>}{\left(D+6E^{\frac{1}{2}}\right)}^{\frac{1}{3}}\right)}^{\frac{1}{2}})}^{\frac{1}{2}}]\end{array}$

$\begin{array}{c}=\frac{1}{2}[{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\Delta \right)}^{\frac{1}{2}}\begin{array}{c}\\ \\ \end{array}\\ +{\left(\frac{4}{3}\left(ab+bc+bd+cd\right)-\Delta +4bcd\mathrm{<mo>\; /\; </mo>}{\left(\frac{2}{3}\left(ab+bc+bd+cd\right)+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}]\\ =\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }\mathrm{<mo>\; /\; </mo>}{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right]\\ =\rho (\; G\; )\end{array}$

It is consistent with the spectral radius obtained as above.

This completes the proof. □

Example 1. Solve the spectral radius of graph $G=G_{4}o\left(5,6,3,4,6\right)$ .

By employing maple 13.0 to calculate, we can get that 1.5808, −5.3747, −9.5359, 13.3297 are the nonzero eigenvalues of the graph G. By comparison, it is obvious that 13.3297 is the spectral radius of the graph G.

Theorem 3.2. Let $G\in N\left(G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_9\right)$ . Then the energy of graph G as follows, where the notations is defined as same as above Theorem.

(i) If $G\in N\left(G_1\right)$ . Then

$E\left(G\right)=2{\left(ab\right)}^{\frac{1}{2}}+2{\left(cd\right)}^{\frac{1}{2}}\mathrm{.}$

(ii) If $G\in N\left(G_2\right)$ . Then

$E\left(G\right)=2{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\mathrm{.}$

(iii) If $G\in N\left(G_3\right)$ .Then

$E\left(G\right)=2{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\mathrm{.}$

(iv) If $G\in N\left(G_4\right)$ . Then

$E\left(G\right)=2{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\mathrm{.}$

(v) If $G\in N\left(G_5\right)$ . Then

$E\left(G\right)=2{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\mathrm{.}$

(vi) If $G\in N\left(G_6\right)$ . Then

$E\left(G\right)={\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }\mathrm{<mo>\; /\; </mo>}{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\mathrm{.}$

(vii) If $G\in N\left(G_7\right)$ . Then

$E\left(G\right)=2{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\mathrm{.}$

(viii) If $G\in N\left(G_8\right)$ . Then

$\begin{array}{c}E\left(G\right)={\left[2ab+2bc+2cd+2{\left({\left(ab+bc+cd\right)}^2-4abcd\right)}^{\frac{1}{2}}\right]}^{\frac{1}{2}}\\ +{\left[2ab+2bc+2cd-2{\left({\left(ab+bc+cd\right)}^2-4abcd\right)}^{\frac{1}{2}}\right]}^{\frac{1}{2}}\mathrm{.}\end{array}$

(ix) If $G\in N\left(G_9\right)$ . Then

$\begin{array}{c}E\left(G\right)=[2ab+2bc+2cd+2de+2({\left(ab+bc+cd+de\right)}^2-4(abcd+bcde\begin{array}{c}\\ \end{array}\\ +{{abde))}^{\frac{1}{2}}]}^{\frac{1}{2}}+[2ab+2bc+2cd+2de-2({\left(ab+bc+cd+de\right)}^2\begin{array}{c}\\ \end{array}\\ -{{4\left(abcd+bcde+abde\right))}^{\frac{1}{2}}]}^{\frac{1}{2}}\mathrm{.}\end{array}$

Proof. Here we only consider the cases $G\in N\left(G_2\right)$ . The proof of other cases is quite similar to $G\in N\left(G_2\right)$ and is thus omitted.

The proof of Theorem 3.2 follows from Theorem 3.1. So we have

${\lambda }_1=\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }/{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right],$

${\lambda }_2=\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}-{\left(\frac{4}{3}{c}^{\prime }-\Delta +4d^{\prime }/{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right],$

${\lambda }_3=-\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}+{\left(\frac{4}{3}{c}^{\prime }-\Delta -4d^{\prime }/{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right],$

${\lambda }_4=-\frac{1}{2}\left[{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}-{\left(\frac{4}{3}{c}^{\prime }-\Delta -4d^{\prime }/{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\right)}^{\frac{1}{2}}\right].$

Due to ${\lambda }_3,{\lambda }_4<0$ , ${\lambda }_1,{\lambda }_2>0$ , we get

$\begin{array}{c}E\left(G\right)=\left|{\lambda }_1\right|+\left|{\lambda }_2\right|+\left|{\lambda }_3\right|+\left|{\lambda }_4\right|\\ ={\lambda }_1+{\lambda }_2-{\lambda }_3-{\lambda }_4\\ =2{\left(\frac{2}{3}{c}^{\prime }+\Delta \right)}^{\frac{1}{2}}\end{array}$

It is consistent with the energy obtained as above.

This completes the proof. □

4. The Spectral Characterization of Graphs with Rank 4

In this section, we will investigate which graph $G\in N\left(G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_9\right)$ is DS and find some cospectral graphs.

Theorem 4.1. Let $G={G^{\prime }}_4\cup r{K}_1$ , where $a=b=e=1$ in ${G^{\prime }}_4$ . Then G is DS.

Proof. Suppose that G has $3+c^{\prime }+d^{\prime }+r$ vertices. Checking G, we note that it only contains one triangle. This implies, by Lemma 2.2 (v), that if graph H is cospectral with G, then H must contain one triangle. By Lemma 2.1 and Lemma 2.4, ${G^{\prime }}_2\cup g{K}_1$ (here $b=c=d=1$ in ${G^{\prime }}_2$ ), ${G^{\prime }}_3\cup m{K}_1$ (here $a=b=c=1$ in ${G^{\prime }}_3$ ) and ${G^{\prime }}_5\cup w{K}_1$ (here $b=c=f=1$ in ${G^{\prime }}_5$ ) contains one triangle, respectively. It has been proved that ${G^{\prime }}_2\cup g{K}_1$ (here $b=c=d=1$ in ${G^{\prime }}_2$ ) is DS. In the following we consider two cases.

Case 1. Assume that G and ${G^{\prime }}_3\cup m{K}_1$ are cospectral and let $1\le d\le e$ , $1\le c^{\prime }\le d^{\prime }$ . Therefore, G and ${G^{\prime }}_3\cup m{K}_1$ have the same vertices and coefficients of their characteristic polynomials. By Lemma 2.4 (iv) and (iii), we have

$(\begin{array}{l}3+c^{\prime }+d^{\prime }+r=3+d+e+m\\ 3+c^{\prime }+d^{\prime }+c^{\prime }{d}^{\prime }=3+d+e\\ c^{\prime }+d^{\prime }+2c^{\prime }{d}^{\prime }=d+e+de\end{array}$

Solving the equation system as above, we obtain that $r-m=c^{\prime }{d}^{\prime }=de$ , which implies $d=c^{\prime }{d}^{\prime }/e$ and $r-m>0$ . By $3+c^{\prime }+d^{\prime }+r=3+d+e+m$ and $r-m>0$ , we can obtain that $d+e>c^{\prime }+d^{\prime }$ . Taking $d=c^{\prime }{d}^{\prime }/e$ into $d+e>c^{\prime }+d^{\prime }$ , we obtain that $e^2-\left(c^{\prime }+d^{\prime }\right)e+c^{\prime }{d}^{\prime }>0$ . Solving this equation, we obtain that $e>d^{\prime }$ or $e<c^{\prime }$ . However, by $c^{\prime }{d}^{\prime }=de$ and $1\le d\le e$ , $1\le c^{\prime }\le d^{\prime }$ , we obtain that $c^{\prime }\le d\le e\le d^{\prime }$ or $d\le c^{\prime }\le d^{\prime }\le e$ , which in contradict with $e>d^{\prime }$ or $e<c^{\prime }$ . Hence G and ${G^{\prime }}_3\cup m{K}_1$ are not cospectral.

Case 2. Assume that G and ${G^{\prime }}_5\cup w{K}_1$ are cospectral. Therefore, G and ${G^{\prime }}_5\cup w{K}_1$ have the same vertices and coefficients of their characteristic polynomials. By Lemma 2.4 (iv) and (v), we obtain that

$(\begin{array}{l}3+c^{\prime }+d^{\prime }+r=3+a+d+e+w\\ 3+c^{\prime }+d^{\prime }+c^{\prime }{d}^{\prime }=3+a+d+e+ed\\ c^{\prime }+d^{\prime }+2c^{\prime }{d}^{\prime }=a+d+e+ad+ae+2ed+aed\end{array}$

Solving the equation system as above, we have

$(\begin{array}{l}w-r=ed-c^{\prime }{d}^{\prime }\\ c^{\prime }{d}^{\prime }=ad+ae+ed+aed\\ c^{\prime }+d^{\prime }+c^{\prime }{d}^{\prime }=a+d+e+ed\end{array}$

By $c^{\prime }{d}^{\prime }=ad+ae+ed+aed$ , we obtain that $c^{\prime }=\left(ad+ae+ed+aed\right)/d^{\prime }$ . Taking $c^{\prime }=\left(ad+ae+ed+aed\right)/d^{\prime }$ into $c^{\prime }+d^{\prime }+c^{\prime }{d}^{\prime }=a+d+e+ed$ , we obtain that ${d^{\prime }}^2+\left(ad+ae+aed-a-d-e\right)d^{\prime }+ad+ae+ed+aed=0$ . Supposing the roots of the equation as above are $d_{11}\mathrm{,}{d}_{12}$ , we have

$(\begin{array}{l}{d}_{11}+d_{12}=a\left(1-d\right)+d\left(1-ae\right)+e\left(1-a\right)\\ d_{11}{d}_{12}=ad+ae+ed+aed\end{array}$

By the definition of ${G^{\prime }}_5$ , one has $a\mathrm{,}e\mathrm{,}d\ge 1$ , which implies that $d_{11}+d_{12}\le 0$ , $d_{11}{d}_{12}>0$ . By $d_{11}{d}_{12}>0$ , we know that $d_{11}\mathrm{,}{d}_{12}$ are nonzero and have the same sign. However, by $d_{11}+d_{12}\le 0$ , we know that $d_{11},d_{12}<0$ . This contradicts the fact $d_{11}\mathrm{,}{d}_{12}\mathrm{<mo>\; >\; </mo>0}$ . Thus, G and ${G^{\prime }}_5\cup w{K}_1$ are not cospectral.

Next, assume that $G_{4}o\left(\mathrm{1,1,}{c}^{\prime }\mathrm{,}{d}^{\prime }\mathrm{,1}\right)$ and $G_{4}o\left(\mathrm{1,1,}{c^{\prime }}^{\prime }\mathrm{,}{d^{\prime }}^{\prime }\mathrm{,1}\right)$ are cospectral and ${c^{\prime }}^{\prime }<c^{\prime }\le d^{\prime }<{d^{\prime }}^{\prime }$ . Therefore, they have the same vertices and coefficients of their characteristic polynomials. By Lemma 2.4 (iv), we get that

$(\begin{array}{l}3+{c^{\prime }}^{\prime }+{d^{\prime }}^{\prime }=3+c^{\prime }+d^{\prime }\\ 3+{c^{\prime }}^{\prime }+{d^{\prime }}^{\prime }+{c^{\prime }}^{\prime }{d^{\prime }}^{\prime }=3+c^{\prime }+d^{\prime }+c^{\prime }{d}^{\prime }\\ {c^{\prime }}^{\prime }+{d^{\prime }}^{\prime }+2{c^{\prime }}^{\prime }{d^{\prime }}^{\prime }=c^{\prime }+d^{\prime }+2c^{\prime }{d}^{\prime }\end{array}$

Solving the equation system as above, we obtain that ${c^{\prime }}^{\prime }+{d^{\prime }}^{\prime }=c^{\prime }+d^{\prime }$ , ${c^{\prime }}^{\prime }{d^{\prime }}^{\prime }=c^{\prime }{d}^{\prime }$ . By ${c^{\prime }}^{\prime }{d^{\prime }}^{\prime }=c^{\prime }{d}^{\prime }$ , we obtain that ${c^{\prime }}^{\prime }=c^{\prime }{d}^{\prime }/{d^{\prime }}^{\prime }$ . Taking ${c^{\prime }}^{\prime }=c^{\prime }{d}^{\prime }/{d^{\prime }}^{\prime }$ into ${c^{\prime }}^{\prime }+{d^{\prime }}^{\prime }=c^{\prime }+d^{\prime }$ , we have ${{d^{\prime }}^{\prime }}^2-\left(c^{\prime }+d^{\prime }\right){d^{\prime }}^{\prime }+c^{\prime }{d}^{\prime }=0$ . Solving this equation, we obtain that ${d^{\prime }}^{\prime }=c^{\prime }$ or ${d^{\prime }}^{\prime }=d^{\prime }$ . If ${d^{\prime }}^{\prime }=c^{\prime }$ , ${c^{\prime }}^{\prime }<d^{\prime }$ , then we have ${c^{\prime }}^{\prime }+{d^{\prime }}^{\prime }<c^{\prime }+d^{\prime }$ , a contradiction; If ${d^{\prime }}^{\prime }=d^{\prime }$ , $c^{\prime }>{c^{\prime }}^{\prime }$ , then we have ${c^{\prime }}^{\prime }+{d^{\prime }}^{\prime }<c^{\prime }+d^{\prime }$ , a contradiction. Thus, $G_{4}o\left(\mathrm{1,1,}{c}^{\prime }\mathrm{,}{d}^{\prime }\mathrm{,1}\right)$ and $G_{4}o\left(\mathrm{1,1,}{c^{\prime }}^{\prime }\mathrm{,}{d^{\prime }}^{\prime }\mathrm{,1}\right)$ are not cospectral.

From the argument above, we obtain that G is DS. □

Theorem 4.2. Let $G={G^{\prime }}_3$ , where $a=b=c=1$ in ${G^{\prime }}_3$ . Then G is DS if and only if $w\ne ed$ or ${e^{\prime }}^2-\left(a+d+e+de\right)e^{\prime }+ad+ae+de+aed=0$ has no positive integer solution.

Proof. Suppose that G has $3+d^{\prime }+e^{\prime }$ vertices. By Lemma 2.2 (v), we know if graph H is cospectral with graph G, then H must contain one triangle. By Lemma 2.1 and Theorem 2.4, ${G^{\prime }}_2\cup g{K}_1$ (here $b=c=d=1$ ), ${G^{\prime }}_4\cup r{K}_1$ (here $a=b=e=1$ ) and ${G^{\prime }}_5\cup w{K}_1$ (here $b=c=f=1$ ) contain one triangle, respectively. It has been proved that ${G^{\prime }}_2\cup g{K}_1$ (here $b=c=d=1$ ) is DS. In the following we consider two cases.

Case 1. Assume that G and ${G^{\prime }}_4\cup r{K}_1$ are cospectral and let $1\le d^{\prime }\le e^{\prime }$ , $1\le c\le d$ . Therefore, G and ${G^{\prime }}_4\cup r{K}_1$ have the same vertices and coefficients of their characteristic polynomials. By Lemma 2.4 (iii) and (iv), we have

$(\begin{array}{l}3+d^{\prime }+e^{\prime }=3+c+d+r\\ 3+d^{\prime }+e^{\prime }=3+c+d+cd\\ s+e^{\prime }+d^{\prime }{e}^{\prime }=c+d+2cd\end{array}$

Solving the equation system as above, we obtain that $r=cd=d^{\prime }{e}^{\prime }$ , which implies that $d^{\prime }=cd/e^{\prime }$ and $r>0$ . By $3+d^{\prime }+e^{\prime }=3+c+d+r$ and $r>0$ , we can obtain that $d^{\prime }+e^{\prime }>c+d$ . Taking $d^{\prime }=cd/e^{\prime }$ into $d^{\prime }+e^{\prime }>c+d$ , we obtain that ${e^{\prime }}^2-\left(c+d\right)e^{\prime }+cd>0$ . Solving the equation as above, we obtain that $e^{\prime }>d$ or $e^{\prime }<c$ . However, by $cd=d^{\prime }{e}^{\prime }$ , $1\le d^{\prime }\le e^{\prime }$ , $1\le c\le d$ , we obtain that $c\le d^{\prime }\le e^{\prime }\le d$ or $d^{\prime }\le c\le d\le e^{\prime }$ , which in contradict with $e^{\prime }>d$ or $e^{\prime }<c$ . Thus, G and ${G^{\prime }}_4\cup r{K}_1$ are not cospectral.

Case 2. Assume that G and ${G^{\prime }}_5\cup w{K}_1$ are cospectral. Therefore, G and ${G^{\prime }}_5\cup w{K}_1$ have the same vertices and coefficients of their characteristic polynomials. By Lemma 2.4 (iii) and (v), we have

$(\begin{array}{l}3+d^{\prime }+e^{\prime }=3+a+d+e+w\\ 3+d^{\prime }+e^{\prime }=3+a+d+e+ed\\ s+d^{\prime }+d^{\prime }{e}^{\prime }=a+d+e+ad+ae+2ed+aed\end{array}$

Solving the equation system as above, we have

$(\begin{array}{l}w=ed\\ d^{\prime }{e}^{\prime }=ad+ae+ed+aed\\ d^{\prime }+e^{\prime }=a+d+e+2ed\end{array}$

By $d^{\prime }{e}^{\prime }=ad+ae+ed+aed$ , we obtain that $d^{\prime }=\left(ad+ae+ed+aed\right)/e^{\prime }$ . Taking $d^{\prime }=\left(ad+ae+ed+aed\right)/e^{\prime }$ into $d^{\prime }+e^{\prime }=a+d+e+2ed$ , we obtain that ${e^{\prime }}^2-\left(a+d+e+de\right)e^{\prime }+ad+ae+de+aed=0$ . If $w=ed$ and ${e^{\prime }}^2-\left(a+d+e+de\right)e^{\prime }+ad+ae+de+aed=0$ has positive integer solution are satisfied at the same time, then G and ${G^{\prime }}_5\cup w{K}_1$ are cospectral. On the contrary, G and ${G^{\prime }}_5\cup w{K}_1$ are not cospectral.

Then, assume that $G_{3}o\left(\mathrm{1,1,1,}{d}^{\prime }\mathrm{,}{e}^{\prime }\right)$ and $G_{3}o\left(\mathrm{1,1,1,}{d^{\prime }}^{\prime }\mathrm{,}{e^{\prime }}^{\prime }\right)$ are cospectral and let ${d^{\prime }}^{\prime }<d^{\prime }\le e^{\prime }<{e^{\prime }}^{\prime }$ . Therefore, they have the same vertices and coefficients of their characteristic polynomials. By Lemma 2.4 (iii), we have

$(\begin{array}{l}3+d^{\prime }+e^{\prime }=3+{d^{\prime }}^{\prime }+{e^{\prime }}^{\prime }\\ d^{\prime }+e^{\prime }+d^{\prime }{e}^{\prime }={d^{\prime }}^{\prime }+{e^{\prime }}^{\prime }+{d^{\prime }}^{\prime }{e^{\prime }}^{\prime }\end{array}$

Solving the equation system as above, we obtain that $d^{\prime }+e^{\prime }={d^{\prime }}^{\prime }+{e^{\prime }}^{\prime }$ , $d^{\prime }{e}^{\prime }={d^{\prime }}^{\prime }{e^{\prime }}^{\prime }$ . By $d^{\prime }{e}^{\prime }={d^{\prime }}^{\prime }{e^{\prime }}^{\prime }$ , we have $d^{\prime }={d^{\prime }}^{\prime }{e^{\prime }}^{\prime }/e^{\prime }$ . Taking $d^{\prime }={d^{\prime }}^{\prime }{e^{\prime }}^{\prime }/e^{\prime }$ into $d^{\prime }+e^{\prime }={d^{\prime }}^{\prime }+{e^{\prime }}^{\prime }$ , we have ${e^{\prime }}^2-\left({d^{\prime }}^{\prime }+{e^{\prime }}^{\prime }\right)e^{\prime }+{d^{\prime }}^{\prime }{e^{\prime }}^{\prime }=0$ . Solving the equation as above, we obtain that $e^{\prime }={d^{\prime }}^{\prime }$ or $e^{\prime }={e^{\prime }}^{\prime }$ . If $e^{\prime }={d^{\prime }}^{\prime }$ , $d^{\prime }<{e^{\prime }}^{\prime }$ . Then we have $d^{\prime }+e^{\prime }<{d^{\prime }}^{\prime }+{e^{\prime }}^{\prime }$ , which in contradict with $d^{\prime }+e^{\prime }={d^{\prime }}^{\prime }+{e^{\prime }}^{\prime }$ ; When $e^{\prime }={e^{\prime }}^{\prime }$ , $d^{\prime }>{d^{\prime }}^{\prime }$ . Then we have $d^{\prime }+e^{\prime }>{d^{\prime }}^{\prime }+{e^{\prime }}^{\prime }$ , which in contradict with $d^{\prime }+e^{\prime }={d^{\prime }}^{\prime }+{e^{\prime }}^{\prime }$ . Thus, $G_{3}o\left(\mathrm{1,1,1,}{d}^{\prime }\mathrm{,}{e}^{\prime }\right)$ and $G_{3}o\left(\mathrm{1,1,1,}{d^{\prime }}^{\prime }\mathrm{,}{e^{\prime }}^{\prime }\right)$ are not cospectral.

In conclusion, we obtain that G is DS if and only if $w\ne ed$ or ${e^{\prime }}^2-\left(a+d+e+de\right)e^{\prime }+ad+ae+de+aed=0$ has no positive integer solution.

□

Figure 2. G and H.

Corollary 4.3. Let $G={G^{\prime }}_3$ where $a=b=c=1$ in ${G^{\prime }}_3$ and $H={G^{\prime }}_5\cup k{K}_1$ where $b=c=d=e=f=1$ in ${G^{\prime }}_5$ . They are cospectral if and only if $k=1$ and ${e^{\prime }}^2-\left(a+3\right)e^{\prime }+3a+1=0$ has positive integer solution, where the graphs $G\mathrm{,}H$ are depicted in Figure 2.

Proof. By Theorem 4.2, we can obtain it obviously. □

5. Conclusion

In this paper, we give the expressions of the spectral radius and energy of all graphs with rank 4. At the same time, we investigate some graph $G\in N\left(G_1\mathrm{,}{G}_2\mathrm{,}\cdots \mathrm{,}{G}_9\right)$ is DS and find some cospectral graphs.

Acknowledgements

This work is supported by the planning project of Qinghai Minzu University (No. 2021XJXS18), the innovation project of Qinghai Minzu University (No. 07M2022001).

Conflicts of Interest

The author declares that they have no conflicts of interest.

References

[1]	Li, X., Shi, Y. and Gutman, I. (2012) Graph Energy. Springer, New York. https://doi.org/10.1007/978-1-4614-4220-2
[2]	Gutman, I. (2001) The Energy of a Graph: Old and New Results. In: Betten, A., Kohnert, A., Laue, R. and Wassermann, A., Eds., Algebraic Combinatorics and Applications, Springer-Verlag, Berlin, 196-211. https://doi.org/10.1007/978-3-642-59448-9_13
[3]	Gutman, I., Li, X. and Zhang, J. (2009) Graph Energy. In: Dehmer, M. and Emmert-Streib, F., Eds., Analysis of Complex Networks, From Biology to Linguistics, Wiley-VCH, Weinheim, 145-174. https://doi.org/10.1002/9783527627981.ch7
[4]	Chang, G.J., Huang, L.H. and Yeh, H.G. (2011) A Characterization of Graphs with Rank 4. Linear Algebra and its Applications, 434, 1793-1798. https://doi.org/10.1016/j.laa.2010.09.040
[5]	Wu, T., Feng, L. and Ma, H. (2016) On the Characteristic Polynomials of Graphs with Nullity n - 4. Acta Scientiarum Naturalium Universitatis Sunyatseni, 55, 57-63.
[6]	Monsalve, J. and Rada, J. (2021) External Spectral Radius of Graphs with Rank 4. Linear Algebra and its Applications, 609, 1-11. https://doi.org/10.1016/j.laa.2020.08.017
[7]	van Dam, E.R. and Haemers, W.H. (2003) Which Graphs Are Determined by Their Spectrum? Linear Algebra and its Applications, 373, 241-272. https://doi.org/10.1016/S0024-3795(03)00483-X
[8]	Bhattacharya, A., Friedland, S. and Peled, U.N. (2008) On the First Eigenvalue of Bipartite Graphs. The Electronic Journal of Combinatorics, 15, 144. https://doi.org/10.37236/868