#### Date of Award

7-14-2014

#### Document Type

Thesis and Dissertation

#### Degree Name

Master of Science (MS)

#### Department

Department of Mathematics

#### First Advisor

Michael J. Plantholt

#### Abstract

The main objective of this thesis is to review and expand the study of graph decomposability. An *H*-decomposition of a graph *G=(V,E)* is a partitioning of the edge set, $E$, into edge-disjoint isomorphic copies of a subgraph *H*. In particular we focus on the decompositions of graphs into paths. We prove that a 2,4 mutligraph with maximum multiplicity 2 admits a *C_2,C_3*-free Euler tour (and thus, a decomposition into paths of length 3 if it has size a multiple of 3) if and only if it avoids a set of 15 forbidden structures. We also prove that a 4-regular multigraph with maximum multiplicity 2 admits a decomposition into paths of length three if and only if it has size a multiple of 3 and no three vertices induce more than 4 edges. We go on to outline drafted work reflecting further research into path decomposition problems.

#### Recommended Citation

Mendell, David Joshua, "P_4-Decomposability in Regular Graphs and Multigraphs" (2014). *Theses and Dissertations*. 221.

http://ir.library.illinoisstate.edu/etd/221

#### Page Count

31

## Comments

Imported from ProQuest Mendell_ilstu_0092N_10332.pdf