科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let D = (V(D), A(D)) be a digraph. The competition graph of D. is the graph with vertex set V(D) and edge set {uv is an element of (V(D) 2) : there exists w is an element of V(D), (uw) over right arrow, (vw) over right arrow is an element of A(D)}. The double competition graph of D, is the graph with vertex set V(D) and edge set {uv is an element of (V(D) 2) : there exists w(1), w(2) is an element of V(D). (uw(1)) over right arrow, (vw(1)) over right arrow, (w(2)u) over right arrow, (w(2)v) over right arrow is an element of A(D)}. A poser of dimension at most two is a digraph whose vertices are some points in the Euclidean plane R(2) and there is an arc going from a vertex (x(1), y(1)) to a vertex (x(2), y(2)) if and only if x(1) > x(2) and y(1) > y(2). 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 poser and the minimum sizes of certain intersection representations of that graph.
- 出版日期2010-3-28
- 单位上海交通大学
