Skew-adjacency matrices of graphs

The spectra of the skew-adjacency matrices of a graph are considered as a possible way to distinguish adjacency cospectral graphs. This leads to the following topics: graphs whose skew-adjacency matrices are all cospectral; relations between the matchings polynomial of a graph and the characteristic polynomials of its adjacency and skew-adjacency matrices; skew-spectral radii and an analogue of the Perron–Frobenius theorem; and, the number of skew-adjacency matrices of a graph with distinct spectra.     

Emission of Cherenkov radiation as a mechanism for Hamiltonian friction

We study the motion of a heavy tracer particle weakly coupled to a dense, weakly interacting Bose gas exhibiting Bose–Einstein condensation. In the so-called mean-field limit, the dynamics of this system approaches one determined by nonlinear Hamiltonian evolution equations. We prove that if the initial speed of the tracer particle is above the speed of sound in the Bose gas, and for a suitable class of initial states of the Bose gas, the particle decelerates due to emission of Cherenkov radiation of sound waves, and its motion approaches a uniform motion at the speed of sound, as time t tends to ∞.     

Distance spectra and distance energy of integral circulant graphs

The distance energy of a graph G is a recently developed energy-type invariant, defined as the sum of absolute values of the eigenvalues of the distance matrix of G. There was a vast research for the pairs and families of non-cospectral graphs having equal distance energy, and most of these constructions were based on the join of graphs. A graph is called circulant if it is Cayley graph on the circulant group, i.e. its adjacency matrix is circulant. A graph is called integral if all eigenvalues of its adjacency matrix are integers. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. In this paper, we characterize the distance spectra of integral circulant graphs and prove that these graphs have integral eigenvalues of distance matrix D. Furthermore, we calculate the distance spectra and distance energy of unitary Cayley graphs. In conclusion, we present two families of pairs (G₁,G₂) of integral circulant graphs with equal distance energy - in the first family G₁ is subgraph of G₂, while in the second family the diameter of both graphs is three.     

对称群上Cayley图的DNA计算

有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法.     

On locally primitive Cayley graphs of finite simple groups

In this paper we investigate locally primitive Cayley graphs of finite nonabelian simple groups. First, we prove that, for any valency d for which the Weiss conjecture holds (for example, d?20 or d is a prime number by Conder, Li and Praeger (2000) [1]), there exists a finite list of groups such that if G is a finite nonabelian simple group not in this list, then every locally primitive Cayley graph of valency d on G is normal. Next we construct an infinite family of p-valent non-normal locally primitive Cayley graph of the alternating group for all prime p?5. Finally, we consider locally primitive Cayley graphs of finite simple groups with valency 5 and determine all possible candidates of finite nonabelian simple groups G such that the Cayley graph Cay(G,S) might be non-normal.     

Ballistic motion of a tracer particle coupled to a Bose gas

We study the motion of a heavy tracer particle weakly coupled to a dense interacting Bose gas exhibiting Bose–Einstein condensation. In the so-called mean-field limit, the dynamics of this system approaches one determined by nonlinear Hamiltonian evolution equations. We derive the effective dynamics of the tracer particle, which is described by a non-linear integro-differential equation with memory, and prove that if the initial speed of the tracer particle is below the speed of sound in the Bose gas the motion of the particle approaches an inertial motion at constant velocity at large times.     

Equality of Lifshitz and van Hove exponents on amenable Cayley graphs

We study the low energy asymptotics of periodic and random Laplace operators on Cayley graphs of amenable, finitely generated groups. For the periodic operator the asymptotics is characterised by the van Hove exponent or zeroth Novikov–Shubin invariant. The random model we consider is given in terms of an adjacency Laplacian on site or edge percolation subgraphs of the Cayley graph. The asymptotic behaviour of the spectral distribution is exponential, characterised by the Lifshitz exponent. We show that for the adjacency Laplacian the two invariants/exponents coincide. The result holds also for more general symmetric transition operators. For combinatorial Laplacians one has a different universal behaviour of the low energy asymptotics of the spectral distribution function, which can be actually established on quasi-transitive graphs without an amenability assumption. The latter result holds also for long range bond percolation models.     

Frobenius–Perron theory of modified ADE bound quiver algebras

The Frobenius–Perron dimension for an abelian category was recently introduced in [5]. We apply this theory to the category of representations of the finite-dimensional radical square zero algebras associated to certain modified ADE graphs. In particular, we take an ADE quiver with arrows in a certain orientation and an arbitrary number of loops at each vertex. We show that the Frobenius–Perron dimension of this category is equal to the maximum number of loops at a vertex. Along the way, we introduce a result which can be applied in general to calculate the Frobenius–Perron dimension of a radical square zero bound quiver algebra. We use this result to introduce a family of abelian categories which produce arbitrarily large irrational Frobenius–Perron dimensions.     

Divisible design graphs

A divisible design graph is a graph whose adjacency matrix is the incidence matrix of a divisible design. Divisible design graphs are a natural generalization of (v,k,λ)-graphs, and like (v,k,λ)-graphs they make a link between combinatorial design theory and algebraic graph theory. The study of divisible design graphs benefits from, and contributes to, both parts. Using information of the eigenvalues of the adjacency matrix, we obtain necessary conditions for existence. Old results of Bose and Connor on symmetric divisible designs give other conditions and information on the structure. Many constructions are given using various combinatorial structures, such as (v,k,λ)-graphs, distance-regular graphs, symmetric divisible designs, Hadamard matrices, and symmetric balanced generalized weighing matrices. Several divisible design graphs are characterized in terms of the parameters.     

The vertex-transitive TLF-planar graphs

We consider the class of the topologically locally finite (in short TLF) planar vertex-transitive graphs. We characterize these graphs by finite combinatorial objects called labeling schemes. As a result, we are able to enumerate and describe all TLF-planar vertex-transitive graphs of given degree, as well as most of their transitive groups of automorphisms. In addition,we are able to decide whether a given TLF-planar transitive graph is Cayley or not. This class contains all the one-ended planar Cayley graphs and the normal transitive tilings of the plane.     

The Index of a Periodic Graph

For periodic graphs, a special class of infinite, but locally finite graphs, an index theory is developed that can serve in classifying these graphs and that enables connections with various graph invariants as in the case of finite graphs. The index is defined with the aid of certain finite matrices that result rather canonically from reductions of the infinite adjacency operator due to the periodicity. As a central result we derive a sharp global lower bound for the index of any periodic graph.     

Spectral analysis of the affine graph over the finite ring

We apply two methods to the block diagonalization of the adjacency matrix of the Cayley graph defined on the affine group. The affine group will be defined over the finite ring Z/pⁿZ. The method of irreducible representations will allow us to find nontrivial eigenvalue bounds for two different graphs. One of these bounds will result in a family of Ramanujan graphs. The method of covering graphs will be used to block diagonalize the affine graphs using a Galois group of graph automorphisms. In addition, we will demonstrate the method of covering graphs on a generalized version of the graphs of Lubotzky et al. [A. Lubotzky, R. Phillips, P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261-277].     

The Legendre Collocation Spectral Method for the Ground State Solutions of the Bose-Einstein Condensates北大核心CSCD

近年来,有关Bose-Einstein凝聚态基态解的实验研究已经取得了一系列重要的成果.该文在相关研究成果的基础上,首先通过降维和无量纲化方法将Bose-Einstein凝聚态基态解问题转换成能量泛函极值问题,在离散该泛函时,尝试使用Legendre配置谱方法离散该能量泛函的一维和二维情形.其次,对该能量泛函极小值问题进行了数值模拟.最后,通过分析实验数据结果和图像得出,针对非旋转的Bose-Einstein凝聚态的基态解问题可以使用Legendre配置谱方法来求解,且数值结果的误差较小.     

Corrigendum to “Harmonic analysis on perturbed Cayley Trees” [J. Funct. Anal. 261 (3) (2011) 604–634]

Due to the boundary effects, the standard definition of the integrated density of the states (i.d.s. for short) used in [F. Fidaleo, Harmonic analysis on perturbed Cayley Trees, J. Funct. Anal. 261 (3) (2011) 604–634], does not work for nonamenable graphs like Cayley Trees and density zero perturbations of those. On the other hand, Proposition 2.3 in the previous mentioned paper works under the right definition we are going to describe, and which is useful for all the applications. For the sake of completeness and the convenience of the reader, we also show that both the definitions coincide in the amenable case.     

Bose–Einstein condensation in satisfiability problems

This paper is concerned with the complex behavior arising in satisfiability problems. We present a new statistical physics-based characterization of the satisfiability problem. Specifically, we design an algorithm that is able to produce graphs starting from a k-SAT instance, in order to analyze them and show whether a Bose–Einstein condensation occurs. We observe that, analogously to complex networks, the networks of k-SAT instances follow Bose statistics and can undergo Bose–Einstein condensation. In particular, k-SAT instances move from a fit-get-rich network to a winner-takes-all network as the ratio of clauses to variables decreases, and the phase transition of k-SAT approximates the critical temperature for the Bose–Einstein condensation. Finally, we employ the fitness-based classification to enhance SAT solvers (e.g., ChainSAT) and obtain the consistently highest performing SAT solver for CNF formulas, and therefore a new class of efficient hardware and software verification tools.     

Hamiltonian properties of triangular grid graphs

A triangular grid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional triangular grid. In 2000, Reay and Zamfirescu showed that all 2-connected, linearly-convex triangular grid graphs (with the exception of one of them) are hamiltonian. The only exception is a graph D which is the linearly-convex hull of the Star of David. We extend this result to a wider class of locally connected triangular grid graphs. Namely, we prove that all connected, locally connected triangular grid graphs (with the same exception of graph D) are hamiltonian. Moreover, we present a sufficient condition for a connected graph to be fully cycle extendable. We also show that the problem Hamiltonian Cycle is NP-complete for triangular grid graphs.     

整循环图的秩（英文）

A graph is called an integral graph if it has an integral spectrum i.e.,all eigenvalues are integers.A graph is called circulant graph if it is Cayley graph on the circulant group,i.e.,its adjacency matrix is circulant.The rank of a graph is defined to be the rank of its adjacency matrix.This importance of the rank,due to applications in physics,chemistry and combinatorics.In this paper,using Ramanujan sums,we study the rank of integral circulant graphs and gave some simple computational formulas for the rank and provide an example which shows the formula is sharp.     

The spectral characterization of graphs of index less than 2 with no path as a component

A graph is said to be determined by the adjacency and Laplacian spectrum (or to be a DS graph, for short) if there is no other non-isomorphic graph with the same adjacency and Laplacian spectrum, respectively. It is known that connected graphs of index less than 2 are determined by their adjacency spectrum. In this paper, we focus on the problem of characterization of DS graphs of index less than 2. First, we give various infinite families of cospectral graphs with respect to the adjacency matrix. Subsequently, the results will be used to characterize all DS graphs (with respect to the adjacency matrix) of index less than 2 with no path as a component. Moreover, we show that most of these graphs are DS with respect to the Laplacian matrix.     

Graphically abelian groups

We define a group G to be graphically abelian if the function g?g⁻¹ induces an automorphism of every Cayley graph of G. We give equivalent characterizations of graphically abelian groups, note features of the adjacency matrices for Cayley graphs of graphically abelian groups, and show that a non-abelian group G is graphically abelian if and only if G=E×Q, where E is an elementary abelian 2-group and Q is a quaternion group.     

Hamiltonian properties of locally connected graphs with bounded vertex degree

We consider the existence of Hamiltonian cycles for the locally connected graphs with a bounded vertex degree. For a graph G, let Δ(G) and δ(G) denote the maximum and minimum vertex degrees, respectively. We explicitly describe all connected, locally connected graphs with Δ(G)?4. We show that every connected, locally connected graph with Δ(G)=5 and δ(G)?3 is fully cycle extendable which extends the results of Kikust [P.B. Kikust, The existence of the Hamiltonian circuit in a regular graph of degree 5, Latvian Math. Annual 16 (1975) 33-38] and Hendry [G.R.T. Hendry, A strengthening of Kikust’s theorem, J. Graph Theory 13 (1989) 257-260] on full cycle extendability of the connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for the locally connected graphs with Δ(G)?7 is NP-complete.