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$
11
  • $\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, 2015 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, 2015 at 9:34
  • $\begingroup$ You are right - sorry! $\endgroup$ Nov 30, 2015 at 9:37
  • $\begingroup$ Sorry again for my notational slip-up... hope the question makes more sense now $\endgroup$ Nov 30, 2015 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, 2015 at 14:21

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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