The competition number of a graph with?exactly?two?holes |
| |
Authors: | Bo-Jr Li Gerard J Chang |
| |
Institution: | 1. Department of Mathematics, National Taiwan University, Taipei, 10617, Taiwan 3. National Center for Theoretical Sciences, Taipei Office, Taipei, Taiwan 2. Institute for Mathematical Sciences, National Taiwan University, Taipei, 10617, Taiwan
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|