Let Γ be an abelian group, and let γ : E (G) → Γ be a function assigning values in Γ to every edge of a graph G. For a subgraph H of G, let γ (H) = ∑e ∈ E (H) γ (e). For a set A of vertices of G, an A-path is a path with both endpoints in A and otherwise disjoint from A. In this article, we show that either there exist k vertex disjoint A-paths P1, P2, ..., Pk such that γ (Pi) ≠ 0 for all 1 ≤ i ≤ k, or there exists a set X of vertices such that G - X does not contain a non-zero A-path with | X | ≤ 50 k4. © 2009 Elsevier Inc. All rights reserved.
Packing non-zero A-paths in an undirected model of group labeled graphs / Wollan, PAUL JOSEPH. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - 100:2(2010), pp. 141-150. [10.1016/j.jctb.2009.05.003]
Packing non-zero A-paths in an undirected model of group labeled graphs
WOLLAN, PAUL JOSEPH
2010
Abstract
Let Γ be an abelian group, and let γ : E (G) → Γ be a function assigning values in Γ to every edge of a graph G. For a subgraph H of G, let γ (H) = ∑e ∈ E (H) γ (e). For a set A of vertices of G, an A-path is a path with both endpoints in A and otherwise disjoint from A. In this article, we show that either there exist k vertex disjoint A-paths P1, P2, ..., Pk such that γ (Pi) ≠ 0 for all 1 ≤ i ≤ k, or there exists a set X of vertices such that G - X does not contain a non-zero A-path with | X | ≤ 50 k4. © 2009 Elsevier Inc. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
