<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 1" %>
On Upper Bound Graphs with Respect to Unary Operations on Graphs
Hiroshi Era1, Kenjiro Ogawa2, and Morimasa Tsuchiya2
1Faculty of Information and Communication, Bunkyo University, Chigasaki 253-8550, Japan
era@shonan.bunkyo.ac.jp
2Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan
{kenjiro, tsuchiya} @ss.u-tokai.ac.jp
Annals of Combinatorics 6 (1) p.1-6 March, 2002
AMS Subject Classification: 05C62
Abstract:
We consider upper bound graphs with respect to unary operations on graphs, that is, line graphs, middle graphs, total graphs and squares of graphs. According to the characterization of upper bound graphs, we deal with characterizations of upper bound graphs obtained by graph operations of upper bound graphs. For example, the line graph of a connected upper bound graph G is an upper bound graph if and only if or , where and the square of an upper bound graph G is an upper bound graph if and only if G = K3 or G = K1 +H, where H = mK1 &cup nK2 (m ≡1, n ≡ 0) 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.
Keywords: upper bound graphs, posets, line graphs

References:

1. M. Behzad and G. Chartrand, Total graphs and traversability, Proc. Edinburgh Math. Soc. 15 (1966) 117每120.

2. H. Era and M. Tsuchiya, On upper bound graphs whose complements are also upper bound graphs, Discrete Math. 179 (1998) 103每109.

3. H. Era, K.Ogawa, and M. Tsuchiya, On upper bound graphs with respect to operations on graphs, Theoret. Comput. Sci. 235 (2000) 219每223.

4. T. Hamada and I. Yoshimura, Traversability and connectivity of the middle graph of a graph, Discrete Math. 14 (1976) 247每255.

5. F. Harary, Graph Theory, Addison-Wesley, 1969.

6. F.R. McMorris and T. Zaslavsky, Bound graphs of a partially ordered set, J. Combin. Inform. System Sci. 7 (1982) 134每138.