# Maximal induced cycles on $n$-clique graphs

For any set $X$ we set $[X]^2 = \big\{\{a,b\}: a, b\in X\text{ and } a\neq b\big\}$.

We say a simple undirected graph $G=(V,E)$ is an $n$-clique graph if there are $S_1,\ldots,S_n\subseteq V$ such that

1. $|S_k| = n$ for all $k=1,\ldots, n$;
2. $V = \bigcup_{k=1}^n S_k$;
3. $i\neq k \in \{1,\ldots,n\}$ implies $|S_i \cap S_k| = 1$.
4. $E = \bigcup_{k=1}^n [S_k]^2$ (that is, all the $S_k$ are complete, and there are no edges between different $S_k$.)

Let $c(n)$ be the maximum length of an induced cycle that any $n$-clique graph $G$ can have. Is there an explicit formula for $c(n)$, and if not, what is $\lim_{n\to\infty}\frac{c(n)}{n}$?

• If you take any graph with $n$ vertices, add a vertex on each edge and replace each vertex $v$ of the original graph with a clique $K_d$ (connecting the new vertices adjacent to it, where $d$ is the degree of $v$), isn't the result exactly an $n$-clique graph? And so its induced cycles correspond 1-1 to those of the original graph? – Wolfgang Nov 30 '15 at 9:18
• In fact, I missed condition 2 which implies that all cliques have same size and thus the clique graph of $G$ (i.e. the "original" graph of my comment) must be a complete graph. Which means the problem is trivial, c(n)=3 for all n. Am I missing something? – Wolfgang Nov 30 '15 at 9:34
• You are right - sorry! – Dominic van der Zypen Nov 30 '15 at 9:37
• Sorry again for my notational slip-up... hope the question makes more sense now – Dominic van der Zypen Nov 30 '15 at 14:09
• For me it doesn't, sorry. Your condition 3 (was 2 before) should be removed, maybe. Or can you provide an example of a non trivial n-clique graph as you are imagining it? (and is it on purpose that the new condition 1 uses the same n as cardinality?) – Wolfgang Nov 30 '15 at 14:21

I am not sure that I understand all conditions correctly, since the question looks too straightforward, but if yes, then there are no cycles for $n\leq 2$ and for $n>2$ I claim that $c(n)=n$.
At first, $c(n)\leq n$. Indeed, no two edges of our cycle $x_1\dots x_{c(n)}x_1$ may belong to the same clique (if $c(n)\geq n+1\geq 4$), else the cycle is not induced.
Example of induced cycle $1\dots n$ of length $n$: $S_i$ contains vertices $i,i+1$ (modulo $n$, of course), and $n-2$ vertices $v_{i,j}$, $j\in \{1,\dots,n\}\setminus \{i+1,i-1\}$.
• Not sure if I understand your answer correctly... So you say $c(n) = 3$ for all $n$? And could you indicate which condition is unclear so that I can write it more clearly, please? Thanks! – Dominic van der Zypen Nov 30 '15 at 14:46
• No, $c(n)=n$ for all $n>2$. – Fedor Petrov Nov 30 '15 at 15:05