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是连通图。如果满足以下条件的相邻非简单顶点u和v连续收缩得到的图是新星（nova）：(1)u和v与G的一个简单顶点相邻(2)不存在对非简单相邻顶点x和不与满足一定条件的G的相似顶点相邻的图，则G是上界图。第二个结果是利用偏集中禁止子集的概念刻画了一类受限的上界图。对于一个偏序集P，一个偏序集Q是P的m-传票集，如果(1)Q是P的m-传票集，(2)对于任意对x，y （Q, x,y <=m）对于P中的某个m，则存在m‘在Q中且x，y <=m’。这个定义是由D.D.Scott在1986年提出的。利用这一概念，我们得到了以下结果：(1)如果G的正则偏序集不包含偏序集P_<2K2>作为m-传讯集，则G是一个分裂上界图。(2)G是一个阈值上界图，如果G的正则序集不包含2K_2或P_w作为m个集。(3)G是差分上界图，如果G的正则序集包含P_<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.