Clawfreeness of the powers of a graph

2012 
Let n@?N. We describe a list G"n of graphs such that if the nth power G^n of a graph G contains a claw then some graph in G"n appears as an induced subgraph of G. We show that our set G"n 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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    10
    References
    0
    Citations
    NaN
    KQI
    []