Advanced search options

Sorted by: relevance · author · university · date | New search

You searched for `+publisher:"Rutgers University" +contributor:("Grigoriadis, Michael")`

.
Showing records 1 – 2 of
2 total matches.

▼ 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 31, 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. 31 Oct 2020.

Vancouver:

Khan, Imdadullah 1. Spanning subgraphs in graphs and hypergraphs. [Internet] [Doctoral dissertation]. Rutgers University; 2011. [cited 2020 Oct 31]. 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

Rutgers University

2. Jamshed, Asif. Embedding spanning subgraphs into large dense graphs.

Degree: PhD, Computer Science, 2010, Rutgers University

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

In this thesis we are going to present some results on embedding spanning subgraphs into large dense graphs. Spanning Trees Bollob'as conjectured that if G is a graph on n vertices, δ(G) geq (1/2 + epsilon) n for some ε > 0, and T is a bounded degree tree on n vertices, then T is a subgraph of G. The problem was solved in the affirmative by Koml'os, S'ark"ozy and Szemer'edi for large graphs. They then strengthened their result, and showed that the maximum degree of T need not be bounded: there exists a constant c such that T is a subgraph of G if Δ(T) leq cn / log n, δ(G) geq (1/2 + epsilon) n and n is large. Both proofs are based on the Regularity Lemma-Blow-up Lemma Method. Recently, using other methods, it was shown that bounded degree trees embed into graphs with minimum degree n/2 + C log n, where C is a constant depending on the maximum degree of T. Here we show that in general n/2 + O(Delta(T) cdot log n) is sufficient for every Δ(T) leq cn / log n. We also show that this bound is tight for the two extreme values of m i.e. when m = C and when m = cn / log n. Powers of Hamiltonian Cycles In 1962 P'osa conjectured that if δ(G) geq frac{2}{3}n then G contains the square of a Hamiltonian cycle. Later, in 1974, Seymour generalized this conjecture: if δ(G) geq (frac{k-1}{k})n then G contains the (k-1)th power of a Hamiltonian cycle. In 1998 the conjecture was proved by Koml'os, S'ark"ozy and Szemer'edi for large graphs using the Regularity Lemma. We present a ``deregularised" proof of the P'osa-Seymour conjecture which results in a much lower threshold value for n, the size of the graph for which the conjecture is true. We hope that the tools used in this proof will push down the threshold value for n to around 100 at which point we will be able to verify the conjecture for every n.

Subjects/Keywords: Hamiltonian graph theory; Spanning trees (Graph theory); Embeddings (Mathematics)

Record Details Similar Records

❌

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

APA (6^{th} Edition):

Jamshed, A. (2010). Embedding spanning subgraphs into large dense graphs. (Doctoral Dissertation). Rutgers University. Retrieved from http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417

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

Jamshed, Asif. “Embedding spanning subgraphs into large dense graphs.” 2010. Doctoral Dissertation, Rutgers University. Accessed October 31, 2020. http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417.

MLA Handbook (7^{th} Edition):

Jamshed, Asif. “Embedding spanning subgraphs into large dense graphs.” 2010. Web. 31 Oct 2020.

Vancouver:

Jamshed A. Embedding spanning subgraphs into large dense graphs. [Internet] [Doctoral dissertation]. Rutgers University; 2010. [cited 2020 Oct 31]. Available from: http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417.

Council of Science Editors:

Jamshed A. Embedding spanning subgraphs into large dense graphs. [Doctoral Dissertation]. Rutgers University; 2010. Available from: http://hdl.rutgers.edu/1782.1/rucore10001600001.ETD.000056417