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.Zasramsky利用团覆盖概念刻画了上界图.本文用构造法和禁止子结构给出了不同的刻画。上界图可以通过收缩变换为新星，新星可以通过分裂变换为上界图。其中nova是通过用至少有两条边的完全图替换每条边而从星图K_1中获得的图类。利用这些结果，我们得到了上界图的一个刻画：设G是连通图。G是上界图，如果满足下列条件的相邻非单纯顶点u和v的连续压缩得到的图是新值：(1)u和v与G的一个单纯顶点相邻。(2)不存在不与满足一定条件的单纯顶点相邻的非单纯相邻顶点对xAndy。第二个结果是利用偏序集中的禁子集的概念刻画了一类受限的上界图。对于偏序集P，偏序集Q是P的m-子集当且仅当(1)Q是P的子集，并且，(2)对任意对q，y，q，x，y&lt；=m，对P中的某个m，则Q中存在m‘，其中x，y&lt；=m’.这一定义是由D.D.Scott于1986年提出的。(2)G是门限上界图当且仅当G的标准偏序集不包含2K_2或P_w作为m-子集。(3)G是差上界图当且仅当G的标准偏序集包含P_(？)lt；2k2&gt；或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.