The gamma graph of a graph

Abstract

The gamma graph of a graph G has its γ-sets as vertices and any two vertices are adjacent if the corresponding γ-sets differ exactly by one vertex. We obtain the collection of all forbidden subgraphs on five vertices of the gamma graph. The closure property of the gamma graphs under various graph products are studied. The structural property of the gamma graph of a cograph is also studied. The relationship between the clique number and the independence number of a graph and its gamma graph is also discussed.

Keywords:

• Gamma graph
• forbidden subgraph
• cograph

2010 Mathematics Subject Classification:

• 05C69
• 05C76