The competition number of a graph with exactly two holes
Journal
Journal of Combinatorial Optimization
Journal Volume
23
Journal Issue
1
Pages
1-8
Date Issued
2012
Author(s)
Abstract
Given an acyclic digraph D, the competition graph C(D) of D is the graph with the same vertex set as D and two distinct vertices x and y are adjacent in C(D) if and only if there is a vertex v in D such that (x, v) and (y, v) are arcs of D. The competition number κ(G) of a graph G is the least number of isolated vertices that must be added to G to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly two holes is at most three. © Springer Science+Business Media, LLC 2010.
Type
journal article