Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs

Summary A variety of examples of 4-connected 4-regular graphs with no pair of disjoint Hamiltonian circuits were constructed in response to Nash-Williams conjecture that every 4-connected 4-regular graph is Hamiltonian and also admits a pair of edge-disjoint Hamiltonian circuits. Nash-Williams's problem is especially interesting for planar graphs since 4-connected planar graphs are Hamiltonian. Examples of 4-connected 4-regular planar graphs in which every pair of Hamiltonian circuits have edges in common are included in the above mentioned examples.B. Grünbaum asked whether 5-connected planar graphs always admit a pair of disjoint Hamiltonian circuits. In this paper we introduce a technique that enables us to construct infinitely many examples of 5-connected planar graphs, 5-regular and non regular, in which every pair of Hamiltonian circuits have edges in common.     

On bags and bugs

Usual graph classes, such as complete graphs, paths, cycles and stars, frequently appear as extremal graphs in graph theory problems. Here we want to turn the reader's attention to two novel, simply defined, graph classes that appear as extremal graphs in several graph theory problems. We call them bags and bugs. As examples of problems where bags and bugs appear, we show that balanced bugs maximize the index of graphs with fixed number of vertices and diameter ?2, while odd bags maximize the index of graphs with fixed number of vertices and radius ?3.     

An excluding algorithm for testing whether a family of graphs are determined by their generalized spectra

What kinds of graphs are determined by their spectra (DS for short) is a difficult problem in spectral graph theory. In [W. Wang, C.X. Xu, A sufficient condition for a family of graphs being determined by their generalized spectra, European J. Combin., in press], the authors give a sufficient condition for a family of graphs being DS with respect to their generalized spectra. However, there are many graphs in this family, which do not satisfy the condition. To investigate the DS property of graphs in such a situation, an excluding algorithm is presented in this paper, which is proved to be simple and effective as illustrated by some numerical examples.     

Distance-regular graphs and (α, β)-geometries

We study the relation between distance-regular graphs and (α, β)-geometries in two different ways. We give necessary and sufficient conditions for the neighbourhood geometry of a distance-regular graph to be an (α, β)-geometry, and describe some (classes of) examples. On the other hand, properties of certain regular two-graphs allow us to construct (0, α)-geometries on the corresponding Taylor graphs.     

Star clusters in independence complexes of graphs

We introduce the notion of star cluster of a simplex in a simplicial complex. This concept provides a general tool to study the topology of independence complexes of graphs. We use star clusters to answer a question arisen from works of Engström and Jonsson on the homotopy type of independence complexes of triangle-free graphs and to investigate a large number of examples which appear in the literature. We present an alternative way to study the chromatic and clique numbers of a graph from a homotopical point of view and obtain new results regarding the connectivity of independence complexes.     

On the Laplacian spectral radii of bipartite graphs

The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we provide structural and behavioral details of graphs with maximum Laplacian spectral radius among all bipartite connected graphs of given order and size. Using these results, we provide a unified approach to determine the graphs with maximum Laplacian spectral radii among all trees, and all bipartite unicyclic, bicyclic, tricyclic and quasi-tree graphs, respectively.     

Topology of matching,chessboard, and general bounded degree graph complexes

We survey results and techniques in the topological study of simplicial complexes of (di-, multi-, hyper-)graphs whose node degrees are bounded from above. These complexes have arisen in a variety of contexts in the literature. The most well-known examples are the matching complex and the chessboard complex. The topics covered here include computation of Betti numbers, representations of the symmetric group on rational homology, torsion in integral homology, homotopy properties, and connections with other fields.In memory of Gian-Carlo Rota     

Geometric aspects of 2-walk-regular graphs

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarte?s clique bound to 1-walk-regular graphs, Godsil?s multiplicity bound and Terwilliger?s analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.     

Main eigenvalues and automorphisms of a graph

We study some aspects of the relationship between algebras associated with graphs and automorphism groups. We study an algebra generated by the adjacent matrix of a graph and the all ones matrix, and derive a lower bound for the rank of the automorphism group of a graph. If a graph attains the equality in the above bound, it is calledextremal. We also describe some properties and examples of extremal graphs.     

Main eigenvalues and automorphisms of a graph

We study some aspects of the relationship between algebras associated with graphs and automorphism groups. We study an algebra generated by the adjacent matrix of a graph and the all ones matrix, and derive a lower bound for the rank of the automorphism group of a graph. If a graph attains the equality in the above bound, it is calledextremal. We also describe some properties and examples of extremal graphs.     

Sparse ramsey graphs

IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer. Dedicated to Paul Erdős on his seventieth birthday     

Graphs with a common eigenvalue deck

In this paper, we consider graphs whose deck consists of cards (which are the vertex-deleted subgraphs) that share the same eigenvalue, say μ. We show that, the characteristic polynomial can be reconstructed from the deck, providing a new proof of Tutte’s result for this class of graphs. Moreover, for the subclass of non-singular graphs, the graph can be uniquely reconstructed from the eigenvectors of the cards associated with the eigenvalue μ. The remaining graphs in this class are shown to be μ-cores graphs.     

The non-orientable genus of some metacyclic groups

We describe non-orientable, octagonal embeddings for certain 4-valent, bipartite Cayley graphs of finite metacyclic groups, and give a class of examples for which this embedding realizes the non-orientable genus of the group. This yields a construction of Cayley graphs for which is arbitrarily large, where and are the orientable genus and the non-orientable genus of the Cayley graph.Work supported in part by the Research Council of Slovenia, Yugoslavia and NSF Contract DMS-8717441.Supported by NSF Contract DMS-8601760.     

Minimum cycle bases of graphs on surfaces

In this paper we study the cycle base structures of embedded graphs on surfaces. We first give a sufficient and necessary condition for a set of facial cycles to be contained in a minimum cycle base (or MCB in short) and then set up a 1-1 correspondence between the set of MCBs and the set of collections of nonseparating cycles which are in general positions on surfaces and are of shortest total length. This provides a way to enumerate MCBs in a graph via nonseparating cycles. In particular, some known results such as P.F. Stadler's work on Halin graphs [Minimum cycle bases of Halin graphs, J. Graph Theory 43 (2003) 150-155] and Leydold and Stadler's results on outer-planar graphs [Minimum cycle bases of outerplanar graphs, Electronic J. Combin. 5(16) (1998) 14] are concluded. As applications, the number of MCBs in some types of graphs embedded in lower surfaces (with arbitrarily high genera) is found. Finally, we present an interpolation theorem for the number of one-sided cycles contained in MCB of an embedded graph.     

On products and line graphs of signed graphs, their eigenvalues and energy

In this article we examine the adjacency and Laplacian matrices and their eigenvalues and energies of the general product (non-complete extended p-sum, or NEPS) of signed graphs. We express the adjacency matrix of the product in terms of the Kronecker matrix product and the eigenvalues and energy of the product in terms of those of the factor graphs. For the Cartesian product we characterize balance and compute expressions for the Laplacian eigenvalues and Laplacian energy. We give exact results for those signed planar, cylindrical and toroidal grids which are Cartesian products of signed paths and cycles.We also treat the eigenvalues and energy of the line graphs of signed graphs, and the Laplacian eigenvalues and Laplacian energy in the regular case, with application to the line graphs of signed grids that are Cartesian products and to the line graphs of all-positive and all-negative complete graphs.     

Vertex and edge PI indices of Cartesian product graphs

The Padmakar-Ivan (PI) index of a graph G is the sum over all edges uv of G of the number of edges which are not equidistant from u and v. In this paper, the notion of vertex PI index of a graph is introduced. We apply this notion to compute an exact expression for the PI index of Cartesian product of graphs. This extends a result by Klavzar [On the PI index: PI-partitions and Cartesian product graphs, MATCH Commun. Math. Comput. Chem. 57 (2007) 573-586] for bipartite graphs. Some important properties of vertex PI index are also investigated.     

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.     

On bounds for the index of double nested graphs

The index of a simple graph is the largest eigenvalue of its adjacency matrix. It is well-known that in the set of all connected graphs with fixed order and size the graphs with maximal index are nested split graphs. It was recently observed that double nested graphs assume the same role if we restrict ourselves to bipartite graphs. In this paper we provide some bounds (lower and upper) for the index of double nested graphs. Some computational results are also included.     

Triples,current graphs and biembeddings

A family of ladder graphs, used by Youngs in his work on the Heawood conjecture, is used to provide constructions of Skolem and related triple systems, triangular biembeddings of certain complete graphs, and genus embeddings of certain complete multipartite graphs.     

Sieve methods in combinatorics

We develop the Turán sieve and a ‘simple sieve’ in the context of bipartite graphs and apply them to various problems in combinatorics. More precisely, we provide applications in the cases of characters of abelian groups, vertex-colourings of graphs, Latin squares, connected graphs, and generators of groups. In addition, we give a spectral interpretation of the Turán sieve.