Packing non-zero \(A\)-paths in group-labelled graphs (Q879161): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:27, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Packing non-zero \(A\)-paths in group-labelled graphs |
scientific article |
Statements
Packing non-zero \(A\)-paths in group-labelled graphs (English)
0 references
8 May 2007
0 references
Let \(G=(V,E)\) be an oriented graph whose edges are labelled by the elements of a group \(\Gamma\) and let \(A\subseteq V\). An \(A\)-path is a path whose ends are both in \(A\). The weight of a path \(P\) in \(G\) is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in \(P\). (If \(\Gamma\) is not abelian, we sum the labels in their order along the path.) The authors give a connection of this problem to some other problems studied in the literature. The authors prove that for any integer \(k\), either there are \(k\)-vertex-disjoint \(A\)-paths each of non-zero weight, or there is a set of at most \(2k-2\) vertices that meets each non-zero \(A\)-path.
0 references
packing non-zero paths
0 references
group-labelled graphs
0 references