Signless Laplacian determination of a family of double starlike trees
UDC 517.9Two graphs are said to be $Q$-cospectral if they have the same signless Laplacian spectrum.A graph is said to be DQS if there are no other nonisomorphic graphs $Q$-cospectral with it. A tree is called double starlike if it has exactly two vertices of degree greater than 2.Let $H_n(p,q)$ wit...
Saved in:
| Date: | 2021 |
|---|---|
| Main Authors: | , , , , , |
| Format: | Article |
| Language: | English |
| Published: |
Institute of Mathematics, NAS of Ukraine
2021
|
| Online Access: | https://umj.imath.kiev.ua/index.php/umj/article/view/634 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Ukrains’kyi Matematychnyi Zhurnal |
| Download file: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860507066852966400 |
|---|---|
| author | Sharafdini , R. Abdian, A. Z. Behmaram, A. к Zeydi Abdian, Ali ь Sharafdini , R. Abdian, A. Z. Behmaram, A. |
| author_facet | Sharafdini , R. Abdian, A. Z. Behmaram, A. к Zeydi Abdian, Ali ь Sharafdini , R. Abdian, A. Z. Behmaram, A. |
| author_sort | Sharafdini , R. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2025-03-31T08:46:40Z |
| description | UDC 517.9Two graphs are said to be $Q$-cospectral if they have the same signless Laplacian spectrum.A graph is said to be DQS if there are no other nonisomorphic graphs $Q$-cospectral with it. A tree is called double starlike if it has exactly two vertices of degree greater than 2.Let $H_n(p,q)$ with $n \ge 2,$ $p \geq q \geq 2$ denote the double starlike tree obtained by attaching $p$ pendant vertices to one pendant vertex of the path $P_n$ and $q$ pendant vertices to the other pendant vertex of $P_n.$ In this paper, we prove that $H_n(p,q)$ is  DQS for $n\ge 2,$ $p\geq q\geq 2.$
  |
| doi_str_mv | 10.37863/umzh.v73i9.634 |
| first_indexed | 2026-03-24T02:03:25Z |
| format | Article |
| fulltext |
DOI: 10.37863/umzh.v73i9.634
UDC 517.9
R. Sharafdini (Persian Gulf Univ., Bushehr, Iran),
A. Z. Abdian (Lorestan Univ., College Sci., Khoramabad, Iran),
A. Behmaram (Univ. Tabriz, Iran)
SIGNLESS LAPLACIAN DETERMINATION
OF A FAMILY OF DOUBLE STARLIKE TREES
БЕЗЗНАКОВЕ ЛАПЛАСIВСЬКЕ ВИЗНАЧЕННЯ СIМ’Ї
ПОДВIЙНО ЗIРКОПОДIБНИХ ДЕРЕВ
Two graphs are said to be Q-cospectral if they have the same signless Laplacian spectrum. A graph is said to be DQS if
there are no other nonisomorphic graphs Q-cospectral with it. A tree is called double starlike if it has exactly two vertices
of degree greater than 2. Let Hn(p, q) with n \geq 2, p \geq q \geq 2 denote the double starlike tree obtained by attaching p
pendant vertices to one pendant vertex of the path Pn and q pendant vertices to the other pendant vertex of Pn. In this
paper, we prove that Hn(p, q) is DQS for n \geq 2, p \geq q \geq 2.
Два графи називаються Q-коспектральними, якщо вони мають однаковi беззнаковi лапласiвськi спектри. Граф
називається DQS, якщо не iснує iнших неiзоморфних графiв, що є Q-коспектральними по вiдношенню до нього.
Дерево називається подвiйно зiркоподiбним, якщо воно має рiвно двi вершини степеня бiльшого за 2. Нехай Hn(p, q)
з n \geq 2, p \geq q \geq 2 є подвiйно зiркоподiбним деревом, одержаним за допомогою додавання p висячих вершин до
однiєї висячої вершини шляху Pn та q висячих вершин до iншої висячої вершини Pn. У цiй роботi запропоновано
доведення того, що Hn(p, q) є DQS для n \geq 2, p \geq q \geq 2.
1. Introduction. All graphs considered here are simple and undirected. All notions on graphs that
are not defined here can be found in [4].
Let G = (V,E) be a graph with vertex set V (G) = \{ v1, . . . , vn\} and edge set E(G), where
v1, v2, . . . , vn are indexed in the nonincreasing order of degrees, i.e., d1 \geq d2 \geq . . . \geq dn, where
di = di(G) = dG(vi) is the degree of the vertex vi, for i = 1, . . . , n. We denote the degree sequence
of G by \mathrm{d}\mathrm{e}\mathrm{g}(G) = (d1, d2, . . . , dn). The number of triangles of G is denoted by t(G).
For v \in V (G), the graph G - v is an induced subgraph of G obtained from G by deleting the
vertex v and all edges incident with it. For two disjoint graphs G and H, let G \cup H denotes the
disjoint union of G and H.
The line graph of a graph G, denoted by GL, has the edges of G as its vertices, and two vertices
of GL are adjacent if and only if the corresponding edges in G have a common vertex.
We denote by Pn, Cn, and K1,n - 1 the path, the cycle and the star of order n, respectively.
The adjacency matrix AG of G is a square matrix of order n, whose (i, j)-entry is 1 if vi and
vj are adjacent in G and 0 otherwise.
The degree matrix DG of G is a diagonal matrix of order n defined as DG = \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(d1, . . . , dn).
The matrices LG = DG - AG and QG = DG +AG are called the Laplacian matrix and the signless
Laplacian matrix of G, respectively. The multiset of eigenvalues of QG (resp., LG, AG) is called
the Q-spectrum (resp., L-spectrum, A-spectrum) of G. Since AG, LG and QG are real symmetric,
their eigenvalues are real numbers. Moreover, LG and QG are positive semidefinite, and so their
eigenvalues are nonnegative. We use q1(G) \geq q2(G) \geq . . . \geq qn(G) to denote the Q-spectrum
of G.
c\bigcirc R. SHARAFDINI, A. Z. ABDIAN, A. BEHMARAM, 2021
1274 ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
SIGNLESS LAPLACIAN DETERMINATION OF A FAMILY OF DOUBLE STARLIKE TREES 1275
p q. . .
n − 2 n −1 n
...
...
...
...321
Fig. 1. Double starlike tree Hn(p, q).
Two graphs are Q-cospectral (resp., L-cospectral, A-cospectral) if they have the same Q-
spectrum (resp., L-spectrum, A-spectrum). A graph G is said to be DQS (resp., DLS, DAS) if
there is no other nonisomorphic graph Q-cospectral (resp., L-cospectral, A-cospectral) with G.
Obviously, if a graph is DLS, then it is not necessary DQS. For example, consider, K1,3 that is
Q-cospectral with K3 \cup K1.
The problem “which graphs are determined by their spectra?” originates from chemistry. Günthard
and Primas [6] raised this question in the context of Hückels theory. Since this problem is generally
very difficult, van Dam and Haemers [14] proposed a more modest problem, that is, “Which trees
are determined by their spectra?”.
A tree is called starlike if it has exactly one vertex of degree greater than 2. We denote by
T (l1, l2, . . . , l\Delta ) the starlike tree with maximum degree \Delta such that
T (l1, l2, . . . , l\Delta ) - v = Pl1 \cup Pl2 \cup . . . \cup Pl\Delta , (1.1)
where v is the vertex of degree \Delta , l1, l2, . . . , l\Delta are any positive integers. A starlike tree with
maximum degree 3 is called a T -shape tree. A tree is called double starlike if it has exactly two
vertices of degree greater than 2. Denote by Hn(p, q) the tree obtained by attaching p pendant
vertices (vertices of degree 1) to one pendant vertex of Pn and q pendant vertices to the other
pendant vertex of Pn (see Fig. 1). It is clear that Hn(p, q) is double starlike if and only if n \geq 2 and
p \geq q \geq 2.
Note that:
Liu et al., proved that double starlike trees Hn(p, p), n \geq 2, p \geq 1, are DLS [9];
Lu and Liu proved that double starlike trees Hn(p, q) are DLS [10];
H1(2, 1) is the star K1,3 which is not DQS, since it is Q-cospectral with K3 \cup K1 [14];
H1(p, q) \sim = K1,p+q, which is DQS when p+ q \not = 3 [8];
Hn(1, 1) \sim = Pn+2, which is DQS [14];
Omidi and Vatandoost proved that starlike trees with maximum degree 4 are DQS [12];
Bu and Zhou proved that starlike trees whose maximum degree exceed 4 are DQS [3];
if p \geq 1, then Hn(p, 1) is a starlike tree, which is DQS [3, 12];
Omidi gave all T -shape trees, which are DQS [11].
In this paper, we prove that for n \geq 2, p \geq q \geq 2 the double starlike tree Hn(p, q) is DQS.
2. Preliminaries. Some useful established results about the spectrum are presented in this
section, will play an important role throughout this paper.
Lemma 2.1 [13, 14]. For any graph, the following can be determined by its adjacency and
Laplacian spectrum:
(i) the number of vertices;
(ii) the number of edges.
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
1276 R. SHARAFDINI, A. Z. ABDIAN, A. BEHMARAM
For any graph, the following can be determined by its adjacency spectrum:
(iii) the number of closed walks of any length;
(iv) being regular or not and the degree of regularity.
For any graph, the following can be determined by its Laplacian spectrum:
(v) the number of components;
(vi) the sum of the squares of degrees of vertices.
For any graph, the following can be determined by its signless Laplacian spectrum:
(vii) the number of bipartite components;
(viii) the sum of the squares of degrees of vertices.
Lemma 2.2 [1]. Let G be a graph with n vertices, m edges, t triangles and vertex degrees
d1, d2, . . . , dn. Let Tk =
\sum n
i=1
qi(G)k, then
T0 = n, T1 =
n\sum
i=1
di = 2m, T2 = 2m+
n\sum
i=1
d2i , T3 = 6t+ 3
n\sum
i=1
d2i +
n\sum
i=1
d3i .
Lemma 2.3 [7]. Let G be a graph with V (G) \not = \varnothing and E(G) \not = \varnothing . Then
d1 + 1 \leq \mu 1(G) \leq \mathrm{m}\mathrm{a}\mathrm{x}
\biggl\{
di(di +mi) + dj(dj +mj)
di + dj
\bigm| \bigm| \bigm| \bigm| vivj \in E(G)
\biggr\}
,
where \mu 1(G) denotes the spectral radius of LG and mi denotes the average of the degrees of the
vertices adjacent to vertex vi in G.
Lemma 2.4 [4]. Let G be a graph. Then qn(G) \geq 0 with equality if and only if G is a bipartite
graph. Bedsides, the multplicity of 0 as the signless Laplacian eigenvalue of G, is the number of
bipartite components of G. Moreover, \mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}Q(G) = \mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}L(G) if and only if G is a bipartite graph.
Lemma 2.5 [16]. If two graphs G and H are Q-cospectral, then their line graphs GL and HL
are A-cospectral. The converse is true if G and H have the same number of vertices and edges.
Lemma 2.6 (Interlacing theorem [14]). Suppose that N is a symmetric n\times n matrix with eigen-
values a1 \geq a2 \geq . . . \geq an. Then the eigenvalues b1 \geq b2 \geq . . . \geq bm of a principal submatrix of
N of size m satisfy ai \geq bi \geq an - m+i for i = 1, 2, . . . ,m.
Lemma 2.7 [5]. If G is a graph of order n, then q2(G) \geq d2(G) - 1 and q3(G) \geq d3(G) -
\surd
2.
A connected graph with n vertices is said to be unicyclic if it has n edges. If the girth of a
unicyclic graph is odd, then this unicyclic graph is said to be odd unicyclic.
Lemma 2.8 [2]. Let G be a graph Q-spectral with a tree of order n. Then G is either a tree or
a union of a tree of order f and c odd unicyclic graphs, and n = 4cf.
Lemma 2.9 [15]. Let G be a graph of order n and v \in V (G). Then, for i = 1, 2, . . . , n - 1,
qi+1(G) - 1 \leq qi(G - v) \leq qi(G),
where the right equality holds if and only if v is an isolated vertex.
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
SIGNLESS LAPLACIAN DETERMINATION OF A FAMILY OF DOUBLE STARLIKE TREES 1277
3. Main results. We first bound the second largest and the third largest signless Laplacian
eigenvalues of H = Hn(p, q) with n \geq 2 and p \geq q \geq 2.
Lemma 3.1. For a double starlike tree H = Hn(p, q) with n \geq 2 and p \geq q \geq 2 we have
(i) q2(H) \leq q + 3 +
1
q + 2
;
(ii) q3(H) < 4.
Proof. Let u and v be the vertices in H = Hn(p, q) of degree p+ 1 and q + 1, respectively.
(i) By Lemma 2.9 we have
q2(H) - 1 \leq q1(H - u) < q1(H).
It follows from Lemmas 2.3 and 2.4 that
q1(H - u) \leq q + 2 +
1
q + 2
,
from which we conclude that
q2(H) \leq q2(H - u) + 1 \leq q + 3 +
1
q + 2
.
(ii) Let Nuv be the (p+q+n - 2)\times (p+q+n - 2) principal submatrix of the signless Laplacian
matrix of H formed by removing the rows and the columns corresponding to u and v. In this case,
the largest eigenvalue of Nuv is less than 4. By Lemma 2.6 we have
q3(H) < 4. (3.1)
Lemma 3.1 is proved.
Proposition 3.1. Let G be a connected graph Q-cospectral with Hn(p, q), n \geq 2 and p \geq q \geq
\geq 2. Then:
(i) d1(G) \leq p+ 1;
(ii) d2(G) \leq q + 4;
(iii) d3(G) \leq 5.
Proof. (i) By Lemma 2.1, G has n + p + q vertices and n + p + q - 1 edges. It follows
from Lemma 2.4 that G has only one bipartite component. Therefore, G is a tree, since G is
connected. By Lemmas 2.3 and 2.4, we have d1(G) + 1 \leq q1(G) = \mu 1(G) \leq p+ 2 +
1
p+ 2
and so
\Delta = d1(G) \leq p+ 1.
(ii) By Lemma 3.1(i) we obtain
q2(G) = q2(Hn(p, q)) \leq q + 3 +
1
q + 2
.
By Lemma 2.7 d2(G) \leq q + 4.
(iii) By Lemma 3.1(ii) we get q3(G) = q3(Hn(p, q)) < 4. It follows from Lemma 2.7 that
d3(G) \leq 5.
Proposition 3.1 is proved.
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
1278 R. SHARAFDINI, A. Z. ABDIAN, A. BEHMARAM
Proposition 3.2. Let G be a connected graph Q-cospectral with Hn(p, q), n \geq 2 and p \geq q \geq
\geq 2. Then G is a double starlike tree with the degree set
\mathrm{d}\mathrm{e}\mathrm{g}(G) =
\biggl(
p+ 1, q + 1, 2, . . . , 2\underbrace{} \underbrace{}
n - 2
, 1, . . . , 1\underbrace{} \underbrace{}
p+q
\biggr)
.
Proof. It follows from Lemma 2.1 that G is bipartite with n + p + q vertices and n +
+ p + q - 1 edges. So, G is a tree. Denote by nk the number of vertices of degree k in G
for k \in \{ 1, 2, 3, . . . , d1(G)\} . By Lemma 2.1(i), (ii), (viii) and Lemma 2.2 we have the following
equations:
d1(G)\sum
k=1
nk = n+ p+ q,
d1(G)\sum
k=1
knk = 2(n+ p+ q - 1),
d1(G)\sum
k=1
k2nk = (p+ 1)2 + (q + 1)2 + p+ q + 4(n - 2),
d1(G)\sum
k=1
k3nk = (p+ 1)3 + (q + 1)3 + p+ q + 8(n - 2).
By Lemma 2.5 Hn(p, q)
L and GL are A-cospectral. In addition, by Lemma 2.1(iii) they have
the same number of triangles (six times the number of closed walks of length 3). In other words,
d1(G)\sum
k=1
\biggl(
k
3
\biggr)
nk =
\biggl(
p+ 1
3
\biggr)
+
\biggl(
q + 1
3
\biggr)
.
Let us denote by ni the number of vertices of degree i in G for i = 1, 2, 3, 4, 5. Therefore,
n1 + n2 + n3 + n4 + n5 = n+ p+ q - 2,
n1 + 2n2 + 3n3 + 4n4 + 5n5 = 2(n+ p+ q - 1) - x,
n1 + 4n2 + 9n3 + 16n4 + 25n5 = (p+ 1)2 + p+ q + (q + 1)2 + 4(n - 2) - y,
n1 + 8n2 + 27n3 + 64n4 + 125n5 = (p+ 1)3 + p+ q + (q + 1)3 + 8(n - 2) - w,
6n3 + 24n4 + 60n5 = (p+ 1)p(p - 1) + (q + 1)q(q - 1) - z,
where
x = d1 + d2, y = d21 + d22, w = d31 + d32, z = d1(d
2
1 - 3d1 + 2) + d2(d
2
2 - 3d2 + 2).
It follows that
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
SIGNLESS LAPLACIAN DETERMINATION OF A FAMILY OF DOUBLE STARLIKE TREES 1279
n5 =
12(2x - 3y + w - z)
12
= 0, n4 =
- 48(2x - 3y + w - z)
12
= 0,
and so
n1 = p+ q, n2 = n - 2, n3 = 0, d1 = p+ 1, d2 = q + 1.
This means that G is a tree having exactly two vertices of degree more than 2. So, G is a double
starlike tree with the degree set \mathrm{d}\mathrm{e}\mathrm{g}(G) =
\Bigl(
p+ 1, q + 1, 2, . . . , 2\underbrace{} \underbrace{}
n - 2
, 1, . . . , 1\underbrace{} \underbrace{}
p+q
\Bigr)
.
Proposition 3.2 is proved.
Proposition 3.3. There is no connected graph Q-spectral with Hn(p, q), n \geq 2 and p \geq q \geq 2.
Proof. Let G be a connected graph Q-cospectral with Hn(p, q) for n \geq 2 and p \geq q \geq 2. By
Proposition 3.2, G is a double starlike tree with \mathrm{d}\mathrm{e}\mathrm{g}(G) =
\Bigl(
p + 1, q + 1, 2, . . . , 2\underbrace{} \underbrace{}
n - 2
, 1, . . . , 1\underbrace{} \underbrace{}
p+q
\Bigr)
. Now
we show that G \sim = Hn(p, q). We consider the following two cases:
Case 1. The two vertices of degree greater than 2 are adjacent in G.
Suppose that there exist q - a (resp., p - b) pendant vertices adjacent to the vertices of degree
p+ 1 in G, where a and b are nonnegative integers satisfying that
0 \leq b \leq p, 0 \leq a \leq q.
Let mi
GL be the number of vertices of degree i in GL. Therefore,
m1
GL = a+ b, mp+q
GL = 1, mp+1
GL = b, mp
GL = p - b, mq
GL = p - a,
mq+1
GL = a, m2
GL = n - 2 - a - b, mk
GL = 0, k /\in \{ 1, 2, p, q, p+ 1, q + 1, p+ q\} .
Note that Hn(p, q)
L and GL are A-cospectral. By Lemma 2.1(ii), (iii), Hn(p, q)
L and GL have
the same number of edges and the same number of closed walks of length 4. Moreover, they have
the same number of 4-cycles. Lemma 2.1 implies that Hn(p, q)
L and GL have the same number of
induced paths of length 2, that is,\biggl(
p+ 1
2
\biggr)
+
\biggl(
q + 1
2
\biggr)
+ p
\biggl(
p
2
\biggr)
+ q
\biggl(
q
2
\biggr)
+ (n - 3)
\biggl(
2
2
\biggr)
=
=
\biggl(
p+ q
2
\biggr)
+ b
\biggl(
p+ 1
2
\biggr)
+ (p - b)
\biggl(
p
2
\biggr)
+
+a
\biggl(
q + 1
2
\biggr)
+ (q - a)
\biggl(
p
2
\biggr)
+ (n - 2 - a - b)
\biggl(
2
2
\biggr)
.
It follows that (p - 1)(q - 1)+ b(p - 1)+a(q - 1) = 0, a contradiction, since 0 \leq b \leq p, 0 \leq a \leq q
and p \geq q \geq 2.
Case 2. The two vertices of degree greater than 2 are non-adjacent in G as shown in Fig. 2.
Suppose that there exist q - a (resp., p - b) pendant vertices adjacent to the vertices of degree
p+ 1 in G, where a and b are nonnegative integers satisfying that 0 \leq b \leq p, 0 \leq a \leq q. We show
that a = b = 0. Then, by counting the number of vertices in G and Hn(p, q), we obtain
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
1280 R. SHARAFDINI, A. Z. ABDIAN, A. BEHMARAM
1 2 3
. . .
l1 − 1 l1
...
...
...
...
12
. . .
lb − 1lb
12
. . .
l1 − 1l1
p
b
2 1. . .la − 1 la
2 1. . .l1 − 1 l1
a
q
Fig. 2. The graph G in Case 2 of Proposition 3.3.
l +
a\sum
j=1
l\prime j +
b\sum
l=1
l\prime \prime j + p+ q = n+ p+ q.
Hence l + a+ b = n. On the other hand,
m1
GL = a+ b, mp+1
GL = b+ 1, mp
GL = p - b, mq+1
GL = a+ 1, mq
GL = q - a,
m2
GL = n - 3 - a - b, mk
GL = 0, k /\in \{ 1, 2, p, q, p+ 1, q + 1\} .
Note that Hn(p, q)
L and GL are A-cospectral. By Lemma 2.1, Hn(p, q)
L and GL have the same
number of edges and the same number of closed walks of length 4. Moreover, they have the same
number of 4-cycles. Lemma 2.5 implies that Hn(p, q)
L and GL have the same number of induced
paths of length 2, that is,\biggl(
p+ 1
2
\biggr)
+
\biggl(
q + 1
2
\biggr)
+ p
\biggl(
p
2
\biggr)
+ q
\biggl(
q
2
\biggr)
+ (n - 3)
\biggl(
2
2
\biggr)
=
= (b+ 1)
\biggl(
p+ 1
2
\biggr)
+ (p - b)
\biggl(
p
2
\biggr)
+
+(q - a)
\biggl(
q
2
\biggr)
+ (a+ 1)
\biggl(
q + 1
2
\biggr)
+
+(p - a)
\biggl(
p
2
\biggr)
+ (n - 3 - a - b)
\biggl(
2
2
\biggr)
.
By a simple computation a(q - 1) + b(p - 1) = 0 and so a = b = 0. Therefore, l = n. This means
that G \sim = Hn(p, q).
Proposition 3.3 is proved.
Lemma 3.2. Let G be a disconnected graph Q-cospectral with Hn(p, q), n \geq 2 and p \geq q \geq 2.
Then G has no triangles.
Proof. By Lemma 2.4 G has one bipartite component. We show that t(G) = 0. Suppose
not and so t(G) \geq 1. Obviously, t(G) \leq 2, otherwise, since G is disconnected, it follows from
Lemma 2.8 that G has at least three odd unicyclic components each of them has a triangle. So
q1(G), q2(G), q3(G) \geq 4, which is a contradiction to Lemma 3.1(ii). First suppose that t(G) = 1.
Consider the following two cases:
Case 1. Let dn(G) < 1, i.e., dn(G) = 0. Since G has only one bipartite component, one may
deduce that G has only one isolated vertex.
Subcase 1.1. By Lemma 2.8 G = K1 \cup H1, where H1 is an odd unicyclic graph consisting of a
triangle. By Lemmas 2.5 and 2.1(iii), we have
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
SIGNLESS LAPLACIAN DETERMINATION OF A FAMILY OF DOUBLE STARLIKE TREES 1281
t(GL) = t(Hn(p, q)
L) =
\biggl(
p+ 1
3
\biggr)
+
\biggl(
q + 1
3
\biggr)
.
Let us denote by ni, the number of vertices of degree i for i = 1, 2, 3, 4, 5. Therefore,
n1 + n2 + n3 + n4 + n5 = n+ p+ q - 3,
n1 + 2n2 + 3n3 + 4n4 + 5n5 = 2(n+ p+ q - 1) - x,
n1 + 4n2 + 9n3 + 16n4 + 25n5 = (p+ 1)2 + p+ q + (q + 1)2 + 4(n - 2) - y,
n1 + 8n2 + 27n3 + 64n4 + 125n5 = (p+ 1)3 + p+ q + (q + 1)3 + 8(n - 2) - w - 6,
6n3 + 24n4 + 60n5 = (p+ 1)p(p - 1) + (q + 1)q(q - 1) - z,
where
x = d1 + d2, y = d21 + d22, w = d31 + d32, z = d1(d
2
1 - 3d1 + 2) + d2(d
2
2 - 3d2 + 2).
By a simple computation n4 =
- 48(2x - 3y + w - z + 6)
12
< 0, a contradiction, since 2x - 3y +
+ w - z = 0.
Subcase 1.2. Let t(G) = 2. By a similar argument and by using the previous notations we obtain
G = K1 \cup H1 \cup H2, and so
n1 + n2 + n3 + n4 + n5 = n+ p+ q - 3,
n1 + 2n2 + 3n3 + 4n4 + 5n5 = 2(n+ p+ q - 1) - x,
n1 + 4n2 + 9n3 + 16n4 + 25n5 = (p+ 1)2 + p+ q + (q + 1)2 + 4(n - 2) - y,
n1 + 8n2 + 27n3 + 64n4 + 125n5 = (p+ 1)3 + p+ q + (q + 1)3 + 8(n - 2) - w - 12,
6n3 + 24n4 + 60n5 = (p+ 1)p(p - 1) + (q + 1)q(q - 1) - z.
By a simple computation n4 =
- 48(2x - 3y + w - z + 12)
12
< 0, a contradiction, since 2x - 3y +
+ w - z = 0.
Case 2. Let dn(G) \geq 1. By Lemma 2.8 if t(G) = 1, then G = Y \cup T, where Y and T
are a connected graph consisting of a triangle and a tree, respectively. Consider the following two
subcases:
Subcase 2.1. By using the previous notations
n1 + n2 + n3 + n4 + n5 = n+ p+ q - 2,
n1 + 2n2 + 3n3 + 4n4 + 5e = 2(n+ p+ q - 1) - x,
n1 + 4n2 + 9n3 + 16n4 + 25n5 = (p+ 1)2 + p+ q + (q + 1)2 + 4(n - 2) - y,
n1 + 8n2 + 27n3 + 64d+ 125n5 = (p+ 1)3 + p+ q + (q + 1)3 + 8(n - 2) - w - 6,
6n3 + 24n4 + 60n5 = (p+ 1)p(p - 1) + (q + 1)q(q - 1) - z.
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
1282 R. SHARAFDINI, A. Z. ABDIAN, A. BEHMARAM
By a simple computation n4 =
- 48(2x - 3y + w - z + 6)
12
< 0, a contradiction, since 2x - 3y +
+ w - z = 0.
Subcase 2.2. Let t(G) = 2. By Lemma 2.8, we have G = T \cup Y1 \cup Y2, where Y1 and Y2 are
connected graphs consisting of a triangle and T is a tree with at least two vertices. By using the
previous notations, we have
n1 + n2 + n3 + n4 + n5 = n+ p+ q - 2,
n1 + 2n2 + 3n3 + 4n4 + 5n5 = 2(n+ p+ q - 1) - x,
n1 + 4n2 + 9n3 + 16n4 + 25n5 = (p+ 1)2 + p+ q + (q + 1)2 + 4(n - 2) - y,
n1 + 8n2 + 27n3 + 64n4 + 125n5 = (p+ 1)3 + p+ q + (q + 1)3 + 8(n - 2) - w - 12,
6n3 + 24n4 + 60n5 = (p+ 1)p(p - 1) + (q + 1)q(q - 1) - z,
where
x = d1 + d2, y = d21 + d22, w = d31 + d32, z = d1(d
2
1 - 3d1 + 2) + d2(d
2
2 - 3d2 + 2).
By a simple computation n4 =
- 48(2x - 3y + w - z + 12)
12
< 0, a contradiction.
Lemma 3.2 is proved.
Proposition 3.4. There is no disconnected graph Q-spectral with Hn(p, q), n \geq 2 and
p \geq q \geq 2.
Proof. Suppose by the contrary that G is a disconnected graph Q-spectral with Hn(p, q), n \geq 2
and p \geq q \geq 2. By Lemma 3.2, t(G) = 0. Similar to Proposition 3.2 we have the following two
cases:
Case 1. Let dn(G) = 0. By Lemma 2.8 if s = 1, then G = Y \cup T, where Y is a connected
graph consisting of a unique cycle of order at least 5 and T = K1. On the other hand, Lemma 2.8
implies that Hn(p, q) is either K1,3 or P4, a contradiction. So, let s = 2. In this case G =
= Y1 \cup Y2 \cup K1, where Y1 and Y2 are connected graph consisting of an unique cycle of order at
least 5. It is clear that | V (G)| = 16 and | E(G)| = 15. Since \mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}Q(G) = \mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}Q(Hn(p, q)), so
| V (G)| = | V (Hn(p, q))| = n+ p+ q. Therefore, n+ p+ q = 16, that is, p+ q = 16 - n. Applying
the previous notations, we get
n1 + n2 + n3 + n4 + n5 = 13,
n1 + 2n2 + 3n3 + 4n4 + 5e = 2(15) - x,
n1 + 4n2 + 9n3 + 16n4 + 25n5 = (16 - n - q)2 + (q + 1)2 + 16 - n+ 4(n - 2) - y,
n1 + 8n2 + 27n3 + 64n4 + 125n5 = (16 - n - q)3 + (q + 1)3 + 16 - n+ 8(n - 2) - w,
6n3 + 24n4 + 60n5 = q(q - 1)(q + 1) + (16 - n - q)(17 - n - q)(15 - n - q) - z.
(Note that the degree of one of vertices is dn(G) = 0 and the two others degrees are d1, d2. We can
subtract these three vertices from 16. So, the number of vertices of degrees 1, 2, 3, 4 and 5 is 13.)
Then
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
SIGNLESS LAPLACIAN DETERMINATION OF A FAMILY OF DOUBLE STARLIKE TREES 1283
n5 =
12(2x - 3y + w - z + 710 + 3n2 + n(6q - 89) + 3q(q - 31))
12
=
= 710 + 3n2 + n(6q - 89) + 3q(q - 31). (3.2)
We know that n \geq 2, q \geq p \geq 2 and n+ p+ q = 16. By substituting (n, q) \in \{ (2, 12), . . . , (11, 3)\}
in (3.2), we will have a contradiction.
If s \geq 3, then q1(G), q2(G), q3(G) \geq 4, a contradiction to (3.1).
Case 2. Let dn(G) \geq 1. Applying the previous notations
n1 + n2 + n3 + n4 + n5 = n+ p+ q - 2,
n1 + 2n2 + 3n3 + 4n4 + 5e = 2(n+ p+ q - 1) - x,
n1 + 4n2 + 9n3 + 16n4 + 25n5 = (p+ 1)2 + p+ q + (q + 1)2 + 4(n - 2) - y,
n1 + 8n2 + 27n3 + 64n4 + 125n5 = (p+ 1)3 + p+ q + (q + 1)3 + 8(n - 2) - w,
6n3 + 24n4 + 60n5 = (p+ 1)p(p - 1) + (q + 1)q(q - 1) - z.
By solving this system of equations, we obtain that
n3 = n4 = n5 = 0.
Since G is dis-connected, it follows from Lemma 2.8 that G consists of at least one odd unicyclic
graph that the order of its odd cycle is greater than or equal to 5. This means that G has at least one
vertex of degree 3 or 4 or 5.
Proposition 3.4 is proved.
Combining Propositions 3.3 and 3.4, we have the following main result.
Theorem 3.1. Any double starlike tree Hn(p, q), n \geq 2 and p \geq q \geq 2, is DQS.
Note that if uv is an edge of H = Hn(p, q), then the degree of uv as a vertex of the line graph
Hn(p, q)
L is dH(u) + dH(v) - 2. Since
\mathrm{d}\mathrm{e}\mathrm{g}(H) =
\biggl(
p+ 1, q + 1, 2, . . . , 2\underbrace{} \underbrace{}
n - 2
, 1, . . . , 1\underbrace{} \underbrace{}
p+q
\biggr)
,
it is easy to see that the degree sequence of HL is
\mathrm{d}\mathrm{e}\mathrm{g}(HL) =
\biggl(
p+ 1, q + 1, p, . . . , p\underbrace{} \underbrace{}
p
, q, . . . , q\underbrace{} \underbrace{}
q
, 2, . . . , 2\underbrace{} \underbrace{}
n - 3
\biggr)
.
Corollary 3.1. Let G be a graph such that GL is A-cospectral with Hn(p, q)
L. If | V (G)| =
= | V (Hn(p, q))| , then GL \sim = Hn(p, q)
L.
Proof. Let G be a graph such that GL is A-cospectral with Hn(p, q)
L. Therefore, by
Lemma 2.1(i), G and Hn(p, q) have the same number of edges. Hence, by Lemma 2.5
\mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}Q(G) = \mathrm{S}\mathrm{p}\mathrm{e}\mathrm{c}Q(Hn(p, q)),
since | V (G)| = | V (Hn(p, q))| . In the other hand, Theorem 3.1 implies that G \sim = Hn(p, q). Therefore,
GL \sim = Hn(p, q)
L.
Corollary 3.1 is proved.
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
1284 R. SHARAFDINI, A. Z. ABDIAN, A. BEHMARAM
References
1. C. Bu, J. Zhou, Signless Laplacian spectral characterization of the cones over some regular graphs, Linear Algebra
and Appl., 436, 3634 – 3641 (2012).
2. C. Bu, J. Zhou, H. B. Li, Spectral determination of some chemical graphs, Filomat, 26, 1123 – 1131 (2012).
3. C. Bu, J. Zhou, Starlike trees whose maximum degree exceed 4 are determined by their Q-spectra, Linear Algebra
and Appl., 436, 143 – 151 (2012).
4. D. Cvetković, P. Rowlinson, S. Simić, An introduction to the theory of graph spectra, London Math. Soc. Stud. Texts,
75 (2010).
5. K. Ch. Das, On conjectures involving second largest signless Laplacian eigenvalue of graphs, Linear Algebra and
Appl., 432, 3018 – 3029 (2010).
6. Hs. H. Günthard, H. Primas, Zusammenhang von Graphtheorie und Mo – Theotie von Molekeln mit Systemen konjugi-
erter Bindungen, Helv. Chim. Acta, 39, 1645 – 1653 (1956).
7. J. S. Li, X. D. Zhang, On the Laplacian eigenvalues of a graph, Linear Algebra and Appl., 285, 305 – 307 (1998).
8. M. Liu, B. Liu, F. Wei, Graphs determined by their (signless) Laplacian spectra, Electron. J. Linear Algebra, 22,
112 – 124 (2011).
9. X. Liu, Y. Zhang, P. Lu, One special double starlike graph is determined by its Laplacian spectrum, Appl. Math.
Lett., 22, 435 – 438 (2009).
10. P. Lu, X. Liu, Laplacian spectral characterization of some double starlike trees, Harbin Gongcheng Daxue Xuebao/
J. Harbin Engrg. Univ., 37, № 2, 242 – 247 (2016); arXiv:1205.6027v2[math.CO].
11. G. R. Omidi, On a signless Laplacian spectral characterization of T-shape trees, Linear Algebra and Appl., 431,
1600 – 1615 (2009).
12. G. R. Omidi, E. Vatandoost, Starlike trees with maximum degree 4 are determined by their signless Laplacian spectra,
Electron. J. Linear Algebra, 20, 274 – 290 (2010).
13. C. S. Oliveira, N. M. M. de Abreu, S. Jurkiewilz, The characteristic polynomial of the Laplacian of graphs in
(a, b)-linear cases, Linear Algebra and Appl., 365, 113 – 121 (2002).
14. E. R. van Dam, W. H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra and Appl., 373,
241 – 272 (2003).
15. J. Wang, F. Belardo, A note on the signless Laplacian eigenvalues of graphs, Linear Algebra and Appl., 435,
2585 – 2590 (2011).
16. J. Zhou, C. Bu, Spectral characterization of line graphs of starlike trees, Linear and Multilinear Algebra, 61,
1041 – 1050 (2013).
Received 27.12.18,
after revision — 23.06.20
ISSN 1027-3190. Укр. мат. журн., 2021, т. 73, № 9
|
| id | umjimathkievua-article-634 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-24T02:03:25Z |
| publishDate | 2021 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/a8/8b9a98b9d13b54a4501aca0bd661fca8.pdf |
| spelling | umjimathkievua-article-6342025-03-31T08:46:40Z Signless Laplacian determination of a family of double starlike trees Signless Laplacian determination of a family of double starlike trees Signless Laplacian determination of a family of double starlike trees Sharafdini , R. Abdian, A. Z. Behmaram, A. к Zeydi Abdian, Ali ь Sharafdini , R. Abdian, A. Z. Behmaram, A. Double starlike trees Signless Laplacian spectrum Spectral determination Line graph Double starlike trees Signless Laplacian spectrum Spectral determination Line graph UDC 517.9Two graphs are said to be $Q$-cospectral if they have the same signless Laplacian spectrum.A graph is said to be DQS if there are no other nonisomorphic graphs $Q$-cospectral with it. A tree is called double starlike if it has exactly two vertices of degree greater than 2.Let $H_n(p,q)$ with $n \ge 2,$ $p \geq q \geq 2$ denote the double starlike tree obtained by attaching $p$ pendant vertices to one pendant vertex of the path $P_n$ and $q$ pendant vertices to the other pendant vertex of $P_n.$ In this paper, we prove that $H_n(p,q)$ is&nbsp; DQS for $n\ge 2,$ $p\geq q\geq 2.$ &nbsp; UDC 517.9 Беззнакове лапласiвське визначення сiм’ї подвiйно зiркоподiбних дерев Два графи називаються $Q$-коспектральними, якщо вони мають однакові беззнакові лапласівські спектри.Граф називається DQS, якщо не існує інших неізоморфних графів, що є $Q$-коспектральними по відношенню до нього. Дерево називається подвійно зіркоподібним, якщо воно має рівно дві вершини степеня більшого за 2.Нехай $H_n(p,q)$ з $n \ge 2,$ $p \geq q \geq 2$ є подвійно зіркоподібним деревом, одержаним за допомогою додавання $p$ висячих вершин до однієї висячої вершини шляху $P_n$ та $q$ висячих вершин до іншої висячої вершини $P_n.$ У цій роботі запропоновано доведення того, що $H_n(p,q)$ є DQS для $n\ge 2,$ $p\geq q\geq 2.$ Institute of Mathematics, NAS of Ukraine 2021-09-16 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/634 10.37863/umzh.v73i9.634 Ukrains’kyi Matematychnyi Zhurnal; Vol. 73 No. 9 (2021); 1274 - 1284 Український математичний журнал; Том 73 № 9 (2021); 1274 - 1284 1027-3190 en https://umj.imath.kiev.ua/index.php/umj/article/view/634/9110 Copyright (c) 2021 Ali Zeydi Abdian |
| spellingShingle | Sharafdini , R. Abdian, A. Z. Behmaram, A. к Zeydi Abdian, Ali ь Sharafdini , R. Abdian, A. Z. Behmaram, A. Signless Laplacian determination of a family of double starlike trees |
| title | Signless Laplacian determination of a family of double starlike trees |
| title_alt | Signless Laplacian determination of a family of double starlike trees Signless Laplacian determination of a family of double starlike trees |
| title_full | Signless Laplacian determination of a family of double starlike trees |
| title_fullStr | Signless Laplacian determination of a family of double starlike trees |
| title_full_unstemmed | Signless Laplacian determination of a family of double starlike trees |
| title_short | Signless Laplacian determination of a family of double starlike trees |
| title_sort | signless laplacian determination of a family of double starlike trees |
| topic_facet | Double starlike trees Signless Laplacian spectrum Spectral determination Line graph Double starlike trees Signless Laplacian spectrum Spectral determination Line graph |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/634 |
| work_keys_str_mv | AT sharafdinir signlesslaplaciandeterminationofafamilyofdoublestarliketrees AT abdianaz signlesslaplaciandeterminationofafamilyofdoublestarliketrees AT behmarama signlesslaplaciandeterminationofafamilyofdoublestarliketrees AT k signlesslaplaciandeterminationofafamilyofdoublestarliketrees AT zeydiabdianali signlesslaplaciandeterminationofafamilyofdoublestarliketrees AT ʹ signlesslaplaciandeterminationofafamilyofdoublestarliketrees AT sharafdinir signlesslaplaciandeterminationofafamilyofdoublestarliketrees AT abdianaz signlesslaplaciandeterminationofafamilyofdoublestarliketrees AT behmarama signlesslaplaciandeterminationofafamilyofdoublestarliketrees |