On relations between upper bound graphs and graph operations

我们考虑图上运算的上界图。利用边缘团盖的概念，讨论了由上界图的图运算得到的上界图的刻画。例如，对于具有|V(G)|【大于等于】2和|V(H)|【大于等于】2的上界图G和H，当且仅当H是完全图时，构成G[H]是上界图，且当且仅当G对应的边团盖的交图是上界图时，上界图G的平方是上界图。我们考虑P和Q之间的变换，它们的上波特图是相同的。我们得到P可以通过两个变换的有限序列，即在偏序集上的加和减，变换成Q。进一步给出了上界图相同的最小偏序集和最大偏序集的一些性质。我们确定偏置集的最大距离。同样地，我们也考虑关于变换和距离的双界图。接下来我们处理半有界图。对于偏序集P，当V(G)=V(P)和μ， ε e (G)当且仅当存在μ和υ的公共上界或μ和υ的公共下界时，图G是P的半有界图。我们利用双界图的性质对半界图进行了刻画，并利用团盖对半界图进行了另一种刻画。得到了关于上界图和双界图构造的一些结果。这些结果引出了上界图和双界图的其他性质。

We consider upper bound graphs with respect to operations on graphs. Using a concept of edge clique covers, we deal with characterizations of upper bound graphs obtained by graph operations of upper bound graphs. For example, for upper bound graphs G and H with |V(G)|【greater than or equal】2 and |V(H)|【greater than or equal】2, the composition G[H] is an upper bound graph if and only if H is a complete graph, and the square of an upper bound graph G is an upper bound graph if and only if the intersection graph of the corresponding edge clique cover of G is an upper bound graph.We consider transformations between posets P and Q, whose upper baud graphs are the same. We obtain that P can be transformed into Q by a finite sequence of two transformations, that is, additions and deletions on posets. Furthermore we show some properties on minimum posets and maximal posets whose upper bound graphs are the same. We determine the maximum distance of posets.Similarly we also consider double bound graphs on transformations and distances.Next we deal with semi bound graphs. For a poset P, a graph G is a semi bound graph of P if V(G)=V(P) and μ,υεE(G) if and only if there exists a common upper bound of μ and υ or a common lower bound of μ and υ. We characterize semi bound graphs using properties on double bound graphs, and have another characterization of semi bound graphs in terms of clique covers.We obtain some results on construction of upper bound graphs and double bound graphs. These results induce other characterizations on upper bound graphs and double bound graphs.