Gerbner, Dániel and Keszegh, Balázs and Palmer, Cory and Patkós, Balázs (2017) On the number of cycles in a graph with restricted cycle lengths. SIAM JOURNAL ON DISCRETE MATHEMATICS. ISSN 08954801 (In Press)

Text
fewcyclessidma2.pdf Download (409kB)  Preview 
Abstract
Let $L$ be a set of positive integers. We call a (directed) graph $G$ an $L$\emph{cycle graph} if all cycle lengths in $G$ belong to $L$. Let $c(L,n)$ be the maximum number of cycles possible in an $n$vertex $L$cycle graph (we use $\vec{c}(L,n)$ for the number of cycles in directed graphs). In the undirected case we show that for any fixed set $L$, we have $c(L,n)=\Theta(n^{\lfloor k/\ell \rfloor})$ where $k$ is the largest element of $L$ and $2\ell$ is the smallest even element of $L$ (if $L$ contains only odd elements, then $c(L,n)=\Theta(n)$ holds.) We also give a characterization of $L$cycle graphs when $L$ is a single element. In the directed case we prove that for any fixed set $L$ we have $\vec{c}(L,n)=(1+o(1))(\frac{n1}{k1})^{k1}$, where $k$ is the largest element of $L$. We determine the exact value of $\vec{c}(\{k\},n)$ for every $k$ and characterize all graphs attaining this maximum.
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
Depositing User:  Balázs Patkós 
Date Deposited:  18 Sep 2017 14:26 
Last Modified:  18 Sep 2017 14:26 
URI:  http://real.mtak.hu/id/eprint/62816 
Actions (login required)
View Item 