On the powers of graphs with bounded asteroidal number

Abstract

For an undirected graph G=(V,E), the k-th power Gk is the graph with the same vertex set as G such that two vertices are adjacent in Gk if and only if their distance in G is at most k. A set of vertices A  V is an asteroidal set if for every vertex a  A, the set a\{a} is contained in one connected component of G-NG [a],where NG [a] is closed neighborhood of a in G. The asteroidal number of a graph G is the maximum cardinality of an asteroidal set in G. The class of graphs with asteroidal number at most s is denoted by A(s). In this paper, we show that if Gk  A(s) for s ≥ 2, then so is Gk+1 .This generalizes a previous result for the family of AT-free graphs. Moreover, we consider the forbidden configurations for the powers of graphs with bounded asteroidal number, Based on these forbidden configurations, we show that every proper power of AT-free graphs is perfect