3
$\begingroup$

Let $\Gamma$ be a finite simplicial graph. For every $k \geq 0$, let $C_k(\Gamma)$ denote the graph whose vertices are the induced cycles of $\Gamma$ and whose edges link two cycles if their intersection contains a path of length $k$. For instance, if $k=0$ one gets the intersection graph of the induced cycles of $\Gamma$.

Question: Suppose that $\mathrm{girth}(\Gamma) \geq 5$. Is it true that $C_3(\Gamma)$ is connected whenever $\Gamma$ does not contain a separating star?

Heuristically, it seems plausible that $C_k(\Gamma)$ should be connected if the minimal size of a connected separating subgraph of $\Gamma$ is "large" compared to $k$.

Remark 1: The question has a positive answer if the cycles in the definition of $C_k(\Gamma)$ are not required to be induced.

Remark 2: The condition on the girth in the question cannot be removed as can be seen from the case where $\Gamma$ is the one-skeleton on a $3$-cube.

$\endgroup$

0

Your Answer

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