TR-2011-07

Balanced generic circuits without long paths

Csaba Király, Ferenc Péterfalvi

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}

}