# ALGEBRAIC COMBINATORICS

Four-Valent Oriented Graphs of Biquasiprimitive Type
Algebraic Combinatorics, Volume 4 (2021) no. 3, pp. 409-434.

Let $\mathrm{𝒪𝒢}\left(4\right)$ denote the family of all graph-group pairs $\left(\Gamma ,G\right)$ where $\Gamma$ is 4-valent, connected and $G$-oriented ($G$-half-arc-transitive). Using a novel application of the structure theorem for biquasiprimitive permutation groups of the second author, we produce a description of all pairs $\left(\Gamma ,G\right)\in \mathrm{𝒪𝒢}\left(4\right)$ for which every nontrivial normal subgroup of $G$ has at most two orbits on the vertices of $\Gamma$, and at least one normal subgroup has two orbits. In particular we show that $G$ has a unique minimal normal subgroup $N$ and that $N\cong {T}^{k}$ for a simple group $T$ and $k\in \left\{1,2,4,8\right\}$. This provides a crucial step towards a general description of the long-studied family $\mathrm{𝒪𝒢}\left(4\right)$ in terms of a normal quotient reduction. We also give several methods for constructing pairs $\left(\Gamma ,G\right)$ of this type and provide many new infinite families of examples, covering each of the possible structures of the normal subgroup $N$.

Revised:
Accepted:
Published online:
DOI: https://doi.org/10.5802/alco.161
Classification: 05C25,  20B25,  05E18
Keywords: Edge-transitive graphs, automorphism groups, oriented graphs, graph quotients, vertex-transitive graphs, quasiprimitive permutation groups, Cayley graphs.
@article{ALCO_2021__4_3_409_0,
author = {Poznanovi\'c, Nemanja and Praeger, Cheryl E.},
title = {Four-Valent {Oriented} {Graphs} of {Biquasiprimitive} {Type}},
journal = {Algebraic Combinatorics},
pages = {409--434},
publisher = {MathOA foundation},
volume = {4},
number = {3},
year = {2021},
doi = {10.5802/alco.161},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.161/}
}
Poznanović, Nemanja; Praeger, Cheryl E. Four-Valent Oriented Graphs of Biquasiprimitive Type. Algebraic Combinatorics, Volume 4 (2021) no. 3, pp. 409-434. doi : 10.5802/alco.161. https://alco.centre-mersenne.org/articles/10.5802/alco.161/

[1] Al-bar, Jehan A.; Al-kenani, Ahmad N.; Muthana, Najat Mohammad; Praeger, Cheryl E. Finite edge-transitive oriented graphs of valency four with cyclic normal quotients, J. Algebraic Combin., Volume 46 (2017) no. 1, pp. 109-133 | Article | MR 3666414 | Zbl 1368.05064

[2] Al-bar, Jehan A.; Al-kenani, Ahmad N.; Muthana, Najat Mohammad; Praeger, Cheryl E. A normal quotient analysis for some families of oriented four-valent graphs, Ars Math. Contemp., Volume 12 (2017) no. 2, pp. 361-381 | Article | MR 3646701 | Zbl 1370.05088

[3] Al-bar, Jehan A.; Al-kenani, Ahmad N.; Muthana, Najat Mohammad; Praeger, Cheryl E.; Spiga, Pablo Finite edge-transitive oriented graphs of valency four: a global approach, Electron. J. Combin., Volume 23 (2016) no. 1, Paper no. Paper 1.10 | Article | MR 3484715 | Zbl 1329.05142

[4] Bosma, Wieb; Cannon, John; Playoust, Catherine The Magma algebra system. I. The user language, J. Symbolic Comput., Volume 24 (1997) no. 3-4, pp. 235-265 Computational algebra and number theory (London, 1993) | Article | MR MR1484478 | Zbl 0898.68039

[5] Conder, Marston; Zhou, Jin-Xin; Feng, Yan-Quan; Zhang, Mi-Mi Edge-transitive bi-Cayley graphs, J. Combin. Theory Ser. B, Volume 145 (2020), pp. 264-306 | Article | MR 4113182 | Zbl 1448.05098

[6] Coxeter, Harold S.; Moser, William O. J. Generators and relations for discrete groups, Springer Science & Business Media, 1957 | Zbl 0077.02801

[7] Godsil, Chris; Royle, Gordon Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | Article | MR 1829620 | Zbl 0968.05002

[8] Guralnick, Robert M. Subgroups of prime power index in a simple group, J. Algebra, Volume 81 (1983) no. 2, pp. 304-311 | Article | MR 700286 | Zbl 0515.20011

[9] Huppert, Bertram Endliche Gruppen. I, Die Grundlehren der Mathematischen Wissenschaften, Band 134, Springer-Verlag, Berlin-New York, 1967, xii+793 pages | MR 0224703 | Zbl 0217.07201

[10] King, Carlisle S. H. Generation of finite simple groups by an involution and an element of prime order, J. Algebra, Volume 478 (2017), pp. 153-173 | Article | MR 3621666 | Zbl 1376.20018

[11] Marušič, Dragan Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser. B, Volume 73 (1998) no. 1, pp. 41-76 | Article | MR 1620595 | Zbl 0924.05034

[12] Marušič, Dragan Recent developments in half-transitive graphs, Discrete Math., Volume 182 (1998) no. 1-3, pp. 219-231 | Article | MR 1603691 | Zbl 0891.05036

[13] Marušič, Dragan; Nedela, Roman On the point stabilizers of transitive groups with non-self-paired suborbits of length 2, J. Group Theory, Volume 4 (2001) no. 1, pp. 19-43 | Article | MR 1808836 | Zbl 0982.20002

[14] Marušič, Dragan; Praeger, Cheryl E. Tetravalent graphs admitting half-transitive group actions: alternating cycles, J. Combin. Theory Ser. B, Volume 75 (1999) no. 2, pp. 188-205 | Article | MR 1676888 | Zbl 0936.05055

[15] Morris, Joy; Praeger, Cheryl E.; Spiga, Pablo Strongly regular edge-transitive graphs, Ars Math. Contemp., Volume 2 (2009) no. 2, pp. 137-155 | Article | MR 2545504 | Zbl 1216.05056

[16] Potočnik, Primož; Šparl, Primož On the radius and the attachment number of tetravalent half-arc-transitive graphs, Discrete Math., Volume 340 (2017) no. 12, pp. 2967-2971 | Article | MR 3698084 | Zbl 1370.05095

[17] Potočnik, Primož; Spiga, Pablo; Verret, Gabriel A census of 4-valent half-arc-transitive graphs and arc-transitive digraphs of valence two, Ars Math. Contemp., Volume 8 (2015) no. 1, pp. 133-148 | Article | MR 3281125 | Zbl 1317.05191

[18] Potočnik, Primož; Verret, Gabriel On the vertex-stabiliser in arc-transitive digraphs, J. Combin. Theory Ser. B, Volume 100 (2010) no. 6, pp. 497-509 | Article | MR 2718673 | Zbl 1230.05141

[19] Potočnik, Primož; Wilson, Steve The separated box product of two digraphs, European J. Combin., Volume 62 (2017), pp. 35-49 | Article | MR 3621721 | Zbl 1358.05240

[20] Poznanović, Nemanja; Praeger, Cheryl E. Biquasiprimitive oriented graphs of valency four, 2017 MATRIX annals (MATRIX Book Ser.), Volume 2, Springer, Cham, 2019, pp. 337-341 | Article | MR 3931075 | Zbl 1415.05074

[21] Praeger, Cheryl E. Imprimitive symmetric graphs, Ars Combin., Volume 19 (1985) no. A, pp. 149-163 | MR 790928 | Zbl 0575.05047

[22] Praeger, Cheryl E. An O’Nan–Scott theorem for finite quasiprimitive permutation groups and an application to $2$-arc transitive graphs, J. London Math. Soc. (2), Volume 47 (1993) no. 2, pp. 227-239 | Article | MR 1207945 | Zbl 0738.05046

[23] Praeger, Cheryl E. Finite normal edge-transitive Cayley graphs, Bull. Austral. Math. Soc., Volume 60 (1999) no. 2, pp. 207-220 | Article | MR 1711938 | Zbl 0939.05047

[24] Praeger, Cheryl E. Finite transitive permutation groups and bipartite vertex-transitive graphs, Illinois J. Math., Volume 47 (2003) no. 1-2, pp. 461-475 | MR 2031334 | Zbl 1032.20004

[25] Praeger, Cheryl E.; Schneider, Csaba Permutation groups and Cartesian decompositions, London Mathematical Society Lecture Note Series, 449, Cambridge University Press, Cambridge, 2018, xiii+323 pages | Article | MR 3791829 | Zbl 1428.20002

[26] Rivera, Alejandra Ramos; Šparl, Primož New structural results on tetravalent half-arc-transitive graphs, J. Combin. Theory Ser. B, Volume 135 (2019), pp. 256-278 | Article | MR 3926270 | Zbl 1404.05081

[27] Zhou, Jin-Xin; Feng, Yan-Quan The automorphisms of bi-Cayley graphs, J. Combin. Theory Ser. B, Volume 116 (2016), pp. 504-532 | Article | MR 3425255 | Zbl 1327.05151