Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for +publisher:"Rutgers University" +contributor:("Reed, Bruce"). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Rutgers University

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

Degree: PhD, Computer Science, 2011, Rutgers University

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 n1, n2, ldots , nr, and G is a graph on n = n1+n2 + ... +nr vertices with minimum degree at least [sigmar/i=1 n1/2 then G contains H as a subgraph. A proof of this conjecture for graphs withn[greater than or less than] n0 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 n0 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).

Advisors/Committee Members: Khan, Imdadullah, 1980- (author), Szemeredi, Endre (chair), Steiger, William (internal member), Grigoriadis, Michael (internal member), Reed, Bruce (outside member).

Subjects/Keywords: Graph theory; Hypergraphs

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

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

APA (6th 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 (16th 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 (7th 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

.