Classifying cubic s-regular graphs of orders 22p and 22p²
A graph is s-regular if its automorphism group acts regularly on the set of s-arcs. In this study, we classify the connected cubic s-regular graphs of orders 22p and 22p² for each s ≥ 1, and each prime p.
Gespeichert in:
| Datum: | 2013 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2013
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/152355 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Classifying cubic s-regular graphs of orders 22p and 22p² / A.A. Talebi, N. Mehdipoor // Algebra and Discrete Mathematics. — 2013. — Vol. 16, № 2. — С. 293–298. — Бібліогр.: 18 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-152355 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1523552019-06-12T01:25:24Z Classifying cubic s-regular graphs of orders 22p and 22p² Talebi, A.A. Mehdipoor, N. A graph is s-regular if its automorphism group acts regularly on the set of s-arcs. In this study, we classify the connected cubic s-regular graphs of orders 22p and 22p² for each s ≥ 1, and each prime p. 2013 Article Classifying cubic s-regular graphs of orders 22p and 22p² / A.A. Talebi, N. Mehdipoor // Algebra and Discrete Mathematics. — 2013. — Vol. 16, № 2. — С. 293–298. — Бібліогр.: 18 назв. — англ. 1726-3255 2000 MSC:05C25, 20b25. http://dspace.nbuv.gov.ua/handle/123456789/152355 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 study, we classify the connected cubic s-regular graphs of orders 22p and 22p² for each s ≥ 1, and each prime p. |
| format |
Article |
| author |
Talebi, A.A. Mehdipoor, N. |
| spellingShingle |
Talebi, A.A. Mehdipoor, N. Classifying cubic s-regular graphs of orders 22p and 22p² Algebra and Discrete Mathematics |
| author_facet |
Talebi, A.A. Mehdipoor, N. |
| author_sort |
Talebi, A.A. |
| title |
Classifying cubic s-regular graphs of orders 22p and 22p² |
| title_short |
Classifying cubic s-regular graphs of orders 22p and 22p² |
| title_full |
Classifying cubic s-regular graphs of orders 22p and 22p² |
| title_fullStr |
Classifying cubic s-regular graphs of orders 22p and 22p² |
| title_full_unstemmed |
Classifying cubic s-regular graphs of orders 22p and 22p² |
| title_sort |
classifying cubic s-regular graphs of orders 22p and 22p² |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2013 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/152355 |
| citation_txt |
Classifying cubic s-regular graphs of orders 22p and 22p² / A.A. Talebi, N. Mehdipoor // Algebra and Discrete Mathematics. — 2013. — Vol. 16, № 2. — С. 293–298. — Бібліогр.: 18 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT talebiaa classifyingcubicsregulargraphsoforders22pand22p2 AT mehdipoorn classifyingcubicsregulargraphsoforders22pand22p2 |
| first_indexed |
2025-07-13T02:53:56Z |
| last_indexed |
2025-07-13T02:53:56Z |
| _version_ |
1837498619810283520 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 16 (2013). Number 2. pp. 293 – 298
c© Journal “Algebra and Discrete Mathematics”
Classifying cubic s-regular graphs
of orders 22p and 22p
2
A. A. Talebi and N. Mehdipoor
Communicated by Z. Marciniak
Abstract. A graph is s-regular if its automorphism group
acts regularly on the set of s-arcs. In this study, we classify the
connected cubic s-regular graphs of orders 22p and 22p2 for each
s ≥ 1, and each prime p.
1. Introduction
In this study, all graphs considered are assumed to be undirected,
finite, simple, and connected, unless stated otherwise. For a graph X,
V (X), E(X), Arc(X), and Aut(X) denote its vertex set, edge set, arc
set, and full automorphism group, respectively. Let G be a subgroup of
Aut(X). For u, v ∈ V (X), uv 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
2000 MSC: 05C25, 20b25.
Key words and phrases: s-regular graphs, s-arc-transitive graphs, symmetric
graphs, regular covering.
294 Classifying cubic s-regular graphs of orders 22p
the set Ω of K-orbits in V (X) is the vertex set of X/K and B, C ∈ Ω
are adjacent if and only if there exist 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 cubic map X̃ → X̃/N is the composition ph of p and h (in
this paper, all functions are composed from left to right). 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 ≤ i ≤ s, and vi−1 6=
vi+1 for 1 ≤ 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
said to be 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 [17, 18] 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 [4, 5] classified the cubic s-regular graphs up to order 2048
with the help of the “Low index normal subgroups” routine in MAGMA
system [2]. Cheng and Oxley [3] classified the cubic s-regular graphs of
order 2p. Recently, by using the covering technique, cubic s-regular graphs
with order 2p2, 2p3, 4p, 4p2, 6p, 6p2, 8p, 8p2, 10p, 10p2, 12p, 12p2, 14p
and 16p were classified in [1, 7 − 12, 15, 16].
In this paper, by employing the covering technique, and group-theore-
tical construction, we investigate connected cubic s-regular graphs of
orders 22p and 22p2 for each s ≥ 1, and each prime p.
A. A. Talebi, N. Mehdipoor 295
2. Preliminaries
We start by introducing two propositions for later applications in this
paper.
Proposition 2.1. [14, Theorem 9] 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. [18] If X is an s-arc regular cubic graph, then s ≤ 5.
Remark. If X is a regular graph with valency k on n vertices and
s ≥ 1, then there exactly nk(k − 1)s−1 s-arcs. It follows that if X is
s-arc transitive then |Aut(X)| must be divisible by nk(k − 1)s−1, and
if X is s-regular, then |Aut(X)| = nk(k − 1)s−1. In particular, a cubic
arc-transitive graph X is s-regular if and only if |Aut(X)| = (3n)2s−1.
3. Cubic s-regular graphs of orders 22p and 22p
2
In this section, we investigate the connected cubic s-regular graphs of
orders 22p and 22p2, where p is a prime. We have the following lemma,
by [4, 5].
Lemma 3.1. Let p be a prime. Let X be a connected cubic symmetric
graph. If X has order 22p, and p ≤ 89, then X is isomorphic to one of the
2-regular graph F242 with order 242, the 3-regular graphs F110, F506A
with orders 110, 506 respectively, or the 4-regular graph F506B with
order 506.
Lemma 3.2. Let p be a prime. Then, there is no cubic symmetric graph
of order 22p for p > 89.
Proof. Suppose that X is a connected cubic symmetric graph of the order
22p, where p > 89 is a prime. Set A := Aut(X). By proposition 2.2, and
[18], X is at most 5-regular. Then, |A| = 2s. 3. 11. p, where 1 ≤ s ≤ 5.
Then we deduce that solvable. Because if not, then by the classification
of finite simple groups, its composition factors would have to be one of
the following non-abelian simple groups
M11, M12, PSL(2, 11), PSL(2, 19), PSL(2, 23),
PSL(2, 32), or PSU(5, 2).
(3.1)
296 Classifying cubic s-regular graphs of orders 22p
Since p > 89, this contradicts the order of A. Therefore, A is solvable,
and hence, elementary Abelian. Let N is a minimal normal subgroup of
A. Then, N is an elementary Abelian. Hence, N is 2, 3, 11, or p-group.
Then, N has more than two orbits on V (X), and hence it is semiregular,
by proposition 2.1. Thus, |N | | 22p. Therefore |N | = 2, 11, or p. In each
case, we get a contradiction.
case I): |N | = p
If |N | = p, then the quotient graph XN of X relative to N is an
A/N -symmetric graph of the order 22, by Proposition 2.1. It is impossible
by [4]. Suppose that Q := Op(A) be the maximal normal p-subgroup of
A. Therefore, Op(A) = 1.
case II): |N | = 2
If |N | = 2, then Proposition 2.1, implies that the quotient graph XN
corresponding to orbits of N has odd number of vertices and valency 3,
which is impossible.
case III): |N | = 11
Now, we consider the quotient graph XN = X/N of X relative to N ,
where A/N is a s-regular of Aut(XN ). Let K/N be a minimal normal
subgroup of A/N . By the same argument as above K/N is solvable, and
elementary Abelian. Then, we must have |K/N | = 2, or p. Consequently
|K| = 22, or 11p. If |K| = 22, we consider the quotient graph XK = X/K
of X relative to K, where A/K is a s-regular of Aut(XK). By Proposition
2.1, XK is an A/K-symmetric graph of the order p. Then, with the same
reasoning as case II, we get a contradiction. Now, suppose that |K| = 11p.
Since p > 89, K has a normal subgroup of order p, which is characteristic
in K and hence is normal in A, contradicting to Op(A) = 1.
Theorem 3.3. Let p be a prime. Let X be a connected cubic symmetric
graph. Let p be a prime. Let X be a connected cubic symmetric graph.
If X has order 22p then, X is isomorphic to one of the 2-regular graph
F 242 with order 242, the 3-regular graphs F 110, F 506A with orders 110,
506 respectively, or the 4-regular graph F506B with order 506.
Proof. By Lemmas 3.1 and 3.2, the proof is complete.
Theorem 3.4. Let p be a prime. Then, there is no cubic symmetric
graph of order 22p2.
Proof. For p ≤ 7, by [3], there is no connected cubic symmetric graph
of the order 22p2. Thus we may assume that p ≥ 11. Suppose that X
is a connected cubic symmetric graph of the order 22p2, where p > 7 is
A. A. Talebi, N. Mehdipoor 297
a prime. Set A := Aut(X). Then, |A| = 2s. 3. 11. p2, where 1 ≤ s ≤ 5.
First, suppose that A is nonsolvable. Then, A is a product of isomorphic
non-abelian simple groups. By the classification of finite simple groups,
its composition factors would have to be a non-abelian simple {2, 3, 11}-
group, or {2, 3, 11, p}-group. Let q be a prime. Then, by [13, pp. 12-14],
and [6], a non-abelian simple {2, q, p}-group is one of the groups
A5, A6, PSL(2, 7), PSL(2, 8), PSL(2, 17), PSL(3, 3),
PSU(3, 3), or PSU(4, 2).
(3.2)
But, this is contradiction to the order of A. Then, composition factors
is a {2, 3, 11, p}-group. By the classification of finite simple groups, its
composition factors would have to be one of the following non-abelian
simple groups listed in (3.1). However, this contradicts the order of A.
Therefore, A is solvable, and hence, elementary Abelian. Let N is a
minimal normal subgroup of A. Then, N is an elementary Abelian. Hence,
N is 2, 3, 11, or p-group. Then, N has more than two orbits on V (X), and
hence it is semiregular, by proposition 2.1. Thus, |N | | 22p2. Therefore
|N | = 2, 11, p, or p2. In each case, we get a contradiction.
case I): |N | = p2
If |N | = p2, then the quotient graph XN of X relative to N is an
A/N -symmetric graph of the order 22, by Proposition 2.1. It is impossible
by [4]. Suppose that Q := Op(A) be the maximal normal p-subgroup of A.
case II): |N | = p
Now, we consider the quotient graph XN = X/N of X relative to N ,
where A/N is a s-regular of Aut(XN ). Let K/N be a minimal normal
subgroup of A/N . By the same argument as above K/N is solvable, and
elementary Abelian. Then, we must have |K/N | = 2, 11, or p. Now, by
considering the quotient graph XK with the same reasoning as lemma
3.2, a contradiction can be obtained.
case III): |N | = 11
Now, we consider the quotient graph XN = X/N of X relative to N ,
where A/N is a s-regular of Aut(XN ). Let K/N be a minimal normal
subgroup of A/N . By the same argument as above K/N is solvable, and
elementary Abelian. Then, we must have |K/N | = 2, p, or p2. Consequently
|K| = 22, 11p, or 11p2. Then, with the same reasoning as case III of lemma
3.2 , we arrive at a contradiction.
case IV): |N | = 2
In this case by the argument as in the case II of Lemma 3.2 a similar
contradiction is obtained.
298 Classifying cubic s-regular graphs of orders 22p
References
[1] M. Alaeiyan and M. K. Hosseinipoor A classification of the cubic s-regular graphs
of orders 12p and 12p
2, Acta Universitatis Apulensis (2011), 153−158.
[2] W. Bosma and J. Cannon, Handbook of Magma Function, Sydney University Press,
Sydney, 1994.
[3] Y. Cheng and J. Oxley, On weakly symmetric graphs of order twice a prime, J.
Combin. Theory Ser. B 42 (1987), 196−211.
[4] M. D. E. Conder, Trivalent (cubic) symmetric graphs on up to 2048 vertices, J
(2006). http://www.math.auckland.ac.nz conder/symmcubic2048list.txt.
[5] 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.
[6] J. H. Conway, R. T. Curties, S. P. Norton, R. A. Parker, and R. A. Wilson, Atlas
of Finite Groups, Clarendon Press, Oxford, 1985.
[7] Y. Q. Feng and J. H. Kwak, Classifying cubic symmetric graphs of order 10p or
10p
2, Sci. China Ser. A 49 (2006), 300−319.
[8] 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.
[9] 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.
[10] 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.
[11] Y. Q. Feng, J. H. Kwak and K. Wang, Classifying cubic symmetric graphs of order
8p or 8p
2, European J. Combin. 26 (2005), 1033−1052.
[12] Y. Q. Feng, J. H. Kwak and M .Y. Xu, Cubic s-regular graphs of order 2p
3, J.
Graph Theory 52 (2006), 341−352.
[13] D. Gorenstein, Finite Simple Groups, Plenum Press, New York, 1982.
[14] P. Lorimer, Vertex-transitive graphs: Symmetric graphs of prime valency, J. Graph
Theory 8 (1984), 55−68.
[15] J.M. Oh, A classification of cubic s-regular graphs of order 14p, Discrete Math.
309 (2009), 2721−2726.
[16] J.M. Oh, A classification of cubic s-regular graphs of order 16p, Discrete Math.
309 (2009), 3150−3155.
[17] W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947),
459−474.
[18] W. T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959),
621−624.
Contact information
A. A. Talebi,
N. Mehdipoor
Department of Mathematics, University of
Mazandaran, Babolsar, Iran
E-Mail: a.talebi@umz.ac.ir,
nargesmehdipoor@yahoo.com
Received by the editors: 07.03.2012
and in final form 14.08.2013.
|