9
$\begingroup$

How many cycles $C_k$ $(k \geq 3)$ are there in a $n $ vertex graph such that graph doesn't have any cycle $C_m$ $(m>k)$.

For example $n=5$, $k=3$, then graph will have at most two $C_3$'s so that $G$ will not have any $C_k (k > 3).$

I am thinking that there are $O(n)$ cycles will be there satisfying above conditions.

Can some one help me out.

$\endgroup$
  • 2
    $\begingroup$ are you talking about vertex-induced cycles? disjoint cycles? $\endgroup$ – Igor Shinkar Sep 27 '13 at 10:29
  • 1
    $\begingroup$ The answer may depend on the parity of $m-k$. For example, consider a balanced blow-up of a 5-cycle. This graph contains no 6-cycles, but it contains $\Theta(n^5)$ induced 5-cycles. $\endgroup$ – Igor Shinkar Sep 27 '13 at 10:32
  • 5
    $\begingroup$ @IgorShinkar I read the question as "what is the maximum number of $k$-cycles in an $n$-vertex graph that has no $m$-cycle for any $m > k$?" so $m$ is not a parameter, it's universally quantified $\endgroup$ – Sasho Nikolov Sep 27 '13 at 12:07
  • $\begingroup$ I assume you're talking about induced cycles (holes). If you want the minimum number, it's surely 0, an empty graph. If you want the maximum number, it is n^3 for k=3 (consider a complete graph). $\endgroup$ – Yixin Cao Sep 28 '13 at 7:56
  • $\begingroup$ @YixinCao For k=3, If you consider a complete graph with 'n' vertices then we will have cycle whose length is more than 3. I am looking for maximum number cycles of length k in a graph such that graph shouldn't contain any cycle of length more than k $\endgroup$ – Kumar Sep 29 '13 at 6:23
5
$\begingroup$

It is not $O(n)$ unless $k=3$. For $k$ even, the maximum length of a cycle in the complete bipartite graph $K_{n,k/2}$ is $k$, and the number of length-$k$ cycles is $(\frac{k}{2}-1)! n^{k/2}=\Theta(n^{k/2})$. For instance, $K_{2,n}$ has a quadratic number of 4-cycles, but no cycles longer than 4.

On the other hand, for any constant bound $k$ on the length of the longest cycle, the number of triangles really is $O(n)$. Here's a quick proof: in a depth first search tree, each edge goes from the lower of its two endpoints to an ancestor at most $k-1$ steps back, so any leaf of the tree has degree at most $k-1$ and belongs to at most $\binom{k-1}{2}$ triangles. Now remove the leaf and induct.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yes, you are right :) $\endgroup$ – virgi Feb 4 '14 at 7:28
1
$\begingroup$

I wrote a short clingo program to check the small values (it can quickly handle graphs of up to 7 vertices. Beyond that, the grounding can take quite a while):

I got this table

                            n (vertices)
                         3   4   5   6   7

                      3  1   1   2   2   3

                      4      3   3   6  10

k (cycle length)      5         12  12  12

                      6             60  60

                      7                360

Here's the program:

num(1..n).
is_sym_order(empty,0).
ncontains(empty,K) :- num(K).
is_sym_order(cons(K,empty),1) :- num(K).
last(cons(K,empty), K) :- num(K).
is_sym_order(cons(K,S),M+1) :- is_sym_order(S,M), ncontains(S,K), last(S,L), K > L.
ncontains(cons(K,S), J) :- J != K, ncontains(S,J), is_sym_order(cons(K,S),_).
last(cons(K,S), L) :- last(S,L), is_sym_order(cons(K,S),_).
sec_last(cons(A,S),A) :- is_sym_order(cons(A,S),2).
sec_last(cons(K,S), SL) :- sec_last(S,SL), is_sym_order(cons(K,S),_).
is_sub_order(cons(A,S), M) :- A > SL, sec_last(S,SL), is_sym_order(cons(A,S), M).

vertex(1..n).
{is_edge(V,W)} :- vertex(V), vertex(W), V < W.
sym_edge(V,W;W,V) :- is_edge(V,W).

is_path(cons(V,empty)) :- vertex(V).

is_path(cons(A,cons(B,S))) :- is_path(cons(B,S)), sym_edge(A,B), is_sym_order(cons(A,cons(B,S)),_).
is_cycle(cons(A,S)) :- is_path(cons(A,S)), is_edge(V,A), last(S,V), is_sub_order(cons(A,S),M), M >= k.

:- is_cycle(S), is_sub_order(S,M), M > k.
prim_cycle(S) :- is_cycle(S), is_sub_order(S,k).
:~ not is_cycle(S), is_sub_order(S,k).[1,S]

num_cycs(C) :- C = #count{is_cycle(S):is_cycle(S)}.
#show is_edge/2.
#show num_cycs/1.
#show prim_cycle/1.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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