On the Upper Embeddability of Johnson Graphs for n>k≥2

Topological graph embeddings, particularly 2-cell embeddings, establish a fundamental link between graph theory and surface topology. For a connected graph G, the minimum genus γ(G) and maximum genus γ_M(G) are defined as the smallest and largest genera of orientable surfaces admitting a 2-cell embedding of G, respectively. It is known that an upper bound for the maximum genus of a graph G is
γ_M(G)≤ ⌊β(G)/2⌋, where β(G) is the Betti number of G. A graph is said to be upper embeddable if this equality is achieved.

First, we introduce a lexicographic labeling of the vertices and edges of the Johnson graph J(n,k). Using this labeling, a spanning tree is constructed by sequentially adding edges while avoiding cycles. We prove that this spanning tree is a splitting tree, whose complement contains at most one component with an odd number of edges, and hence establish the upper embeddability of J(n,k) for all n>k≥2 through Jungerman’s characterization. Finally, by applying the classical upper bound in terms of the Betti number, we obtain an explicit formula for the maximum genus of J(n,k).

We prove that the Johnson graph J(n,k) is upper embeddable for all n>k≥2 by explicitly constructing a splitting tree. As a consequence, the maximum genus of J(n,k) is obtained as γ_M(J(n,k))≤ ⌊(k(n-k)-2)/(2k!)∏_{i=1}^{k-1}(n-i)⌋.

In this study, we establish the upper embeddability of the Johnson graph J(n,k) for all n>k≥2. Using an explicit splitting tree together with Jungerman’s characterization, we show that the maximum genus of J(n,k) attains the theoretical upper bound given by its Betti number. This leads to an exact formula for γ_M(J(n,k)).