||Graph Theory and Competition Graphs.
Starting from predator-prey concepts in ecological food webs, Joel Cohen introduced the notion of competition graphs
in 1968. 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 zx,zy ∈ E.
We define a digraph of a relation on ℝn where each element in the set has a vertex there is an edge
(a1, a2, ..., an) to (b1, b2, ..., bn
) if and only if ai > bi ∀i.
We are interested in finding forbidden subgraphs of competition graphs of this relation on ℝ3.
- Week 1:
- This week I reviewed the basic concepts of graph theory and prepared my first project presentation.
Some of the basic concepts I reviewed were path, walk, cycle, circuit, directed and undirected graphs.
Furthermore, I did some background work on integer sequences and graph isomorphism algorithms. I also
looked into developing an algorithm for fingerprint identification and explored several problems in
competition graphs. The first presentation has been uploaded to the link at the bottom.
- Week 2:
- For this week, I reviewed several literatures of graph theory and reviewed adjacency matrices while
also writing a program in maple to draw directed graphs and its competition graphs. I continued to look
further into the problems of graph theory. Some of the challanges I have been facing is reducing the
graphing command to two parameters that will allow the user to modify the number of dimensions and
vertices for maple to draw directed graphs and its competition graph. My preliminary program draws a
two dimensional digraphs and its competition graphs based on the position and number of vertices.
- Week 3:
- I continued with the literature review and other additional literatures. I wrote more maple scripts
to generate directed graphs and its competition graph. I focused on the problem of finding forbidden
subgraphs of its competition graphs by looking at different cases where the number of vertices and the
numbers of edges incident to them were different for each graph. Furthermore, I looked into constructing
some proofs of the forbidden subgraphs of its competition graphs.
- Week 4:
- I found one of the family of forbidden subgraphs for the competition graph of our relation. The star
graph with n vertices and n-1 edges is a forbidden subgraph of the competition graph. I worked on the
proof for this particular family of forbidden subgraph. My coworker Aquia found another family of forbidden
subgraph, which was a graph with cycle length of 4 or greater is forbidden for the competition graph of our
relation. I started the idea generalizing it to all finite posets. To illustrate, If S is a finite poset,
we are trying to categorize the forbidden subgraphs of the competition graph for the corresponding digraph.
- Week 5:
- I tried to come up with more examples of forbidden subgraphs for the competition graph of our relation
in order to find another family of forbidden subgraphs. I continued to focus on finite poset to try to
categorize the forbidden subgraphs of the competition graph for the corresponding digraph. Furthermore,
I reviewed a recently published literature called "On Competition Graphs of n-tuply partial orders, which
both of Dr. Brian Nakamura and my mentor emailed it to my
coworkers and me. After meeting with my mentor, he suggest that we look at tree competition graphs with end
vertices of degree 1 and try to find a digraph that corresponds to them. To make it simple, we started this
with the case on ℝ2. The key idea is to check whether we can find an isolated vertex of the
digraph that will give us the desired tree graph with the end vertices of degree 1.
- Week 6:
- After meeting with my mentor and receiving feedback from him, I revised the proof of the claw graph as
a forbidden subgraph for the competition graph of our relation. Furthermore, I started the introduction of
my summer report by defining some terms and summarizing some literatures that are relevant to our problem.
For this week, I became more proficient using LaTeX to type up my documents. Moreover, I started working on
my final presentation, which will be presented on July 18, 2014. I also continued to work on the problem
generalized to all finite posets.
- Week 7:
- I continued to work on the problems while also preparing for a final presentation on Friday. I am also
working on final summary report. On my summary report, I included some figures which help illustrate the
idea of a definition or proof. I got together with my mentor to get feedback from him so we can properly
present our results to the audience. Finally, my coworkers and I presented our results on Friday July 18, 2014.
The second presentation has been uploaded to the link at the bottom.
- Week 8:
- I am working on the summary report and continuing working on the future problems. I have so far completed
introduction of the summary report.
- Week 9:
- This week I will focus on completing my summary report. My coworkers and I will be presenting our project
briefly to high school students for the program of Young Scholars. The presentation will last for about 5
minutes. The next 55 minutes will be devoted for high school students to ask questions regarding research or