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$
8
  • $\begingroup$ Is $G$ an honest graph? If it is a multigraph as well, this may be impossible. $\endgroup$ Mar 21, 2014 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, 2014 at 10:37
  • $\begingroup$ yes you are right. $G$ should be a simple (or honest) graph $\endgroup$ Mar 21, 2014 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$ Mar 21, 2014 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$ Apr 5, 2014 at 7:20

2 Answers 2

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$
1
  • $\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$ Mar 21, 2014 at 16:56

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.