<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue4" %>
On k-th Power of Upper Bound Graphs
Morimasa Tsuchiya
Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan
tsuchiya@ss.u-tokai.ac.jp
Annals of Combinatorics 7 (4) p.495-498 December, 2003
AMS Subject Classification: 05C62
Abstract:
We consider k-th power of upper bound graphs. According to the characterization of upper bound graphs, we obtain a characterization of k-th power of upper bound graphs. That is, for a connected upper bound graph G, Gk is an upper bound graph if and only if for any pair of Ak-simplicial vertices s1, s2 such that dG(s1, s2) k, there exists a Gk-simplicial vertex s satisfying the conditions: dG(s, s1) k and dG(s, s2) k Furthermore we also get some properties on squares of upper bound graphs.
Keywords: upper bound graph, k-th power

References:

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

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

3. H. Era, K. Ogawa, andM. Tsuchiya, On upper bound graphs with respect to unary operations on graphs, Ann. Combin. 6 (2002) 1每6.

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

5. K. Ogawa and M. Tsuchiya, On upper bound graphs with respect to line graphs, Southeast Asian Bull. Math. 23 (1999) 265每269.