Path coverings with paths (Q2712592)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Path coverings with paths |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Path coverings with paths |
scientific article |
Statements
27 January 2002
0 references
path coverings
0 references
mixed graphs
0 references
Path coverings with paths (English)
0 references
The authors give two new proofs of a result by \textit{K. Heinrich}, \textit{D. Langdeau} and \textit{H. Verrall} [J. Comb. Des. 8, No. 2, 100-121 (2000; Zbl 0946.05022)] that provide necessary and sufficient conditions for the existence of a set \(S\) of 3-paths in \(K_n\) having the property the every 2-path in \(K_n\) lies in exactly one of the paths in \(S\). The authors then use these proofs to consider the case when \(n\equiv 3\pmod 4\) when no such exact covering is possible, and to solve the problem of covering \((k-1)\)-paths with \(k\) paths for all \(k\geq 3\). One of the proofs uses mixed graphs, that is graphs that contain both oriented and non-oriented edges. The other uses an algebraic approach.
0 references
