Uniformly dissociated graphs

作者：Bresar Bostjan^*; Hartnell Bert L; Rall Douglas F

来源：Ars Mathematica Contemporanea, 2017, 13(2): 293-306.

DOI：10.26493/1855-3974.1013.46a

• Dissociation number
• well-covered graphs
• girth
• Moore graph
• polarity graph

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.

• 出版日期2017