Published in:
Discrete Mathematics Volume 312, Issue 15, 6 August 2012, Pages 2262-2271
We call a graph $G=(V,E)$ a \emph{$(k,\ell)$-circuit} if $|E|=k|V|-\ell+1$ and every $X \subset V$ with $2 \leq |X| \leq |V|-1$ satisfies $i(X) \leq k|X|-\ell$. A $(2,3)$-circuit is also called a \emph{generic circuit}. We say that a graph is \emph{balanced} if the difference between its maximum and minimum degree is at most $1$. J.~Graver, B.~Servatius and H.~Servatius asked in \cite{graver} whether a balanced generic circuit always admits a decomposition into two disjoint Hamiltonian paths. We show that this does not hold, moreover there are balanced $(k,k+1)$-circuits for all $k \geq 2$ which do not contain any Hamiltonian path nor a path longer than $|V|^\lambda$ for $\lambda > \frac{\log 8}{\log 9} \simeq 0,9464$.
Bibtex entry:
@techreport{egres-11-07,
AUTHOR | = | {Kir{\'a}ly, Csaba and P{\'e}terfalvi, Ferenc}, |
TITLE | = | {Balanced generic circuits without long paths}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2011}, |
NUMBER | = | {TR-2011-07} |