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

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

1 Answer 1

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .