Packing k-edge Trees in Graphs of Restricted Vertex Degrees
| dc.creator | Kelmans, Alexander | |
| dc.date | 2006-10-11 | |
| dc.date.accessioned | 2026-07-07T07:28:59Z | |
| dc.date.available | 2026-07-07T07:28:59Z | |
| dc.description | Let v(G) be the number of vertices and t(G,k) the maximum number of disjoint k-edge trees in G. In this paper we show that (a1) if G is a graph with every vertex of degree at least two and at most s, where s > 3, then t(G,2) is at least v(G)/(s+1), (a2) if G is a graph with every vertex of degree at least two and at most 3 and G has no 5-vertex components, then t(G,2) is at least v(G)/4, (a3) if G is a graph with every vertex of degree at least one and at most s and G has no k--vertex component, where k >1 and s > 2, then t(G,k) is at least (v(G) - k)/(sk - k +1), and (a4) the above bounds are attained for infinitely many connected graphs. Our proofs provide polynomial time algorithms for finding the corresponding packings in a graph. Keywords: subgraph packing, 2-edge and k-edge paths, k-edge trees, polynomial time approximation algorithms. | |
| dc.description | 14 pages | |
| dc.identifier | https://arxiv.org/abs/math/0610384 | |
| dc.identifier | http://arxiv.org/abs/math/0610384 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/117933 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C10 | |
| dc.title | Packing k-edge Trees in Graphs of Restricted Vertex Degrees | |
| dc.type | text |