The competition number of a graph with exactly two holes

The competition number of a graph with exactly two holes

0.00 Avg rating0 Votes
Article ID: iaor2012233
Volume: 23
Issue: 1
Start Page Number: 1
End Page Number: 8
Publication Date: Jan 2012
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: graphical methods
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.

Reviews

Required fields are marked *. Your email address will not be published.