4
$\begingroup$

Let "$k$-necklace" denote the (multi)graph obtained from a cycle of length $k$ by duplicating every edge.

Note that the number of cycles in $k$-necklace is at least $2^k.$

Question : Suppose a simple graph $G$ contains at least $n^k$ cycles where $n$ is the number of vertices of $G$. Is it possible to obtain a $\Omega(k)$-necklace from $G$ by a sequence of deletion and contraction of edges?

I would be equally happy if one can guarantee $\sqrt k$-necklace (or $k^\alpha$ necklace for some $\alpha > 0$) instead of $k$-necklace.

$\endgroup$
  • $\begingroup$ Is $G$ an honest graph? If it is a multigraph as well, this may be impossible. $\endgroup$ – Alex Degtyarev Mar 21 '14 at 9:59
  • $\begingroup$ If you take a tree with $n$ vertices and duplicate a single edge $n^k$ times, then there are $\binom{n^k}{2}$ cycles, but no $k$-necklace minors (provided $k \geq 3$). $\endgroup$ – Tony Huynh Mar 21 '14 at 10:37
  • $\begingroup$ yes you are right. $G$ should be a simple (or honest) graph $\endgroup$ – Raghav Kulkarni Mar 21 '14 at 16:50
  • $\begingroup$ Don't cycles of length 2 count? In which case a k-necklace contains more than 2^k cycles for k>2. Gerhard "Ask Me About System Design" Paseman, 2014.03.21 $\endgroup$ – Gerhard Paseman Mar 21 '14 at 17:41
  • 1
    $\begingroup$ @Zsbán Ambrus: $n$ is the number of vertices, so it is not possible to have $2^n$ components. Raghav: I haven't been able to solve your problem, but I found it interesting enough to make a blog post about it: see 11011110.livejournal.com/286355.html $\endgroup$ – David Eppstein Apr 5 '14 at 7:20
2
$\begingroup$

I believe Anton Malyshev's answer to Do graphs with large number of paths contain large chain minor? answers this question as well. It is a bipartite planar permutation graph in which there are $n/2$ pairs of vertices $u_i$ and $v_i$, with edges from both $u_i$ and $v_i$ to $u_{i+1}$ and $v_{i+1}$ but not to each other. It contains large chain minors (paths with each edge doubled), but its cycle minors can have at most four doubled edges, two each at their minimum and maximum indices. Its number of cycles is $\Theta(2^{n/2})=n^{\Theta(n/\log n)}$.

Here is a drawing of the graph:

Malyshev's bipartite planar permutation graph

To form a cycle in it, start at one of the outer blue vertices, then at each step, extend two ends of a path (generally in one of two ways) to the two vertices at the next level inward, closing off the cycle at one of the inner two blue vertices. Or do the same thing starting and ending somewhere in the middle instead of the outside and the center, allowing the vertices and edges farther out to be used to double some of the edges in the minor.

$\endgroup$
1
$\begingroup$

If $G$ is a simple graph then this can fail for small $n$ (for $\alpha=1$). A $k$-necklace can only be a minor of a graph $G$ if $G$ has at least $3k/2$ vertices (as one vertex-identification can be responsible for at most two of the doubled edges in the necklace). But the complete graph on $4k/3$ vertices has more than $(4k/3)^k$ cycles.

$\endgroup$
  • $\begingroup$ yes, you are correct. the exact bound does not hold. I would like asymptotic bound, i.e., $\Omega(k)$-necklace (or $\sqrt k$ or anything polynomial in $k$) $\endgroup$ – Raghav Kulkarni Mar 21 '14 at 16:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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