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$
5
  • 2
    $\begingroup$ are you talking about vertex-induced cycles? disjoint cycles? $\endgroup$ Sep 27, 2013 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$ Sep 27, 2013 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$ Sep 27, 2013 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, 2013 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, 2013 at 6:23

2 Answers 2

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.

$\endgroup$
1
  • $\begingroup$ yes, you are right :) $\endgroup$
    – virgi
    Feb 4, 2014 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.
$\endgroup$

Your Answer

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

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