Homomorphisms and polynomial invariants of graphs

This paper initiates a general study of the connection between graph homomorphisms and the Tutte polynomial. This connection can be extended to other polynomial invariants of graphs related to the Tutte polynomial such as the transition, the circuit partition, the boundary, and the coboundary polynomials. As an application, we describe in terms of homomorphism counting some fundamental evaluations of the Tutte polynomial in abelian groups and statistical physics. We conclude the paper by providing a homomorphism view of the uniqueness conjectures formulated by Bollobás, Pebody and Riordan.     

Discrepancy and eigenvalues of Cayley graphs

We consider quasirandom properties for Cayley graphs of finite abelian groups. We show that having uniform edge-distribution (i.e., small discrepancy) and having large eigenvalue gap are equivalent properties for such Cayley graphs, even if they are sparse. This affirmatively answers a question of Chung and Graham (2002) for the particular case of Cayley graphs of abelian groups, while in general the answer is negative.     

The eigenvalues of q-Kneser graphs

In this note, by proving some combinatorial identities, we obtain a simple form for the eigenvalues of $q$-Kneser graphs.     

Polynomial invariants of graphs II

Negami and Kawagoe has already defined a polynomial associated with each graphG as what discriminates graphs more finely than the polynomialf(G) defined by Negami and the Tutte polynomial. In this paper, we shall show that the polynomial includes potentially the generating function counting the independent sets and the degree sequence of a graphG, which cannot be recognized fromf(G) in general, and discuss on of treesT with observations by computer experiments.     

Average distance in graphs and eigenvalues

Brendan McKay gave the following formula relating the average distance between pairs of vertices in a tree T and the eigenvalues of its Laplacian:

     

Fuchsian groups and small eigenvalues of the Laplace operator

In the spectral theory of automorphic functions, small eigenvalues (i.e., those lying in the interval [0, 1/4]) of the Laplace operator are of particular interest. In this note we give an upper bound for the number of small eigenvalues of the Laplace operator for noncompact Riemann surfaces, which are quotient spaces of the upper half plane by the action of Fuchsian groups of the first kind, and also of the multiplicity of small eigenvalues.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 122, pp. 24–29, 1982.     

Milnor invariants for spatial graphs

Link-homotopy has been an active area of research for knot theorists since its introduction by Milnor in the 1950s. We introduce a new equivalence relation on spatial graphs called component-homotopy, which reduces to link-homotopy in the classical case. Unlike previous attempts at generalizing link-homotopy to spatial graphs, our new relation allows analogues of some standard link-homotopy results and invariants.In particular we can define a type of Milnor group for a spatial graph under component-homotopy, and this group determines whether or not the spatial graph is splittable. More surprisingly, we will also show that whether the spatial graph is splittable up to component-homotopy depends only on the link-homotopy class of the links contained within it. Numerical invariants of the relation will also be produced.     

Variational aspects of Laplace eigenvalues on Riemannian surfaces

We study the existence and properties of metrics maximising the first Laplace eigenvalue among conformal metrics of unit volume on Riemannian surfaces. We describe a general approach to this problem and its higher eigenvalue versions via the direct method of calculus of variations. The principal results include the general regularity properties of _λk${\lambda }_k$-extremal metrics and the existence of a partially regular _λ1${\lambda }_1$-maximiser.     

Combinatorial invariants on planar graphs

This paper introduces three kinds of operators on planar graphs with binary weights on edges, for which combinatorial invariants on two kinds of equivalences are found. Further, it is shown that the Jones polynomial and the bracket polynomial which are proved to be new topological invariants on knots in topology become special cases. Moreover, these invariants are a kind of generalization of Tutte polynomial on graphs.Supported by the NNSF of China.     

Neumaier graphs with few eigenvalues

Designs, Codes and Cryptography - A Neumaier graph is a non-complete edge-regular graph containing a regular clique. In this paper we give some sufficient and necessary conditions for a Neumaier...     

Biregular graphs with three eigenvalues

We consider nonregular graphs having precisely three distinct eigenvalues. The focus is mainly on the case of graphs having two distinct valencies and our results include constructions of new examples, structure theorems, valency constraints, and a classification of certain special families of such graphs. We also present a new example of a graph with three valencies and three eigenvalues of which there are currently only finitely many known examples.     

Hamiltonian s-properties and eigenvalues of k-connected graphs

Chvátal and Erdös (1972) [5] proved that, for a k-connected graph G, if the stability number $\alpha (G)\le k?s$, then G is Hamilton-connected ($s=1$) or Hamiltonian ($s=0$) or traceable ($s=?1$). Motivated by the result, we focus on tight sufficient spectral conditions for k-connected graphs to possess Hamiltonian s-properties. We say that a graph possesses Hamiltonian s-properties, which means that the graph is Hamilton-connected if $s=1$, Hamiltonian if $s=0$, and traceable if $s=?1$.For a real number $a\ge 0$, and for a k-connected graph G with order n, degree diagonal matrix $D(G)$ and adjacency matrix $A(G)$, we have identified best possible upper bounds for the spectral radius ${\lambda }_1(aD(\mathrm{\Gamma })+A(\mathrm{\Gamma }))$, where Γ is either G or the complement of G, to warrant that G possesses Hamiltonian s-properties. Sufficient conditions for a graph G to possess Hamiltonian s-properties in terms of upper bounds for the Laplacian spectral radius as well as lower bounds of the algebraic connectivity of G are also obtained. Other best possible spectral conditions for Hamiltonian s-properties are also discussed.