In this paper we study domination number of Johnson graphs J (n, r). We establish general bounds for the domination number of Johnson graph J(n, r) and prove that it is non-decreasing with n. We also compute exact values for γ(J(n, r)) in specific cases, showing that γ(J(n,2)) = ⌊n/2⌋ for n ≥ 4, and we determine γ(J(n , 3)) for even n ≥ 6, which depends quadratically on n. For odd n ≥ 7, we provide an upper bound for γ(J(n , 3)), which we conjecture to be tight. Our approach relies on translating the problem of computing γ(J(n , 3)) into the problem of finding a minimum edge covering by triangles among all graphs of order n with independence number at most 2.

The rotation distance between two search trees on a graph G is defined as the minimum number of rotations required to transform one tree into the other. A central problem in this context is to determine the maximum rotation distance between any pair of search trees on G , which corresponds to finding the diameter of the rotation graph R(G) , or equivalently, the combinatorial diameter of the graph associahedron of G . In this article, we establish a relationship between the structure of H ( G) and H ( G - S ) for a specific subset S of edges of G . More precisely, we show that if W is a set of true twins in G , and S consists of all edges in G with both endpoints in W , then H ( G - S) is a quotient graph of R(G) . Our main result provides a lower bound for diam( R ( G - S)) in terms of diam( R ( G )). We apply this result to determine the diameter of rotation graphs of general windmill graphs. Furthermore, we improve the known bound for the diameter of graph associahedra of balanced complete bipartite graphs.

In this article we contribute to the analysis of the spectral properties of graph associahedra, providing a lower bound for the second largest eigenvalue of the graph associahedra A(G) of G. Additionally, using equitable partitions, we analyze the spectrum of stellohedra A ( K 1 , n ) , proving the existence of an eigenvalue in the interval (n - 2, n - 1] and identifying two additional small eigenvalues.

For k ≥ 1 and n ≥ 2k, the well known Kneser graph KG(n, k) has all k-element subsets of an n-element set as vertices; two such subsets are adjacent if they are disjoint. Schrijver constructed a vertex-critical subgraph SG(n, k) of KG(n, k) with the same chromatic number. In this paper, we compute the diameter of the graph SG(2k + r,k) with r ≥ 1. We obtain that the diameter of SG(2k + r, k) is equal to 2 if r ≥ 2k - 2; 3 if k≥ - 2 ≤ r ≤ 2k - 3; k if r = 1; and for 2 ≤ r ≤ k - 3, we obtain that the diameter of SG(2k + r, k) is at most equal to k - r + 1.