| 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 |
