Question:
are there any known examples of $k$-regular graphs that have no regular $f$-faktor, $1\le f\lt k;\ k\ge 3$, resp., can their existence or nonexistence be proved?
$\begingroup$
$\endgroup$
4
asked Dec 3, 2021 at 11:09
-
1$\begingroup$ For the record: If $k$ and $f$ are even then it does not exist $\endgroup$– Fedor PetrovCommented Dec 4, 2021 at 12:04
-
1$\begingroup$ If $k$ is odd, take a graph $G$ on $k+2$ vertices whose complement has degree sequence $2,1,...,1$. Take $k$ copies of $G$ and another vertex $u$ and join $u$ with vertices of degree $k-1$ in $G$. This graph does not have a non-trivial factor. $\endgroup$– Fedor PetrovCommented Dec 4, 2021 at 12:10
-
$\begingroup$ @FedorPetrov very nice; that construction may yield "irreducible instances" for vertex-cover heuristics for which regular graphs are hard, but in some cases the regular graph may be reduced by deleting the edges of an $f$-factor. $\endgroup$– Manfred WeisCommented Dec 4, 2021 at 14:33
-
1$\begingroup$ Finally, if $k$ is even but $f$ is odd, take any graph with odd number of vertices $\endgroup$– Fedor PetrovCommented Dec 4, 2021 at 19:13
Add a comment
|