Timeline for Do the windmills $K_5^{(3)}$ and $K_5^{(4)}$ admit graceful labellings?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2022 at 13:01 | vote | accept | Rebecca J. Stones | ||
| Jun 15, 2022 at 6:25 | comment | added | Brendan McKay | @hoboonsuan Thanks, that saves me some computing time. I have $K_5^{(4)}$ down to 20 seconds and wonder if $K_5^{(6)}$ is plausible. | |
| Jun 15, 2022 at 5:42 | comment | added | ho boon suan | @BrendanMcKay By Bosák's result in my answer, $K_5^{(2j+1)}$ for $j\ge0$ is ungraceful. | |
| Jun 15, 2022 at 5:37 | comment | added | Brendan McKay | Actually, 2 seconds and 2 minutes once I realized that the reverse of a labelling is also a labelling. Now I wonder about $K_5^{(5)}$ — is anything known. | |
| Jun 15, 2022 at 5:09 | comment | added | Brendan McKay | My little C program says that neither $K_5^{(3)}$ nor $K_5^{(4)}$ have graceful labellings. It took 3 seconds and 4 minutes, respectively. This confirms Mikhail's result so I think this is sufficient verification. | |
| Jun 15, 2022 at 2:45 | answer | added | ho boon suan | timeline score: 7 | |
| Jun 15, 2022 at 1:10 | comment | added | Timothy Chow | I'd expect that a SAT solver should be able to confirm the nonexistence of a graceful labeling in these two cases. Introduce Boolean variables $x_{ij}$ to indicate that vertex $i$ gets label $j$ and Boolean variables $y_{ij}$ to indicate that edge $i$ gets label $j$. It is not hard to write down all the necessary constraints as SAT clauses. I'd also recommend adding a few symmetry-breaking constraints to speed up the computation. | |
| Jun 14, 2022 at 23:13 | history | edited | Rebecca J. Stones | CC BY-SA 4.0 |
deleted 113 characters in body
|
| Jun 14, 2022 at 23:02 | history | edited | Rebecca J. Stones | CC BY-SA 4.0 |
added 156 characters in body
|
| Jun 14, 2022 at 21:57 | history | edited | Rebecca J. Stones | CC BY-SA 4.0 |
added 172 characters in body
|
| Jun 14, 2022 at 21:28 | history | edited | Rebecca J. Stones | CC BY-SA 4.0 |
added 151 characters in body
|
| Jun 14, 2022 at 21:08 | history | edited | Rebecca J. Stones | CC BY-SA 4.0 |
added 101 characters in body
|
| Jun 14, 2022 at 12:05 | comment | added | Mikhail Tikhomirov | My brute-force wasn't able to find a labelling for any of the two. | |
| Jun 14, 2022 at 11:53 | history | edited | Rebecca J. Stones | CC BY-SA 4.0 |
edited body
|
| Jun 14, 2022 at 11:45 | history | edited | Rebecca J. Stones | CC BY-SA 4.0 |
added 44 characters in body
|
| Jun 14, 2022 at 11:37 | history | asked | Rebecca J. Stones | CC BY-SA 4.0 |