zbMATH — the first resource for mathematics

A classification of semisymmetric graphs of order \(2pq\). (English) Zbl 0944.05051
Let \(X\) be a bipartite graph with bipartition \(V(X)=U(X)\cup W(X)\). Let \(A=\)Aut\((X)\), \(A^+=\{g\in A\mid U(X)^g=U(X)\) and \(W(X)^g=W(X)\}\). Suppose \(G\) is a subgroup of \(A^+\). Then \(X\) is said to be \(G\)-semitransitive, if \(G\) acts transitively on both \(U(X)\) and \(W(X)\), and semitransitive, if \(X\) is \(A^+\)-semitransitive. We call a graph semisymmetric if it is regular and edge-transitive but not vertex-transitive. This paper gives a classification of semisymmetric graphs of order \(2pq\) where \(p\) and \(q\) are distinct primes. Given a group \(G\) and a subgroup \(H\) of \(G\), we use \([G:H]\) to denote the set of right cosets of \(H\) in \(G\). Let \(G\) be a group, let \(L\) and \(R\) be subgroups of \(G\) and let \(D=\bigcup_i Rd_iL\) be a union of double cosets of \(R\) and \(L\) in \(G\). Define a bipartite graph \(X=B(G,L,R;D)\) with bipartition \(V(X)=[G:L]\cup [G:R]\) and edge set \(E(X)=\{(Lg,Rdg)\mid g\in G\) and \(d\in D\}\). This graph is called the bi-coset graph of \(G\) with respect to \(L\), \(R\) and \(D\). Given a \(G\)-semitransitive and \(G\)-edge transitive graph \(X\) with bipartition \(V(X)=U(X)\cup W(X)\), where \(|U(X)|=p\) and \(|W(X)|=pq\) for two distinct primes \(p\) and \(q\), we define a bipartite graph \(\overline X\) with bipartition \(V(\overline X)=U(\overline X)\cup W(\overline X)\) as follows: \(U(\overline X)=\{u_i\mid u\in U(X)\) and \(1\leq i\leq q\}\), \(W(\overline X)=W(X)\), \(E(\overline X)=\{(u_i,w)\mid (u,w)\in E(X)\) and \(1\leq i\leq q\}\). Suppose \(Y\) is a semisymmetric graph of order \(2pq\), where \(p\) and \(q\) are distinct primes. Then either \(Y\) is biprimitive and \(Y\) is one of the bi-coset graphs \(B(G,L,R;D)\) with \(G=M_{23}\) or \(\text{PSL}(2,q)\), \(q=11,13,23,59,61\), or \(Y\) is not biprimitive and \(Y\) is isomorphic to the graph \(\overline X\) derived from one of the bi-coset graphs \(B(G,L,R;D)\) with \(G= \text{PSL}(2,11), \text{PSL}(5,2),S_p\) or \(G\) is a semidirect product of \(Z_p\) by a \(Z_{qk}\), where \(qk\) divides \(p-1\) (Theorem 2.8).

05C20 Directed graphs (digraphs), tournaments
20B25 Finite automorphism groups of algebraic, geometric, or combinatorial structures
Full Text: DOI
[1] DOI: 10.4153/CMB-1968-063-0 · Zbl 0182.58102 · doi:10.4153/CMB-1968-063-0
[2] DOI: 10.1016/0095-8956(72)90030-5 · Zbl 0228.05114 · doi:10.1016/0095-8956(72)90030-5
[3] Cheng Y., J. Combin. Theory 4 pp 196– (1987) · Zbl 0583.05032 · doi:10.1016/0095-8956(87)90040-2
[4] DOI: 10.1112/blms/13.1.1 · Zbl 0463.20003 · doi:10.1112/blms/13.1.1
[5] Conway J.H., Atlas of Finite Groups (1985)
[6] Dickson L.E., Linear Groups with an exposition of the Galois field theory 1901 (1958) · JFM 32.0128.01
[7] DOI: 10.1007/978-1-4612-0731-3 · doi:10.1007/978-1-4612-0731-3
[8] Du S.F., Graph Theory Notes (1995)
[9] DOI: 10.1023/A:1018625926088 · Zbl 0937.05049 · doi:10.1023/A:1018625926088
[10] DOI: 10.1016/S0021-9800(67)80069-3 · Zbl 0158.42501 · doi:10.1016/S0021-9800(67)80069-3
[11] Huppert B., Endliche Gruppen I (1967) · Zbl 0217.07201
[12] Iofinova, M.E. and Ivanov, A.A. Biprimitive cubic graphs (Russian), in Investigation in Algebraic Theory of Combinatorial Objects. Proceedings of the seminar. pp.124–134. Moscow: Institute for System Studies.
[13] Ivanov I.V., Comb. Annals of Discrete Mathematices 34 pp 273– (1987)
[14] DOI: 10.1007/BF02582940 · Zbl 0594.05009 · doi:10.1007/BF02582940
[15] Klin, M.H. Colloquia Mathematica Societatis Janos Bolyai. Algebraic Methods in Graph Theory. Szeged, Hungary. Vol. 25, pp.399–403. Budapest On edge but not vertex transitive regular graphs
[16] DOI: 10.1016/0021-8693(87)90223-7 · Zbl 0632.20011 · doi:10.1016/0021-8693(87)90223-7
[17] DOI: 10.1112/jlms/s2-31.2.237 · Zbl 0573.20003 · doi:10.1112/jlms/s2-31.2.237
[18] Manning W.A., Tran. Amer. Math. Soc 19 pp 127– (1918)
[19] DOI: 10.1006/jctb.1993.1046 · Zbl 0793.05071 · doi:10.1006/jctb.1993.1046
[20] DOI: 10.1006/jctb.1993.1068 · Zbl 0793.05072 · doi:10.1006/jctb.1993.1068
[21] DOI: 10.1007/BF01304186 · Zbl 0136.44608 · doi:10.1007/BF01304186
[22] DOI: 10.1017/S1446788700036090 · doi:10.1017/S1446788700036090
[23] Titov, V.K. On symmetry in the graphs (Russian), Voprocy Kibemetiki (15). Proceedings of the II All Union Seminar on Combinatorial Mathematices. pp.76–109. Moscow: Nauka. Part 2
[24] DOI: 10.1006/jctb.1993.1037 · Zbl 0793.05074 · doi:10.1006/jctb.1993.1037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.