We consider upper bound graphs with respect to operations on graphs, that is, the sum, the Cartesian product, the composition, the normal product of graphs and so on. According to the characterization of upper bound graphs, we deal with characterizations of upper bound graphs obtained by graph operations on upper bound graphs. For example, for upper bound graphs G and H with V(G) greater than or equal to 2 and V(H) greater than or equal to 2, the composition G[H] is an upper bound graph if and only if H is a complete graph, or the conjunction G boolean AND H is an upper bound graph if and only if E(G)= 0 or, E(H)= 0 or, G = K-1,K-n and H =K-2. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 4]
展开▼