کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418803 681720 2009 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The competition number of a graph with exactly hh holes, all of which are independent
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The competition number of a graph with exactly hh holes, all of which are independent
چکیده انگلیسی

Given an acyclic digraph DD, the competition graph C(D)C(D) of DD is the graph with the same vertex set as DD where two distinct vertices xx and yy are adjacent in C(D)C(D) if and only if there is a vertex vv in DD such that (x,v)(x,v) and (y,v)(y,v) are arcs of DD. The competition number κ(G)κ(G) of a graph GG is the least number of isolated vertices that must be added to GG to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly hh holes, all of which are independent, is at most h+1h+1. This generalizes the result for h=0h=0 given by Roberts, and the result for h=1h=1 given by Cho and Kim.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1337–1341
نویسندگان
, ,