Skip to main content
2 of 2
added 42 characters in body

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}$?