Advanced search options

You searched for `+publisher:"Rutgers University" +contributor:("Reed, Bruce")`

. One record found.

▼ Search Limiters

Rutgers University

1. Khan, Imdadullah, 1980-. Spanning subgraphs in graphs and hypergraphs.

Degree: PhD, Computer Science, 2011, Rutgers University

URL: http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299

This thesis consists of three new fundamental results on the existence of spanning subgraphs in graphs and hypergraphs. Cycle Factors in Graphs: A classical conjecture of El-Zahar states that if H is a graph consisting of r vertex disjoint cycles of length n_{1}, n_{2}, ldots , n_{r}, and G is a graph on n = n_{1+n}_{2} + ... +n_{r} vertices with minimum degree at least [sigmar/i=1 n_{1}/2
then G contains H as a subgraph. A proof of this conjecture for graphs withn[greater than or less than] n_{0} was announced by S. Abbasi (1998) using the Regularity Lemma-Blow-up Lemma method. We give a new, ``de-regularized" proof of the conjecture for large graphs that avoids the use of the Regularity Lemma, and thus the resulting n_{0} is much smaller. Perfect Matching in three-uniform hypergraphs A perfect matching in a three-uniform hypergraph on n=3k vertices is a subset of n/3 disjoint edges. We prove that if H is a three-uniform hypergraph on n=3k vertices such that every vertex belongs to at least {n-1choose 2} - {2n/3choose 2}+1 edges, then H contains a perfect matching. We give a construction to show that our result is best possible. Perfect Matching in four-uniform hypergraphs A perfect matching in a four-uniform hypergraph is a subset of lfloorfrac{n}{4}
floor disjoint edges. We prove that if H is a sufficiently large four-uniform hypergraph on n=4k vertices such that every vertex belongs to more than {n-1choose 3} - {3n/4 choose 3} edges, then H contains a perfect matching. Our bound is tight and settles a conjecture of Hán, Person and Schacht (2009).

Subjects/Keywords: Graph theory; Hypergraphs

Record Details Similar Records

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^{th} Edition):

Khan, Imdadullah, 1. (2011). Spanning subgraphs in graphs and hypergraphs. (Doctoral Dissertation). Rutgers University. Retrieved from http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299

Chicago Manual of Style (16^{th} Edition):

Khan, Imdadullah, 1980-. “Spanning subgraphs in graphs and hypergraphs.” 2011. Doctoral Dissertation, Rutgers University. Accessed October 29, 2020. http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299.

MLA Handbook (7^{th} Edition):

Khan, Imdadullah, 1980-. “Spanning subgraphs in graphs and hypergraphs.” 2011. Web. 29 Oct 2020.

Vancouver:

Khan, Imdadullah 1. Spanning subgraphs in graphs and hypergraphs. [Internet] [Doctoral dissertation]. Rutgers University; 2011. [cited 2020 Oct 29]. Available from: http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299.

Council of Science Editors:

Khan, Imdadullah 1. Spanning subgraphs in graphs and hypergraphs. [Doctoral Dissertation]. Rutgers University; 2011. Available from: http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000061299