Theses and Dissertations
Issuing Body
Mississippi State University
Advisor
Dobson, Edward
Committee Member
Johnson, Corlis
Committee Member
Knudson, Kevin
Committee Member
Smith, Robert
Committee Member
Stocker IV, S. Russell
Date of Degree
8-8-2009
Document Type
Dissertation - Open Access
Major
Mathematical Sciences
Degree Name
Doctor of Philosophy
College
College of Arts and Sciences
Department
Department of Mathematics and Statistics
Abstract
We study the Erdős- Sòs conjecture that states that ever graph of average degree greater than k-1 contains every tree of order k+1. While the conjecture was studied for some graphs, it still remains open and of interest after more than 40 years. We study the conjecture for graphs with no K2,s where, s ≥ 2 and k > 12(s-1). We use the fact that as G contains no K2,s, any two distinct vertices in G have at most s-1 neighbors in common in proving the results. We have answered in the affirmative that the Erdős- Sòs conjecture is true for graphs defined above, thus adding to the list of graphs for which the conjecture is true. We also study the Cayley Isomorphism Problem that states that for which finite groups H is it true that any two Cayley graphs of H are isomorphic if and only if they are isomorphic by a group automorphism of H ? (H is a CI-group with respect to graphs.) Determining whether or not a group is a CI-group with respect to graphs has received considerable attention over the last 40 or so years. In particular, we study the problem for (pq,r)-metacirculant color digraphs where p < q < r and pq/| α|. We use the fact that Γ is a CI-color digraph of H if and only if given a permutation γ ∈ SH such that γ-1HLγ ≤ Aut(Γ), HL and γ-1HLγ are conjugate in Aut(Γ). We consider the Cayley isomorphism problem for a nonabelian group of order pqr, where p, q, r are distinct primes such that pq/(r- 1). We show that the results are true, not only for Cayley graphs but for some related classes of non Cayley vertex transitive graphs, thus solving the problem for that case.
URI
https://hdl.handle.net/11668/15499
Recommended Citation
Balasubramanian, Suman, "On the Erdos-Sos conjecture and the Cayley Isomorphism Problem" (2009). Theses and Dissertations. 3368.
https://scholarsjunction.msstate.edu/td/3368
Comments
Cayley graph||(pq r)–metacirculant||Tree||K2 s||Cayley Isomorphism Problem||Erdős–Sós Conjecture