کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420437 683937 2010 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
چکیده انگلیسی

Let D=(V(D),A(D))D=(V(D),A(D)) be a digraph. The competition graph of DD, is the graph with vertex set V(D)V(D) and edge set {uv∈V(D)2:∃w∈V(D),uw⃗,vw⃗∈A(D)}. The double competition graph of DD, is the graph with vertex set V(D)V(D) and edge set {uv∈V(D)2:∃w1,w2∈V(D),uw1⃗,vw1⃗,w2u⃗,w2v⃗∈A(D)}. A poset of dimension at most two is a digraph whose vertices are some points in the Euclidean plane R2R2 and there is an arc going from a vertex (x1,y1)(x1,y1) to a vertex (x2,y2)(x2,y2) if and only if x1>x2x1>x2 and y1>y2y1>y2. We show that a graph is the competition graph of a poset of dimension at most two if and only if it is an interval graph, at least half of whose maximal cliques are isolated vertices. This answers an open question on the doubly partial order competition number posed by Cho and Kim. We prove that the double competition graph of a poset of dimension at most two must be a trapezoid graph, generalizing a result of Kim, Kim, and Rho. Some connections are also established between the minimum numbers of isolated vertices required to be added to change a given graph into the competition graph, the double competition graph, of a poset and the minimum sizes of certain intersection representations of that graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 6, 28 March 2010, Pages 706–717
نویسندگان
, ,