On Path Decompositions of Graphs and Multigraphs

IIMA Institutional Repository

Please use this identifier to cite or link to this item: http://hdl.handle.net/11718/14399

Full metadata record

DC Field	Value	Language
dc.contributor.author	Tipnis, Shailesh K	-
dc.date.accessioned	2015-09-03T10:31:59Z	-
dc.date.available	2015-09-03T10:31:59Z	-
dc.date.issued	2015-08-28	-
dc.identifier.uri	http://hdl.handle.net/11718/14399	-
dc.description	The R & P seminar held at Wing 11 Committee Room, IIM Ahmedabad on August 28, 2015 by Prof. Shailesh K. Tipnis, Illinois State University, USA on "On Path Decompositions of Graphs and Multigraphs".	en_US
dc.description.abstract	For graphs G and H, graph G is said to admit an H-decomposition if the edges of G can be partitioned into isomorphic copies of H. Let P4 denote the path on 4 vertices. We survey results that assert that certain graphs and multigraphs admit a P4 decomposition. We then prove that unless P = NP some of these results are best possible by proving that their extensions are NP-complete. The positive results and the NP-complete results provide evidence for a conjecture about P4 decomposability of even-regular multigraphs.	en_US
dc.language.iso	en	en_US
dc.publisher	Indian Institute of Management, Ahmedabad	en_US
dc.subject	Decompositions	en_US
dc.subject	Multigraphs	en_US
dc.subject	Graphs and Multigraphs	en_US
dc.subject	H-decomposition	en_US
dc.title	On Path Decompositions of Graphs and Multigraphs	en_US
dc.type	Video	en_US
Appears in Collections:	R & P Seminar

Files in This Item:

File	Description	Size	Format
IIMA_28_08_2015.mp4	IIMA_28_08_2015	247.17 MB	MP4 Video	View/Open