Geodesic
The complexity of $P$4-decomposition of regular graphs and multigraphs
Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2015_17_2_a0,
     author = {Diwan, Ajit and Dion, Justine and Mendell, David and Plantholt, Michael and Tipnis, Shailesh},
     title = {The complexity of $P$\protect\textsubscript{4}-decomposition of regular graphs and multigraphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2015-2016},
     doi = {10.46298/dmtcs.2128},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2128/}
}
TY  - JOUR
AU  - Diwan, Ajit
AU  - Dion, Justine
AU  - Mendell, David
AU  - Plantholt, Michael
AU  - Tipnis, Shailesh
TI  - The complexity of $P$4-decomposition of regular graphs and multigraphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2128/
DO  - 10.46298/dmtcs.2128
LA  - en
ID  - DMTCS_2015_17_2_a0
ER  - 
%0 Journal Article
%A Diwan, Ajit
%A Dion, Justine
%A Mendell, David
%A Plantholt, Michael
%A Tipnis, Shailesh
%T The complexity of $P$4-decomposition of regular graphs and multigraphs
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2128/
%R 10.46298/dmtcs.2128
%G en
%F DMTCS_2015_17_2_a0
Diwan, Ajit; Dion, Justine; Mendell, David; Plantholt, Michael; Tipnis, Shailesh. The complexity of $P$4-decomposition of regular graphs and multigraphs. Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 2. doi : 10.46298/dmtcs.2128. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2128/

Cité par Sources :