Homomorphisms of Graphs

Author

Samuel Lyle, Clemson UniversityFollow

Date of Award

8-2008

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Mathematical Science

Committee Chair/Advisor

Laskar, Renu C

Committee Member

Shier , Douglas R

Committee Member

Hedetniemi , Stephen T

Abstract

Understanding the structure of graphs is fundamental to advances in many areas of graph theory, as well as in many applications. In many cases, an analysis of the structure of graphs follows one of two approaches; either many structural properties are considered over a restricted class of graphs, or a particular structural property is considered over many classes of graphs. Both approaches will be considered in this dissertation.
Graphs which do not contain a clique of size r, i.e., K_r-free graphs, are of fundamental importance in the area of extremal graph theory. Many results have been obtained about dense triangle-free graphs, but not much is known about dense K_r-free graphs when r ≥ 4. Of particular interest are results pertaining to independent sets, colorings, and homomorphisms. Another method of describing the structure of a graph is through the concept of a role assignment. A role assignment is a mapping r from a graph G to a graph G_R, i.e., r:G → G_R, by a surjective labeling of the vertices of G with the vertices of G_R, i.e., r:V(G)→ V(G_R). For S ⊆ V(G), we define r(S) = {r(s): s∈ S}. Each role assignment must satisfy the following condition that ∀ v ∈ V(G), r(N(v)) = N(r(v)). Not much is known about the classes of graphs for which meaningful results about role assignments can be obtained.
The goal of this dissertation is to address the following two issues. First, what results can be obtained about the structure of dense K_r-free graphs? Secondly, what additional properties of a graph are necessary in order to obtain results about role assignments? For which classes of graphs is the problem of determining role assignments tractable, and for which classes of graphs is it difficult?
In regard to the first issue, a structural theorem is obtained which allows many properties of dense K_r-free graphs to be described in terms of the properties of dense triangle-free graphs. In particular, we determine a minimum degree condition which will permit the vertices of a dense K_r-free graphs to be partitioned into sets S₀, S₁, ..., S_r-3, where each set S_i, 1 ≤ i ≤ r-3, is independent, and the graph induced by the set S₀ is a dense triangle-free graph. Two results regarding the size of large independent sets in K_r-free graphs are obtained, for the cases r = 4 and r ≥ 5 respectively. The binding number of dense K_r-free graphs is also considered. We improve previously published results regarding the binding number by giving a construction of K₄-free graphs with large binding number, and proving stricter upper bounds on the binding number of dense K_r-free graphs.
In regard to the second issue, role assignments are considered for the classes of chordal graphs, strongly chordal graphs, and trees. A necessary condition is given for a chordal graph to have a role assignment to K_r for some value of r. For chordal graphs with small clique size, as well as strongly chordal graphs, this necessary condition is shown to be sufficient. Additionally, role assignments of the d-dimensional hypercube, along with graphs of similar structure, are considered.

Recommended Citation

Lyle, Samuel, "Homomorphisms of Graphs" (2008). All Dissertations. 255.
https://open.clemson.edu/all_dissertations/255