Timeline for Regular graphs with $a$ and $b$ Hamiltonian edges
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 10, 2014 at 10:21 | vote | accept | joro | ||
| Jan 6, 2014 at 12:46 | comment | added | joro | @Wolfgang I wrote "compared to a' edges", maybe not very clear. Since 1 > 0 this is enough for rho=1 in the example. | |
| Jan 6, 2014 at 12:34 | comment | added | Wolfgang | I agree. It was just your sentence "The gadget contains sufficiently many b′ edges" that puzzled me. Each copy of the gadget contains just 1... | |
| Jan 6, 2014 at 11:08 | comment | added | joro | @Wolfgang I can give you explicit the smaller graph of GA_5. The b' edge is (2,5) and it is on NO H-path between degree 4 vertices. 2 copies of GA_5 give two b edges and introduce two a edges, giving rho=1 (there are no a' edges). Certainly 2-connected are much easier. | |
| Jan 6, 2014 at 10:51 | comment | added | Wolfgang | RE: gadget. I understand the uv H-paths (equivalently H-cycles containing the edge uv=52). But I have a hard time finding your "sufficiently many b′ edges". As far as I see, each edge occurs in some uv H-path. The only b edges in the construction may be the uv of each gadget. Is that what you mean? RE: last graph. Thank you. For 2-connected graphs it is indeed easy to guarantee a-edges. BTW I think similar constructions taking as gadget the Meredith graph with one or two edges removed should also work and have higher connectivity, but it is somewhat messy to check by hand. | |
| Jan 6, 2014 at 6:05 | comment | added | joro | @Wolfgang The last graph with rho=2: [(0, 4), (0, 6), (0, 7), (0, 11), (1, 5), (1, 8), (1, 9), (1, 10), (2, 6), (2, 7), (2, 10), (2, 15), (3, 8), (3, 9), (3, 10), (3, 14), (4, 8), (4, 9), (4, 11), (5, 8), (5, 9), (5, 10), (6, 7), (6, 11), (7, 11), (12, 16), (12, 18), (12, 19), (12, 23), (13, 17), (13, 20), (13, 21), (13, 22), (14, 18), (14, 19), (14, 22), (15, 20), (15, 21), (15, 22), (16, 20), (16, 21), (16, 23), (17, 20), (17, 21), (17, 22), (18, 19), (18, 23), (19, 23)] | |
| Jan 6, 2014 at 5:58 | comment | added | joro | @Wolfgang I dropped 3-connectivity indeed. RE: gadget. I believe nvcleemp verified the graphs. The gadget works with $u,v$ H-paths, not with H-cycles. The gadget has 2 additional edges to the low degree vertices, one enters it and one leaves. Necessary condition for a cycle is a H-path in the gadget. The edges of the graph soon. | |
| Jan 5, 2014 at 21:17 | comment | added | Wolfgang | Also I try to understand your $GA_5$. Take the H-cycle 073164250 as octogon with 52 on top, then the graph has a vertical axis of symmetry. The H-cycles 036175240 and 074623150 + their reflected ones show that there are no a and b edges. So there are no $a'$ and $b'$ edges either. ??? | |
| Jan 5, 2014 at 16:55 | comment | added | Wolfgang | Can you provide the last graph in standard form, please? | |
| Dec 30, 2013 at 7:35 | history | edited | joro | CC BY-SA 3.0 |
Added rho=2
|
| Dec 29, 2013 at 15:27 | history | answered | joro | CC BY-SA 3.0 |