2010arXiv (Cornell University)Open access

Well-covered and uniformly well-covered graphs

Rashid Zaare-Nahandi

Open full text 0 citations

Abstract

A graph $G$ is called well-covered if all maximal independent sets of vertices have the same cardinality. A well-covered graph $G$ is called uniformly well-covered if there is a partition of the set of vertices of $G$ such that each maximal independent set of vertices has exactly one vertex in common with each part in the partition. The problem of determining which graphs is well-covered, was proposed in 1970 by M.D. Plummer. Let $\cal G$ be the class of graphs with some disjoint maximal cliques covering all vertices. In this paper, some necessary and sufficient conditions are presented to recognize which graphs in the class $\cal G$ are well-covered or uniformly well-covered. This characterization has a nice algebraic interpretation according to zero-divisor elements of edge ring of graphs which is illustrated in this paper.

Open-access reader

About this research paper

What this paper is about

A graph $G$ is called well-covered if all maximal independent sets of vertices have the same cardinality. A well-covered graph $G$ is called uniformly well-covered if there is a partition of the set of vertices of $G$ such that each maximal independent set of vertices has exactly one vertex in common with each part in the partition. The problem of determining which graphs is well-covered, was proposed in 1970 by M.D. Plummer. Let $\cal G$ be the class of graphs with some disjoint maximal cliques covering all vertices. In this paper, some necessary and sufficient conditions are presented to recognize which graphs in the class $\cal G$ are well-covered or uniformly well-covered. This characterization has a nice algebraic interpretation according to zero-divisor elements of edge ring of graphs which is illustrated in this paper.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

A graph $G$ is called well-covered if all maximal independent sets of vertices have the same cardinality. A well-covered graph $G$ is called uniformly well-covered if there is a partition of the set of vertices of $G$ such that each maximal independent set of vertices has exactly one vertex in common with each part in the partition. The problem of determining which graphs is well-covered, was proposed in 1970 by M.D. Plummer. Let $\cal G$ be the class of graphs with some disjoint maximal cliques covering all vertices. In this paper, some necessary and sufficient conditions are presented to recognize which graphs in the class $\cal G$ are well-covered or uniformly well-covered. This characterization has a nice algebraic interpretation according to zero-divisor elements of edge ring of graphs which is illustrated in this paper.

Key concepts: Combinatorics, Mathematics, Chordal graph, Discrete mathematics, Frequency partition of a graph, Partition (number theory), Vertex (graph theory), Disjoint sets

Related papers

Back to paper searchBrowse research topicsOriginal source
Well-covered and uniformly well-covered graphs — Research Paper | ScholarLens