ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.06
https://doi.org/10.26493/1855-3974.2621.26f
(Also available at http://amc-journal.eu)
Some remarks on the square graph of the
hypercube
Seyed Morteza Mirafzal *
Department of Mathematics, Lorestan University, Khoramabad, Iran
Received 6 May 2021, accepted 26 June 2022, published online 18 November 2022
Abstract
Let Γ = (V,E) be a graph. The square graph Γ2 of the graph Γ is the graph with the
vertex set V (Γ2) = V in which two vertices are adjacent if and only if their distance in
Γ is at most two. The square graph of the hypercube Qn has some interesting properties.
For instance, it is highly symmetric and panconnected. In this paper, we investigate some
algebraic properties of the graph Q2n. In particular, we show that the graph Q
2
n is distance-
transitive. We show that the graph Q2n is an imprimitive distance-transitive graph if and
only if n is an odd integer. Also, we determine the spectrum of the graph Q2n. Finally, we
show that when n > 2 is an even integer, then Q2n is an automorphic graph, that is, Q
2
n is a
distance-transitive primitive graph which is not a complete or a line graph.
Keywords: Square of a graph, distance-transitive graph, hypercube, automorphism group, Johnson
graph, automorphic graph.
Math. Subj. Class. (2020): Primary 05C25, 94C15
*The author is thankful to the anonymous reviewers for their valuable comments and suggestions.
E-mail address: smortezamirafzal@yahoo.com (Seyed Morteza Mirafzal)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.06
https://doi.org/10.26493/1855-3974.2621.26f
(Dostopno tudi na http://amc-journal.eu)
Nekaj pripomb v zvezi s kvadratnim grafom
hiperkocke
Seyed Morteza Mirafzal *
Department of Mathematics, Lorestan University, Khoramabad, Iran
Prejeto 6. maja 2021, sprejeto 26. junija 2022, objavljeno na spletu 18. novembra 2022
Povzetek
Naj bo Γ = (V,E) graf. Kvadratni graf Γ2 grafa Γ je graf z množico vozlišč V (Γ2) =
V , v katerem sta dve vozlišči sosednji, če je njuna razdalja v grafu Γ največ dve. Kvadratni
graf hiperkocke Qn ima določene zanimive lastnosti. Tako je npr. visoko simetričen in vse-
povezan. V tem članku raziskujemo nekatere algebraične lastnosti grafa Q2n. V prvi vrsti
pokažemo, da je graf Q2n razdaljno tranzitiven. Dokažemo tudi, da je graf Q
2
n neprimitiven
razdaljno tranzitiven graf natanko takrat, ko je n sodo število. Določimo tudi spekter grafa
Q2n. Nazadnje dokažemo: če je n > 2 sodo število, potem je Q
2
n avtomorfen graf, kar
pomeni, da je Q2n razdaljno tranzitiven primitiven graf, ki ni ne polni ne povezavni graf.
Ključne besede: Kvadrat grafa, razdaljno tranzitiven graf, hiperkocka, grupa avtomorfizmov, John-
sonov graf, avtomorfni graf.
Math. Subj. Class. (2020): 05C25, 94C15
*Avtor se zahvaljuje neznanim recenzentom za njihove dragocene pripombe in predloge.
E-poštni naslov: smortezamirafzal@yahoo.com (Seyed Morteza Mirafzal)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/