On families of partially ordered sets which have the common structure of upper or lower bounds and the character of graphs which represents them

在本研究中，我们从不同的角度考虑偏序集上界图的刻画。对于偏序集P，P的上界图是图G_p=（X，E），其中一条边uv属于E当且仅当存在X的元素m使得m是u和v的上界. F. R. McMorris和T.Zaslavsky利用团覆盖的概念给出了上界图的一个刻画.本文利用构造性方法和禁止子结构给出了不同的刻画.一个上界图可以通过压缩变换成一个新星，新星可以通过分裂变换成一个上界图.其中nova是从一个星星K_通过<1.n>用至少有两条边的完全图替换每条边而得到的一类图。利用这些结果，我们得到了上界图的一个刻画：设G是连通图。G是一个上界图，如果满足下列条件的相邻非单纯顶点u和v的连续收缩所得到的图是一个nova：（1）u和v与G的一个单纯顶点相邻。（2）不存在满足一定条件的非单纯相邻顶点对x和y不与G的相似顶点相邻.第二个结果是用偏序集中禁止子集的概念来刻画某些限制类上界图.对偏序集P，偏序集Q是P的m-子集当且仅当：（1）Q是P的子集，（2）对Q的任意对x，y，x，y &lt;=m，对P中的某个m，则Q中存在m'且x，y &lt;= m'。这个定义是由D. D. Scott在1986年提出的。利用这一概念，我们得到了如下结果：（1）G是分裂上界图当且仅当G的标准偏序集不含偏序集P_<2K2>m-子偏序集。(2)G是阈值上界图当且仅当G的标准偏序集不含2K_2或P_w作为m-子偏序集. (3)G是差上界图当且仅当G的标准偏序集含有P_w<2K2>或P^作为m-子偏序集，其中P_w和P^是偏序集的某些初等类.

In this research, we consider the characterizations of upper bound graphs of posets from various aspects. For a poset P, the upper bound graph of P is the graph G_p=(X,E), where an edge uv belongs to E iff there exists an element m of X such that m is an upper bound of u and v. F.R.McMorris and T.Zaslavsky show a characterization of upper bound graphs using the clique covering conception. Here we give different characterizations by constructive method and also by forbidden substructuresAn upper bound graph can be transformed into a nova by contractions and a nova can be transformed into an upper bound graph by splits. Where nova is a graph class obtained from a star K_<1.n> by replacing each edge with a complete graph with at least two edges. By these results, we get a characterization on upper bound graphs as follows.Let G be a connected graph. G is an upper bound graph if the graph obtained by successive contractions of adjacent non-simplicial vertices u and v satisfying the following conditions is a nova :(1)u and v are adjacent to a simplicial vertex of G.(2)there exist no pair of non-simplicial adjacent vertices x andy which are not adjacent to simlicial vertices of G satisfying ceirtain conditions.The second result is on the characterization of some restricted class of upper bound graphs by concept of forbidden subset in posets. For a poset P, a poset Q is an m-subposet of P iff (1)Q is a subposet of P and, (2)for any pair x,y of Q, x,y <=m for some m in P then there exists m' in Q with x,y <=m'. This definition is introduced by D.D.Scott in 1986. Using this concept we give the following results,(1)G is a split upper bound graph iff the canonical poset of G contain no poset P_<2K2> as an m-subposet.(2)G is a threshold upper bound graph iff the canonical poset of G contain no 2K_2 or P_w as m-subposets.(3)G is difference upper bound graph iff the canonical poset of G contain P_<2K2> or P^as m-subposets.where P_w and P^are certain elementary classes of posets.