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

点击翻译按钮获取中文摘要

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.