On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

开关图的几个代数性质

首先对开关图的自同构群进行了研究,随即讨论了它的点传递性,并得到Calyley图的开关图依然是Cayley图.     

Two‐sided Group Digraphs and Graphs

We study a family of digraphs (directed graphs) that generalises the class of Cayley digraphs. For nonempty subsets of a group G, we define the two‐sided group digraph to have vertex set G, and an arc from x to y if and only if for some and . In common with Cayley graphs and digraphs, two‐sided group digraphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine necessary and sufficient conditions on L and R under which may be viewed as a simple graph of valency , and we call such graphs two‐sided group graphs. We also give sufficient conditions for two‐sided group digraphs to be connected, vertex‐transitive, or Cayley graphs. Several open problems are posed. Many examples are given, including one on 12 vertices with connected components of sizes 4 and 8.     

On polynomial digraphs

Let Φ(x,y) be a bivariate polynomial with complex coefficients. The zeroes of Φ(x,y) are given a combinatorial structure by considering them as arcs of a directed graph G(Φ). This paper studies some relationship between the polynomial Φ(x,y) and the structure of G(Φ).     

Characterizations of Clifford semigroup digraphs

This paper characterizes directed graphs which are Cayley graphs of strong semilattices of groups and, in particular, strong chains of groups, i.e. of completely regular semigroups which are also called Clifford semigroups.     

A note on total colourings of digraphs

In the paper two different arc-colourings and two associated with the total colourings of digraphs are considered. In one of these colourings we show that the problem of calculating the total chromatic index reduces to that of calculating the chromatic number of the underlying graph. In the other colouring we find the total chromatic indices of complete symmetric digraphs and tournaments.     

Homotopy of ends and boundaries of CAT(0) groups

For n ≥ 0, we exhibit CAT(0) groups that are n-connected at infinity, and have boundary which is (n − 1)-connected, but this boundary has non-trivial nth-homotopy group. In particular, we construct 1-ended CAT(0) groups that are simply connected at infinity, but have a boundary with non-trivial fundamental group. Our base examples are 1-ended CAT(0) groups that have non-path connected boundaries. In particular, we show all parabolic semidirect products of the free group of rank 2 and have a non-path connected boundary.     

Regular maps of graphs of order 4<Emphasis Type="Italic">p</Emphasis>

A 2-cell embedding f : X → S of a graph X into a closed orientable surface S can be described combinatorially by a pair M = (X;ρ ) called a map, where ρ is a product of disjoint cycle permutations each of which is the permutation of the arc set of X initiated at the same vertex following the orientation of S . It is well known that the automorphism group of M acts semi-regularly on the arc set of X and if the action is regular, then the map M and the embedding f are called regular. Let p and q be primes. Du et al. [J. Algebraic Combin., 19, 123-141 (2004)] classified the regular maps of graphs of order pq . In this paper all pairwise non-isomorphic regular maps of graphs of order 4 p are constructed explicitly and the genera of such regular maps are computed. As a result, there are twelve sporadic and six infinite families of regular maps of graphs of order 4 p ; two of the infinite families are regular maps with the complete bipartite graphs K2p,2p as underlying graphs and the other four infinite families are regular balanced Cayley maps on the groups Z4p , Z22 × Zp and D4p .     

On the pagenumber of trivalent Cayley graphs

Book embedding of graphs is one of the graph layout problem. It is useful for the multiprocessor network layout or the fault-tolerant processor arrays. We show that the trivalent Cayley graphs proposed by Vadapalli and Srimani can be embedded in five pages, and show some additional results on cube-connected cycles.