A study on competition numbers of graphs in the aspect of primary predator index
Jihoon Choi, Soogang Eoh, Suh-Ryung Kim · arXiv (Cornell University) · 2016
The competition graph of a digraph D is defined as a graph which has the same vertex set as D and has an edge xy between two distinct vertices x and y if and only if, for some vertex z ∈ V (D), the arcs (x,z) and (y,z) are in D. The competition number of a graph G is defined to be the smallest number k such that G together with k isolated vertices is the competition graph of an acyclic digraph. In this paper, we define the primary predator index p of a graph G with competition number k as the largest number p such that an acyclic digraph whose competition graph is G together with k isolated vertices has p vertices of in-degree 0, and show that the competition number k(G) and the primary predator index p(G) of a graph G are related as k(G) ≥ �e(G) − |V (G)| + p(G). As a matter of fact, this generalizes the inequality k(G) ≥ �e(G)−|V (G)|+2 given by Opsut [7] as p(G) ≥ 2 for a graph with at least one edge. In the process, we introduce a notion of effective competition cover, which is possessed by a large family of graphs, and show that our inequality actually becomes an equality for a graph having an effective competition cover and the competition number of a certain graph having an effective competition cover may be obtained by utilizing its primary predator index. Especially, we present a precise relationship between the competition number and the primary predator index of a diamond-free plane graph. � This work forms part of the author’s master’s thesis at Seoul National University. † This research was supported by Global Ph.D Fellowship Program through the National Research