Extending earlier results of Godsil and of Dobson and Malnič on Johnson graphs, we characterise those merged Johnson graphs
J
=
J
(
n
,
k
)
I
which are Cayley graphs, that is, which are connected and ...have a group of automorphisms acting regularly on the vertices. We also characterise the merged Johnson graphs which are not Cayley graphs but which have a transitive group of automorphisms with vertex-stabilisers of order 2. Even though these merged Johnson graphs are all vertex-transitive, we show that only relatively few of them are Cayley graphs or have a transitive group of automorphisms with vertex-stabilisers of order 2.
Let p be an odd prime, and D2p = (a,b I aP = b2 = l,bab= a 1) the dihedral group of order 2p. In this paper, we completely classify the cubic Cayley graphs on D2p up to isomorphism by means of ...spectral method. By the way, we show that two cubic Cayley graphs on D2p are isomorphic if and only if they are cospectral. Moreover, we obtain the number of isomorphic classes of cubic Cayley graphs on D2 by using Gauss' celebrated law of quadratic reciprocity.
For a few decades the smallest known non-Schurian coherent configuration was the association scheme on 15 points, coming from a doubly regular tournament. Last year the second author, using a ...computer, enumerated all coherent configurations of order up to 15. A consequence of the enumeration is that all coherent configurations up to 13 points are Schurian and a unique non-Schurian rank 11 coherent configuration of order 14 exists. This coherent configuration has two fibers of sizes 6 and 8, and an automorphism group of order 24 isomorphic to
SL
(2, 3). We provide a computer free interpretation of this new object, relying on some simple interplay between group theoretical and combinatorial arguments.
A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p ...super(3) for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p super(3) and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p super(3) exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p greater than or equal to 7, the connected pentavalent symmetric graphs of order 2p super(3) are all regular covers of the dipole Dip5 with covering transposition groups of order p super(3), and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 | (p-1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 | (p plus or minus 1). In the seven infinite families, each graph is unique for a given order.
Let B0(2, 5) be the largest two-generator finite Burnside group of exponent five. It has the order 534. We define an automorphism ψ which translates generating elements into their inverses. Let ...Св0(2,5)(ψ) be the centralizer of ψ in B0(2, 5). It is known that |СВ0(2,5)(π)| = 516. The growth functions of the centralizer are computed for some generating sets in the article. As the result we got diameters and average diameters of corresponding the Cayley graphs of Св0(2,5(ψ).
In this paper, assuming that each node is incident with two or more fault-free links, we show that an
n-dimensional alternating group graph can tolerate up to 4
n
−
13 link faults, where
n
⩾
4, while ...retaining a fault-free Hamiltonian cycle. The proof is computer-assisted. The result is optimal with respect to the number of link faults tolerated. Previously, without the assumption, at most 2
n
−
6 link faults can be tolerated for the same problem and the same graph.
A graph is vertex-transitive if its automorphism group acts transitively on vertices of the graph. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting ...regularly on its vertices. In this paper, a complete classification is given of tetravalent vertex-transitive non-Cayley graphs of order
2
p
2
for any prime
p
.
The bi-Cayley graph of a finite group G with respect to a subset S⊆G , which is denoted by \BCay(G,S) , is the graph with vertex set G×{1,2} and edge set {{(x,1),(sx,2)}∣x∈G, s∈S} . A ...finite group G is called a \textit{bi-Cayley integral group} if for any subset S of G , \BCay(G,S) is a graph with integer eigenvalues. In this paper we prove that a finite group G is a bi-Cayley integral group if and only if G is isomorphic to one of the groups Z^k_2 , for some k, Z_3 or S_3 .