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:

AUTHOR = {Kir{\'a}ly, Csaba and P{\'e}terfalvi, Ferenc},
TITLE = {Balanced generic circuits without long paths},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2011},
NUMBER = {TR-2011-07}

Last modification: 26.9.2017. Please email your comments to Tamás Király!