### Uniformly dissociated graphs

#### Abstract

A set *D* of vertices in a graph *G* is called a dissociation set if every vertex in *D* has at most one neighbor in *D*. We call a graph *G* 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 *K*_{4}-free geodetic graphs with diameter 2. A general construction by which any graph can be embedded as an induced subgraph 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 *C*_{7}, or obtainable from an arbitrary graph *H* with girth at least 7 by identifying each vertex of *H* with a leaf of a copy of *P*_{3}.

#### Keywords

DOI: https://doi.org/10.26493/1855-3974.1013.46a

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications