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

Comments

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

Download

Share

COinS