Search

A graph is said to be a bi-Cayley graph over a group H if it admits H as a semiregular automorphism group with two vertex-orbits. A bi-dihedrant is a bi-Cayley graph over a dihedral group. In this paper, it is shown that every connected trivalent edge-transitive bi-dihedrant is also vertex-transitive, and then we present a classification of trivalent arc-transitive bi-dihedrants, and study the Cayley property of trivalent vertex-transitive bi-dihedrants.

Bicirkulant je graf, ki dopušča avtomorfizem z natanko dvema orbitama vozlišč enake velikosti. V članku so karakterizirani vsi neizomorfni 4-valentni povezavno tranzitivni bicirkulanti. Posledično je izpeljana karakterizacija 4-valentnih ločno tranzitivnih dihedrantov. A bicirculant is a graph admitting an automorphism with exactly two vertex-orbits of equal size. All non-isomorphic 4-valent edge-transitive bicirculants are characterized in this article. As a corollary, a characterization of 4-valent arc-transitive dihedrants is obtained.

Let G be a finite group. A Cayley graph over G is a simple graph whose automorphism group has a regular subgroup isomorphic to G. A Cayley graph is called a CI-graph (Cayley isomorphism) if its isomorphic images are induced by automorphisms of G. A well-known result of Babai states that a Cayley graph Γ of G is a CI-graph if and only if all regular subgroups of Aut(Γ) isomorphic to G are conjugate in Aut(Γ). A semi-Cayley graph (also called bi-Cayley graph by some authors) over G is a simple graph whose automorphism group has a semiregular subgroup isomorphic to G with two orbits (of equal size). In this paper, we introduce the concept of SCI-graph (semi-Cayley isomorphism) and prove a Babai type theorem for semi-Cayley graphs. We prove that every semi-Cayley graph of a finite group G is an SCI-graph if and only if G is cyclic of order 3. Also, we study the isomorphism problem of a special class of semi-Cayley graphs.

Let G be a vertex colored graph. The minimum number χ(G) of colors needed for coloring of a graph G is called the chromatic number. Recently, Adiga et al. [1] have introduced the concept of color energy of a graph Ec(G) and computed the color energy of few families of graphs with χ(G) colors. In this paper we derive explicit formulas for the color energies of the unitary Cayley graph Xn, the complement of the colored unitary Cayley graph (Xn)c and some gcd-graphs.

This chapter contains the definition of the profinite fundamental group of a profinite graph and its properties. To make this precise there is a study of free actions of profinite groups on profinite graphs and their quotients (called Galois coverings). This leads to the concept of universal Galois \(\mathcal{C}\)-covering and \(\mathcal{C}\)-simply connected profinite graphs. The concept of \(\mathcal{C}\)-simple connectivity permits a characterization of freeness of a pro-\(\mathcal{C}\) group in terms of Cayley graphs.

A Cayley graph of a group G is called normal edge-transitive if the normalizer of the right representation of the group in the automorphism of the Cayley graph acts transitively on the set of edges of the graph. In this paper, we determine all connected normal edge-transitive Cayley graphs of the group U6n.

Let R be a commutative ring with unity and R +, U(R), and Z*(R) be the additive group, the set of unit elements, and the set of all nonzero zero-divisors of R, respectively. We denote by ℂ𝔸𝕐(R) and G R , the Cayley graph Cay(R +, Z*(R)) and the unitary Cayley graph Cay(R +, U(R)), respectively. For an Artinian ring R, Akhtar et al. (2009) studied G R . In this article, we study ℂ𝔸𝕐(R) and determine the clique number, chromatic number, edge chromatic number, domination number, and the girth of ℂ𝔸𝕐(R). We also characterize all rings R whose ℂ𝔸𝕐(R) is planar. Moreover, we determine all finite rings R whose ℂ𝔸𝕐(R) is strongly regular. We prove that ℂ𝔸𝕐(R) is strongly regular if and only if it is edge transitive. As a consequence, we characterize all finite rings R for which G R is a strongly regular graph.

Let S be a set of transpositions that generates the symmetric group S n , where n ≥ 3 . The transposition graph T ( S ) is defined to be the graph with vertex set { 1 , … , n } and with vertices i and j being adjacent in T ( S ) whenever ( i , j ) ∈ S . We prove that if the girth of the transposition graph T ( S ) is at least 5, then the automorphism group of the Cayley graph Cay ( S n , S ) is the semidirect product R ( S n ) ⋊ Aut ( S n , S ) , where Aut ( S n , S ) is the set of automorphisms of S n that fixes S . This strengthens a result of Feng on transposition graphs that are trees. We also prove that if the transposition graph T ( S ) is a 4 -cycle, then the set of automorphisms of the Cayley graph Cay ( S 4 , S ) that fixes a vertex and each of its neighbors is isomorphic to the Klein 4-group and hence is nontrivial. We thus identify the existence of 4-cycles in the transposition graph as being an important factor in causing a potentially larger automorphism group of the Cayley graph.

A classification is given for connected edge-transitive tetravalent Cayley graphs of square-free order. The classification shows that, with a few exceptions, a connected edge-transitive tetravalent Cayley graph of square-free order is either arc-regular or edge-regular. It thus provides a generic construction of half-transitive graphs of valency 4.

Let Γ be a graph and let G be a vertex-transitive subgroup of the full automorphism group Aut(Γ) of Γ. The graph Γ is called G-normal if G is normal in Aut(Γ). In particular, a Cayley graph Cay(G, S) on a group G with respect to S is normal if the Cayley graph is R(G)-normal, where R(G) is the right regular representation of G. Let T be a non-abelian simple group and let G = Tℓ with ℓ ≥ 1. We prove that if every connected T-vertex-transitive cubic symmetric graph is T-normal, then every connected G-vertex-transitive cubic symmetric graph is G-normal. This result, among others, implies that a connected cubic symmetric Cayley graph on G is normal except for T ≅ A47 and a connected cubic G-symmetric graph is G-normal except for T ≅ A7, A15 or PSL(4, 2).

A graph is one-regular if its automorphism group acts regularly on the arc set. In this paper, we construct a new infinite family of one-regular Cayley graphs of any prescribed valency. In fact, for any two positive integers ℓ,k⩾2 except for (ℓ,k)∈{(2,3),(2,4)}, the Cayley graph Cay(Dn,S) on dihedral groups Dn=〈a,b|an=b2=(ab)2=1〉 with S={a1+ℓ+⋯+ℓtb|0⩽t⩽k−1} and n=∑j=0k−1ℓj is one-regular. All of these graphs have cyclic vertex stabilizers and girth 6. As a continuation of Marušič and Pisanski's classification of cubic one-regular Cayley graphs on dihedral groups in [D. Marušič, T. Pisanski, Symmetries of hexagonal graphs on the torus, Croat. Chemica Acta 73 (2000) 969–981], the 5-valent one-regular Cayley graphs on dihedral groups are classified. Also, with only finitely many possible exceptions, all of one-regular Cayley graphs on dihedral groups of any prescribed prime valency are constructed.

A graph is 1-arc-regular if its full automorphism group acts regularly on the set of its arcs. In this paper, we investigate 1-arc-regular graphs of prime valency, especially of valency 3. First, we prove that if G is a soluble group then a (G, 1)-arc-regular graph must be a Cayley graph of a subgroup of G. Next we consider trivalent Cayley graphs of a finite nonabelian simple group and obtain a sufficient condition under which one can guarantee that Cay(G, S) is 1-arc-regular. Finally, as an application of the result, we construct two infinite families of 1-arc-regular trivalent Cayley graphs with insoluble automorphism groups and, in particular, one of the families is not a Cayley graph.

A graph group, or right-angled Artin group, is a group given by a presentation where the only relators are commutators of the generators. A graph group presentation corresponds in a natural way to a simplicial graph, with each generator corresponding to a vertex, and each commutator relator corresponding to an edge. Suppose that G is a graph group whose corresponding graph is a tree and H is a subgroup of G. We show that if H is quasiconvex with respect to either the word metric on G or the CAT(0) metric on the universal cover of the standard complex for G, then H is separable, that is, H is the intersection of finite index subgroups of G. We also discuss some consequences relating to certain 3-manifold groups.

A 2-arc in a graph X is a sequence of three distinct vertices of graph X where the first two and the last two are adjacent. A graph X is 2-arc-transitive if its automorphism group acts transitively on the set of 2-arcs of X. Some properties of 2-arc-transitive Cayley graphs of Abelian groups are considered. It is also proved that the set of generators of a 2-arc-transitive Cayley graph of an Abelian group which is not a circulant contains no elements of odd order.

Let A n be the alternating group of degree n with n ≥ 3 . Set S = { ( 1 2 i ) , ( 1 i 2 ) ∣ 3 ≤ i ≤ n } . The alternating group graph, denoted by A G n , is defined as the Cayley graph on A n with respect to S . Jwo et al. (1993) [J.-S. Jwo, S. Lakshmivarahan, S.K. Dhall, A new class of interconnection networks based on the alternating group, Networks 23 (1993) 315–326] introduced the alternating group graph A G n as an interconnection network topology for computing systems, and they proved that A G n is arc-transitive. In this work, it is shown that the full automorphism group of A G n is the semi-direct product R ( A n ) ⋊ Aut ( A n , S ) , where R ( A n ) is the right regular representation of A n and Aut ( A n , S ) = { α ∈ Aut ( A n ) ∣ S α = S } ≅ S n − 2 × S 2 . It follows from this result that A G n is arc-transitive but not 2-arc-transitive.

A graph is one-regular if its automorphism group acts regularly on the set of its arcs. In this paper tetravalent one-regular graphs of order 4p2, where p is a prime, are classified.

As it is introduced by Bermond, Pérennes, and Kodate and by Fragopoulou and Akl, some Cayley graphs, including most popular models for interconnection networks, admit a special automorphism, called complete rotation. Such an automorphism is often used to derive algorithms or properties of the underlying graph. For example, some optimal gossiping algorithms can be easily designed by using a complete rotation, and the constructions of the best known edge disjoint spanning trees in the toroidal meshes and the hypercubes are based on such an automorphism. Our purpose is to investigate such Cayley graphs. We relate some symmetries of a graph with potential algebraic symmetries appearing in its definition as a Cayley graph on a group.

A graph X is k-arc-transitive if its automorphism group acts transitively on the set of k-arcs of X. A circulant is a Cayley graph of a cyclic group. A classification of 2-arc-transitive circulants is given.

A graph is vertex-transitive if its automorphism group acts transitively on its vertices. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this paper, the cubic vertex-transitive non-Cayley graphs of order $8p$ are classified for each prime $p$. It follows from this classification that there are two sporadic and two infinite families of such graphs, of which the sporadic ones have order $56$, one infinite family exists for every prime $p>3$ and the other family exists if and only if $p\equiv 1\mod 4$. For each family there is a unique graph for a given order.

LetX be a connected graph with bounded valency and at least one thick end. We show that the existence of certain subgroups of the automorphism group ofX always implies thatX has infinite Hadwiger number.

Letq be a prime of the formq = 40x + 13,q = 40x + 27,q = 40x + 37, orq = 40x + 43. Then a connected, undirected, 4-valent, non-bipartite graph on whichPSL 2 (q) acts 2-arc transitively is non-Cayley.

In this article, we study the randomness-efficient graph tests for homomorphism over arbitrary groups (which can be used in locally testing the Hadamard code and PCP construction). We try to optimize both the amortized-tradeoff (between number of queries and error probability) and the randomness complexity of the homomorphism test simultaneously. For an abelian group G = Zpm, by using the λ-biased set S of G, we show that, on any given bipartite graph H = (V1, V2;E), the graph test for linearity over G is a test with randomness complexity |V1| log |G| + |V2|O(log |S|), query complexity |V1| + |V2| + |E| and error probability at most p-|E| + (1 - p-|E| ċ δ for any f which is 1 - p-1(1 +√δ2-λ/2 )-far from being affine linear. For a non-abelian group G, we introduce a random walk of some length, l say, on expander graphs to design a probabilistic homomorphism test over G with randomness complexity log |G| + O(log log |G|), query complexity 2l +1 and error probability at most 1 - δ2l2/(δl+δ2l2-δ2l)+ 2ψ(λ, l) for any f which is 2δ/(1 - λ)-far from being affine homomorphism, here ψ(λ, l) = Σ0≤i

Graph automata were first introduced by P. Rosenstiehl [10], under the name of intelligent graphs, surely because a network of finite automata is able to know some properties about its own structure. Hence P. Rosenstiehl created some algorithms that find Eulerian paths or Hamiltonian cycles in those graphs, with the condition that every vertex has a fixed degree [11]. Those algorithms are called “myopic” since each automaton has only the knowledge of the state of its immediate neighborhood. This hypothesis seems to be absolutely essential for the modelisation of the physical reality. A. Wu and A. Rosenfeld ([12] [13]) developed ideas of P. Rosenstiehl, using a simpler and more general formalism: the d-graphs. For each of these authors, a graph automata is formed by synchronous finite automata exchanging information according to an adjacent graph.

Let G be a flnite group, and let 1G 62 S µ G. A Cayley di-graph i = Cay(G;S) of G relative to S is a di-graph with a vertex set G such that, for x;y 2 G, the pair (x;y) is an arc if and only if yx i1 2 S. Further, if S = S i1 := fs i1 js 2 Sg, then i is undirected. i is conected if and only if G = hsi. A Cayley (di)graph i = Cay(G;S) is called normal if the right regular representation of G is a normal subgroup of the automorphism group of i. A graph i is said to be arc-transitive, if Aut(i) is transitive on an arc set. Also, a graph i is s-regular if Aut(i) acts regularly on the set of s-arcs. In this paper, we flrst give a complete classiflcation for arc-transitive Cayley graphs of valency flve on flnite Abelian groups. Moreover, we classify s-regular Cayley graph with valency flve on an abelian group for each s ‚ 1.

For original paper see Vadapalli and Srimani, ibid., vol. 7, no. 1, p 26-32, 1996, where the authors have proposed a new family of Cayley graph interconnection networks of constant degree four. Our comments show that their proposed graph is not new but is the same as the wrap-around butterfly graph. The structural kinship of the proposed graph with the de Bruijn graph is also discussed.

LetXG,H denote the Cayley graph of a finite groupG with respect to a subsetH. It is well-known that its automorphism groupA(XG,H) must contain the regular subgroupLG corresponding to the set of left multiplications by elements ofG. This paper is concerned with minimizing the index [A(XG,H)∶LG] for givenG, in particular when this index is always greater than 1. IfG is abelian but not one of seven exceptional groups, then a Cayley graph ofG exists for which this index is at most 2. Nearly complete results for the generalized dicyclic groups are also obtained.

If X is a Cayley graph of a group G possessing a normal subgroup N, then there is a quotient graph of X which is a Cayley graph of GN. With the aid of this result, it is shown that the free product of at least two and at most countably many groups, each of which is at most countably generated, admits a graphical regular representation.

The genus of a group is defined to be the minimum genus for any Cayley color graph of the group. All finite planar groups have been determined, but little is known about the genus of finite nonplanar groups. In this paper two families of toroidal groups are presented; the genus is calculated for certain abelian groups; and upper bounds are given for the genera of the symmetric and alternating groups and for some hamiltonian groups. Introduction. Corresponding to a presentation P, in terms of generators and relations, for a group G is the Cayley color graph Dp(G), defined as follows: The vertices of Dp(G) are the elements of G; with the generators are associated distinct colors, and there is a directed edge in Dp(G) from g, to 92 and colored with the color of generator h, if and only if g1h -g2 in G. For each generator of order two, we adopt the standard convention of replacing each pair of directed edges (g1, g2 ) and (g2, g1) by the single undirected edge [g1 g 21 . The genus, y, of a graph is the minimum genus among the genera of all closed orientable 2-manifolds in which the graph can be imbedded. The genus of a Cayley color graph, y(Dp(G)), is the genus of the graph that results when all arrows and colors are omitted from Dp(G). We define the genus of a group G to be the minimum genus for any Cayley color graph of G; i.e. y(G)= min y(Dp(G)). over P If G has no finite genus, we write y(G) = oo. Levinson [10] has shown that an infinite group G has either y(G) = 0 or y(G) = w. Here we consider only finite groups. A minimal presentation has no redundant generators. If y(G) = y(Dp(G)), we call P a genus presentation for G. Dyck [71 (see also Burnside L4, Chapters 18 and 191) considered maps on closed orientable 2-manifolds that are transformed into themselves in accordance with a fixed group G, acting transitively on the regions of the map. Any such map gives an upper bound for y(G), as a "dual" formed in terms of Burnside's white regions gives a Cayley color graph for G. Brahana L31 studied groups represented by regular maps on closed orientable 2?manifolds; these maps correspond to presentations on two generators, one of which is of order two. In this context the Presented to the Society, January 18, 1972; received by the editors September 13, 1971. AMS (MOS) subject classifications (1970). Primary 05C10, 05C25, 20F05; Secondary 20F10, 55A15.

Let T be a set of transpositions of the symmetric group Sn. The transposition graph Tra(T) of T is the graph with vertex set {1, 2, ..., n} and edge set {ij|(i j) ∈ T}. In this paper it is shown that if n ≥ 3, then the automorphism group of the transposition graph Tra(T) is isomorphic to Aut(Sn, T) = {α ∈ Aut(Sn)|Tα = T} and if T is a minimal generating set of Sn then the automorphism group of the Cayley graph Cay(Sn, T) is the semiproduct R(Sn) Aut(Sn, T), where R(Sn) is the right regular representation of Sn. As a result, we generalize a theorem of Godsil and Royle [C.D. Godsil, G. Royle, Algebraic Graph Theory, Springer, New York, 2001, p. 53] regarding the automorphism groups of Cayley graphs on Sn : if T is a minimal generating set of Sn and the automorphism group of the transposition graph Tra(T) is trivial then the automorphism group of the Cayley graph Cay(Sn, T) is isomorphic to Sn.

In this paper, we first prove that each biquasiprimitive permutation group containing a regular dihedral subgroup is biprimitive, and then give a classification of such groups. The classification is then used to classify vertex-quasiprimitive and vertex-biquasiprimitive edge-transitive dihedrants. Moreover, a characterization of valencies of normal edge-transitive dihedrants is obtained, and some classes of examples with certain valences are constructed.

A regular cover of a graph is said to be an edge-transitive cover if the fibre-preserving automorphism subgroup acts edge-transitively on the covering graph. In this paper we classify edge-transitive regular Zn-covers of the Heawood graph, and obtain a new infinite family of one-regular cubic graphs. Also, as an application of the classification of edge-transitive regular Zn-covers of the Heawood graph, we prove that any bipartite edge-transitive cubic graph of order 14p is isomorphic to a normal Cayley graph of dihedral group if the prime p>13.

An infinite familiy of 12-arc-transitive graphs of valency 4 with alternating cycles of length 4 is given. Besides, an infinite family of 12-arc-transitive graphs of valency 4 with vertex stabilizer isomorphic to Z2×Z2 is constructed.

For a positive integer s, a graph Γ is called s-arc transitive if its full automorphism group AutΓ acts transitively on the set of s-arcs of Γ. Given a group G and a subset S of G with S = S-1 and 1 ∉ S, let Γ = Cay(G, S) be the Cayley graph of G with respect to S and GR the set of right translations of G on G. Then GR forms a regular subgroup of AutΓ. A Cayley graph Γ = Cay(G, S) is called normal if GR is normal in AutΓ. In this paper we investigate connected cubic s-arc transitive Cayley graphs Γ of finite non-Abelian simple groups. Based on Li's work (Ph.D. Thesis (1996)), we prove that either Γ is normal with s ≤ 2 or G = A47 with s = 5 and AutΓ ≃ A48. Further, a connected 5-arc transitive cubic Cayley graph of A47 is constructed.

This chapter discusses a 0-symmetric graph with 96 vertices. The chapter presents a nonabelian group J of order n, with two generators S and Y. If there is an automorphism of J taking each generator to its inverse and then a group H of order 2n can be constructed by adjoining the involutory element R, the group H can be generated by three involutory elements. The group H may also have a 0-symmetric Cayley graph. The group H of order 96 that results from a procedure called can be generated by three quaternion transformations. The chapter further illustrates a Hamiltonian circuit where the graph was bipartite and was seen to be of girth 8.

In this paper, we prove that every vertex-transitive graph can be expressed as the edge-disjoint union of symmetric graphs. We define a multicycle graph and conjecture that every vertex-transitive graph can be expressed as the edge-disjoint union of multicycles. We verify this conjecture for several subclasses of vertex-transitive graphs, including Cayley graphs, multidimensional circulants, and vertex-transitive graphs with a prime or twice a prime number of nodes. We conclude with some open questions of interest.

This chapter discusses a procedure for obtaining bipartite Cayley graphs of girth 4. The non-bipartite graphs of girth 4 are companion graphs of bipartite ones. The only exception found is the graph corresponding to the group G 3, 5, 5 , where none of the three parameters p, q, and r is even. It is easy to obtain bipartite Cayley graphs of girth 4 using a procedure that is described in the chapter. If J is defined as being generated by the involutory element R and the non-involutory element S, the trivalent Cayley graph of J with respect to the generators R and S cannot be 0-syrnrnetric. The graph does not fulfill the necessary condition for a Cayley graph to be 1 z because J admits an automorphism leaving R fixed and taking S into its inverse S –1 .

This chapter describes finite groups and computing. A group, like a semigroup, has a single binary operation. Classical examples of groups are the integers under addition, and the nonzero real numbers under multiplication. Mappings that transform a graph into itself are known as automorphisms of graph. The set of all automorphisms of a given graph forms the automorphism group of the graph. The elements upon which the group is based are called the generators of the group, and the products so defined are called words. Multiplication in the group corresponds to a succession of walks, and a cycle in the graph is a representation for the identity element. The principal tool in determining the order of a group is a corollary to Lagrange's theorem. The problem of determining a group from its generators and relations is essentially a pattern-recognition problem.

We study the automorphisms of a Cayley graph that preserve its natural edge-colouring. More precisely, we are interested in groups G, such that every such automorphism of every connected Cayley graph on G has a very simple form: the composition of a left-translation and a group automorphism. We find classes of groups that have the property, and we determine the orders of all groups that do not have the property. We also have analogous results for automorphisms that permute the colours, rather than preserving them., Comment: 29 pages (including 5-page appendix of notes to aid the referee). Made minor revisions suggested by the referee