## 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*-free graphs when

_{r}*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*, i.e.,

_{R}*r:G → G*, by a surjective labeling of the vertices of

_{R}*G*with the vertices of

*G*, i.e.,

_{R}*r:V(G)→ V(G*. For

_{R})*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*-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?

_{r}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*, where each set

_{0}, S_{1}, ..., S_{r-3}*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

_{0}*K*-free graphs are obtained, for the cases

_{r}*r = 4*and

*r ≥ 5*respectively. The binding number of dense

*K*-free graphs is also considered. We improve previously published results regarding the binding number by giving a construction of

_{r}*K*-free graphs with large binding number, and proving stricter upper bounds on the binding number of dense

_{4}*K*-free graphs.

_{r}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*for some value of

_{r}*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