0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Wolfgang Nov 30 '15 at 9:18
  • $\begingroup$ 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? $\endgroup$ – Wolfgang Nov 30 '15 at 9:34
  • $\begingroup$ You are right - sorry! $\endgroup$ – Dominic van der Zypen Nov 30 '15 at 9:37
  • $\begingroup$ Sorry again for my notational slip-up... hope the question makes more sense now $\endgroup$ – Dominic van der Zypen Nov 30 '15 at 14:09
  • $\begingroup$ 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?) $\endgroup$ – Wolfgang Nov 30 '15 at 14:21
2
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Dominic van der Zypen Nov 30 '15 at 14:46
  • 1
    $\begingroup$ No, $c(n)=n$ for all $n>2$. $\endgroup$ – Fedor Petrov Nov 30 '15 at 15:05
  • $\begingroup$ Doesn't condition 3 rule out "non-adjacent cliques"? $\endgroup$ – Dima Pasechnik Nov 30 '15 at 15:11
  • $\begingroup$ Dima, I mean cliques whose edges in the cycle are not adjacent. $\endgroup$ – Fedor Petrov Nov 30 '15 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.