Longest induced cycles in circulant graphs (Q2571295)

The only circulant graphs considered in this paper are the circulant graphs \( X_n = \text{Cay}(Z_n,Z_n^*) \) whose generating set is the set of units of \(Z_n\), \(Z_n^*\). The question of the size of the longest induced cycle in these graphs is addressed, and the author successfully improves on both the upper and lower bounds of \textit{P. Berrizbeitia} and \textit{R. E. Giudici} [Discrete Math. 282, 239--243 (2004; Zbl 1055.05087)]. Let \(m(n)\) denote the length of the longest induced cycle in \(X_n\), and let \( M(r) \) be the maximal \(m(n)\) over all \(n\) with \(r\) distinct prime divisors. The main result of the paper can be stated as follows: \(2^r + 2 \leq M(r) \leq 6r!\). While the improvement of the upper bound is a simple restatement of the original proof of Berrizbeitia and Giudici, the lower bound is obtained by using a clever construction based on a representation of the elements in \(Z_n\) via their residue classes modulo the distinct primes in the prime factorization of \(n\). This is based on the simple observation that two vertices \(x\) and \(y\) of \(X_n\) are adjacent if and only if \( x \not \equiv y \pmod{p} \) for all prime divisors \(p\) of \(n\). Based on this representation, the value \(M(r)\) is shown to be non-decreasing with increasing \(r\), and maybe a bit surprisingly, the value \(m(p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_r^{\alpha_r}) \) is shown to be equal to \(M(r)\) for all prime factorizations with sufficiently large primes \(p_i\), \( 1 \leq i \leq r \) (i.e., the powers of the primes in the prime factorization are shown not to add any extra length to the longest induced cycle in \(X_n\)). The cycle of length \(2^r+2\) needed for the lower bound is then constructed via a manipulation of the reflective Gray code. The paper concludes with several extensions of the results to some other classes of multipartite graphs. It should be noted that the long induced cycles constructed use only the three remainders \(0,1\) and \(2\). It appears likely that the presented construction could be altered further to produce induced cycles of even greater length.