A note on periodicity of the 2-distance operator (Q2725190)

Let \(\varphi \) be a graph operator defined on the class \(C_{f}\) of all finite undirected graphs. A graph \(G\in C_{f}\) is said to be \(\varphi \)-periodic if there exists a positive integer \(r\) such that \(\varphi ^{r}(G)\cong G\); the minimum \(r\) with this property is called the periodicity of \(G\) in the operator \(\varphi \). For each integer \(k\geq 2\) the \(k\)-distance operator on \(C_f\), denoted \(T_{k}\), is defined as follows: \(T_{k}(G)\) has the same vertex set as \(G\) and two distinct vertices are adjacent in \(T_{k}(G)\) if and only if their distance in \(G\) is \(k\). NEWLINENEWLINENEWLINEIn this paper it is shown that for every even positive integer \(r\) there exists a graph \(G\) whose periodicity in the operator \(T_{2}\) is \(r\). This solves a problem raised by E. Prisner concerning the existence of periods greater than 2 for \(T_{2}\). Also, if \(G\) is a graph such that \(\text{diam }G= \text{diam }\overline{G}=2\) and \(\overline{G}\not\cong G\) then \(G\) is \(T_{2}\)-periodic with periodicity 2. A class of graphs \(G\) such that \(\text{diam }G= \text{diam }\overline{G}=2\) is described.