首页 | 本学科首页   官方微博 | 高级检索  
     


Dimension-2 poset competition numbers and dimension-2 poset double competition numbers
Authors:Yaokun Wu  Junjie Lu
Affiliation:Department of Mathematics, Shanghai Jiao Tong University, Shanghai, 200240, China
Abstract: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 View the MathML source. The double competition graph of D, is the graph with vertex set V(D) and edge set View the MathML source. A poset of dimension at most two is a digraph whose vertices are some points in the Euclidean plane R2 and there is an arc going from a vertex (x1,y1) to a vertex (x2,y2) if and only if x1>x2 and y1>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.
Keywords:Competition graph   Double competition graph   Food web   Interval graph   Intersection number   Trapezoid graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号