Ajit Diwan ; Justine Dion ; David Mendell ; Michael Plantholt ; Shailesh Tipnis - The complexity of $P$<sub>4</sub>-decomposition of regular graphs and multigraphs

dmtcs:2128 - Discrete Mathematics & Theoretical Computer Science, September 9, 2015, Vol. 17 no.2 - https://doi.org/10.46298/dmtcs.2128
The complexity of $P$<sub>4</sub>-decomposition of regular graphs and multigraphsArticle

Authors: Ajit Diwan 1; Justine Dion 2; David Mendell 2; Michael Plantholt 2; Shailesh Tipnis 2

  • 1 Department of Computer Science and Engineering [Bombay]
  • 2 Department of Mathematics, Illinois State University

Let G denote a multigraph with edge set E(G), let &micro;(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 &micro;(G) &#x2264;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 &#x2265;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 &#x2265;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 &#x2265;1, every 6k-regular multigraph with &micro;(G) &#x2264;2k has a P4-decomposition. We show that unless P = NP, this result is best possible with respect to &micro;(G) by proving that for all integers k &#x2265;3 the problem of determining if P4 decomposes a 2k-regular multigraph with &micro;(G) &#x2264;&#x230A;2k&#8202;/&#8202;3 &#x230B;+ 1 is NP-Complete.


Volume: Vol. 17 no.2
Section: Graph Theory
Published on: September 9, 2015
Submitted on: August 27, 2014
Keywords: $P$<sub>4</sub>-decomposition,multigraphs,NP-complete,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 477 times.
This article's PDF has been downloaded 1164 times.