Timeline for $(k,n)$-binary graphs
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 3, 2018 at 0:01 | vote | accept | Dominic van der Zypen | ||
| Oct 2, 2018 at 16:21 | comment | added | Gerhard Paseman | No biggie. You might observe that F and G have Hamiltonian cycles (sort of) which I think lead to a quick proof of longest path, or at least a good lower bound. Gerhard "Prefers Easy Arguments This Morning" Paseman, 2018.10.02. | |
| Oct 2, 2018 at 16:14 | comment | added | Philipp Lampe | @GerhardPaseman Sorry, when writing the answer I had not really noticed your second comment that an easy parity argument works for all even $k$. So I have made the answer CW and added the remark about even $k$. | |
| Oct 2, 2018 at 16:09 | history | edited | Philipp Lampe | CC BY-SA 4.0 |
Added discussion for general $k$; made community wiki. ; Post Made Community Wiki
|
| Oct 2, 2018 at 16:06 | comment | added | Gerhard Paseman | Never mind. Let F be the subset with an even number of zeros and G a component with an odd number of zeros. F and G are connected components, and F is connected to G iff k is odd. I think the longest path can be found by an appropriate traversal of F and G. Gerhard "Coffee Not Working Fast Today" Paseman, 2018.10.02. | |
| Oct 2, 2018 at 16:00 | comment | added | Gerhard Paseman | Can you confirm my conjecture above about even k? Gerhard "Almost Sure It Is Obvious" Paseman, 2018.10.02. | |
| Oct 2, 2018 at 15:57 | history | answered | Philipp Lampe | CC BY-SA 4.0 |