Graph automorphisms with maximal projection distances
An automorphism \(\pi \) of a graph \(G\) such that for every vertex \(v\), \(d(v,\pi.v)=d(G)\), (the diameter of \(G\)), is called a diametrical automorphism of \(G\). A graph with such an automorphism is called a DA graph. A related notion is that of a \(k\)-distance lower bound or \(\text{dl}_{k}\) automorphism \(\pi \) such that \(d(v,\pi.v)\geq k\) for all vertices \(v\). The authors consider the cycle structure of \(\text{dl}_{k}\) graphs and obtain easy lower and upper bounds for the number of edges of a DA graph and conjecture a tight upper bound. They prove that recognizing DA graphs is NP-complete by reducing the fixed-point-free automorphism problem to the DA problem. A similar result is proved for \(\text{dl}_{k}\) graphs. They then obtain a \(O(|V|+ |E|)\)-time algorithm for recognizing whether a cograph \(G\) is DA, using the structure of the cotree \(T_{G}\) of \(G\). Lastly, an \(O(|V|^{2})\)-time algorithm is obtained for recognizing whether a circular arc graph is DA, using a normalized intersection model of such a graph. For the entire collection see [Zbl 0921.00033].
This page was built for publication: Graph automorphisms with maximal projection distances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4934329)
