Laplacian Spectral Characterization of (Broken) Dandelion Graphs
- PDF / 676,023 Bytes
- 19 Pages / 612 x 792 pts (letter) Page_size
- 27 Downloads / 211 Views
DOI: 10.1007/s13226-020-0441-5
LAPLACIAN SPECTRAL CHARACTERIZATION OF (BROKEN) DANDELION GRAPHS1 Xiaoyun Yang∗ and Ligong Wang∗,∗∗ ∗ Department
of Applied Mathematics, School of Science, Northwestern Polytechnical University, Xi’an, Shaanxi 710072, P. R. China
∗∗ Xi’an-Budapest
Joint Research Center for Combinatorics, Northwestern Polytechnical University, Xi’an, Shaanxi 710129, P. R. China e-mails: [email protected]; [email protected] (Received 19 June 2018; after final revision 2 February 2019; accepted 10 May 2019)
∗ ) be a connected unicyclic graph with p + t(m + 1) vertices obtained from the Let H(p, tK1,m
cycle Cp and t copies of the star K1,m by joining the center of K1,m to each one of t consecutive vertices of the cycle Cp through an edge, respectively. When t = p, the graph is called a dandelion graph and when t 6= p, the graph is called a broken dandelion graph. In this paper, we prove that ∗ ∗ ) (0 < t < p) are ) and the broken dandelion graph H(p, tK1,m the dandelion graph H(p, pK1,m
determined by their Laplacian spectra when m 6= 2 and p is even. Key words : Laplacian spectrum; graph determined by its Laplacian spectrum; unicyclic graph; bipartite graph. 2010 Mathematics Subject Classification : 05C50.
1. I NTRODUCTION Let G be a simple and undirected graph with vertex set V (G) = {v1 , v2 , ..., vn } and edge set E(G). If vi , vj ∈ V (G) are adjacent, then we denote by vi vj the edge joining vi and vj . Let di = dG (vi ) denote the degree of a vertex vi in G and deg(G) = (d1 , d2 , ..., dn ) the degree sequence of G. For convenience, the degree sequence of G can be written as deg(G) = (1n1 , ..., k nk , ..., ∆n∆ ), where ∆ = ∆(G) denotes the maximum degree of all vertices of G and nk is the number of vertices of 1
This work was supported by the National Natural Science Foundation of China (No. 11871398), the Nature Science
Basic Research Plan in Shannxi Province of China (Program No. 2018JM1032) and the National College Students Innovation and Entrepreneurship Training Program (No. 201610699011).
916
XIAOYUN YANG AND LIGONG WANG
degree k in the graph G. Let A(G) = (aij )n×n denote the adjacency matrix of G, where aij = 1 if vi vj ∈ E(G) and aij = 0 otherwise. Let D(G) = diag(d1 , d2 , ..., dn ) be the diagonal matrix of vertex degrees of G. The matrices L(G) = D(G) − A(G) and Q(G) = D(G) + A(G) are called the Laplacian matrix and the signless Laplacian matrix of G, respectively. The polynomials φ(G) = φ(G, x) = det(xIn − L(G)) = l0 xn + l1 xn−1 + ... + ln and ψ(G) = ψ(G, x) = det(xIn − Q(G)) = q0 xn + q1 xn−1 + ... + qn are defined as the Laplacian characteristic polynomial and the signless Laplacian characteristic polynomial of G, respectively. Since A(G), L(G) and Q(G) are real and symmetric, their eigenvalues are all real numbers. Assume that λ1 ≥ λ2 ≥ · · · ≥ λn , µ1 ≥ µ2 ≥ · · · ≥ µn and ν1 ≥ ν2 ≥ · · · ≥ νn are the adjacency eigenvalues, the Laplacian eigenvalues and the signless Laplacian eigenvalues of G, respectively. Two graphs are said to be A-cospectral (L-cospectral or
Data Loading...
