# Aα-Spectral Characterizations of Some Joins

Authors: Tingzeng Wu; Tian Zhou
Journal: Journal of Mathematics
 (2020)

---

## Abstract

LetG be a graph with n vertices. For every real α∈0,1, write AαG for the matrix AαG=αDG+1−αAG, where AG and DG denote the adjacency matrix and the degree matrix of G, respectively. The collection of eigenvalues of AαG together with multiplicities are called the Aα-spectrum of G. A graph G is said to be determined by its Aα-spectrum if all graphs having the same Aα-spectrum as G are isomorphic to G. In this paper, we show that some joins are determined by their Aα-spectra for α∈0,1/2or1/2,1.


---

## Body

## 1. Introduction

We useG to denote a simple graph with vertex set VG=v1,v2,…,vn and edge set EG=e1,e2,…,em. The degree of a vertex v∈VG is denoted by dv. For a subgraph H of G, let G−EH denote the subgraph obtained from G by deleting the edges of H. Let ciG and piG denote, respectively, the numbers of i-cycles and i-vertex paths in G. Let c3Gv denote the number of triangles containing the vertex v of G. Let G∪H be the union of two graphs G and H which have no common vertices. For any positive integer l, let lG denote be the union of l disjoint copies of graph G. The join of two disjoint graphs G and H, denoted by G∨H, is the graph obtained by joining each vertex of G to each vertex of H. For convenience, the complete graph, path, cycle and star on n vertices are denoted by Kn, Pn, Cn, and K1,n−1, respectively.LetAG and DG denote, respectively, the adjacency matrix and degree matrix of G. For every real α∈0,1, write AαG for the matrix AαG=αDG+1−αAG. Note that A0G=AG and 2A1/2G=QG, where QG is the signless Laplacian matrix of G. The polynomial(1)ϕG=ϕG,x=detxI−AαG=∑i=1ncαiGxn−i,is called Aα-characteristic polynomial, where I is the identity matrix of order n. The theory of Aα-characteristic polynomial of a graph is well elaborated [1–8].TheAα-spectrum of G is a collection of roots of ϕG together with multiplicities. Two graphs are said to be Aα-cospectral if they have the same Aα-spectrum. A graph is called an Aα-DS graph if it is determined by its Aα-spectrum, meaning that there exists no other graph that is nonisomorphic to it but Aα-cospectral with it.It is interesting to characterize which graph is determined by some graph spectrum [9–11]. The problem was raised by Günthard and Primas [12] in 1956 with motivations from chemistry. In recent years, although many graphs have been proved to be DS graphs, the problem of determining DS graphs is still far from being completely solved [13, 14]. Recently, Lin et al. [15] considered the problem which graph is determined by its Aα-spectrum? And they gave some characterizing properties of Aα-spectrum and proposed the following problem.Problem 1.
Characterizing graphsG determined by their Aα-spectra such that G∨Kmm≥1 is also determined by their Aα-spectra for α∈0,1/2 or 1/2,1.
Liu and Lu [16] discussed the problem which join graph is determined by its Q-spectrum? And they pointed out the following problem.Problem 2.
Prove or disprove thatKn¯∨Km is determined by its Q-spectrum for m≥3.
In this paper, we focus on Problem1 above, and we prove that some join graphs are Aα-DS graphs. Furthermore, we also give a special solution for Problem 2. The rest of this paper is organized as follows. In Section 2, we present some characterizing properties of the Aα-spectrum of graphs and give the formula to compute c3Gv in Kn−EH, where H is a subgraph of Kn with l edges. In Section 3, we give a solution for Problem 1.


## 2. Preliminaries

LetGn denote the set of graphs each of which is obtained from Kn by removing five or fewer edges. For n≥10, there exist exactly 45 nonisomorphic graphs each of which is obtained from Kn by removing five or fewer edges [17]. These graphs are labeled by Gij, 1≤i≤5and0≤j≤25 and illustrated in Figure 1. Checking the structure of Gij, we know that Gij=H∨Km, where H is a graph obtained form Kt deleting some edges, and t+m=n, e.g., G44=K4−EC4∨Kn−4.Figure 1
The graphs obtained fromKn by deleting five or fewer edges drawn as lines in a disk.Cámara and Haemers [18] discussed the problem which Gij∈Gn is determined by its A0-spectrum. And they gave the following result.Theorem 1 (see [18]).
LetG∈Gn be a graph with n≠7 vertices. Then, G is A0-DS graph.Lemma 1 (see [19]).
LetH⊆Kn be a graph with l edges and let G=Kn−EH. Then,(2)c3G=n3−ln−2+∑v∈VHdv2−c3H.By Lemma1, the number of triangles of some G∈Gn is calculated [17], see Table 1.Table 1
The numbers of triangles of some graphs inGn.
Graphc3GGraphc3GG30n3−3n+9G59,G524n3−5n+17G31n3−3n+7G42,G45,G48n3−4n+10G40n3−4n+14G44,G46,G410n3−4n+12G43n3−4n+9G50,G51,G514n3−5n+12G52n3−5n+11G55,G512,G520,G523n3−5n+15G54n3−5n+20G58,G511,G513,G517n3−5n+13G32,G33n3−3n+8G53,G57,G518,G519,G522n3−5n+14G41,G47n3−4n+11G56,G510,G515,G516,G525n3−5n+16Lemma 2 (see [17]).
LetH⊆Kn be a graph with l edges and let G=Kn−EH. Then,(3)c4G=3n4−2ln−22+2l2+n−5∑v∈VHdv2−p4H+c4H.By Lemma2, the number of quadrangles of some G∈Gn is calculated [17], see Table 2.Using the Principle of Inclusion-Exclusion, we can obtain the following result.Table 2
The numbers of quadrangles of some graphs inGn.
Graphc4GGraphc4GG423n4−4n2+22n−22G483n4−4n2+22n−23G503n4−5n2+27n−21G513n4−5n2+27n−20G533n4−5n2+29n−32G573n4−5n2+29n−30G553n4−5n2+30n−38G5233n4−5n2+30n−39G5113n4−5n2+28n−26G5173n4−5n2+28n−27G5193n4−5n2+29n−33G5223n4−5n2+29n−33Lemma 3.
LetH⊆Kn be a graph with k edges and let G=Kn−EH. Let v∈VG, and let v be an endpoint of l≤k edges in EH. Then,(4)c3Gv=n−12−k−l−ln−1−l+c3G¯v+|P3|−l2.Proof.
LetEH=e1,e2,…,ek. Let Si denote the set of triangles of Kn containing eii=1,2,…,k and v. Thus, there exists exactly n−12 triangles containing v in Kn. By the Inclusion-Exclusion Principle, we have(5)c3Gv=n−12−∑i=1lSi+∑i<jSi∩Sj−∑i<j<kSi∩Sj∩Sk.
For any edgeei, if v is an endpoint of ei, then there exists n−1−l triangles containing ei. Otherwise, there exists k−l triangles containing ei. So, ∑i=1lSi=ln−1−l+k−l. For any given ei and ej, if v is a common endpoint of ei and ej, then there exists c3G¯v triangles containing ei and ej. Otherwise, there exists P3 triangles containing ei and ej in G¯, where P3 is a path which v is origin endpoint and P3 is the number of vertices with length 2 to v. Thus, ∑i<jSi∩Sj=c3G¯v+P3. Since any two edges in l edges induce a triangle, ∑i<j<kSi∩Sj∩Sk=l2. By the above arguments, we arrive in equation (4).Lemma 4 (see [20] and [5]).
LetG be a graph with n vertices and m edges, and let d1,d2,…,dn be the degree sequence of G. Suppose that ϕAαG,x=∑jcαjxn−j. Then,(i)
cα0=1(ii)
cα1=−2αm(iii)
cα2=2α2m2−1−α2m−1/2α2∑idi2(iv)
cα3=−21−α3c3G+2α1−α2m2−α1−α2∑idi2−1/3α34m3−3m∑idi2+∑idi3(v)
cα4=−1/4α4∑idi4−α21−α2∑idi3+2/3α4m∑idi3+5/2α21−α2m∑idi2−α4m2∑idi2−1/21−α4∑idi2+1/8α4∑idi22−α21−α2∑vivj∈EGdidj−2α1−α3∑idic3Gvi+4α1−α3mc3G−21−α4c4G+2/3α4m4−2α21−α2m3+1/21−α4m2+1/21−α4mFor convenience, by Lemmas3 and 4, we calculate the value ∑idic3Gvi of some graphs in Gn, see Table 3.Table 3
The value∑idic3Gvi of some graphs in Gn.
Graph∑idic3GviGraph∑idic3GviG421/2n4−2n3−27/2n2+65n−50G481/2n4−2n3−27/2n2+65n−52G501/2n4−2n3−35/2n2+79n−48G511/2n4−2n3−35/2n2+79n−46G531/2n4−2n3−35/2n2+89n−79G571/2n4−2n3−35/2n2+89n−75G5191/2n4−2n3−35/2n2+89n−80G5221/2n4−2n3−35/2n2+89n−78G5111/2n4−2n3−35/2n2+84n−61G5171/2n4−2n3−35/2n2+84n−63G551/2n4−2n3−35/2n2+94n−94G5231/2n4−2n3−35/2n2+94n−96G561/2n4−2n3−35/2n2+99n−110G5251/2n4−2n3−35/2n2+99n−112Lemma 5 (see [21]).
LetG and H be two graphs with n vertices. For α∈0,1, if G and H are Aα-cospectral, then the following statements hold:(i)
VG=VH.(ii)
EG=EH.(iii)
IfG is r-regular, then H is r-regular.Suppose thatd1≥d2≥⋯≥dn and d1′≥d2′≥⋯≥dn′ are the degree sequences of G and H, respectively. If G and H are Aα-cospectral with α∈0,1, then(iv)
∑1≤i<j≤ndidj=∑1≤i<j≤ndi′dj′.(v)
∑1≤i≤ndi2=∑1≤i≤ndi′2.Lemma 6 (see [21]).
The complete graphKn is determined by its Aα-spectrum.Lemma 7 (see [21]).
The graphkK2∪n−2kK1¯ is determined by its Aα-spectrum, where 1≤k≤⌊n/2⌋ and 0≤α≤1.By Lemma7, we can obtain a corollary as follows.Corollary 1.
GraphsG10, G21, G34, G49, and G521 are determined by their Aα-spectra, where 0≤α≤1.The M-coronal of ann×n square matrix M, denoted by ΓMx, is defined to be the sum of the entries of the matrix xIn−M−1, that is,(6)ΓMx=1nTxIn−M−11n,where 1n denotes the column vector of size n with all the entries equal to one and 1nT means the transpose of 1n ([22, 23]).Lemma 8 (see [16]).
IfG is an arbitrary graph and H1 and H2 are Q-cospectral graphs with ΓQH1x=ΓQH2x, then G∨H1 and G∨H2 are Q-cospectral.By Lemma8, we obtain directly the following corollary.Corollary 2.
IfG is an arbitrary graph and H1 and H2 are Q-cospectral graphs with ΓQH1x=ΓQH2x, then G∨H1 and G∨H2 are A1/2-cospectral.Lemma 9.
The each of following holds:(i)
Km−ElK2∨K4−EK1,3 and Km−ElK2∨K4−EK3 are A1/2-cospectral, where 0≤l≤⌊m/2⌋(ii)
Km−EPl∨K4−EK1,3 and Km−EPl∨K4−EK3 are A1/2-cospectral, where 2≤l≤mProof.
Directly calculating the signless Laplacian polynomials ofK4−EK1,3 and K4−EK3 yield det|xI−QK4−EK1,3|=det|xI−QK4−EK3|=x4−6x3+9x2+4x. Furthermore, by simple computations, we have ΓQK4−EK1,3x=ΓQK4−EK3x=4x−1/xx−4. By Corollary 2, it is easy to see that the results in Lemma 9 hold.
By Lemma9, we obtain some A1/2-cospectral mates in Gn.Corollary 3.
The following results hold:(i)
GraphsG30 and G32 are A1/2-cospectral(ii)
GraphsG41 and G45 are A1/2-cospectral(iii)
GraphsG58 and G514 are A1/2-cospectral(iv)
GraphsG57 and G513 are A1/2-cospectralRemark 1.
By Corollaries1 and 3, we know that K2¯∨Km=G10 is a Q-DS graph, and K3¯∨Km=G30 and G32 are Q-cospectral. These results answer the special case of Problem 2.


## 3. Main Results

In this section, we show that all graphs inGn are determined by their Aα-spectra.Theorem 2.
GraphsG20 and G21 are Aα-DS graphs, where 0<α≤1.Proof.
The result follows from Lemma5 and Corollary 1.Theorem 3.
Let G be a graph obtained fromKn by deleting three edges, and then G is determined by the Aα-spectra when α∈0,1/2∪1/2,1.Proof.
Checking Figure1, we know that G is isomorphic to one of {G30, G31, G32, G33, G34}. Directly computing yields ∑i=1ndi2G31=n3−2n2−11n+20, ∑i=1ndi2G33=n3−2n2−11n+22, and ∑i=1ndi2G30=∑i=1ndi2G32=n3−2n2−11n+24. By Lemma 4 (iv) and Table 1, we have(7)cα3G32−cα3G30=21−α3c3G30−c3G32+13α3∑idi3G30−∑idi3G32=21−α3−2α3=2−6α+6α2−4α3.
Solving equation(8)4α3−6α2+6α−2=0,we have α=1/2, 1/2+3i/2, or 1/2−3i/2. This implies that cα3G32≠cα3G30 for α∈0,1/2∪1/2,1.
By Corollaries1 and 3 (i) and Lemma 7 (i), (ii), and (v), the result in Theorem 3 holds.Remark 2.
By the proof of Theorem3, it can be known that G31, G33, and G34 are determined by their Q-spectra.Lemma 10.
Each of the following holds:(i)
GraphsG44 and G410 are not Aα-cospectral, where α∈0,1/2∪1/2,1(ii)
GraphsG42 and G48 are not Aα-cospectral, where α∈0,1/2∪1/2,1(iii)
GraphsG41, G45, and G47 are not pairwise Aα-cospectral, where α∈0,1/2∪1/2,1Proof.
(i)
By Lemma4 (iv) and Table 1, we have cα3G44−cα3G410=2α3. Solving equation(9)2α3=0,we obtainα=0, 0 or 0. It implies that G42 and G48 are not Aα-cospectral, when α∈0,1/2∪1/2,1.(ii)
By Lemma4 (v) and Tables 1–3, we obtain that(10)cα4G48−cα4G42=−2α−14−α2α−12+4αα−13.Solving equation(11)−2α−14−α2α−12+4αα−13=0,we haveα=1, 1, 2, or −2. This indicates that G42 and G48 are not Aα-cospectral when α∈0,1/2∪1/2,1.(iii)
Similarly, by Lemma4 (iv) and Table 1, we obtain that(12)cα3G41−cα3G45=4α3−6α2+6α−2,cα3G41−cα3G47=2α3,cα3G45−cα3G47=−2α3+6α2−6α+2.Solving equation(13)−2α3+6α2−6α+2=0,we obtainα=1, 1 or 1. By the roots of equations (8), (9), and (13), we know that G41, G45, and G47 are not pairwise Aα-cospectral when α∈0,1/2∪1/2,1.Theorem 4.
GraphsG40, G41, G42, G43, G44, G45, G46, G47, G48, G49, and G410 are determined by their Aα-spectra, respectively, where α∈0,1/2∪1/2,1.Proof.
By simple computations, we obtain that∑i=1ndi2G40=n3−2n2−15n+36, ∑i=1ndi2G43=n3−2n2−15n+26,∑i=1ndi2G46=n3−2n2−15n+34, ∑i=1ndi2G42=∑i=1ndi2G48=n3−2n2−15n+28, ∑i=1ndi2G41=∑i=1ndi2G45=∑i=1ndi2G47=n3−2n2−15n+30, and ∑i=1ndi2G44=∑i=1ndi2G410=n3−2n2−15n+32.
By Corollaries1 and 3 (ii) and Lemmas 5 and 10, graphs G40, G41, G42, G43, G44, G45, G46, G47, G48, G49, and G410 are Aα-DS graphs, where α∈0,1/2∪1/2,1.Lemma 11.
Each of the following holds:(i)
GraphsG50 and G51 are not Aα-cospectral, where α∈0,1/2∪1/2,1(ii)
GraphsG59 and G516 are not Aα-cospectral, where α∈1/2,1(iii)
GraphsG510 and G524 are not Aα-cospectral, where α∈1/2,1(iv)
GraphsG53, G57, G513, G519, and G522 are not pairwise Aα-cospectral, where α∈0,1/2∪1/2,1.(v)
GraphsG55, G518, G520, and G523 are not pairwise Aα-cospectral, where α∈0,1/2∪1/2,1(vi)
GraphsG56, G512, G515, and G525 are not pairwise Aα-cospectral, where α∈1/2,1(vii)
GraphsG58, G511, G514, and G517 are not pairwise Aα-cospectral, where α∈0,1/2∪1/2,1Proof.
(i)
By Lemma4 (v) and Tables 1–3, we have(14)cα4G50−cα4G51=2α−14+α2α−12−4αα−13.By the roots of equations (11), we know that G50 and G51 not Aα-cospectral when α∈0,1/2∪1/2,1.(ii) By Lemma4 (iv) and Table 1, we have cα3G59−cα3G516=6α3−6α2+6α−2. Solving equation(15)6α3−6α2+6α−2=0,we haveα=43+−23+1/3<1/2, 243+−23−3i−1+2/6, or 2−23+43−3i−1+2/6. It implies that G59 and G516 are not Aα-cospectral when α∈1/2,1.(iii)
Similarly, by Lemma4 (iv) and Table 1, we have cα3G510−cα3G524=6α3−6α2+6α−2. By the roots of equation (15), we know that G510 and G524 are not Aα-cospectral, where α∈1/2,1.(iv)
Analogously, by Lemma4 (iv) and (v) and Tables 1–3, we obtain that(16)cα4G53−cα4G57=4α−14+2α2α−12−8αα−13,cα3G53−cα3G513=4α3−6α2+6α−2,cα3G53−cα3G519=2α3,cα3G53−cα3G522=2α3,cα3G57−cα3G513=4α3−6α2+6α−2,cα3G57−cα3G519=2α3,cα3G57−cα3G522=2α3,cα3G513−cα3G519=−2α3+6α2−6α+2,cα3G513−cα3G522=−2α3+6α2−6α+2,cα4G519−cα4G522=α2α−12−4αα−13,cα4G517−cα4G511=2α−14+α2α−12−4αα−13.Solving equation(17)α2α−12−4αα−13=0,we obtainα=0, 1, 1, or 4/3. By the roots of equations (8), (9), (11), (13), and (17), we obtain that G53, G57, G513, G519, and G522 are not pairwise Aα−cospectral when α∈0,1/2∪1/2,1.(v)
Similarly, by Lemma4 (iv) and (v) and Tables 1–3, we obtain that(18)cα3G55−cα3G518=2α3−6α2+6α−2,cα3G55−cα3G520=2α3,cα4G55−cα4G523=−2α−14−α2α−12+4αα−13,cα3G518−cα3G520=6α2−6α+2,cα3G518−cα3G523=−2α3+6α2−6α+2,cα3G520−cα3G523=−2α3.Solving equation(19)6α2−6α+2=0,we obtainα=3+3i/6 or 3−3i/6. By the roots of equations (9), (11), (13), and (19), we obtain that G55, G518, G520, and G523 are not pairwise Aα−cospectral when α∈0,1/2∪1/2,1.(vi)
By Lemma4 (iv) and (v) and Tables 1–3, we have(20)cα3G56−cα3G512=8α3−6α2+6α−2,cα3G56−cα3G515=6α3,cα4G56−cα4G525=4α3,cα3G512−cα3G515=−2α3+6α2−6α+2,cα3G512−cα3G525=−4α3+6α2−6α+2,cα3G515−cα3G525=−2α3.Solving equation(21)8α3−6α2+6α−2=0,we obtainα=93+−33+1/4<1/2, 293+−33−3i−1+2/8, or 2−33+93−3i−1+2/8. By the roots of equations (8), (11), (13), and (21), we obtain that G56, G512, G515, and G525 are not Aα-cospectral when α∈1/2,1.(vii)
Finally, by Lemma4 (iv) and (v) and Tables 1–3, we have(22)cα3G58−cα3G511=2α3,cα3G58−cα3G514=4α3−6α2+6α−2,cα3G58−cα3G517=2α3,cα3G511−cα3G514=2α3−6α2+6α−2,cα4G511−cα4G517=−2α−14−α2α−12+4αα−13,cα3G514−cα3G517=−2α3+6α2−6α+2.By the roots of equations (8), (9), (11), and (13), we obtain that G58, G511, G514, and G517 are not Aα-cospectral when α∈0,1/2∪1/2,1.Theorem 5.
GraphsG50, G51, G52, G53, G54, G55, G56, G57, G58, G59, G510, G511, G512, G513, G514, G515, G516, G517, G518, G519, G520, G522, G523, G524, and G525 are, respectively, determined by their Aα-spectra, where when α∈1/2,1.Proof.
By simple computations, we have that∑i=1ndi2G50=∑i=1ndi2G51=n3−2n2−19n+34, ∑i=1ndi2G52=n3−2n2−19n+32, ∑i=1ndi2G53=∑i=1ndi2G57=∑i=1ndi2G513=∑i=1ndi2G519=∑i=1ndi2G522=n3−2n2−19n+38, ∑i=1ndi2G54=n3−2n2−19n+50, ∑i=1ndi2G55=∑i=1ndi2G518=∑i=1ndi2G520=∑i=1ndi2G523=n3−2n2−19n+40, ∑i=1ndi2G56=∑i=1ndi2G512=∑i=1ndi2G515=∑i=1ndi2G525=n3−2n2−19n+42, ∑i=1ndi2G58=∑i=1ndi2G511=∑i=1ndi2G514=∑i=1ndi2G517=n3−2n2−19n+36, ∑i=1ndi2G59=∑i=1ndi2G516=n3−2n2−19n+46, and ∑i=1ndi2G510=∑i=1ndi2G524=n3−2n2−19n+44.
By Corollaries1 and 3 (iii) and (iv) and Lemmas 5 and 11, graphs G50, G51, G52, G53, G54, G55, G56, G57, G58, G59, G510, G511, G512, G513, G514, G515, G516, G517, G518, G519, G520, G521, G522, G523, G524, and G525 are determined by their Aα-DS graphs, respectively, where α∈1/2,1.
By Corollary1 and Theorems 2–5, directly yields the following result.Theorem 6.
LetG∈Gn be a graph with n≠7 vertices. G is determined by its Aα-spectrum, where α∈1/2,1.Remark 3.
By Theorems2–4, we know that almost complete graphs are determined by their Aα-spectra, where α∈0,1/2∪1/2,1, each Gij is a join. Thus, these results is a solution of Problem 1. Motivated by these results, we pose the following two questions.Question 1.
Prove or disprove thatG59 and G516 are Aα-cospectral, where α∈0,1/2.Question 2.
Prove or disprove thatG510 and G524 are Aα-cospectral, where α∈0,1/2.



---

*Source: 8294312-2020-12-07.xml*