On relations between upper bound graphs and graph operations

我们考虑关于图上的运算的上界图。利用边团覆盖的概念，讨论了由上界图的图运算得到的上界图的特征。例如，对于具有|V(G)|[大于等于]2和|V(H)|[大于等于]2的上界图G和H，合成图G[H]是上界图当且仅当H是完全图，上界图G的平方是上界图当且仅当G的相应边团覆盖的交图是上界图。我们得到了P可以通过两个变换的有限序列，即偏序集上的添加和删除来变换为Q。此外，我们还给出了上界图相同的最小偏序集和极大偏序集的一些性质。我们确定了偏序集的最大距离。同样，我们还考虑了关于变换和距离的双界图。接下来，我们讨论半有界图。对于偏序集P，图G是P的半有界图，当V(G)=V(P)且μ，υεE(G)当且仅当存在μ和υ的公共上界或μ和υ的公共下界。利用双界图的性质刻画了半界图，并利用团覆盖刻画了半界图，得到了上界图和双界图的一些构造结果。这些结果还给出了上界图和双界图的其他刻画。

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.