Packing 3-vertex paths in cubic 3-connected graphs
| dc.creator | Kelmans, Alexander | |
| dc.date | 2008-01-08 | |
| dc.date.accessioned | 2026-07-07T08:53:17Z | |
| dc.date.available | 2026-07-07T08:53:17Z | |
| dc.description | Let v(G) and p(G) be the number of vertices and the maximum number of disjoint 3-vertex paths in G, respectively. We discuss the following old Problem: Is the following claim (P) true ? (P) if G is a 3-connected and cubic graph, then p(G) = [v(G)/3], where [v(G)/3] is the floor of v(G)/3. We show, in particular, that claim (P) is equivalent to some seemingly stronger claims. It follows that if claim (P) is true, then Reed's dominating graph conjecture (see [14]) is true for cubic 3-connected graphs. | |
| dc.description | 24 pages and 11 figures | |
| dc.identifier | https://arxiv.org/abs/0801.1239 | |
| dc.identifier | http://arxiv.org/abs/0801.1239 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/145569 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C10, 90C27 | |
| dc.title | Packing 3-vertex paths in cubic 3-connected graphs | |
| dc.type | text |