Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
Minimum Degree Conditions For Tilings In Graphs And Hypergraphs, Andrew Lightcap
Minimum Degree Conditions For Tilings In Graphs And Hypergraphs, Andrew Lightcap
Mathematics Theses
We consider tiling problems for graphs and hypergraphs. For two graphs and , an -tiling of is a subgraph of consisting of only vertex disjoint copies of . By using the absorbing method, we give a short proof that in a balanced tripartite graph , if every vertex is adjacent to of the vertices in each of the other vertex partitions, then has a -tiling. Previously, Magyar and Martin [11] proved the same result (without ) by using the Regularity Lemma.
In a 3-uniform hypergraph , let denote the minimum number of edges that contain for all pairs of vertices. …
Two Problems On Bipartite Graphs, Albert Bush
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 …