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

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*,
*G*^{k} is an upper bound graph if and only if
for any pair of *A*^{k}-simplicial vertices *s*_{1}, *s*_{2}
such that *d*_{G}(*s*_{1}, *s*_{2}) *k*,
there exists a *G*^{k}-simplicial vertex *s* satisfying the conditions:
*d*_{G}(*s*, *s*_{1}) *k* and *d*_{G}(*s*, *s*_{2}) *k*
Furthermore we also get some properties on squares of upper bound graphs.

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.