#### 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-1-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 MSU*. 3368.

https://scholarsjunction.msstate.edu/td/3368

## Comments

Cayley graph||(pq r)–metacirculant||Tree||K2 s||Cayley Isomorphism Problem||Erdős–Sós Conjecture