Record Details


Field	Value

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

Creator	DIWAN, AA DION, JE MENDELL, DJ PLANTHOLT, MJ TIPNIS, SK

Subject	DECOMPOSITION P-4-decomposition multigraphs NP-complete

Description	Let G denote a multigraph with edge set E (G), let mu(G) denote the maximum edge multiplicity in G, and let P k denote the path on k vertices. Heinrich et al.(1999) showed that P-4 decomposes a connected 4-regular graph G if and only if vertical bar E(G)vertical bar is divisible by 3. We show that P-4 decomposes a connected 4-regular multigraph G with mu(G) = 3, P-4 decomposes a connected 2 k-regular graph G if and only if vertical bar E(G)vertical bar is divisible by 3. We prove that for all integers k >= 2, the problem of determining if P-4 decomposes a (2 k + 1)-regular graph is NP-Complete. El-Zanati et al.(2014) showed that for all integers k >= 1, every 6 k-regular multigraph with mu(G) = 3 the problem of determining if P-4 decomposes a 2 k-regular multigraph with mu(G)

Publisher	DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE

Date	2016-01-15T10:50:19Z 2016-01-15T10:50:19Z 2015

Type	Article

Identifier	DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 17(2)63-76 1462-7264 1365-8050 http://dspace.library.iitb.ac.in/jspui/handle/100/18390

Language	en

ICAR Research Data Repository for Knowledge Management