Up-embeddability via girth and the degree-sum of adjacent vertices

Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d _G (u) + d _G (v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d _G (u) + d _G (v) ⩾ n − 2g + 3 (resp. d _G (u) + d _G (v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight. This work was supported by National Natural Science Foundation of China (Grant No. 10571013)     

Characterizing degree-sum maximal nonhamiltonian bipartite graphs

In 1963, Moon and Moser gave a bipartite analogue to Ore’s famed theorem on hamiltonian graphs. While the sharpness examples of Ore’s Theorem have been independently characterized in at least four different papers, no similar characterization exists for the Moon–Moser Theorem. In this note, we give such a characterization, consisting of one infinite family and two exceptional graphs of order eight.     

A new family of distance-regular graphs with unbounded diameter

We construct distance-regular graphs with the same – classical – parameters as the Grassmann graphs on the e-dimensional subspaces of a (2e+1)-dimensional space over an arbitrary finite field. This provides the first known family of non-vertex-transitive distance-regular graphs with unbounded diameter. Mathematics Subject Classification (2000) 05E30     

GI-graphs: a new class of graphs with many symmetries

The class of generalized Petersen graphs was introduced by Coxeter in the 1950s. Frucht, Graver and Watkins determined the automorphism groups of generalized Petersen graphs in 1971, and much later, Nedela and ?koviera and (independently) Lovre?i?-Sara?in characterised those which are Cayley graphs. In this paper we extend the class of generalized Petersen graphs to a class of GI-graphs. For any positive integer n and any sequence j ₀,j ₁,…,j _t?1 of integers mod n, the GI-graph GI(n;j ₀,j ₁,…,j _t?1) is a (t+1)-valent graph on the vertex set \(\mathbb{Z}_{t} \times\mathbb{Z}_{n}\) , with edges of two kinds:

• an edge from (s,v) to (s′,v), for all distinct \(s,s' \in \mathbb{Z}_{t}\) and all \(v \in\mathbb{Z}_{n}\) ,
• edges from (s,v) to (s,v+j _s ) and (s,v?j _s ), for all \(s \in\mathbb{Z}_{t}\) and \(v \in\mathbb{Z}_{n}\) .

By classifying different kinds of automorphisms, we describe the automorphism group of each GI-graph, and determine which GI-graphs are vertex-transitive and which are Cayley graphs. A GI-graph can be edge-transitive only when t≤3, or equivalently, for valence at most 4. We present a unit-distance drawing of a remarkable GI(7;1,2,3).     

Some new strongly regular graphs

We show that three pairwise 4-regular graphs constructed by the second author are members of infinite families.     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.     

Q整图新类

对于一个简单图G, 方阵Q(G)=D(G)+A(G)称为G的无符号拉普拉斯矩阵,其中D(G)和A(G)分别为G的度对角矩阵和邻接矩阵. 一个图是Q整图是指该图的无符号拉普拉斯矩阵的特征值全部为整数.首先通过Stanic 得到的六个顶点数目较小的Q整图,构造出了六类具有无穷多个的非正则的Q整图. 进而,通过图的笛卡尔积运算得到了很多的Q整图类. 最后, 得到了一些正则的Q整图.     

A new family of expansive graphs

An affine graph is a pair (G,σ) where G is a graph and σ is an automorphism assigning to each vertex of G one of its neighbors. On one hand, we obtain a structural decomposition of any affine graph (G,σ) in terms of the orbits of σ. On the other hand, we establish a relation between certain colorings of a graph G and the intersection graph of its cliques K(G). By using the results we construct new examples of expansive graphs. The expansive graphs were introduced by Neumann-Lara in 1981 as a stronger notion of the K-divergent graphs. A graph G is K-divergent if the sequence |V(Kⁿ(G))| tends to infinity with n, where Kⁿ⁺¹(G) is defined by Kⁿ⁺¹(G)=K(Kⁿ(G)) for n?1. In particular, our constructions show that for any k?2, the complement of the Cartesian product C^k, where C is the cycle of length 2k+1, is K-divergent.     

A new characterization of HH-free graphs

We show that a graph G has no houses and no holes if and only if for every connected induced subgraph H of G and every vertex in H, either the vertex is adjacent to all the other vertices in H, or it forms a 2-pair of H with some other vertex in H. As a consequence, there is a simple linear time algorithm to find a 2-pair in HH-free graphs. We also note that the class of Meyniel graphs admits an analogous characterization.     

A new approach to chordal graphs

By a chordal graph is meant a graph with no induced cycle of length ⩾ 4. By a ternary system is meant an ordered pair (W, T), where W is a finite nonempty set, and T ⊆ W × W × W. Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated in a language of the first-order logic. For every finite nonempty set W, a bijective mapping from the set of all connected chordal graphs G with V(G) = W onto the set of all ternary systems (W, T) satisfying the axioms (A1)–(A5) is found in this paper.     

Comparability graphs and a new matroid

We consider a variety of two person perfect information games of the following sort. On the ith round Player I selects a vector v_i of a certain prescribed form and Player II either adds or subtracts v_i from a cumulative sum. Player II's object is to keep the cumulative sum as small as possible. We give bounds on the value of such games under a variety of conditions.     

A new family of Geodesic transitive graphs

We present a new family of locally geodesic transitive graphs with arbitrarily large diameter and valencies, containing a particular case to be geodesic transitive. We also prove that it is a unique family in some generalised family of graphs.     

A new coloring theorem of Kneser graphs

In 1997, Johnson, Holroyd and Stahl conjectured that the circular chromatic number of the Kneser graphs KG(n,k) is equal to the chromatic number of these graphs. This was proved by Simonyi and Tardos (2006) [13] and independently by Meunier (2005) [10], if χ(KG(n,k)) is even. In this paper, we propose an alternative version of Kneser's coloring theorem to confirm the Johnson-Holroyd-Stahl conjecture.     

Line graphs of bipartite graphs with Hamiltonian paths

It is shown that, if t is an integer ≥3 and not equal to 7 or 8, then there is a unique maximal graph having the path P_t as a star complement for the eigenvalue ?2. The maximal graph is the line graph of K_m,m if t = 2m?1, and of K_m,m+1 if t = 2m. This result yields a characterization of L(G ) when G is a (t + 1)‐vertex bipartite graph with a Hamiltonian path. The graphs with star complement P_r ∪ P_s or P_r ∪ C_s for ?2 are also determined. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 137–149, 2003     

A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.