On application of linear algebra in classification cubic s-regular graphs of order 28p
A graph is s-regular if its automorphism group acts regularly on the set of s-arcs. In this paper, by applying concept linear algebra, we classify the connected cubic s-regular graphs of order 28p for each s ≥ 1, and prime p.
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2018
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/188348 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On application of linear algebra in classification cubic s-regular graphs of order 28p / A. Imani, N. Mehdipoor, A.A. Talebi // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 1. — С. 56-72. — Бібліогр.: 24 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188348 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1883482023-02-25T01:26:43Z On application of linear algebra in classification cubic s-regular graphs of order 28p Imani, A. Mehdipoor, N. Talebi, A.A. A graph is s-regular if its automorphism group acts regularly on the set of s-arcs. In this paper, by applying concept linear algebra, we classify the connected cubic s-regular graphs of order 28p for each s ≥ 1, and prime p. 2018 Article On application of linear algebra in classification cubic s-regular graphs of order 28p / A. Imani, N. Mehdipoor, A.A. Talebi // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 1. — С. 56-72. — Бібліогр.: 24 назв. — англ. 1726-3255 2010 MSC: 05C25, 20B25 http://dspace.nbuv.gov.ua/handle/123456789/188348 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
A graph is s-regular if its automorphism group acts regularly on the set of s-arcs. In this paper, by applying concept linear algebra, we classify the connected cubic s-regular graphs of order 28p for each s ≥ 1, and prime p. |
| format |
Article |
| author |
Imani, A. Mehdipoor, N. Talebi, A.A. |
| spellingShingle |
Imani, A. Mehdipoor, N. Talebi, A.A. On application of linear algebra in classification cubic s-regular graphs of order 28p Algebra and Discrete Mathematics |
| author_facet |
Imani, A. Mehdipoor, N. Talebi, A.A. |
| author_sort |
Imani, A. |
| title |
On application of linear algebra in classification cubic s-regular graphs of order 28p |
| title_short |
On application of linear algebra in classification cubic s-regular graphs of order 28p |
| title_full |
On application of linear algebra in classification cubic s-regular graphs of order 28p |
| title_fullStr |
On application of linear algebra in classification cubic s-regular graphs of order 28p |
| title_full_unstemmed |
On application of linear algebra in classification cubic s-regular graphs of order 28p |
| title_sort |
on application of linear algebra in classification cubic s-regular graphs of order 28p |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188348 |
| citation_txt |
On application of linear algebra in classification cubic s-regular graphs of order 28p / A. Imani, N. Mehdipoor, A.A. Talebi // Algebra and Discrete Mathematics. — 2018. — Vol. 25, № 1. — С. 56-72. — Бібліогр.: 24 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT imania onapplicationoflinearalgebrainclassificationcubicsregulargraphsoforder28p AT mehdipoorn onapplicationoflinearalgebrainclassificationcubicsregulargraphsoforder28p AT talebiaa onapplicationoflinearalgebrainclassificationcubicsregulargraphsoforder28p |
| first_indexed |
2025-07-16T10:22:11Z |
| last_indexed |
2025-07-16T10:22:11Z |
| _version_ |
1837798608817094656 |
| fulltext |
“adm-n1” — 2018/4/2 — 12:46 — page 56 — #58
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 25 (2018). Number 1, pp. 56–72
c© Journal “Algebra and Discrete Mathematics”
On application of linear algebra
in classification cubic s-regular graphs
of order 28p
A. Imani, N. Mehdipoor and A. A. Talebi
Communicated by V. V. Kirichenko
Abstract. A graph is s-regular if its automorphism group
acts regularly on the set of s-arcs. In this paper, by applying concept
linear algebra, we classify the connected cubic s-regular graphs of
order 28p for each s > 1, and prime p.
1. Introduction
In this study, all graphs considered are assumed to be finite, simple,
and connected, unless stated otherwise. For a graph X, V (X), E(X), and
Aut(X) denote its vertex set, edge set, and full automorphism group,
respectively. Let G be a subgroup of Aut(X). For u, v ∈ V (X), {u, v}
denotes the edge incident to u and v in X, and NX(u) denotes the
neighborhood of u in X, that is, the set of vertices adjacent to u in X.
A graph X̃ is called a covering of a graph X with projection p :
X̃ → X if there is a surjection p : V (X̃) → V (X) such that p|N
X̃
(ṽ) :
N
X̃
(ṽ) → NX(v) is a bijection for any vertex v ∈ V (X) and ṽ ∈ p−1(v). A
permutation group G on a set Ω is said to be semiregular if the stabilizer
Gv of v in G is trivial for each v ∈ Ω, and is regular if G is transitive, and
semiregular. Let K be a subgroup of Aut(X) such that K is intransitive
on V (X). The quotient graph X/K induced by K is defined as the graph
such that the set Ω of K-orbits in V (X) is the vertex set of X/K and B,
2010 MSC: 05C25, 20B25.
Key words and phrases: S-regular graphs, Homology group, Coxeter graph,
Symmetric graphs, Regular covering.
“adm-n1” — 2018/4/2 — 12:46 — page 57 — #59
A. Imani, N. Mehdipoor, A. A. Talebi 57
C ∈ Ω are adjacent if and only if there exists a u ∈ B and v ∈ C such
that {u, v} ∈ E(X). A covering X̃ of X with a projection p is said to
be regular (or N -covering) if there is a semiregular subgroup N of the
automorphism group Aut(X̃) such that graph X is isomorphic to the
quotient graph X̃/N , say by h, and the quotient map X̃ → X̃/N is the
composition ph of p and h. If N is a cyclic or an elementary Abelian, then,
X̃ is called a cyclic or an elementary Abelian covering of X, and if X̃ is
connected, N becomes the covering transformation group.
An s-arc in a graph X is an ordered (s+ 1)-tuple (v0, v1, . . . , vs) of
vertices of X such that vi−1 is adjacent to vi for 1 6 i 6 s, and vi−1 6= vi+1
for 1 6 i < s; in other words, a directed walk of length s that never includes
a backtracking. For a graph X and a subgroup G of Aut(X), X is said
to be G-vertex-transitive, G-edge-transitive, or G-s-arc-transitive if G
is transitive on the sets of vertices, edges, or s-arcs of X, respectively,
and G-s-regular if G acts regularly on the set of s-arcs of X. A graph X
is called vertex-transitive, edge-transitive, s-arc-transitive, or s-regular
if X is Aut(X)-vertex-transitive, Aut(X)-edge-transitive, Aut(X)-s-arc-
transitive, or Aut(X)-s-regular, respectively. In particular, 1-arc-transitive
means arc-transitive, or symmetric.
Covering techniques have long been known as a powerful tool in
topology, and graph theory. Regular covering of a graph is currently an
active topic in algebraic graph theory. Tutte [23, 24] showed that every
finite cubic symmetric graph is s-regular for some s > 1, and this s is at
most five. It follows that every cubic symmetric graph has an order of the
form 2mp for a positive integer m and a prime number p. In order to know
all cubic symmetric graphs, we need to classify the cubic s-regular graphs
of order 2mp for a fixed positive integer m and each prime p. Conder and
Dobcsányi [5, 6] classified the cubic s-regular graphs up to order 2048 with
the help of the “Low index normal subgroups” routine in MAGMA system
[3]. Cheng and Oxley [4] classified the cubic s-regular graphs of order 2p.
By using the covering technique, cubic s-regular graphs with order
2p2, 2p3, 4p, 4p2, 6p, 6p2, 8p, 8p2, 10p, 10p2,
12p, 12p2, 14p, 36p, 44p, 52p, 66p, 68p, 76p, 22p,
22p2, 10p3, and 8p3
were classified in [1, 8− 13, 19, 20, 22].
In this paper, by employing the covering technique, group-theoretical
construction, and concept linear algebra, is investigated the connected
cubic s-regular graphs of order 28p for each s > 1, and each prime p.
“adm-n1” — 2018/4/2 — 12:46 — page 58 — #60
58 Classification cubic s-regular graph
2. Preliminaries related to covering, Voltage graphs,
lifting problems and the first homology group
Let X be a graph and K be a finite group. By a−1 we mean the reverse
arc to an arc a. A voltage assignment (or K-voltage assignment) of X is a
function ξ : A(X) → K with the property that ξ(a−1) = ξ(a)−1 for each
arc a ∈ A(X). The values of ξ are called voltages, and K is the voltage
group. The graph X ×ξ K (Cov(X, ξ)) derived from a voltage assignment
ξ : A(X) → K has vertex set V (X)×K and edge set E(X)×K, so that an
edge (e, g) ofX×ξK joins a vertex (u, g) to (v, ξ(a)g) for a = (u, v) ∈ A(X)
and g ∈ K, where e = {u, v}. [21] The voltage assignment ξ on arcs
extends to a voltage assignment on walks in a natural way, that is, the
voltage on a walk W, say with consecutive incident arcs a1, a2, . . . , an, is
ξ(a1)ξ(a2) . . . ξ(an).
Clearly, the derived graph X×ξK is a covering of X with the first coor-
dinate projection p : X ×ξ K → X, which is called the natural projection.
By defining (u, g′)g = (u, g′g) for any g ∈ K and (u, g′) ∈ V (X ×ξ K),
K becomes a subgroup of Aut(X ×ξ K) which acts semiregularly on
V (X ×ξ K). Therefore, X ×ξ K can be viewed as a K-covering. For each
u ∈ V (X) and uv ∈ E(X), the vertex set {(u, g)|g ∈ K} is the fibre of
u and the edge set {(u, g)(v, ξ(a)g)| ∈ K} is the fibre of {u, v}, where
a = (u, v). Conversely, each regular covering X̃ of X with a covering
transformation group K can be derived from a K-voltage assignment.
Given a spanning tree T of the graph X, a voltage assignment ξ is said
to be T -reduced if the voltages on the tree arcs are the identity. Gross
and Tucker [15] showed that every regular covering X̃ of a graph X can
be derived from a T -reduced voltage assignment X̃ with respect to an
arbitrary fixed spanning tree T of X.
Let X̃ be a K-covering of X with a projection p. If α ∈ Aut(X) and
α̃ ∈ Aut(X̃) satisfy α̃p = pα, we call α̃ a lift of α, and α the projection of
α̃. Concepts such as a lift of a subgroup of Aut(X) and the projection of a
subgroup of X̃ are self-explanatory [17]. The lifts and projections of such
subgroups are of course subgroups in Aut(X̃) and Aut(X), respectively.
In particular, if the covering graph X̃ is connected, then the covering
transformation group K is the lift of the trivial group, that is,
K = {α̃ ∈ Aut(X̃) : p = α̃p}.
Let T be a spanning tree of a graph X. A closed walk W that contains
only one cotree arc is called a fundamental closed walk. Similarly, a cycle W
that contains only one cotree arc is called a fundamental cycle. Observe
“adm-n1” — 2018/4/2 — 12:46 — page 59 — #61
A. Imani, N. Mehdipoor, A. A. Talebi 59
that a voltage assignment on arcs extends to a voltage assignment on
walks in a natural way. Given α ∈ Aut(X), we define a function ᾱ from
the set of voltages on fundamental closed walks based at a fixed vertex
v ∈ V (X) to the voltage group K by
(ξ(C))ᾱ = ξ(Cα),
where C ranges over all fundamental closed walks at v, and ξ(C) and ξ(Cα)
are the voltages on C and Cα, respectively. Note that if K is abelian, ᾱ
does not depend on the choice of the base vertex, and the fundamental
closed walks at v can be substituted by the fundamental cycles generated
by the cotree arcs of X.
Two coverings X̃1 and X̃2 of X with projection p1 and p2, respectively,
are said to be isomorphic if there exist an automorphism α ∈ Aut(X) and
an isomorphism α̃ :X̃1 → X̃2 such that α̃p2 = p1α. In particular, if α is
the identity automorphism of X, then we say X̃1 and X̃2 are equivalent.
For a graph X, D(X) is a set of darts, which is required to be disjoint
from V (X), I is a mapping of D(X) onto V (X), called the incidence
function, and λ is an involutory permutation of D(X), called the dart-
reversing involution. For convenience or if λ is not explicitly specified we
sometimes write x−1 instead of λx. Intuitively, the mapping I assigns to
each dart its initial vertex, and the permutation λ interchanges a dart
and its reverse. The terminal vertex of a dart x is the initial vertex of
λx. The set of all darts initiated at a given vertex u is denoted by Du,
called the neighborhood of u. The cardinality |Du| of Du is the valency of
the vertex u. The orbits of λ are called edges; thus each dart determines
uniquely its underlying edge. An edge is called a semiedge if λx = x, a
loop if λx 6= x and Iλx = Ix, and it is called a link otherwise. A walk
of length n > 1 is a sequence of n darts W = x1x2 . . . xn such that, for
each index 1 6 k 6 n − 1, the terminal vertex of xk coincides with the
initial vertex of xk+1. Moreover, we define each vertex to be a trivial walk
of length 0. The initial vertex of W is the initial vertex of x1, and the
terminal vertex of W is the terminal vertex of xn. The walk is closed if
the initial and the terminal vertex coincide. In this case we say that the
walk is based at that vertex. If W has initial vertex u and terminal vertex
v, then we usually write W : u → v. Let W1 and W2 be two walks such
that the terminal vertex of W1 coincides with the initial vertex of W2. We
define the product W1W2 as the juxtaposition of the two sequences. A
walk W is reduced if it contains no subsequence of the form xx−1.
By π(X) we denote the fundamental groupoid of a graph X, that is,
the set of all reduced walks equipped with the product W1W2. The group
“adm-n1” — 2018/4/2 — 12:46 — page 60 — #62
60 Classification cubic s-regular graph
π(X,u) is called the fundamental group of X at u. The fundamental
group is not a free group in general. Consequently, the first homology
group H1(X), obtained by abelianizing π(X,u), is not necessarily a free
Z-module. Namely, let re + rs be the minimal number of generators of
π(X,u), where rs is the number of semiedges and re is the number of cotree
loops and links relative to some spanning tree. Then H1(X) ∼= Zre × Zrs
2 .
[18] The first homology group H1(X,Zp) ∼= H1(X)/pH1(X) with Zp as
the coefficient ring can be considered as a vector space over the field Zp.
Observe that
H1(X,Zp) ∼=
{
Zre+rs
p p = 2
Zre
p p > 3.
We start by introducing five propositions for later applications in this
paper. The following proposition is necessary to classify s-regular graph.
Proposition 2.1. [16] Let X be a connected symmetric graph of prime
valency and G a s-regular subgroup of Aut(X) for some s > 1. If a normal
subgroup N of G has more than two orbits, then it is semiregular and G/N
is an s-regular subgroup of Aut(XN ), where XN is the quotient graph
of X corresponding to the orbits of N . Furthermore, X is a N -regular
covering of XN .
Proposition 2.2. [24] If X is an s-arc regular cubic graph, then s 6 5.
Proposition 2.3. [9] Let X be a connected cubic symmetric graph of
order 4p or 4p2 for a prime p. Then X is isomorphic to the 2-regular
hypercube Q3 of order 8, the 2-regular generalized Petersen graphs P (8, 3)
or P (10, 7) of order 16 or 20 respectively, the 3-regular Dodecahedron of
order 20 or the 3-regular Coxeter graph C28 of order 28.
Proposition 2.4. [19] Let p be a prime and let X be a cubic symmetric
graph of order 14p. Then, X is 1-, 2- or 3-regular. Furthermore,
(1) X is 1-regular if and only if X is isomorphic to one of the graphs
F42, F98A, CF14p and DF14p where p > 7 and p ≡ 1 mod 6.
(2) X is 2-regular if and only if X is isomorphic to one of the graphs
F98B and F182C.
(3) X is 3-regular if and only if X is isomorphic to one of the graphs
F28 and F182D.
The next proposition[9, Theorem 6.1] is shown the cyclic or elementary
abelian coverings of the complete graph K4.
“adm-n1” — 2018/4/2 — 12:46 — page 61 — #63
A. Imani, N. Mehdipoor, A. A. Talebi 61
Proposition 2.5. Let K be a cyclic or an elementary abelian group
and let X̃ be a connected K-covering of the complete graph K4 whose
fibre-preserving group is arc-transitive. Then, X is 2-regular. Moreover,
(1) if K is cyclic then X̃ is isomorphic to the complete graph K4,
the 3-dimensional hypercube Q3, or the generalized Petersen graph
P (8, 3).
(2) If K is elementary abelian but not cyclic, then X̃ is isomorphic to
one of ECp3 for a prime p (defined in Example 3.2 in [9]).
3. Coxeter graph
In the mathematical field of graph theory, the Coxeter graph is a
3-regular graph with 28 vertices and 42 edges.
V (X) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
22, 23, 24, 25, 26, 27],
E(X) = [{0, 1}, {0, 23}, {0, 24}, {1, 2}, {1, 12}, {2, 3}, {2, 25}, {3, 4},
{3, 21}, {4, 5}, {4, 17}, {5, 6}, {5, 11}, {6, 7}, {6, 27}, {7, 8},
{7, 24}, {8, 9}, {8, 25}, {9, 10}, {9, 20}, {10, 11}, {10, 26},
{11, 12}, {12, 13}, {13, 14}, {13, 19}, {14, 15}, {14, 27},
{15, 16}, {15, 25}, {16, 17}, {16, 26}, {17, 18}, {18, 19},
{18, 24}, {19, 20}, {20, 21}, {21, 22}, {22, 23}, {22, 27}, {23, 26}].
Figure 1. Coxeter graph.
“adm-n1” — 2018/4/2 — 12:46 — page 62 — #64
62 Classification cubic s-regular graph
We choose
α = (2, 12)(3, 11)(4, 5)(6, 17)(7, 18)(8, 19)(9, 20)(10, 21)(13, 25)(14, 15)
(16, 27)(22, 26),
β = (2, 12)(3, 13)(4, 14)(5, 15)(6, 16)(7, 26)(8, 10)(11, 25)(17, 27)(18, 22)
(19, 21)(23, 24),
γ = (1, 23)(2, 26)(3, 10)(4, 9)(5, 20)(6, 19)(7, 18)(8, 17)(11, 21)(12, 22)
(13, 27)(16, 25),
σ = (0, 1)(2, 24)(3, 18)(4, 17)(5, 16)(6, 15)(7, 25)(11, 26)(12, 23)(13, 22)
(14, 27)(19, 21),
as automorphisms of Coxeter graph. Then Aut(F28A) = 〈α, β, γ, σ〉. The
automorphism group of the Coxeter graph is a group of order 336. It acts
transitively on the vertices, on the edges and on the arcs of the graph.
Therefore the Coxeter graph is a symmetric graph. It has automorphisms
that take any vertex to any other vertex and any edge to any other
edge. According to the Foster census, the Coxeter graph, referenced as
F28A, is the only cubic symmetric graph on 28 vertices. By sage[2]
the automorphism group of Coxeter graph has one proper arc-transitive
subgroup G = 〈β, γ, σ〉.
We choose a spanning tree T of Coxeter graph consisting of the edges
(0, 1), (0, 23), (0, 24), (1, 2), (1, 12), (2, 3), (2, 25), (3, 4),
(3, 21), (4, 5), (4, 17), (5, 6), (5, 11), (6, 7), (6, 27), (7, 8), (8, 9), (9, 10),
(9,20), (10,26), (12,13), (13,14), (13,19), (14,15),(15,16),(17,18),(21,22).
By choosing T , we can define a T -reduced voltage assignment.
We show the cotree arcs by setting
x1 = (7, 24), x2 = (8, 25), x3 = (10, 11), x4 = (11, 12),
x5 = (14, 27), x6 = (15, 25), x7 = (16, 17), x8 = (16, 26),
x9 = (18, 19), x10 = (18, 24), x11 = (19, 20), x12 = (20, 21),
x13 = (22, 23), x14 = (22, 27), x15 = (23, 26).
4. Classifying cubic s-regular graphs of order 28p
In this section, by applying concept linear algebra, the connected
cubic s-regular graphs of orders 28p, where p is a prime, is investigated.
Assume that a connected graph X and a subgroup G 6 Aut(X) are given.
Choose a spanning tree T of X and a set of arcs {x1, . . . , xr} ⊆ A(X)
“adm-n1” — 2018/4/2 — 12:46 — page 63 — #65
A. Imani, N. Mehdipoor, A. A. Talebi 63
containing exactly one arc from each edge in E(X \ T ). Let BT be the
corresponding basis of the first homology group H1(X,Zp) determined by
{x1, . . . , xr}. Further, denote by G∗h = {α∗h|α ∈ G} 6 GL(H1(X,Zp))
the induced action of G on H1(X,Zp), and let MG 6 Zr×r
p be the matrix
representation of G∗h with respect to the basis BT . By M t
G we denote the
dual group consisting of all transposes of matrices in MG.
The following proposition is a special case of [18, Proposition 6.3,
Corollary 6.5].
Proposition 4.1. Let T be a spanning tree of a connected graph X and
let the set {x1, x2, . . . , xr} ⊆ A(X) contain exactly one arc from each
cotree edge. Let ξ : A(X) → Zp be a voltage assignment on X which is
trivial on T , and let Z(ξ) = [ξ(x1), ξ(x2), . . . , ξ(xr)]
t ∈ Zr×1
p . Then the
following hold.
(a) A group G 6 Aut(X) lifts along pξ : Cov(X, ξ) → X if and only
if the induced subspace 〈Z(ξ)〉 is an M t
G-invariant 1-dimensional
subspace.
(b) If ξ
′
: A(X) → Zp is another voltage assignment satisfying (a), then
Cov(X, ξ
′
) is equivalent to Cov(X, ξ) if and only if 〈Z(ξ)〉 = 〈Z(ξ
′
)〉,
as subspaces. Moreover, Cov(X, ξ
′
) is isomorphic to Cov(X, ξ) if
and only if there exists an automorphism α ∈ Aut(X) such that the
matrix M t
α maps 〈Z(ξ
′
)〉 onto 〈Z(ξ)〉.
We have the following theorem, by [5, 6].
Theorem 4.2. Let p < 79 be a prime. Then, there are cubic symmetric
graphs of order 28p. We classify all cubic symmetric graphs in Table 1.
Graph order s-regular
F056A 28*2 1
F056B 28*2 2
F056C 28*2 3
F084A 28*3 2
F364A 28*13 2
F364B 28*13 2
F364C 28*13 2
F364D 28*13 2
F364E 28*13 2
F364F 28*13 2
F364G 28*13 3
Table 1. Cubic symmetric graphs of order 28p with p < 79.
“adm-n1” — 2018/4/2 — 12:46 — page 64 — #66
64 Classification cubic s-regular graph
Remark 4.3. To find all arc-transitive G-admissible Zp-covering pro-
jections of F28A, we have to find, by proposition 4.1, all invariant 1-
dimensional subspaces of the transpose of the matrix MG.
For this purpose, we express the following lemma.
Lemma 4.4. Let B, C and D be the transposes of the matrices which
represent the linear transformations β∗h, γ∗h and σ∗h relative to BT =
{Cxi
|1 6 i 6 15}; the standard ordered basis of H1(F28A,Zp) associated
with the spanning tree T and the arcs xi(i = 1, . . . , 15), respectively. Then
B =
0 0 0 0 0 0 0 1 0 0 0 0 0 0 −1
0 0 1 1 0 0 0 1 0 0 0 0 0 0 0
0 1 0 0 0 −1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 −1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 −1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 −1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 −1 0
0 0 0 0 1 0 0 0 0 0 0 0 1 −1 0
0 0 0 0 0 0 0 −1 0 0 0 −1 0 0 0
0 0 0 0 0 0 0 1 0 0 −1 0 0 0 0
0 0 0 0 0 0 0 0 −1 1 0 0 0 0 0
0 0 0 0 0 0 −1 0 −1 0 0 0 0 0 0
−1 0 0 0 0 0 0 −1 0 0 0 0 0 0 0
C =
0 0 0 0 0 0 0 0 −1 1 −1 0 0 0 1
0 0 0 0 0 0 −1 1 −1 0 −1 0 0 0 0
0 0 0 0 0 0 0 0 −1 0 −1 −1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 1 0 1
0 0 0 0 −1 0 0 0 0 0 1 0 −1 1 −1
0 0 0 0 −1 0 0 1 0 0 0 0 −1 1 −1
0 −1 0 0 −1 1 0 0 0 0 0 0 −1 1 −1
0 0 0 0 −1 1 0 0 1 0 1 0 −1 1 −1
0 0 0 0 0 0 0 0 0 0 0 0 1 −1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 −1 1 −1
0 0 −1 0 0 0 0 0 −1 0 −1 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 1
0 0 1 1 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 0 −1
“adm-n1” — 2018/4/2 — 12:46 — page 65 — #67
A. Imani, N. Mehdipoor, A. A. Talebi 65
D =
0 0 0 0 0 1 −1 0 0 −1 0 0 0 0 0
1 −1 0 0 0 1 −1 0 0 −1 0 0 0 0 0
0 −1 0 0 0 1 0 −1 0 0 0 0 0 0 0
0 0 0 0 0 0 −1 1 0 −1 0 0 0 0 −1
0 0 0 0 −1 0 1 0 0 1 0 0 −1 1 0
1 0 0 0 0 0 0 0 0 0 0 0 −1 1 0
0 0 0 0 0 0 0 0 0 1 0 0 −1 1 0
0 1 −1 0 0 −1 1 0 0 1 0 0 −1 1 0
0 0 0 0 0 0 0 0 0 −1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 −1 0 0 0 0 0
0 1 0 0 0 −1 1 0 0 1 0 −1 −1 0 0
0 −1 0 0 0 1 −1 0 −1 0 −1 0 0 0 0
0 0 0 0 0 0 0 0 1 −1 0 0 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
0 1 −1 −1 0 −1 1 0 0 1 0 0 0 0 0
Proof. The rows of these matrices are obtained by letting the automor-
phisms β, γ and σ act on BT . For example, the permutation β maps the
cycle
[0, 1, 2, 3, 4, 5, 6, 7, 24, 0]
corresponding to x1, to the cycle
[0, 1, 12, 13, 14, 15, 16, 26, 23, 0].
Since the latter is the sum of the base cycles corresponding to x8
and x−1
15 , the first row of B is
(0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,−1).
By similar computations we can get the matrices B, C and D.
By Sage [2] we have the following lemma.
Lemma 4.5. The minimal polynomials of B, C and D are
mB(x)=(x−1)(x+1), mC(x)=(x−1)(x+1) and mD(x)=(x−1)(x+1),
respectively.
By a straightforward calculation, lemma 4.4 and lemma 4.5, we have
ker(B − I) = 〈u1, u2, u3, u4, u5, u6, u7〉,
ker(B + I) = 〈u8, u9, u10, u11, u12, u13, u14, u15〉,
ker(C − I) = 〈v1, v2, v3, v4, v5, v6, v7〉,
ker(C + I) = 〈v8, v9, v10, v11, v12, v13, v14, v15〉,
ker(D − I) = 〈w1, w2, w3, w4, w5, w6〉,
ker(D + I) = 〈w7, w8, w9, w10, w11, w12, w13, w14, w15〉,
“adm-n1” — 2018/4/2 — 12:46 — page 66 — #68
66 Classification cubic s-regular graph
where
u1 =
1
0
0
0
0
0
0
0
0
0
1
−1
0
0
−1
, u2 =
0
1
1
0
0
−1
0
0
0
0
1
−1
0
0
0
, u3 =
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
, u4 =
0
0
0
0
1
0
0
0
0
1
0
0
1
−1
0
, u5 =
0
0
0
0
0
0
1
0
0
1
0
0
1
−1
0
,
u6 =
0
0
0
0
0
0
0
1
0
0
−1
1
0
0
0
, u7 =
0
0
0
0
0
0
0
0
1
−1
0
0
−1
0
0
, u8 =
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
, u9 =
0
1
−1
0
0
−1
0
0
0
0
0
0
0
0
0
, u10 =
0
0
0
1
0
−1
0
0
0
0
0
0
0
0
0
,
u11 =
0
0
0
0
1
0
0
0
0
−1
0
0
1
−1
0
, u12 =
0
0
0
0
0
0
1
0
0
1
0
0
−1
1
0
, u13 =
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
, u14 =
0
0
0
0
0
0
0
0
1
−1
0
0
1
0
0
, u15 =
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
,
“adm-n1” — 2018/4/2 — 12:46 — page 67 — #69
A. Imani, N. Mehdipoor, A. A. Talebi 67
v1 =
1
0
0
0
0
0
0
0
0
1
0
0
0
0
1
, v2 =
0
1
0
0
0
0
−1
1
0
0
0
0
0
0
0
, v3 =
0
0
1
0
0
0
0
0
0
0
0
−1
0
0
0
, v4 =
0
0
0
1
0
0
0
0
0
0
0
1
1
0
1
, v5 =
0
0
0
0
1
−1
0
−1
0
0
0
0
1
−1
1
,
v6 =
0
0
0
0
0
0
0
0
1
0
0
0
1
−1
1
, v7 =
0
0
0
0
0
0
0
0
0
0
1
0
−1
1
−1
, v8 =
1
0
0
0
0
0
0
0
0
−1
0
0
0
0
1
, v9 =
0
1
0
0
0
0
1
−1
0
0
0
0
0
0
2
, v10 =
0
0
1
0
0
0
0
0
0
0
0
1
0
0
2
,
v11 =
0
0
0
1
0
0
0
0
0
0
0
−1
−1
0
−1
, v12 =
0
0
0
0
1
0
0
0
0
0
0
0
1
−1
0
, v13 =
0
0
0
0
0
1
0
−1
0
0
0
0
0
0
1
, v14 =
0
0
0
0
0
0
0
0
1
0
0
0
−1
1
−1
, v15 =
0
0
0
0
0
0
0
0
0
0
1
0
1
−1
−1
,
“adm-n1” — 2018/4/2 — 12:46 — page 68 — #70
68 Classification cubic s-regular graph
w1 =
1
0
0
0
0
1
0
0
0
0
0
0
−1
1
0
, w2 =
0
1
0
0
0
−1
0
0
0
0
1
−1
0
−1
0
, w3 =
0
0
1
0
0
0
0
−1
0
0
1
−1
0
−1
0
, w4 =
0
0
0
1
0
0
0
1
0
0
0
0
−1
1
−1
, w5 =
0
0
0
0
0
0
1
0
0
1
0
0
−1
1
0
,
w6 =
0
0
0
0
0
0
0
0
1
−1
0
0
1
0
0
, w7 =
1
0
0
0
0
−1
0
0
0
0
0
0
−1
1
0
, w8 =
0
1
0
0
0
−1
0
0
0
0
0
0
−1
1
0
, w9 =
0
0
1
0
0
0
0
1
0
0
0
0
1
−1
0
, w10 =
0
0
0
1
0
0
0
−1
0
0
0
0
−1
1
1
,
w11 =
0
0
0
0
1
0
0
0
0
0
0
0
1
−1
0
, w12 =
0
0
0
0
0
0
1
0
0
0
0
0
1
−1
0
, w13 =
0
0
0
0
0
0
0
0
1
0
0
0
−1
0
0
, w14 =
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
, w15 =
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
“adm-n1” — 2018/4/2 — 12:46 — page 69 — #71
A. Imani, N. Mehdipoor, A. A. Talebi 69
Now, we have ker(B ± I) ∩ ker(C ± I) ∩ ker(D ± I) = 0.
Due to the above description, we have the following result.
Corollary 4.6. There is not 〈B,C,D〉-invariant 1-dimensional subspaces
in Z15
p .
Remark 4.7. If X is a regular graph with valency k on m vertices and
s > 1, then there are exactly mk(k − 1)s−1 s-arcs. It follows that if X is
s-arc transitive then |Aut(X)| must be divisible by mk(k − 1)s−1, and
if X is s-regular, then |Aut(X)| = mk(k − 1)s−1. In particular, a cubic
arc-transitive graph X is s-regular if and only if |Aut(X)| = (3m)2s−1.
Theorem 4.8. Let p > 79 be a prime. Then, there is no cubic symmetric
graph of order 28p.
Proof. Suppose that X is a connected cubic symmetric graph of order
28p, where p > 79 is a prime. Set A := Aut(X). let P be a Sylow
p-subgroup of A. If P is normal in A then by Proposition 2.1 X is a
regular covering of the graph F28A with the covering transformation
group Zp. On the contrary, suppose that P is not normal in A. Assume
that NA(P ) is the normalizer of P in A. By Sylow’s theorem, the number
of Sylow p-subgroups of A is 1 + np = | A
NA(P ) |, for a positive integer
n. By Proposition 2.2 X is at most 5-regular and hence |A| is a divisor
of 3 · 7 · 26p. Then 1 + np is a divisor of 3 · 7 · 26. Since p > 79, we
have (n, p) = (1, 83), (1, 167), (17, 79), (1, 223), (3, 149). We consider the
following cases.
Case I: (n, p) = (17, 79), (1, 223), (3, 149).
First, we suppose that (n, p) = (17, 79), (1, 223), (3, 149). Then 3·7·25 |
|A|, implying that X is at least 4-regular. Assume that A is nonsolvable.
Its composition factors would have to be a non-abelian simple {2, 3, 7, p}-
group where p = 79, 149, 223. Now, we can get a contradiction, by the
classification of finite simple groups [14, pp. 12-14] and [7]. Let N be
a minimal normal subgroup of A and X/N the quotient graph of X
corresponding to the orbits of N . Then N is an elementary abelian. By
Proposition 2.1 X/N is at least 4-regular with order 28, 14p, 7p or 4p. If
|X/N | = 28, 14p, 4p, by [3,4], Proposition 2,3 and 2.4 a contradiction can
be obtained. If |X/N | = 7p, then the quotient graph XN corresponding
to orbits of N has odd number(7p) of vertices and valency 3. It is a
contradiction.
Case II: (n, p) = (1, 83), (1, 167).
“adm-n1” — 2018/4/2 — 12:46 — page 70 — #72
70 Classification cubic s-regular graph
Now, we assume that (n, p) = (1, 83), (1, 167). Then 3 · 7 · 22 | |A|,
implying that X is at least 1-regular. With the same reasoning as Case I
A is solvable. Let M be a minimal normal subgroup of A and X/M
the quotient graph of X corresponding to the orbits of M . Then M is
elementary abelian. If |M | 6= p then by Proposition 2.1 X/M is at least
1-regular with order 14p, 7p or 4p. By the same argument as above, there is
no s-regular (s > 1) with order 14p, 7p or 4p. If |M | = p, then the quotient
graph X/M has order 28. The automorphism group of the Coxeter graph
contains no 1-regular subgroup [2]. Therefore the quotient graph X/M is
at least 2-regular. Since M ⊳ A, A/M is solvable. Let T/M be a minimal
normal subgroup of A/M . Hence T/M is an elementary abelian 2-, 7-
group. By Proposition 2.3 X/T is at least 2-regular with order 4 or 14. We
arrive at a contradiction with Proposition 2.5 and [19, Proposition 2.1 and
Corollary 2.2]. Therefore P is normal in A. Then X is a regular covering
of the graph F28A with the covering transformation group Zp. By sage
[2] the automorphisms of Coxeter graph has one proper arc-transitive
subgroup G = 〈β, γ, σ〉. By Remark 4.3, we have to find all invariant one-
dimensional subspaces of the transpose of the matrix MG. In other words,
we need to look for 〈B,C,D〉-invariant 1-dimensional subspaces in Z15
p . By
Corollary 4.6 there is not 〈B,C,D〉-invariant one-dimensional subspaces
in Z15
p . Then by Proposition 4.1.a G 6 Aut(F28A) cannot lift and hence
there is no cubic symmetric graph of order 28p where p > 79.
Corollary 4.9. Let p be a prime and letX be a connected cubic symmetric
graph of order 28p. Then
(1) X is 1-regular if and only if X is isomorphic to the graph F056A.
(2) X is 2-regular if and only if X is isomorphic to one of the eight
graphs F056B, F084A, F364A, F364B, F364C, F364D, F364E
and F364F .
(3) X is 3-regular if and only if X is isomorphic to one of the two graphs
F056C and F364G.
Proof. By Theorems 4.2 and 4.8, the proof is complete.
References
[1] M. Alaeiyan and M. K. Hosseinipoor A classification of the cubic s-regular graphs
of orders 12p and 12p2, Acta Universitatis Apulensis (2011), 153−158.
[2] R.A. Beezer, Sage for Linear Algebra A Supplement to a First course in Linear
Algebra.,Sage web site http://www.sagemath.org. 2011.
[3] W. Bosma and J. Cannon, Handbook of Magma Function, Sydney University Press,
Sydney, 1994.
“adm-n1” — 2018/4/2 — 12:46 — page 71 — #73
A. Imani, N. Mehdipoor, A. A. Talebi 71
[4] Y. Cheng and J. Oxley, On weakly symmetric graphs of order twice a prime, J.
Combin. Theory Ser. B 42 (1987), 196−211.
[5] M. D. E. Conder, Trivalent (cubic) symmetric graphs on up to 2048 vertices, J
(2006). http://www.math.auckland.ac.nz conder/symmcubic2048list.txt.
[6] M. D. E. Conder and P. Dobcsányi, Trivalent symmetric graphs on up to 768
vertices, J. Combin. Math. Combin. Comput. 40 (2002) 41−63.
[7] J. H. Conway, R. T. Curties, S. P. Norton, R. A. Parker, and R. A. Wilson, Atlas
of Finite Groups, Clarendon Press, Oxford, 1985.
[8] Y. Q. Feng and J. H. Kwak, Classifying cubic symmetric graphs of order 10p or
10p2, Sci. China Ser. A 49 (2006), 300−319.
[9] Y. Q. Feng and J. H. Kwak, Cubic symmetric graphs of order a small number
times a prime or a prime square J. Combin. Theory Ser. B 97 (2007), 627−646.
[10] Y. Q. Feng and J. H. Kwak, Cubic symmetric graphs of order twice an odd
prime-power, J. Aust. Math. Soc. 81 (2006), 153−164.
[11] Y. Q. Feng and J. H. Kwak, One-regular cubic graphs of order a small number
times a prime or a prime square, J. Aust. Math. Soc. 76 (2004), 345−356.
[12] Y. Q. Feng, J. H. Kwak and K. Wang, Classifying cubic symmetric graphs of order
8p or 8p2, European J. Combin. 26 (2005), 1033−1052.
[13] Y. Q. Feng, J. H. Kwak and M .Y. Xu, Cubic s-regular graphs of order 2p3, J.
Graph Theory 52 (2006), 341−352.
[14] D. Gorenstein, Finite Simple Groups, Plenum Press, New York, 1982.
[15] J. L. Gross and T.W. Tucker, Generating all graph coverings by permutation
voltage assignments, Discrete Math. 18 (1977), 273−283.
[16] P. Lorimer, Vertex-transitive graphs: Symmetric graphs of prime valency, J. Graph
Theory 8 (1984), 55−68.
[17] A. Malnic, Group actions, covering and lifts of automorphisms, Discrete Math.
182 (1998), 203− 218.
[18] A. Malnič, D. Marušič and P. Potočnik, Elementary abelian covers of graphs, J.
Algebraic Combin. 20 (2004) 71−97.
[19] J.M. Oh, A classification of cubic s-regular graphs of order 14p, Discrete Math.
309 (2009), 2721−2726
[20] J. M. Oh, cubic s-regular graphs of orders 12p, 36p, 44p, 52p, 66p, 68p and 76p, J.
Appl. Math. Inform., 31(2013) 651−659.
[21] M. Skoviera, A construction to the theory of voltage groups, Discrete Math. 61
(1986), 281−292.
[22] A. A. Talebi and N. Mehdipoor, Classifying cubic s-regular graphs of orders 22p,
22p2, Algebra Discrete Math. 16(2013) 293−298.
[23] W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947),
459−474.
[24] W. T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959),
621−624.
“adm-n1” — 2018/4/2 — 12:46 — page 72 — #74
72 Classification cubic s-regular graph
Contact information
A. Imani,
N. Mehdipoor,
A. A. Talebi
Faculty of Mathematics, University of
Mazandaran, Iran
E-Mail(s): al.imani@stu.umz.ac.ir,
nargesmehdipoor@yahoo.com,
a.talebi@umz.ac.ir
Received by the editors: 16.02.2016.
|