DISSOCIATION IN CIRCULANT GRAPHS AND INTEGER DISTANCE GRAPHS

A dissociation set of a graph G is a set of vertices which induces a subgraph of G with maximum degree at most 1, or equivalently, a set of vertices whose complement in G is a 3-path vertex cover (intersecting every 3-path of G ). The maximum cardinality of a dissociation set of G is called the dissociation number of G . We study the dissociation number of a circulant graph (a Cayley graph of the group Z n ) and generalize this concept to the dissociation ratio of an integer distance graph (a Cayley graph of the group Z ).