Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > CARLOS SUBI:
All reports by Author Carlos Subi:

TR08-087 | 31st July 2008
Tomas Feder, Carlos Subi

Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised)

It has been shown that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching
$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove a generalization of a special case of ... more >>>


TR07-063 | 2nd July 2007
Tomas Feder, Carlos Subi

Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations

We conjecture that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$
such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove this conjecture in the case where there are
two dimensions ... more >>>


TR06-016 | 1st February 2006
Tomas Feder, Carlos Subi

Partition into $k$-vertex subgraphs of $k$-partite graphs

The $H$-matching problem asks to partition the vertices of an input graph $G$
into sets of size $k=|V(H)|$, each of which induces a subgraph of $G$
isomorphic to $H$. The $H$-matching problem has been classified as polynomial
or NP-complete depending on whether $k\leq 2$ or not. We consider a variant
more >>>


TR06-015 | 1st February 2006
Tomas Feder, Carlos Subi

On Barnette's conjecture

Barnette's conjecture is the statement that every 3-connected cubic
planar bipartite graph is Hamiltonian. Goodey showed that the conjecture
holds when all faces of the graph have either 4 or 6 sides. We
generalize Goodey's result by showing that when the faces of such a
graph are 3-colored, with adjacent ... more >>>




ISSN 1433-8092 | Imprint