The complexity of $P$4-decomposition of regular graphs and multigraphs

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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.63-76
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01349042
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 26 juillet 2016 - 16:30:21
Dernière modification le : jeudi 7 septembre 2017 - 01:03:44

Fichier

2692-9767-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01349042, version 1

Collections

Citation

Ajit Diwan, Justine Dion, David Mendell, Michael Plantholt, Shailesh Tipnis. The complexity of $P$4-decomposition of regular graphs and multigraphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.63-76. 〈hal-01349042〉

Partager

Métriques

Consultations de la notice

25

Téléchargements de fichiers

140