McKay, Brendan; Schweitzer, Pascal; Schweitzer, Patrick
The competition graph of an acyclic directed graph D is the undirected graph on the same vertex set as D in which two distinct vertices are adjacent if they have a common out-neighbor in D. The competition number of an undirected graph G is the least number of isolated vertices that have to be added to G to make it the competition graph of an acyclic directed graph. We resolve two conjectures concerning competition graphs. First, we prove a conjecture of Opsut by showing that the competition...[Show more]
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.