Some remarks on the square graph of the hypercube - Mirafzal, Seyed Morteza (Ars mathematica contemporanea, 2023)
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 ?$Q_n$? ima določene zanimive lastnosti. Tako je npr. visoko simetričen in vsepovezan. V tem članku raziskujemo nekatere algebraične lastnosti grafa ?$Q^2_n$?. V prvi vrsti pokažemo, da je graf ?$Q^2_n$? 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 ?$Q^2_n$?. Nazadnje dokažemo: če je ?$n > 2$? sodo število, potem je ?$Q^2_n$? avtomorfen graf, kar pomeni, da je ?$Q^2_n$? razdaljno tranzitiven primitiven graf, ki ni ne polni ne povezavni graf.
Keywords: automorphic graph; automorphism group; avtomorfni graf; distance-transitive graph; grupa avtomorfizmov; hiperkocka; hypercube; Johnson graph; Johnsonov graf; kvadrat grafa; razdaljno tranzitiven graf; square of a graph