DIMACS

General Information

me

Student: Kaleigh Clary
Office: CoRE 434
School: Hendrix College
E-mail: claryka@hendrix.edu
Project: Forbidden Subgraphs of Competition Graphs
Mentor: Dr. Gene Fiorini

Project Description

Example of a digraph and its competition graph

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 zV (possibly x or y) such that xz,yzE.

We define a digraph of a relation on ℝn where each element in the set has a vertex there is an edge from
(a1, a2, ..., an) to (b1, b2, ..., bn) if and only if ai > bii.

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


Weekly Log

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.

Presentations