Xiaogang Liu

Given simple graphs and , the neighbourhood corona of and , denoted , is the graph obtained by taking one copy of and copies of , and joining the neighbours … Given simple graphs and , the neighbourhood corona of and , denoted , is the graph obtained by taking one copy of and copies of , and joining the neighbours of the th vertex of to every vertex in the th copy of . In this paper we determine the adjacency spectrum of for arbitrary and , and the Laplacian spectrum and signless Laplacian spectrum of for regular and arbitrary , in terms of the corresponding spectrum of and . The results on the adjacency and signless Laplacian spectra enable us to construct new pairs of adjacency cospectral and signless Laplacian cospectral graphs. As applications of the results on the Laplacian spectra, we give constructions of new families of expander graphs from known ones by using neighbourhood coronae.

View PDF Chat

Eigenvalues of Cayley Graphs

2022-04-21

Xiaogang Liu , Sanming Zhou

We survey some of the known results on eigenvalues of Cayley graphs and their applications, together with related results on eigenvalues of Cayley digraphs and generalizations of Cayley graphs. We survey some of the known results on eigenvalues of Cayley graphs and their applications, together with related results on eigenvalues of Cayley digraphs and generalizations of Cayley graphs.

View PDF Chat

On the A-characteristic polynomial of a graph

2018-02-14

Xiaogang Liu , Shunyi Liu

View PDF Chat

Spectral Properties of Unitary Cayley Graphs of Finite Commutative Rings

2012-10-25

Xiaogang Liu , Sanming Zhou

Let $R$ be a finite commutative ring. The unitary Cayley graph of $R$, denoted $G_R$, is the graph with vertex set $R$ and edge set $\left\{\{a,b\}:a,b\in R, a-b\in R^\times\right\}$, where … Let $R$ be a finite commutative ring. The unitary Cayley graph of $R$, denoted $G_R$, is the graph with vertex set $R$ and edge set $\left\{\{a,b\}:a,b\in R, a-b\in R^\times\right\}$, where $R^\times$ is the set of units of $R$. An $r$-regular graph is Ramanujan if the absolute value of every eigenvalue of it other than $\pm r$ is at most $2\sqrt{r-1}$. In this paper we give a necessary and sufficient condition for $G_R$ to be Ramanujan, and a necessary and sufficient condition for the complement of $G_R$ to be Ramanujan. We also determine the energy of the line graph of $G_R$, and compute the spectral moments of $G_R$ and its line graph.

View PDF Chat

Spectra of Subdivision-Vertex Join and Subdivision-Edge Join of Two Graphs

2017-02-06

Xiaogang Liu , Zuhe Zhang

View PDF Chat

Which wheel graphs are determined by their Laplacian spectra?

2009-10-01

Yuanping Zhang , Xiaogang Liu , Xuerong Yong

Signless Laplacian spectral characterization of some joins

2015-02-08

Xiaogang Liu , Pengli Lu

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. In … 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. In this paper, the signless Laplacian characteristic polynomial of the join of two graphs is first formulated. And then, a lower bound for the i-th largest signless Laplacian eigenvalue of a graph is given. Finally, it is proved that G â¨ K_m, where G is an (n â 2)-regular graph on n vertices, and K_n â¨ K_2 except for n = 3, are determined by their signless Laplacian spectra.

View PDF Chat

One special double starlike graph is determined by its Laplacian spectrum

2008-06-12

Xiaogang Liu , Yuanping Zhang , Pengli Lu

The spectral distribution of random mixed graphs

2017-01-17

Dan Hu , Xueliang Li , Xiaogang Liu +1 more

Perfect state transfer in NEPS of complete graphs

2020-10-14

Yipeng Li , Xiaogang Liu , Shenggui Zhang +1 more

View PDF Chat

Laplacian spectral characterization of some graph products

2012-05-30

Xiaogang Liu , Suijie Wang

View PDF Chat

On the spectral characterization of some unicyclic graphs

2011-07-06

Xiaogang Liu , Suijie Wang , Yuanping Zhang +1 more

Laplacian state transfer in total graphs

2020-09-19

Xiaogang Liu , Qiang Wang

Spectra of subdivision-vertex and subdivision-edge joins of graphs

2012-12-04

Xiaogang Liu , Zuhe Zhang

The subdivision graph $\mathcal{S}(G)$ of a graph $G$ is the graph obtained by inserting a new vertex into every edge of $G$. Let $G_1$ and $G_2$ be two vertex disjoint … The subdivision graph $\mathcal{S}(G)$ of a graph $G$ is the graph obtained by inserting a new vertex into every edge of $G$. Let $G_1$ and $G_2$ be two vertex disjoint graphs. The subdivision-vertex join of $G_1$ and $G_2$, denoted by $G_1\dot{\vee}G_2$, is the graph obtained from $\mathcal{S}(G_1)$ and $G_2$ by joining every vertex of $V(G_1)$ with every vertex of $V(G_2)$. The subdivision-edge join of $G_1$ and $G_2$, denoted by $G_1\underline{\vee}G_2$, is the graph obtained from $\mathcal{S}(G_1)$ and $G_2$ by joining every vertex of $I(G_1)$ with every vertex of $V(G_2)$, where $I(G_1)$ is the set of inserted vertices of $\mathcal{S}(G_1)$. In this paper we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of $G_1\dot{\vee}G_2$ (respectively, $G_1\underline{\vee}G_2$) for a regular graph $G_1$ and an arbitrary graph $G_2$, in terms of the corresponding spectra of $G_1$ and $G_2$. As applications, these results enable us to construct infinitely many pairs of cospectral graphs. We also give the number of the spanning trees and the Kirchhoff index of $G_1\dot{\vee}G_2$ (respectively, $G_1\underline{\vee}G_2$) for a regular graph $G_1$ and an arbitrary graph $G_2$.

Quadratic unitary Cayley graphs of finite commutative rings

2015-04-11

Xiaogang Liu , Sanming Zhou

View PDF Chat

Spectral characterizations of propeller graphs

2014-01-01

Xiaogang Liu , Sanming Zhou

A propeller graph is obtained from an ∞-graph by attaching a path to the vertex of degree four, where an ∞-graph consists of two cycles with precisely one common vertex. … A propeller graph is obtained from an ∞-graph by attaching a path to the vertex of degree four, where an ∞-graph consists of two cycles with precisely one common vertex. In this paper, it is proved that all propeller graphs are determined by their Laplacian spectra as well as their signless Laplacian spectra.

View PDF Chat

Extremality of Graph Entropy Based on Degrees of Uniform Hypergraphs with Few Edges

2019-04-25

Dan Hu , Xue Liang Li , Xiaogang Liu +1 more

View PDF Chat

Distance powers of unitary Cayley graphs

2016-05-30

Xiaogang Liu , Binlong Li

Graphs whose A_α radius does not exceed 2

2020-01-01

Francesco Belardo , Xiaogang Liu , Jianfeng Wang +1 more

Let A(G) and D(G) be the adjacency matrix and the degree matrix of a graph G, respectively.For any real α ∈ [0, 1], we consider A α (G) = αD(G) … Let A(G) and D(G) be the adjacency matrix and the degree matrix of a graph G, respectively.For any real α ∈ [0, 1], we consider A α (G) = αD(G) + (1 -α)A(G) as a graph matrix, whose largest eigenvalue is called the A α -spectral radius of G.We first show that the smallest limit point for the A α -spectral radius of graphs is 2, and then we characterize the connected graphs whose A α -spectral radius is at most 2. Finally, we show that all such graphs, with four exceptions, are determined by their A α -spectra.

Laplacian spectral characterization of some double starlike trees

2012-01-01

Pengli Lu , Xiaogang Liu

A tree is called double starlike if it has exactly two vertices of degree greater than two. Let $H(p,n,q)$ denote the double starlike tree obtained by attaching $p$ pendant vertices … A tree is called double starlike if it has exactly two vertices of degree greater than two. Let $H(p,n,q)$ 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(p,n,q)$ is determined by its Laplacian spectrum.

View PDF Chat

Spectral characterizations of sandglass graphs

2009-02-28

Pengli Lu , Xiaogang Liu , Zhanting Yuan +1 more

Computing the permanental polynomials of graphs

2017-02-15

Xiaogang Liu , Tingzeng Wu

Energies of unitary one-matching bi-Cayley graphs over finite commutative rings

2019-01-14

Xiaogang Liu

The Laplacian energy and Laplacian Estrada index of random multipartite graphs

2016-05-27

Dan Hu , Xueliang Li , Xiaogang Liu +1 more

Laplacian spectral characterization of dumbbell graphs and theta graphs

2016-02-18

Xiaogang Liu , Pengli Lu

Let [Formula: see text] and [Formula: see text] denote the path and cycle on [Formula: see text] vertices, respectively. The dumbbell graph, denoted by [Formula: see text], is the graph … Let [Formula: see text] and [Formula: see text] denote the path and cycle on [Formula: see text] vertices, respectively. The dumbbell graph, denoted by [Formula: see text], is the graph obtained from two cycles [Formula: see text], [Formula: see text] and a path [Formula: see text] by identifying each pendant vertex of [Formula: see text] with a vertex of a cycle, respectively. The theta graph, denoted by [Formula: see text], is the graph formed by joining two given vertices via three disjoint paths [Formula: see text], [Formula: see text] and [Formula: see text], respectively. In this paper, we prove that all dumbbell graphs as well as all theta graphs are determined by their [Formula: see text]-spectra.

View PDF Chat

Spectral characterizations of propeller graphs

2012-01-01

Xiaogang Liu , Sanming Zhou

A propeller graph is obtained from an $\infty$-graph by attaching a path to the vertex of degree four, where an $\infty$-graph consists of two cycles with precisely one common vertex. … A propeller graph is obtained from an $\infty$-graph by attaching a path to the vertex of degree four, where an $\infty$-graph consists of two cycles with precisely one common vertex. In this paper, we prove that all propeller graphs are determined by their Laplacian spectra as well as their signless Laplacian spectra.

View PDF Chat

The von Neumann entropy of random multipartite graphs

2017-08-18

Dan Hu , Xueliang Li , Xiaogang Liu +1 more

Laplacian spectral moment and Laplacian Estrada index of random graphs

2018-02-07

Nan Gao , Dan Hu , Xiaogang Liu +1 more

Energies of complements of unitary one-matching bi-Cayley graphs over commutative rings

2021-05-11

Jinxing Yang , Xiaogang Liu , Ligong Wang

In this paper, we determine the energies of complements of unitary one-matching bi-Cayley graphs over finite commutative rings. We also determine the energies of some one-matching bi-gcd-graphs as well as … In this paper, we determine the energies of complements of unitary one-matching bi-Cayley graphs over finite commutative rings. We also determine the energies of some one-matching bi-gcd-graphs as well as the energies of complements of some one-matching bi-gcd-graphs, which are generalizations of unitary one-matching bi-Cayley graphs.

Graphs determined by their $A_{\alpha}$-spectra

2017-09-04

Huiqiu Lin , Xiaogang Liu , Jie Xue

Let $G$ be a graph with $n$ vertices, and let $A(G)$ and $D(G)$ denote respectively the adjacency matrix and the degree matrix of $G$. Define $$ A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G) $$ for … Let $G$ be a graph with $n$ vertices, and let $A(G)$ and $D(G)$ denote respectively the adjacency matrix and the degree matrix of $G$. Define $$ A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G) $$ for any real $\alpha\in [0,1]$. The collection of eigenvalues of $A_{\alpha}(G)$ together with multiplicities are called the \emph{$A_{\alpha}$-spectrum} of $G$. A graph $G$ is said to be \emph{determined by its $A_{\alpha}$-spectrum} if all graphs having the same $A_{\alpha}$-spectrum as $G$ are isomorphic to $G$. We first prove that some graphs are determined by its $A_{\alpha}$-spectrum for $0\leq\alpha<1$, including the complete graph $K_m$, the star $K_{1,n-1}$, the path $P_n$, the union of cycles and the complement of the union of cycles, the union of $K_2$ and $K_1$ and the complement of the union of $K_2$ and $K_1$, and the complement of $P_n$. Setting $\alpha=0$ or $\frac{1}{2}$, those graphs are determined by $A$- or $Q$-spectra. Secondly, when $G$ is regular, we show that $G$ is determined by its $A_{\alpha}$-spectrum if and only if the join $G\vee K_m$ is determined by its $A_{\alpha}$-spectrum for $\frac{1}{2}<\alpha<1$. Furthermore, we also show that the join $K_m\vee P_n$ is determined by its $A_{\alpha}$-spectrum for $\frac{1}{2}<\alpha<1$. In the end, we pose some related open problems for future study.

On the Normalized Laplacian Permanental Polynomial of a Graph

2019-01-25

Xiaogang Liu , Tingzeng Wu

Unitary homogeneous bi-Cayley graphs over finite commutative rings

2019-08-21

Xiaogang Liu , Chengxin Yan

Let [Formula: see text] denote the unitary homogeneous bi-Cayley graph over a finite commutative ring [Formula: see text]. In this paper, we determine the energy of [Formula: see text] and … Let [Formula: see text] denote the unitary homogeneous bi-Cayley graph over a finite commutative ring [Formula: see text]. In this paper, we determine the energy of [Formula: see text] and that of its complement and line graph, and characterize when such graphs are hyperenergetic. We also give a necessary and sufficient condition for [Formula: see text] (respectively, the complement of [Formula: see text], the line graph of [Formula: see text]) to be Ramanujan.

Fractional revival on Cayley graphs over abelian groups

2024-08-22

Jing Wang , Ligong Wang , Xiaogang Liu

View PDF Chat

SELECTED TOPICS IN SPECTRAL GRAPH THEORY

2016-02-17

Xiaogang Liu

An abstract is not available for this content so a preview has been provided. As you have access to this content, a full PDF is available via the ‘Save PDF’ … An abstract is not available for this content so a preview has been provided. As you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

View PDF Chat

Laplacian characterization of graph products

2010-07-15

Suijie Wang , Xiaogang Liu

This paper studies the Laplacian characterization of three classes of graph products. They are the products of trees and complete graphs, unicyclic graphs and complete graphs, and bicyclic graphs and … This paper studies the Laplacian characterization of three classes of graph products. They are the products of trees and complete graphs, unicyclic graphs and complete graphs, and bicyclic graphs and complete graphs. Let G = (V G, EG) be a connected graph with |EG| ≤ |V G| + 1 and Km the complete graphs with m vertices. The main result of this paper states that, if G (G 6= C6, Θ3,2,5) is determined by its Laplacain spectrum, so is the product G×Km. In addition, the cospectral graphs of C6 ×Km and Θ3,2,5 ×Km have been found.

Extremality of graph entropy based on degrees of uniform hypergraphs with few edges

2017-01-01

Dan Hu , Xueliang Li , Xiaogang Liu +1 more

Let $\mathcal{H}$ be a hypergraph with $n$ vertices. Suppose that $d_1,d_2,\ldots,d_n$ are degrees of the vertices of $\mathcal{H}$. The $t$-th graph entropy based on degrees of $\mathcal{H}$ is defined as … Let $\mathcal{H}$ be a hypergraph with $n$ vertices. Suppose that $d_1,d_2,\ldots,d_n$ are degrees of the vertices of $\mathcal{H}$. The $t$-th graph entropy based on degrees of $\mathcal{H}$ is defined as $$ I_d^t(\mathcal{H}) =-\sum_{i=1}^{n}\left(\frac{d_i^{t}}{\sum_{j=1}^{n}d_j^{t}}\log\frac{d_i^{t}}{\sum_{j=1}^{n}d_j^{t}}\right) =\log\left(\sum_{i=1}^{n}d_i^{t}\right)-\sum_{i=1}^{n}\left(\frac{d_i^{t}}{\sum_{j=1}^{n}d_j^{t}}\log d_i^{t}\right), $$ where $t$ is a real number and the logarithm is taken to the base two. In this paper we obtain upper and lower bounds of $I_d^t(\mathcal{H})$ for $t=1$, when $\mathcal{H}$ is among all uniform supertrees, unicyclic uniform hypergraphs and bicyclic uniform hypergraphs, respectively.

View PDF Chat

On the Lower Bound of the Divisibility of Exponential Sums in Binomial Case

2015-01-01

Xiaogang Liu

Francis Castro, et al [2] computed the exact divisibility of families of exponential sums associated to binomials $F(X) = aX^{d_1} + bX^{d_2}$ over $\mathbb{F}_p$, and a conjecture is presented for … Francis Castro, et al [2] computed the exact divisibility of families of exponential sums associated to binomials $F(X) = aX^{d_1} + bX^{d_2}$ over $\mathbb{F}_p$, and a conjecture is presented for related work. Here we study this question.

Spectral properties of unitary Cayley graphs of finite commutative rings

2012-01-01

Xiaogang Liu , Sanming Zhou

Let $R$ be a finite commutative ring. The unitary Cayley graph of $R$, denoted $G_R$, is the graph with vertex set $R$ and edge set ${{a,b}:a,b\in R, a-b\in R^\times}$, where … Let $R$ be a finite commutative ring. The unitary Cayley graph of $R$, denoted $G_R$, is the graph with vertex set $R$ and edge set ${{a,b}:a,b\in R, a-b\in R^\times}$, where $R^\times$ is the set of units of $R$. An $r$-regular graph is Ramanujan if the absolute value of every eigenvalue of it other than $\pm r$ is at most $2\sqrt{r-1}$. In this paper we give a necessary and sufficient condition for $G_R$ to be Ramanujan, and a necessary and sufficient condition for the complement of $G_R$ to be Ramanujan. We also determine the energy of the line graph of $G_R$, and compute the spectral moments of $G_R$ and its line graph.

View PDF Chat

Spectra of neighbourhood corona and construction of new expanders from known ones

2012-09-26

Xiaogang Liu , Sanming Zhou

Given simple graphs $G_1$ and $G_2$, the neighbourhood corona of $G_1$ and $G_2$, denoted $G_1\star G_2$, is the graph obtained by taking one copy of $G_1$ and $|V(G_1)|$ copies of … Given simple graphs $G_1$ and $G_2$, the neighbourhood corona of $G_1$ and $G_2$, denoted $G_1\star G_2$, is the graph obtained by taking one copy of $G_1$ and $|V(G_1)|$ copies of $G_2$, and joining the neighbours of the $i$th vertex of $G_1$ to every vertex in the $i$th copy of $G_2$. In this paper we determine the adjacency spectrum of $G_1 \star G_2$ for arbitrary $G_1$ and $G_2$, and the Laplacian spectrum and signless Laplacian spectrum of $G_1\star G_2$ for regular $G_1$ and arbitrary $G_2$, in terms of the corresponding spectrum of $G_1$ and $G_2$. The results on the adjacency and signless Laplacian spectra enable us to construct new pairs of adjacency cospectral and signless Laplacian cospectral graphs. As applications of the results on the Laplacian spectra, we give constructions of new families of expander graphs from known ones by using neighbourhood coronae.

Perfect state transfer in NEPS of complete graphs

2020-01-01

Yipeng Li , Xiaogang Liu , Shenggui Zhang +1 more

Perfect state transfer in graphs is a concept arising from quantum physics and quantum computing. Given a graph $G$ with adjacency matrix $A_G$, the transition matrix of $G$ with respect … Perfect state transfer in graphs is a concept arising from quantum physics and quantum computing. Given a graph $G$ with adjacency matrix $A_G$, the transition matrix of $G$ with respect to $A_G$ is defined as $H_{A_{G}}(t) = \exp(-\mathrm{i}tA_{G})$, $t \in \mathbb{R},\ \mathrm{i}=\sqrt{-1}$. We say that perfect state transfer from vertex $u$ to vertex $v$ occurs in $G$ at time $\tau$ if $u \ne v$ and the modulus of the $(u,v)$-entry of $H_{A_G}(\tau)$ is equal to $1$. If the moduli of all diagonal entries of $H_{A_G}(\tau)$ are equal to $1$ for some $\tau$, then $G$ is called periodic with period $\tau$. In this paper we give a few sufficient conditions for NEPS of complete graphs to be periodic or exhibit perfect state transfer.

Graphs determined by the (signless) Laplacian permanental polynomials

2020-11-18

Xiaogang Liu , Tingzeng Wu

Characterizing which graphs are determined by their (signless) Laplacian permanental polynomials is an interesting problem. In this paper, we prove that paths, cycles and lollipop graphs are determined by their … Characterizing which graphs are determined by their (signless) Laplacian permanental polynomials is an interesting problem. In this paper, we prove that paths, cycles and lollipop graphs are determined by their Laplacian permanental polynomials as well as their signless Laplacian permanental polynomials, respectively.

On the Assignment Graphs of Oriented Graphs

2021-11-08

J. Glassband , Eugene Fiorini , Garrison Koch +5 more

In this paper, we extend the ideas of graph pebbling to oriented graphs and find a classification for all graphs with fully traversable pebbling assignments that are isomorphic to their … In this paper, we extend the ideas of graph pebbling to oriented graphs and find a classification for all graphs with fully traversable pebbling assignments that are isomorphic to their assignment graph. We then give some cases in which a graph with a non-fully traversable pebbling assignment is isomorphic to its assignment graph.

One-matching bi-Cayley graphs and homogeneous bi-Cayley graphs over finite cyclic groups

2022-01-06

Xiaogang Liu , Tingzeng Wu

In this paper, we characterize when t-type one-matching (respectively, homogeneous) bi-Cayley graphs over finite cyclic groups are integral. We also give a necessary and sufficient condition for some integral t-type … In this paper, we characterize when t-type one-matching (respectively, homogeneous) bi-Cayley graphs over finite cyclic groups are integral. We also give a necessary and sufficient condition for some integral t-type one-matching (respectively, homogeneous) bi-Cayley graphs over finite cyclic groups of prime power order to be Ramanujan.

State transfers in vertex complemented coronas

2022-07-08

Jingyue Wang , Xiaogang Liu

View PDF Chat

Algebraic degrees of n-Cayley digraphs over abelian groups

2025-05-01

Hao Li , Xiaogang Liu

Integral Cayley graphs over a group of order 6 <i>n</i>

2025-03-18

Jing Wang , Xiaogang Liu , Ligong Wang

Fractional revival on quasi-abelian Cayley graphs

2025-02-20

Yi Fang , Xueyi Huang , Xiaogang Liu +1 more

Fractional revival, a quantum transport phenomenon critical to entanglement generation in quantum spin networks, generalizes the notion of perfect state transfer on graphs. A Cayley graph $\mathrm{Cay}(G,S)$ is called quasi-abelian … Fractional revival, a quantum transport phenomenon critical to entanglement generation in quantum spin networks, generalizes the notion of perfect state transfer on graphs. A Cayley graph $\mathrm{Cay}(G,S)$ is called quasi-abelian if its connection set $S$ is a union of conjugacy classes of the group $G$. In this paper, we establish a necessary and sufficient condition for quasi-abelian Cayley graphs to have fractional revival. This extends a result of Cao and Luo (2022) on the existence of fractional revival in Cayley graphs over abelian groups.

View PDF Chat

Fractional revival on semi-Cayley graphs over abelian groups

2024-12-03

Jing Wang , Ligong Wang , Xiaogang Liu

In this paper, we investigate the existence of fractional revival on semi-Cayley graphs over finite abelian groups. We give some necessary and sufficient conditions for semi-Cayley graphs over finite abelian … In this paper, we investigate the existence of fractional revival on semi-Cayley graphs over finite abelian groups. We give some necessary and sufficient conditions for semi-Cayley graphs over finite abelian groups admitting fractional revival. We also show that integrality is necessary for some semi-Cayley graphs admitting fractional revival. Moreover, we characterize the minimum time when semi-Cayley graphs admit fractional revival. As applications, we give examples of certain Cayley graphs over the generalized dihedral groups and generalized dicyclic groups admitting fractional revival.

View PDF Chat

Enumeration of dicirculant digraphs

2024-09-06

Jing Wang , Ligong Wang , Xiaogang Liu

Let $T_{4p}=\langle a,b\mid a^{2p}=1,a^p=b^2, b^{-1}ab=a^{-1}\rangle$ be the dicyclic group of order $4p$. A Cayley digraph over $T_{4p}$ is called a dicirculant digraph. In this paper, we calculate the number of … Let $T_{4p}=\langle a,b\mid a^{2p}=1,a^p=b^2, b^{-1}ab=a^{-1}\rangle$ be the dicyclic group of order $4p$. A Cayley digraph over $T_{4p}$ is called a dicirculant digraph. In this paper, we calculate the number of (connected) dicirculant digraphs of order $4p$ ($p$ prime) up to isomorphism by using the P\'olya Enumeration Theorem. Moreover, we get the number of (connected) dicirculant digraphs of order $4p$ ($p$ prime) and out-degree $k$ for every $k$.

View PDF Chat

Fractional revival on Cayley graphs over abelian groups

2024-08-22

Jing Wang , Ligong Wang , Xiaogang Liu

View PDF Chat

So's conjecture for integral circulant graphs of 4 types

2024-04-25

Hao Li , Xiaogang Liu

View PDF Chat

Integral Cayley graphs over a group of order $6n$

2024-01-01

Jing Wang , Xiaogang Liu , Ligong Wang

In this paper, we study the integral Cayley graphs over a non-abelian group $U_{6n}=\langle a,b\mid a^{2n}=b^3=1, a^{-1}ba=b^{-1}\rangle$ of order $6n$. We give a necessary and sufficient condition for the integrality … In this paper, we study the integral Cayley graphs over a non-abelian group $U_{6n}=\langle a,b\mid a^{2n}=b^3=1, a^{-1}ba=b^{-1}\rangle$ of order $6n$. We give a necessary and sufficient condition for the integrality of Cayley graphs over $U_{6n}$. We also study relationships between the integrality of Cayley graphs over $U_{6n}$ and the Boolean algebra of cyclic groups. As applications, we construct some infinite families of connected integral Cayley graphs over $U_{6n}$.

View PDF Chat

Algebraic degrees of $n$-Cayley digraphs over abelian groups

2024-01-01

Hao Li , Xiaogang Liu

A digraph is called an $n$-Cayley digraph if its automorphism group has an $n$-orbit semiregular subgroup. We determine the splitting fields of $n$-Cayley digraphs over abelian groups and compute a … A digraph is called an $n$-Cayley digraph if its automorphism group has an $n$-orbit semiregular subgroup. We determine the splitting fields of $n$-Cayley digraphs over abelian groups and compute a bound on their algebraic degrees, before applying our results on Cayley digraphs over non-abelian groups.

On the sum of the k largest absolute values of Laplacian eigenvalues of digraphs

2023-07-20

Xiuwen Yang , Xiaogang Liu , Ligong Wang

Let $L(G)$ be the Laplacian matrix of a digraph $G$ and $S_k(G)$ be the sum of the $k$ largest absolute values of Laplacian eigenvalues of $G$. Let $C_n^+$ be a … Let $L(G)$ be the Laplacian matrix of a digraph $G$ and $S_k(G)$ be the sum of the $k$ largest absolute values of Laplacian eigenvalues of $G$. Let $C_n^+$ be a digraph with $n+1$ vertices obtained from the directed cycle $C_n$ by attaching a pendant arc whose tail is on $C_n$. A digraph is $\mathbb{C}_n^+$-free if it contains no $C_{\ell}^+$ as a subdigraph for any $2\leq \ell \leq n-1$. In this paper, we present lower bounds of $S_n(G)$ of digraphs of order $n$. We provide the exact values of $S_k(G)$ of directed cycles and $\mathbb{C}_n^+$-free unicyclic digraphs. Moreover, we obtain upper bounds of $S_k(G)$ of $\mathbb{C}_n^+$-free digraphs which have vertex-disjoint directed cycles.

View PDF Chat

No Laplacian perfect state transfer in total graphs

2023-05-29

Dayan Liu , Xiaogang Liu

Fractional revival on semi-Cayley graphs over abelian groups

2023-01-01

Jing Wang , Ligong Wang , Xiaogang Liu

Pretty good fractional revival on Cayley graphs over dicyclic groups

2023-01-01

Jing Wang , Ligong Wang , Xiaogang Liu

In this paper, we investigate the existence of pretty good fractional revival on Cayley graphs over dicyclic groups. We first give a necessary and sufficient description for Cayley graphs over … In this paper, we investigate the existence of pretty good fractional revival on Cayley graphs over dicyclic groups. We first give a necessary and sufficient description for Cayley graphs over dicyclic groups admitting pretty good fractional revival. By this description, we give some sufficient conditions for Cayley graphs over dicyclic groups admitting or not admitting pretty good fractional revival.

State transfers in vertex complemented coronas

2022-07-08

Jingyue Wang , Xiaogang Liu

View PDF Chat

Eigenvalues of Cayley Graphs

2022-04-21

Xiaogang Liu , Sanming Zhou

View PDF Chat

One-matching bi-Cayley graphs and homogeneous bi-Cayley graphs over finite cyclic groups

2022-01-06

Xiaogang Liu , Tingzeng Wu

Fractional revival on Cayley graphs over abelian groups

2022-01-01

Jing Wang , Ligong Wang , Xiaogang Liu

In this paper, we investigate the existence of fractional revival on Cayley graphs over finite abelian groups. We give a necessary and sufficient condition for Cayley graphs over finite abelian … In this paper, we investigate the existence of fractional revival on Cayley graphs over finite abelian groups. We give a necessary and sufficient condition for Cayley graphs over finite abelian groups to have fractional revival. As applications, the existence of fractional revival on circulant graphs and cubelike graphs are characterized.

On the Assignment Graphs of Oriented Graphs

2021-11-08

J. Glassband , Eugene Fiorini , Garrison Koch +5 more

Energies of complements of unitary one-matching bi-Cayley graphs over commutative rings

2021-05-11

Jinxing Yang , Xiaogang Liu , Ligong Wang

Graphs determined by the (signless) Laplacian permanental polynomials

2020-11-18

Xiaogang Liu , Tingzeng Wu

Perfect state transfer in NEPS of complete graphs

2020-10-14

Yipeng Li , Xiaogang Liu , Shenggui Zhang +1 more

View PDF Chat

Laplacian state transfer in total graphs

2020-09-19

Xiaogang Liu , Qiang Wang

Graphs whose A_α radius does not exceed 2

2020-01-01

Francesco Belardo , Xiaogang Liu , Jianfeng Wang +1 more

Perfect state transfer in NEPS of complete graphs

2020-01-01

Yipeng Li , Xiaogang Liu , Shenggui Zhang +1 more

Unitary homogeneous bi-Cayley graphs over finite commutative rings

2019-08-21

Xiaogang Liu , Chengxin Yan

Extremality of Graph Entropy Based on Degrees of Uniform Hypergraphs with Few Edges

2019-04-25

Dan Hu , Xue Liang Li , Xiaogang Liu +1 more

View PDF Chat

On the Normalized Laplacian Permanental Polynomial of a Graph

2019-01-25

Xiaogang Liu , Tingzeng Wu

Energies of unitary one-matching bi-Cayley graphs over finite commutative rings

2019-01-14

Xiaogang Liu

Graphs determined by their <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll" id="d1e18" altimg="si42.gif"><mml:msub><mml:mrow><mml:mi>A</mml:mi></mml:mrow><mml:mrow><mml:mi>α</mml:mi></mml:mrow></mml:msub></mml:math>-spectra

2018-11-13

Huiqiu Lin , Xiaogang Liu , Jie Xue

On the A-characteristic polynomial of a graph

2018-02-14

Xiaogang Liu , Shunyi Liu

View PDF Chat

Laplacian spectral moment and Laplacian Estrada index of random graphs

2018-02-07

Nan Gao , Dan Hu , Xiaogang Liu +1 more

Graphs determined by their $A_{\alpha}$-spectra

2017-09-04

Huiqiu Lin , Xiaogang Liu , Jie Xue

The von Neumann entropy of random multipartite graphs

2017-08-18

Dan Hu , Xueliang Li , Xiaogang Liu +1 more

Computing the permanental polynomials of graphs

2017-02-15

Xiaogang Liu , Tingzeng Wu

Spectra of Subdivision-Vertex Join and Subdivision-Edge Join of Two Graphs

2017-02-06

Xiaogang Liu , Zuhe Zhang

View PDF Chat

The spectral distribution of random mixed graphs

2017-01-17

Dan Hu , Xueliang Li , Xiaogang Liu +1 more

Extremality of graph entropy based on degrees of uniform hypergraphs with few edges

2017-01-01

Dan Hu , Xueliang Li , Xiaogang Liu +1 more

View PDF Chat

Graphs determined by their $A_α$-spectra

2017-01-01

Huiqiu Lin , Xiaogang Liu , Jie Xue

Let $G$ be a graph with $n$ vertices, and let $A(G)$ and $D(G)$ denote respectively the adjacency matrix and the degree matrix of $G$. Define $$ A_α(G)=αD(G)+(1-α)A(G) $$ for any … Let $G$ be a graph with $n$ vertices, and let $A(G)$ and $D(G)$ denote respectively the adjacency matrix and the degree matrix of $G$. Define $$ A_α(G)=αD(G)+(1-α)A(G) $$ for any real $α\in [0,1]$. The collection of eigenvalues of $A_α(G)$ together with multiplicities are called the \emph{$A_α$-spectrum} of $G$. A graph $G$ is said to be \emph{determined by its $A_α$-spectrum} if all graphs having the same $A_α$-spectrum as $G$ are isomorphic to $G$. We first prove that some graphs are determined by its $A_α$-spectrum for $0\leqα<1$, including the complete graph $K_m$, the star $K_{1,n-1}$, the path $P_n$, the union of cycles and the complement of the union of cycles, the union of $K_2$ and $K_1$ and the complement of the union of $K_2$ and $K_1$, and the complement of $P_n$. Setting $α=0$ or $\frac{1}{2}$, those graphs are determined by $A$- or $Q$-spectra. Secondly, when $G$ is regular, we show that $G$ is determined by its $A_α$-spectrum if and only if the join $G\vee K_m$ is determined by its $A_α$-spectrum for $\frac{1}{2}

Distance powers of unitary Cayley graphs

2016-05-30

Xiaogang Liu , Binlong Li

The Laplacian energy and Laplacian Estrada index of random multipartite graphs

2016-05-27

Dan Hu , Xueliang Li , Xiaogang Liu +1 more

Laplacian spectral characterization of dumbbell graphs and theta graphs

2016-02-18

Xiaogang Liu , Pengli Lu

View PDF Chat

SELECTED TOPICS IN SPECTRAL GRAPH THEORY

2016-02-17

Xiaogang Liu

View PDF Chat

Quadratic unitary Cayley graphs of finite commutative rings

2015-04-11

Xiaogang Liu , Sanming Zhou

View PDF Chat

Resistance distance and Kirchhoff index of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si3.gif" display="inline" overflow="scroll"><mml:mi>R</mml:mi></mml:math>-vertex join and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si4.gif" display="inline" overflow="scroll"><mml:mi>R</mml:mi></mml:math>-edge join of two graphs

2015-03-16

Xiaogang Liu , Jiang Zhou , Changjiang Bu

Signless Laplacian spectral characterization of some joins

2015-02-08

Xiaogang Liu , Pengli Lu

View PDF Chat

On the Lower Bound of the Divisibility of Exponential Sums in Binomial Case

2015-01-01

Xiaogang Liu

Spectral characterizations of propeller graphs

2014-01-01

Xiaogang Liu , Sanming Zhou

View PDF Chat

Spectra of the neighbourhood corona of two graphs

2013-08-25

Xiaogang Liu , Sanming Zhou

View PDF Chat

Spectra of subdivision-vertex and subdivision-edge neighbourhood coronae

2013-02-08

Xiaogang Liu , Pengli Lu

View PDF Chat

Spectra of subdivision-vertex and subdivision-edge joins of graphs

2012-12-04

Xiaogang Liu , Zuhe Zhang

Coauthor	Papers Together
Sanming Zhou	10
Ligong Wang	8
Shenggui Zhang	6
Dan Hu	6
Pengli Lu	6
Xueliang Li	4
Xuerong Yong	4
Suijie Wang	4
Jing Wang	4
Yuanping Zhang	4
Tingzeng Wu	4
Jie Xue	3
Huiqiu Lin	3
Yuanping Zhang	2
Ligong Wang	2
Yipeng Li	2
Zuhe Zhang	2
Hao Li	2
Jing Wang	2
Xiongfeng Zhan	1
Jing Wang	1
Nan Gao	1
Jing Wang	1
Jingyue Wang	1
Jing Wang	1
Jinxing Yang	1
Xiuwen Yang	1
Xiangquan Gui	1
Garrison Koch	1
Binlong Li	1
Shenggui Zhang	1
Hao Li	1
Zhanting Yuan	1
Jianfeng Wang	1
Chengxin Yan	1
Shunyi Liu	1
E. Sabini	1
Jiang Zhou	1
Qiang Wang	1
Willem H. Haemers	1
J. Glassband	1
Dayan Liu	1
Francesco Belardo	1
Bingyan Zhang	1
Xueyi Huang	1
Andrew J. Woldar	1
S. Lebiere	1
Sheng Gui Zhang	1
Changjiang Bu	1
Xue Liang Li	1

Which graphs are determined by their spectrum?

2003-05-27

Edwin van Dam , Willem H. Haemers

View PDF Chat

An introduction to the theory of graph spectra

2010-10-01

Dragoš Cvetković , Peter Rowlinson , Slobodan Simić

This introductory text explores the theory of graph spectra: a topic with applications across a wide range of subjects, including computer science, quantum chemistry and electrical engineering. The spectra examined … This introductory text explores the theory of graph spectra: a topic with applications across a wide range of subjects, including computer science, quantum chemistry and electrical engineering. The spectra examined here are those of the adjacency matrix, the Seidel matrix, the Laplacian, the normalized Laplacian and the signless Laplacian of a finite simple graph. The underlying theme of the book is the relation between the eigenvalues and structure of a graph. Designed as an introductory text for graduate students, or anyone using the theory of graph spectra, this self-contained treatment assumes only a little knowledge of graph theory and linear algebra. The authors include many developments in the field which arise as a result of rapidly expanding interest in the area. Exercises, spectral data and proofs of required results are also provided. The end-of-chapter notes serve as a practical guide to the extensive bibliography of over 500 items.

Starlike trees are determined by their Laplacian spectrum

2007-02-08

G.R. Omidi , Khosro Tajbakhsh

Developments on spectral characterizations of graphs

2008-09-22

Edwin van Dam , Willem H. Haemers

View PDF Chat

Spectral characterizations of lollipop graphs

2008-03-06

Willem H. Haemers , Xiaogang Liu , Yuanping Zhang

Graph Zn and some graphs related to Zn are determined by their spectrum

2005-05-07

Xiaoling Shen , Yaoping Hou , Yuanping Zhang

Note the T-shape tree is determined by its Laplacian spectrum

2006-06-13

Wei Wang , Chengxian Xu

Spectral Properties of Unitary Cayley Graphs of Finite Commutative Rings

2012-10-25

Xiaogang Liu , Sanming Zhou

View PDF Chat

Spectral characterization of graphs with index at most <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mrow><mml:msqrt><mml:mrow><mml:mn>2</mml:mn><mml:mo>+</mml:mo><mml:msqrt><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msqrt></mml:mrow></mml:msqrt></mml:mrow></mml:math>

2006-10-03

Narges Ghareghani , G.R. Omidi , B. Tayfeh‐Rezaie

Perfect state transfer on distance-regular graphs and association schemes

2015-04-04

Gabriel Coutinho , Chris Godsil , Krystal Guo +1 more

View PDF Chat

Perfect state transfer in cubelike graphs

2011-05-20

Wang-Chi Cheung , Chris Godsil

View PDF Chat

The energy of a graph

2004-06-08

B. Ramachandran

When can perfect state transfer occur?

2012-01-01

Chris Godsil

AbstractLet X be a graph on n vertices with with adjacency matrix A andlet H(t) denote the matrix-valued function exp(iAt). If u and v aredistinct vertices in X, we say … AbstractLet X be a graph on n vertices with with adjacency matrix A andlet H(t) denote the matrix-valued function exp(iAt). If u and v aredistinct vertices in X, we say perfectstatetransferfrom u to v occursif there is a time τ such that |H(τ) u,v | = 1. Our chief problem is tocharacterize the cases where perfect state transfer occurs. We showthat if perfect state transfer does occur in a graph, then the square ofits spectral radius is either an integer or lies in a quadratic extensionof the rationals. From this we deduce that for any integer k thereonly ﬁnitely many graphs with maximum valency k on which perfectstate transfer occurs. We also show that if perfect state transfer fromu to v occurs, then the graphs X\u and X\v are cospectral and anyautomorphism of X that ﬁxes u must ﬁx v (and conversely). 1 Introduction Let Xbe a graph on nvertices with with adjacency matrix Aand let H(t)denote the matrix-valued function exp(iAt). If uand vare distinct vertices inX, we say perfect state transfer

View PDF Chat

The energy of unitary cayley graphs

2009-07-16

Aleksandar Ilić

On the Energy of Unitary Cayley Graphs

2009-07-24

H. N. Ramaswamy , C. R. Veena

In this note we obtain the energy of unitary Cayley graph $X_{n}$ which extends a result of R. Balakrishnan for power of a prime and also determine when they are … In this note we obtain the energy of unitary Cayley graph $X_{n}$ which extends a result of R. Balakrishnan for power of a prime and also determine when they are hyperenergetic. We also prove that ${E(X_{n})\over 2(n-1)}\geq{2^{k}\over 4k}$, where $k$ is the number of distinct prime divisors of $n$. Thus the ratio ${E(X_{n})\over 2(n-1)}$, measuring the degree of hyperenergeticity of $X_{n}$, grows exponentially with $k$.

View PDF Chat

The multi-fan graphs are determined by their Laplacian spectra

2007-09-08

Xiaogang Liu , Yuanping Zhang , Xiangquan Gui

Perfect state transfer on gcd-graphs

2016-12-07

Hiranmoy Pal , Bikash Bhattacharjya

Let G be a graph with adjacency matrix A. The transition matrix of G is denoted by H(t) and it is defined by The graph G has perfect state transfer … Let G be a graph with adjacency matrix A. The transition matrix of G is denoted by H(t) and it is defined by The graph G has perfect state transfer (PST) from a vertex u to another vertex v if there exist such that the uvth entry of has unit modulus. In case when , we say that G is periodic at the vertex u at time . The graph G is said to be periodic if it is periodic at all vertices at the same time. A gcd-graph is a Cayley graph over a finite abelian group defined by greatest common divisors. We establish a sufficient condition for a gcd-graph to have periodicity and PST at . Using this we deduce that there exists gcd-graph having PST over an abelian group of order divisible by 4. Also we find a necessary and sufficient condition for a class of gcd-graphs to be periodic at . Using this we characterize a class of gcd-graphs not exhibiting PST at for all positive integers k.

View PDF Chat

The characteristic polynomial of the Laplacian of graphs in (a,b)-linear classes

2002-11-01

Carla Silva Oliveira , Nair Maria Maia de Abreu , Samuel Jurkiewicz

Energy of unitary Cayley graphs and gcd-graphs

2011-04-15

Dariush Kiani , Mohsen Molla Haji Aghaei , Yotsanan Meemark +1 more

Quantum Communication through an Unmodulated Spin Chain

2003-11-10

Sougato Bose

We propose a scheme for using an unmodulated and unmeasured spin chain as a channel for short distance quantum communications. The state to be transmitted is placed on one spin … We propose a scheme for using an unmodulated and unmeasured spin chain as a channel for short distance quantum communications. The state to be transmitted is placed on one spin of the chain and received later on a distant spin with some fidelity. We first obtain simple expressions for the fidelity of quantum state transfer and the amount of entanglement sharable between any two sites of an arbitrary Heisenberg ferromagnet using our scheme. We then apply this to the realizable case of an open ended chain with nearest neighbor interactions. The fidelity of quantum state transfer is obtained as an inverse discrete cosine transform and as a Bessel function series. We find that in a reasonable time, a qubit can be directly transmitted with better than classical fidelity across the full length of chains of up to 80 spins. Moreover, our channel allows distillable entanglement to be shared over arbitrary distances.

View PDF Chat

Perfect transfer of arbitrary states in quantum spin networks

2005-03-14

Matthias Christandl , Nilanjana Datta , T. C. Dorlas +3 more

We propose a class of qubit networks that admit perfect state transfer of any two-dimensional quantum state in a fixed period of time. We further show that such networks can … We propose a class of qubit networks that admit perfect state transfer of any two-dimensional quantum state in a fixed period of time. We further show that such networks can distribute arbitrary entangled states between two distant parties, and can, by using such systems in parallel, transmit the higher-dimensional systems states across the network. Unlike many other schemes for quantum computation and communication, these networks do not require qubit couplings to be switched on and off. When restricted to $N$-qubit spin networks of identical qubit couplings, we show that $2\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{3}N$ is the maximal perfect communication distance for hypercube geometries. Moreover, if one allows fixed but different couplings between the qubits then perfect state transfer can be achieved over arbitrarily long distances in a linear chain. This paper expands and extends the work done by Christandl et al., Phys. Rev. Lett. 92, 187902 (2004).

View PDF Chat

On the spectral characterization of T-shape trees

2005-12-22

Wei Wang , Chengxian Xu

On the spectral characterizations of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si8.gif" display="inline" overflow="scroll"><mml:mi>∞</mml:mi></mml:math>-graphs

2010-03-30

Jianfeng Wang , Qingxiang Huang , Francesco Belardo +1 more

Perfect State Transfer in Quantum Spin Networks

2004-05-04

Matthias Christandl , Nilanjana Datta , Artur Ekert +1 more

We propose a class of qubit networks that admit perfect transfer of any quantum state in a fixed period of time. Unlike many other schemes for quantum computation and communication, … We propose a class of qubit networks that admit perfect transfer of any quantum state in a fixed period of time. Unlike many other schemes for quantum computation and communication, these networks do not require qubit couplings to be switched on and off. When restricted to N-qubit spin networks of identical qubit couplings, we show that 2 log_3 N is the maximal perfect communication distance for hypercube geometries. Moreover, if one allows fixed but different couplings between the qubits then perfect state transfer can be achieved over arbitrarily long distances in a linear chain.

View PDF Chat

The spectrum and the signless Laplacian spectrum of coronae

2012-06-15

Shu‐Yu Cui , Gui‐Xian Tian

Eigenvalues of Cayley Graphs

2022-04-21

Xiaogang Liu , Sanming Zhou

View PDF Chat

Spectra of coronae

2011-04-14

Cam McLeman , Erin McNicholas

View PDF Chat

Longest Induced Cycles in Circulant Graphs

2005-10-13

Elena Fuchs

In this paper we study the length of the longest induced cycle in the unit circulant graph $X_n = Cay({\Bbb Z}_n; {\Bbb Z}_n^*)$, where ${\Bbb Z}_n^*$ is the group of … In this paper we study the length of the longest induced cycle in the unit circulant graph $X_n = Cay({\Bbb Z}_n; {\Bbb Z}_n^*)$, where ${\Bbb Z}_n^*$ is the group of units in ${\Bbb Z}_n$. Using residues modulo the primes dividing $n$, we introduce a representation of the vertices that reduces the problem to a purely combinatorial question of comparing strings of symbols. This representation allows us to prove that the multiplicity of each prime dividing $n$, and even the value of each prime (if sufficiently large) has no effect on the length of the longest induced cycle in $X_n$. We also see that if $n$ has $r$ distinct prime divisors, $X_n$ always contains an induced cycle of length $2^r+2$, improving the $r \ln r$ lower bound of Berrezbeitia and Giudici. Moreover, we extend our results for $X_n$ to conjunctions of complete $k_i$-partite graphs, where $k_i$ need not be finite, and also to unit circulant graphs on any quotient of a Dedekind domain.

View PDF Chat

The Lollipop Graph is Determined by its Spectrum

2008-05-26

Romain Boulet , Bertrand Jouve

An even (resp. odd) lollipop is the coalescence of a cycle of even (resp. odd) length and a path with pendant vertex as distinguished vertex. It is known that the … An even (resp. odd) lollipop is the coalescence of a cycle of even (resp. odd) length and a path with pendant vertex as distinguished vertex. It is known that the odd lollipop is determined by its spectrum and the question is asked by W. Haemers, X. Liu and Y. Zhang for the even lollipop. A private communication of Behruz Tayfeh-Rezaie pointed out that an even lollipop with a cycle of length at least $6$ is determined by its spectrum but the result for lollipops with a cycle of length $4$ is still unknown. We give an unified proof for lollipops with a cycle of length not equal to $4$, generalize it for lollipops with a cycle of length $4$ and therefore answer the question. Our proof is essentially based on a method of counting closed walks.

View PDF Chat

Spectra of Graphs

2011-12-15

Andries E. Brouwer , Willem H. Haemers

Perfect state transfer on NEPS of the path on three vertices

2015-11-11

Hiranmoy Pal , Bikash Bhattacharjya

View PDF Chat

Quadratic unitary Cayley graphs of finite commutative rings

2015-04-11

Xiaogang Liu , Sanming Zhou

View PDF Chat

The automorphisms of bi-Cayley graphs

2015-11-10

Jin‐Xin Zhou , Yan‐Quan Feng

The Energy of a Graph: Old and New Results

2001-01-01

Iván Gutman

Integral circulant graphs

2006-01-01

Wasin So

New results on the energy of integral circulant graphs

2011-09-18

Aleksandar Ilić , Milan Bašić

View PDF Chat

Laplacian spectral characterization of some graphs obtained by product operation

2012-02-25

Jiang Zhou , Changjiang Bu

Distance powers of unitary Cayley graphs

2016-05-30

Xiaogang Liu , Binlong Li

No Laplacian Perfect State Transfer in Trees

2015-01-01

Gabriel Coutinho , Henry Liu

We consider a system of qubits coupled via nearest-neighbour interaction governed by the Heisenberg Hamiltonian. We further suppose that all coupling constants are equal to $1$. We are interested in … We consider a system of qubits coupled via nearest-neighbour interaction governed by the Heisenberg Hamiltonian. We further suppose that all coupling constants are equal to $1$. We are interested in determining which graphs allow for a transfer of quantum state with fidelity equal to $1$. To answer this question, it is enough to consider the action of the Laplacian matrix of the graph in a vector space of suitable dimension. Our main result is that if the underlying graph is a tree with more than two vertices, then perfect state transfer does not happen. We also explore related questions, such as what happens in bipartite graphs and graphs with an odd number of spanning trees. Finally, we consider the model based on the $XY$-Hamiltonian, whose action is equivalent to the action of the adjacency matrix of the graph. In this case, we conjecture that perfect state transfer does not happen in trees with more than three vertices.

View PDF Chat

Quantum computation and decision trees

1998-08-01

Edward Farhi , Sam Gutmann

Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root, … Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root, to see if the tree contains a node $n$ level from the root. We devise a quantum-mechanical algorithm that evolves a state, initially localized at the root, through the tree. We prove that if the classical strategy succeeds in reaching level $n$ in time polynomial in $n,$ then so does the quantum algorithm. Moreover, we find examples of trees for which the classical algorithm requires time exponential in $n,$ but for which the quantum algorithm succeeds in polynomial time. The examples we have so far, however, could also be solved in polynomial time by different classical algorithms.

View PDF Chat

One-matching bi-Cayley graphs over abelian groups

2008-07-08

István Kovács , Aleksander Malnič , Dragan Marušič +1 more

The spectrum of semi-Cayley graphs over abelian groups

2010-02-09

Xing Gao , Yanfeng Luo

On the Unitary Cayley Graph of a Finite Ring

2009-09-18

Reza Akhtar , Megan Boggess , Tiffany Jackson-Henderson +4 more

We study the unitary Cayley graph associated to an arbitrary finite ring, determining precisely its diameter, girth, eigenvalues, vertex and edge connectivity, and vertex and edge chromatic number. We also … We study the unitary Cayley graph associated to an arbitrary finite ring, determining precisely its diameter, girth, eigenvalues, vertex and edge connectivity, and vertex and edge chromatic number. We also compute its automorphism group, settling a question of Klotz and Sander. In addition, we classify all planar graphs and perfect graphs within this class.

View PDF Chat

Signless Laplacians of finite graphs

2007-01-27

Dragoš Cvetković , Peter Rowlinson , Slobodan K. Simić

View PDF Chat

Introduction To Commutative Algebra

2018-03-09

Michael Atiyah

* Introduction * Rings and Ideals * Modules * Rings and Modules of Fractions * Primary Decomposition * Integral Dependence and Valuations * Chain Conditions * Noetherian Rings * Artin … * Introduction * Rings and Ideals * Modules * Rings and Modules of Fractions * Primary Decomposition * Integral Dependence and Valuations * Chain Conditions * Noetherian Rings * Artin Rings * Discrete Valuation Rings and Dedekind Domains * Completions * Dimension Theory

Laplacian spectral characterization of some graph products

2012-05-30

Xiaogang Liu , Suijie Wang

View PDF Chat

On the Laplacian eigenvalues of a graph

1998-12-01

Jiong-Sheng Li , Xiao‐Dong Zhang

Some Results for the Periodicity and Perfect State Transfer

2011-09-20

Jiang Zhou , Changjiang Bu , Jihong Shen

Let $G$ be a graph with adjacency matrix $A$, let $H(t)=\exp(itA)$. $G$ is called a periodic graph if there exists a time $\tau$ such that $H(\tau)$ is diagonal. If $u$ … Let $G$ be a graph with adjacency matrix $A$, let $H(t)=\exp(itA)$. $G$ is called a periodic graph if there exists a time $\tau$ such that $H(\tau)$ is diagonal. If $u$ and $v$ are distinct vertices in $G$, we say that perfect state transfer occurs from $u$ to $v$ if there exists a time $\tau$ such that $|H(\tau)_{u,v}|=1$. A necessary and sufficient condition for $G$ is periodic is given. We give the existence for the perfect state transfer between antipodal vertices in graphs with extreme diameter.

Spectra of unicyclic graphs

1987-12-01

Dragoš Cvetković , Peter Rowlinson

Perfect state transfer, integral circulants, and join of graphs

2010-03-01

Ricardo Javier Angeles-Canul , Robert M. Norton , Michael Opperman +3 more

We propose new families of graphs which exhibit quantum perfect state transfer. Our constructions are based on the join operator on graphs, its circulant generalizations, and the Cartesian product of … We propose new families of graphs which exhibit quantum perfect state transfer. Our constructions are based on the join operator on graphs, its circulant generalizations, and the Cartesian product of graphs. We build upon the results of Ba\v{s}i\'{c} and Petkovi\'{c} ({\em Applied Mathematics Letters} {\bf 22}(10):1609-1615, 2009) and construct new integral circulants and regular graphs with perfect state transfer. More specifically, we show that the integral circulant $\textsc{ICG}_{n}(\{2,n/2^{b}\} \cup Q)$ has perfect state transfer, where $b \in \{1,2\}$, $n$ is a multiple of $16$ and $Q$ is a subset of the odd divisors of $n$. Using the standard join of graphs, we also show a family of double-cone graphs which are non-periodic but exhibit perfect state transfer. This class of graphs is constructed by simply taking the join of the empty two-vertex graph with a specific class of regular graphs. This answers a question posed by Godsil (arxiv.org math/08062074).

View PDF Chat