Student: | Kaleigh Clary |
---|---|

Office: | CoRE 434 |

School: | Hendrix College |

E-mail: | claryka@hendrix.edu |

Project: | Forbidden Subgraphs of Competition Graphs |

Mentor: | Dr. Gene Fiorini |

Competition graphs arose from analysis of food webs and have applications in biology and network systems. The competition graph *C*(*D*) of a digraph *D* = (*V,E*) has the same vertex set as D, and two distinct vertices *x, y* are adjacent in *C*(*D*) if there is some vertex *z* ∈ *V* (possibly *x* or *y*) such that *xz,yz* ∈ *E*.

We define a digraph of a relation on ℝ^{n} where each element in the set has a vertex there is an edge from

(*a _{1}, a_{2}, ..., a_{n}*) to (

We are interested in finding forbidden subgraphs of competition graphs of this relation on ℝ

- Week 1:
- I selected a problem and reviewed the relevant literature. At the end of the week, I gave a presentation which can be found at the bottom of this page.
- Week 2:
- I continued a literature review and wrote a Maple script to generate competition graphs of our relation. I also began working on a proof showing that some claw graphs are forbidden in competition graphs of our relation.
- Week 3:
- I completed a proof showing subgraphs of maximum degree
*n*-1 are forbidden in competition graphs of our relation and started examining subgraphs of competition graphs of this relation with maximum degree*n*-2. I also looked at the conditions necessary for claw subgraphs of competition graphs of this relation. - Week 4:
- I completed a proof showing there are no forbidden subgraphs of maximum degree
*n*-2 in competition graphs of our relation. I then looked at possible restrictions on the digraphs of our relation or the competition graphs thereof to examine forbidden subgraphs of the competition graphs under those restrictions. - Week 5:
- I investigated the conditions necessary for split subgraphs to exist in competition graphs our our relation, and I started a writeup of my review of the literature in weeks 1 and 2. I also modified the Maple script to allow restrictions of
*D*. - Week 6:
- After consulting with Dr. Brian Nakamura, I looked at a specific restriction of the digraphs of our relation. Suppose you have two different lines through the origin, and suppose you distribute
*n*points along these two lines. We want to determine properties of competition graphs that exist under these constraints. I wrote a second Maple script to examine the digraphs and competition graphs in this restriction and identified specific cases where we can describe the competition graphs. - Week 7:
- I showed that there are no forbidden subgraphs of maximum degree
*n*-2 in competition graphs of our relation in the restricted domain with two lines in ℝ^{2}. Now we are looking at extending this to three dimensions. I also gave a presentation over my work this summer, which can be found at the bottom of this page.