Uniformly dissociated graphs - Brešar, Boštjan (Ars mathematica contemporanea, 2017)
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: disociacijsko število; dobro pokriti grafi; Moore-ovi grafi; ožina; polarnostni grafi