Uniformly dissociated graphs

Abstract

A set <em>D</em> of vertices in a graph <em>G</em> is called a dissociation set if every vertex in <em>D</em> has at most one neighbor in <em>D</em>. We call a graph <em>G</em> uniformly dissociated if all maximal dissociation sets are of the same cardinality. Characterizations of uniformly dissociated graphs with small cardinalities of dissociation sets are proven; in particular, the graphs in which all maximal dissociation sets are of cardinality 2 are the complete graphs on at least two vertices from which possibly a matching is removed, while the graphs in which all maximal dissociation sets are of cardinality 3 are the complements of the <em>K</em>₄-free geodetic graphs with diameter 2. A general construction by which any graph can be embedded as an induced sub graph of a uniformly dissociated graph is also presented. In the main result we characterize uniformly dissociated graphs with girth at least 7 to be either isomorphic to <em>C</em>₇, or obtainable from an arbitrary graph <em>H</em> with girth at least 7 by identifying each vertex of <em>H</em> with a leaf of a copy of <em>P</em>₃.