2016/10/13 by Vadim E. Levit, Levit, Vadim E., Eugen Mândrescu +1 · 2 citations
Computer Science · Mathematics · #05C25 (Secondary) #05C69 #05C75 #05C76 (Primary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Limits and Structures in Graph Theory #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1610.03972
openalex publication_date 2016/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is well-covered if all its maximal independent sets are of the same size (M. D. Plummer, 1970). A well-covered graph is 1-well-covered if the deletion of every vertex leaves a graph which is well-covered as well (J. W. Staples, 1975). A graph G belongs to class Wn if every n pairwise disjoint independent sets in G are included in n pairwise disjoint maximum independent sets (J. W. Staples, 1975). Clearly, W1 is the family of all well-covered graphs. It turns out that G belongs to W2 if and only if it is a 1-well-covered graph without isolated vertices. We show that deleting a shedding vertex does not change the maximum size of a maximal independent set including a given independent set A in a graph G. Specifically, for well-covered graphs, it means that the vertex v is shedding if and only if G-v is well-covered. In addition, we provide new characterizations of 1-well-covered graphs, which we further use in building 1-well-covered graphs by corona, join, and concatenation operations.