On the rotation distance of graphs (Q1318800)

Let \(G\) be a simple undirected graph and suppose that \((x,y)\in E(G)\) and \((x,y')\not\in E(G)\). Then the rotation of \((x,y)\) about \(x\), denoted by \(r= (y,x,y')\) is the operation of removing \((x,y)\) and inserting \((x,y')\) as an edge. The resulting graph is denoted by \(G(r)\). A graph \(G\) can be rotated into a graph \(H\) if there is a rotation \(r\) of \(G\) such that \(G(r)\simeq H\). The rotation graph of all \((n,m)\)-graphs (i.e. all \(n\) vertex \(m\) edge graphs) has all nonisomorphic \((n,m)\)-graphs as vertices and two of its vertices \(G\) and \(H\) are adjacent if and only if \(G\) can be rotated into \(H\). The rotation distance \(\vartheta(G,H)\) is the distance between \(G\) and \(H\) in the rotation graph. The authors show that if \(G\) and \(H\) are \((n,m)\)-graphs, then \(\vartheta(G,H)\geq m- t_{\max}(G,H)\), where \(t_{\max}(G,H)\) is the maximum number of edges of a subgraph contained in both \(G\) and \(H\). They show that this lower bound is sharp by showing that equality holds for 2-regular graphs of order \(n\). The authors introduce the notion of rotation links to establish upper bounds on the rotation distance between two \((n,m)\)-graphs. They show that some of these bounds are sharp for certain special classes of graphs. The problem of determining which graphs are distance graphs remains open but the authors show that \(K_{3,3}\) and \(K_{2,p}\), \(p\geq 1\), are distance graphs. A rotation of a tree that does not disconnect the tree is called a tree rotation. The tree distance between two trees \(G\) and \(H\) is the minimum number of tree rotations needed to transform \(G\) into \(H\) and is denoted by \(\tau(G,H)\). The tree rotation graph for a fixed order is defined in the expected manner. Then \(\tau(G,H)\) is the distance between \(G\) and \(H\) in the tree rotation graph for the trees of order \(| V(G)|\). The authors show that the tree rotation distance can exceed the rotation distance but that \(\tau(G,H)\leq 2\vartheta(G,H)\) for two trees \(G\) and \(H\) of the same order. The authors investigate certain extremal properties of tree rotation graphs. In particular, it is shown that the maximum degree in the tree rotation graph is between \(n(n-3)\) and \(37n^ 2/48- O(n\log n)\). They also prove that the maximum size \(p\) of an induced star satisfies \(2n- o(n)< p< 2n-2\). It is also shown that the diameter is \(n-3\) and the radius is \(n-o(n)\).