Some remarks on the square graph of the hypercube

2021/01/05 by Mirafzal, S. Morteza · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.2101.01615

Abstract

Let Γ=(V,E) be a graph. The square graph Γ² of the graph Γ is the graph with the vertex set V(Γ²)=V in which two vertices are adjacent if and only if their distance in Γ is at most two. The square graph of the hypercube Q_n has some interesting properties. For instance, it is highly symmetric and panconnected. In this paper, we investigate some algebraic properties of the graph Q²_n. In particular, we show that the graph Q²_n is distance-transitive. We show that the graph Q²_n is an imprimitive distance-transitive graph if and only if n is an odd integer. Also, we determine the spectrum of the graph Q_n². Finally, we show that when n >2 is an even integer, then Q²_n is an automorphic graph, that is, Q_n² is a distance-transitive primitive graph which is not a complete or a line graph.

Cited by

• The distance spectrum of the bipartite double cover of strongly regular graphs
• The distance spectrum of the line graph of the crown graph

Related

• Cayley properties of the line graphs induced by consecutive layers of the hypercube
• Cycles and Paths Embedded in Varietal Hypercubes
• An extremal theorem in the hypercube
• Graphs 4_n that are isometrically embeddable in hypercubes
• The square of every subcubic planar graph of girth at least 6 is 7-choosable