Well-covered and uniformly well-covered graphs

Details Well-covered and uniformly well-covered graphs Well-covered and uniformly well-covered graphs

2010-09-27

arxiv.org/abs/1009.5242v2

Mathematics

Combinatorics

9 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Well-covered and uniformly well-covered graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Well-covered and uniformly well-covered graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Well-covered and uniformly well-covered graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-518170