Date of Award

7-14-2014

Document Type

Thesis

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.

Comments

Imported from ProQuest Mendell_ilstu_0092N_10332.pdf

DOI

http://doi.org/10.30707/ETD2014.Mendell.D

Page Count

31

Download

Included in

Mathematics Commons

Share

COinS