On the automorphism groups of connected bipartite irreducible graphs
- PDF / 285,561 Bytes
- 15 Pages / 510.236 x 680.315 pts Page_size
- 87 Downloads / 240 Views
On the automorphism groups of connected bipartite irreducible graphs S MORTEZA MIRAFZAL Department of Mathematics, Lorestan University, Khorramabad, Iran E-mail: [email protected]; [email protected]
MS received 7 January 2020; revised 27 March 2020; accepted 10 April 2020 Abstract. Let G = (V, E) be a graph with the vertex-set V and the edge-set E. Let N (v) denote the set of neighbors of the vertex v of G. The graph G is called irreducible whenever for every v, w ∈ V if v = w, then N (v) = N (w). In this paper, we present a method for finding automorphism groups of connected bipartite irreducible graphs. Then, by our method, we determine automorphism groups of some classes of connected bipartite irreducible graphs, including a class of graphs which are derived from Grassmann graphs. Let a0 be a fixed positive integer. We show that if G is a connected non-bipartite irreducible graph such that c(v, w) = |N (v) ∩ N (w)| = a0 when v, w are adjacent, whereas c(v, w) = a0 , when v, w are not adjacent, then G is a stable graph, that is, the automorphism group of the bipartite double cover of G is isomorphic with the group Aut(G) × Z2 . Finally, we show that the Johnson graph J (n, k) is a stable graph. Keywords. Automorphism group; bipartite double cover of a graph; Grassmann graph; stable graph; Johnson graph. Mathematics Subject Classification.
05C25.
1. Introduction In this paper, a graph G = (V, E) is considered as an undirected simple finite graph, where V = V (G) is the vertex-set and E = E(G) is the edge-set. For the terminology and notation not defined here, we follow [1,2,4,7]. Let G = (U ∪ W, E), U ∩ W = ∅ be a bipartite graph with parts U and W . It is quite possible that we wish to construct some other graphs which are related to G in some aspects. For instance, there are cases in which we can construct a graph G 1 = (U, E 1 ) such that we have Aut(G) ∼ = Aut(G 1 ), where Aut(X ) is the automorphism group of the graph X . For example, note the following cases: (i) Let n ≥ 3 be an integer and [n] = {1, 2, . . . , n}. Let k be an integer such that 1 ≤ k < n2 . The graph B(n, k) introduced in [16] is a graph with the vertex-set V = {v | v ⊂ [n], |v| ∈ {k, k + 1}} and the edge-set E = {{v, w} | v, w ∈ V, v ⊂ w or w ⊂ v}. It is clear that the graph B(n, k) is a bipartite graph with the vertex-set V = V1 ∪ V2 , where V1 = {v ⊂ [n] | |v| = k} and V2 = {v ⊂ [n] | |v| = k + 1}. This graph has some interesting properties which have been investigated recently © Indian Academy of Sciences 0123456789().: V,-vol
57
Page 2 of 15
Proc. Indian Acad. Sci. (Math. Sci.)
(2020) 130:57
[11,16,17,20]. Let G = B(n, k) and let G 1 = (V1 , E 1 ) be the Johnson graph J (n, k) which can be constructed on the vertex-set V1 . It has been proved that if n = 2k + 1, then Aut(G) ∼ = Aut(G 1 ) × Z2 [16]. = Aut(G 1 ), and if n = 2k + 1, then Aut(G) ∼ (ii) Let n and k be integers with n > 2k, k ≥ 1. Let V be the set of all k-subsets and (n −k)-subsets of [n]. The bipartite Kneser graph H (n, k) has V as its vertex-set
Data Loading...
