Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.     

Further results on the least eigenvalue of connected graphs

In this paper, we identify within connected graphs of order n and size n+k (with and ) the graphs whose least eigenvalue is minimal. It is also observed that the same graphs have the largest spectral spread if n is large enough.     

The hamiltonian index of a 2-connected graph

Let G be a graph. Then the hamiltonian index h(G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l≥3. We also show that for any two 2-connected nonhamiltonian graphs G and with at least 74 vertices. The upper bounds are all sharp.     

Graphs with the second largest number of maximal independent sets

Let G be a simple undirected graph. Denote by (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erd?s and Moser raised the problem of determining the maximum value of among all graphs of order n and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most r cycles. In this paper we determine the second largest value of and xi(G) among all graphs of order n. Moreover, the extremal graphs achieving these values are also determined.     

A maximal zero-free interval for chromatic polynomials of bipartite planar graphs

It is well known that (-∞,0) and (0,1) are two maximal zero-free intervals for all chromatic polynomials. Jackson [A zero-free interval for chromatic polynomials of graphs, Combin. Probab. Comput. 2 (1993), 325-336] discovered that is another maximal zero-free interval for all chromatic polynomials. In this note, we show that is actually a maximal zero-free interval for the chromatic polynomials of bipartite planar graphs.     

Acyclic edge colouring of planar graphs without short cycles

Let G=(V,E) be any finite graph. A mapping C:E→[k] is called an acyclic edgek-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced in G by all the edges which have colour i or j, is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G, denoted by .In 2001, Alon et al. conjectured that for any graph G it holds that ; here Δ(G) stands for the maximum degree of G.In this paper we prove this conjecture for planar graphs with girth at least 5 and for planar graphs not containing cycles of length 4,6,8 and 9. We also show that if G is planar with girth at least 6. Moreover, we find an upper bound for the acyclic chromatic index of planar graphs without cycles of length 4. Namely, we prove that if G is such a graph, then .     

Closure operation for even factors on claw-free graphs

Ryjá?ek (1997) [6] defined a powerful closure operation on claw-free graphs G. Very recently, Ryjá?ek et al. (2010) [8] have developed the closure operation on claw-free graphs which preserves the (non)-existence of a 2-factor. In this paper, we introduce a closure operation on claw-free graphs that generalizes the above two closure operations. The closure of a graph is unique determined and the closure turns a claw-free graph into the line graph of a graph containing no cycle of length at most 5 and no cycles of length 6 satisfying a certain condition and no induced subgraph being isomorphic to the unique tree with a degree sequence 111133. We show that these closure operations on claw-free graphs all preserve the minimum number of components of an even factor. In particular, we show that a claw-free graph G has an even factor with at most k components if and only if (, respectively) has an even factor with at most k components. However, the closure operation does not preserve the (non)-existence of a 2-factor.     

The least eigenvalue of the complements of trees

Let be the set of the complements of trees of order n. In this paper, we characterize the unique graph whose least eigenvalue attains the minimum among all graphs in .     

Finite Euclidean graphs and Ramanujan graphs

We consider finite analogues of Euclidean graphs in a more general setting than that considered in [A. Medrano, P. Myers, H.M. Stark, A. Terras, Finite analogues of Euclidean space, J. Comput. Appl. Math. 68 (1996) 221-238] and we obtain many new examples of Ramanujan graphs. In order to prove these results, we use the previous work of [W.M. Kwok, Character tables of association schemes of affine type, European J. Combin. 13 (1992) 167-185] calculating the character tables of certain association schemes of affine type. A key observation is that we can obtain better estimates for the ordinary Kloosterman sum K(a,b;q). In particular, we always achieve , and in many (but not all) of the cases, instead of the well known . Also, we use the ideas of controlling association schemes, and the Ennola type dualities, in our previous work on the character tables of commutative association schemes. The method in this paper will be used to construct many more new examples of families of Ramanujan graphs in the subsequent paper.     

On the number of graphs with a given endomorphism monoid

For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then .     

More on almost self-complementary graphs

A graph X is called almost self-complementary if it is isomorphic to one of its almost complements , where denotes the complement of X and I a perfect matching (1-factor) in . If I is a perfect matching in and is an isomorphism, then the graph X is said to be fairly almost self-complementary if φ preserves I setwise, and unfairly almost self-complementary if it does not.In this paper we construct connected graphs of all possible orders that are fairly and unfairly almost self-complementary, fairly but not unfairly almost self-complementary, and unfairly but not fairly almost self-complementary, respectively, as well as regular graphs of all possible orders that are fairly and unfairly almost self-complementary.Two perfect matchings I and J in are said to be X-non-isomorphic if no isomorphism from X+I to X+J induces an automorphism of X. We give a constructive proof to show that there exists a graph X that is almost self-complementary with respect to two X-non-isomorphic perfect matchings for every even order greater than or equal to four.     

On wreathed lexicographic products of graphs

This paper proves a necessary and sufficient condition for the endomorphism monoid of a lexicographic product G[H] of graphs G,H to be the wreath product of the monoids and . The paper also gives respective necessary and sufficient conditions for specialized cases such as for unretractive or triangle-free graphs G.     

Intersection graphs of ideals of rings

In this paper, we consider the intersection graph G(R) of nontrivial left ideals of a ring R. We characterize the rings R for which the graph G(R) is connected and obtain several necessary and sufficient conditions on a ring R such that G(R) is complete. For a commutative ring R with identity, we show that G(R) is complete if and only if G(R[x]) is also so. In particular, we determine the values of n for which is connected, complete, bipartite, planar or has a cycle. Next, we characterize finite graphs which arise as the intersection graphs of and determine the set of all non-isomorphic graphs of for a given number of vertices. We also determine the values of n for which the graph of is Eulerian and Hamiltonian.     

A note on the automorphism groups of cubic Cayley graphs of finite simple groups

For a finite group G, a Cayley graph on G is said to be normal if . In this note, we prove that connected cubic non-symmetric Cayley graphs of the ten finite non-abelian simple groups G in the list of non-normal candidates given in [X.G. Fang, C.H. Li, J. Wang, M.Y. Xu, On cubic Cayley graphs of finite simple groups, Discrete Math. 244 (2002) 67-75] are normal.     

Edge intersection graphs of linear 3-uniform hypergraphs

Let be the class of edge intersection graphs of linear 3-uniform hypergraphs. It is known that the problem of recognition of the class is NP-complete. We prove that this problem is polynomially solvable in the class of graphs with minimum vertex degree ≥10. It is also proved that the class is characterized by a finite list of forbidden induced subgraphs in the class of graphs with minimum vertex degree ≥16.     

On limit points of Laplacian spectral radii of graphs

The study of limit points of eigenvalues of adjacency matrices of graphs was initiated by Hoffman [A.J. Hoffman, On limit points of spectral radii of non-negative symmetric integral matrices, in: Y. Alavi et al. (Eds.), Lecture Notes Math., vol. 303, Springer-Verlag, Berlin, Heidelberg, New York, 1972, pp. 165-172]. There he described all of the limit points of the largest eigenvalue of adjacency matrices of graphs that are no more than . In this paper, we investigate limit points of Laplacian spectral radii of graphs. The result is obtained: Let , β₀=1 and be the largest positive root of

     

Adjoint polynomials of bridge–path and bridge–cycle graphs and Chebyshev polynomials

The chromatic polynomial of a simple graph G with n>0 vertices is a polynomial of degree n, where α_k(G) is the number of k-independent partitions of G for all k. The adjoint polynomial of G is defined to be , where is the complement of G. We find explicit formulas for the adjoint polynomials of the bridge–path and bridge–cycle graphs. Consequence, we find the zeros of the adjoint polynomials of several families of graphs.