Timeline for Regular graphs without non-trivial $f$-factor
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 4, 2021 at 19:13 | comment | added | Fedor Petrov | Finally, if $k$ is even but $f$ is odd, take any graph with odd number of vertices | |
| Dec 4, 2021 at 14:33 | comment | added | Manfred Weis | @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. | |
| Dec 4, 2021 at 12:10 | comment | added | Fedor Petrov | 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. | |
| Dec 4, 2021 at 12:04 | comment | added | Fedor Petrov | For the record: If $k$ and $f$ are even then it does not exist | |
| Dec 4, 2021 at 11:18 | history | edited | Manfred Weis | CC BY-SA 4.0 |
fixed an inequality direction
|
| Dec 3, 2021 at 11:09 | history | asked | Manfred Weis | CC BY-SA 4.0 |