Physical Sciences and Mathematics Commons^™

Two Problems On Bipartite Graphs, Albert Bush

Mathematics Theses

Erdos proved the well-known result that every graph has a spanning, bipartite subgraph such that every vertex has degree at least half of its original degree. Bollobas and Scott conjectured that one can get a slightly weaker result if we require the subgraph to be not only spanning and bipartite, but also balanced. We prove this conjecture for graphs of maximum degree 3.

The majority of the paper however, will focus on graph tiling. Graph tiling (or sometimes referred to as graph packing) is where, given a graph H, we find a spanning subgraph of some larger graph G that …

Decompositions Of Mixed Graphs With Partial Orientations Of The P4., Adam M. Meadows

Electronic Theses and Dissertations

A decomposition D of a graph H by a graph G is a partition of the edge set of H such that the subgraph induced by the edges in each part of the partition is isomorphic to G. A mixed graph on V vertices is an ordered pair (V,C), where V is a set of vertices, |V| = v, and C is a set of ordered and unordered pairs, denoted (x, y) and [x, y] respectively, of elements of V [8]. An ordered pair (x …

Cyclic, F-Cyclic, And Bicyclic Decompositions Of The Complete Graph Into The 4-Cycle With A Pendant Edge., Daniel Shelton Cantrell

Electronic Theses and Dissertations

In this paper, we consider decompositions of the complete graph on v vertices into 4-cycles with a pendant edge. In part, we will consider decompositions which admit automorphisms consisting of:

(1) a single cycle of length v,

(2) f fixed points and a cycle of length v − f, or

(3) two disjoint cycles.

The purpose of this thesis is to give necessary and sufficient conditions for the existence of cyclic, f-cyclic, and bicyclic Q-decompositions of K_v.