Discipline: Mathematics and Statistics
Subcategory: Mathematics and Statistics
Carissa Babcock - Alverno College
In 2013, Factor, Merz and Sano asked the question: Are there graphs other than C4, the cycle on 4 vertices, where the competition number of a graph G, k(G), is greater than its (1,2)-step competition number, k(1,2)(G)? This research is important since it is providing a partial answer to this previous research. It was thought that by looking at variations of C4 graphs, a similar pattern will be seen. The competition number of a graph G, k(G), is defined as the smallest nonnegative integer k such that a graph G with k isolated vertices is the competition graph for some acyclic digraph. Similarly, the (1,2)-step competition number is defined as the smallest nonnegative integer k such that a graph G with k isolated vertices is the (1,2)-step competition graph for some acyclic digraph. An (i,j)-step competition graph is the generalized concept in which {x,y} will be an edge in the (i,m)-step competition graph, denoted C(i,m)(D), if for some z ∈V(T)-{x,y},d_(T-y) (x,z) ≤i and d_(T-x) (y,z)≤m or d_(T-x) (y,z)≤i and d_(T-y) (x,z)≤m. The competition graph will be the (1,1)-step competition graph, and the (1,2)-step is the (1,2)-step competition graph of the generalized (i,j)-step definition. Here we explore classes of graphs that provide a partial answer to the question asked in that paper and prove that the relationship exists for C4 ∪ C4 graphs. In the future, different variations will be looked at. One concept that will be observed is C4 graphs with pendants. This research was funded by the National Science Foundation and was conducted at Marquette University in the Computation Across the Disciplines REU. Main References: [1] Dutton, R., Brigham, R. A Characterization of Competition Graphs. Discrete Applied Mathematics 6 (1983) 315-317. [2] Factor, K., Merz, S., Sano, Y. The (1,2)-step competition number of a graph. Congressus Numerantium 215, (2013) 153-161. [3] Factor, K., Merz, S. The (1,2)-step competition graph of a tournament. Discrete Applies Mathematics. Volume 159, Issues 2-3 (2011) 100-103.
Funder Acknowledgement(s): National Science Foundation
Faculty Advisor: Kim Factor, kim.factor@marquette.edu
Role: I did all of the research discussed in the abstract. I conducted research based off of questions my mentor asked when she did prior research. My results extend off of her and her research partners' results.