Timeline for Existence of a 2-labelled Hamiltonian Path decomposition of $K_{2n}$
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 13:27 | vote | accept | Alice J. | ||
| Apr 13, 2017 at 13:09 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 30 characters in body; edited tags
|
| Apr 13, 2017 at 13:06 | comment | added | Alice J. | @bof It's not really that I add it, it is that it can not be otherwise. In $K_{2n}$ every vertex has degree $2n-1$ so that if you decompose your graph into $n$ paths, every vertex will play the role of a degree 2 vertex $n-1$ times, and the role of an extremity once. Now if the two extremities had the same label, only the vertices with the same label would be able to play the role of an extremity so it wouldn't be possible. | |
| Apr 13, 2017 at 12:57 | answer | added | monkeymaths | timeline score: 4 | |
| Apr 13, 2017 at 12:54 | comment | added | bof | Do you mean that the condition "the extremities of a path must have distinct labels" should be added to the conditions stated in your post? | |
| Apr 13, 2017 at 12:29 | comment | added | Alice J. | @bof It is necessary : since every vertex is going to play the role of an extremity exactly once, the extrimities must have distinct label, and each of them is represented exactly $n$ times, so each of the two labels is present n times. | |
| Apr 13, 2017 at 12:27 | comment | added | Alice J. | @monkeymaths Indeed, sorry, I am imposing that there are exactly two distinct labels, so not just a's or b's. | |
| Apr 13, 2017 at 11:51 | comment | added | bof | Is it just happenstance that in your example there are just as many $a$'s as $b$'s or is that a requirement? | |
| Apr 13, 2017 at 11:43 | comment | added | monkeymaths | Do you impose any restriction on the labelling? Unless I missed something, you could always just assign the same label 'a' to every vertex... ? | |
| Apr 13, 2017 at 11:08 | history | asked | Alice J. | CC BY-SA 3.0 |