The complexity of P4-decomposition of regular graphs and multigraphs
Ajit A. Diwan, Justine E. Dion, David J. Mendell, Michael J. Plantholt, Shailesh K. Tipnis
Abstract
Let G denote a multigraph with edge set
E(G), let µ(G) denote the maximum edge
multiplicity in G, and let Pk
denote the path on k vertices. Heinrich et al.(1999)
showed that P4 decomposes a connected
4-regular graph G if and only if |E(G)| is
divisible by 3. We show that P4 decomposes a
connected 4-regular multigraph G with µ(G)
≤2 if and only if no 3 vertices of G
induce more than 4 edges and |E(G)| is divisible by
3. Oksimets (2003) proved that for all integers k
≥3, P4 decomposes a connected
2k-regular graph G if and only if
|E(G)| is divisible by 3. We prove that for all integers
k ≥2, the problem of determining if
P4 decomposes a (2k + 1)-regular
graph is NP-Complete. El-Zanati et al.(2014) showed that for all
integers k ≥1, every 6k-regular
multigraph with µ(G) ≤2k has a
P4-decomposition. We show that unless P = NP,
this result is best possible with respect to µ(G)
by proving that for all integers k ≥3 the problem
of determining if P4 decomposes a
2k-regular multigraph with µ(G)
≤⌊2k / 3 ⌋+ 1 is NP-Complete.
Full Text: PDF