Portal de Periódicos da CAPES

Clawfreeness of the powers of a graph

2012; Elsevier BV; Volume: 160; Issue: 9 Linguagem: Inglês

10.1016/j.dam.2012.01.023

1872-6771

Patrick Bahls, Nicole Gin,

Limits and Structures in Graph Theory

Let n∈N. We describe a list Gn of graphs such that if the nth power Gn of a graph G contains a claw then some graph in Gn appears as an induced subgraph of G. We show that our set Gn is the smallest set of graphs with this property. If T is a tree, this gives a precise characterization of the claw-free powers of T.