Cayley Properties of the Line Graphs Induced by Consecutive Layers of the Hypercube
- PDF / 470,472 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 4 Downloads / 192 Views
Cayley Properties of the Line Graphs Induced by Consecutive Layers of the Hypercube S. Morteza Mirafzal1 Received: 26 April 2020 / Revised: 13 August 2020 / Accepted: 26 August 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract Let n > 3 and 0 < k < n2 be integers. In this paper, we investigate some algebraic properties of the line graph of the graph Q n (k, k + 1) where Q n (k, k + 1) is the subgraph of the hypercube Q n which is induced by the set of vertices of weights k and k + 1. The graph Q n (k, k + 1) has a close relation to Johnson graph J (n + 1, k + 1). In fact, it is the square root of the graph J (n +1, k +1). We will see that when n = 2k +1, then the graph Q n (k, k +1) is a non-regular edge-transitive graph; hence, its line graph is a vertex-transitive graph. In the first step, we determine the automorphism groups of these graphs for all values of n, k. In the second step, we study Cayley properties of the line graphs of these graphs. In particular, we show that if k ≥ 3 and n = 2k + 1, then except for the cases (k, n) = (3, 9) and (k, n) = (3, 33), the line graph of the graph Q n (k, k + 1) is a vertex-transitive non-Cayley graph. Also, we show that the line graph of the graph Q n (1, 2) is a Cayley graph if and only if n is a power of a prime p. Moreover, we show that for ‘almost all’ even values of k, the line graph of the graph Q 2k+1 (k, k + 1) is a vertex-transitive non-Cayley graph. Keywords Middle layer cube · Line graph · Automorphism group · k-homogeneous permutation group · Sharply 2-transitive permutation group · Cayley graph Mathematics Subject Classification 05C25
Communicated by Sanming Zhou.
B 1
S. Morteza Mirafzal [email protected] ; [email protected] Faculty of Basic Science, Department of Mathematics, Lorestan University, Khorramabad, Islamic Republic of Iran
123
S. M. Mirafzal
1 Introduction In this paper, a graph Γ = (V , E) is considered as an undirected simple graph where V = V (Γ ) is the vertex-set and E = E(Γ ) is the edge-set. For all the terminology and notation not defined here, we follow [2,8,11]. Let n ≥ 1 be an integer. The hypercube Q n is the graph whose vertex set is {0, 1}n , where two n-tuples are adjacent if they differ in precisely one coordinate. The hypercube Q n has been extensively studied. Nevertheless, many open questions remain. Harary, Hayes, and Wu [13] wrote a comprehensive survey on hypercube graphs. In the graph Q n , the layer L k is the set of vertices which contain k 1’s, namely, vertices of weight k, 1 ≤ k ≤ n. We denote by Q n (k, k + 1) the subgraph of Q n induced by layers L k and L k+1 . For n = 2k + 1, the graph Q 2k+1 (k, k + 1) has been investigated from various aspects by various authors and is called the middle layer cube [7,13,15,29] or regular hyperstar graph (denoted by H S(2k, k)) [18,19,23]. It has been conjectured by Dejter, Erd˝os and Havel [15] among others that Q 2k+1 (k, k + 1) is Hamiltonian. Recently, Mütze [32] showed that the middle layer cube Q 2k+1 (k
Data Loading...
