SOME COVERING BY MONOCHROMATIC PATHS CONCEPTS IN GRAPHS

Iwona Włoch (Poland)

Received April 12, 2008

Abstract

A graph is called well-covered if every maximal independent set of vertices of G is a maximum independent set; recall that S is independent if no two of its vertices are adjacent. In this paper, we study the concept of well-covered by monochromatic paths graphs which is a variation of well-covered graphs. We give some general properties of the well-covered by monochromatic paths graphs and characterizations of several subclasses of the well-covered by monochromatic paths graphs. Next, we give operation of graphs which preserve the property of well-covered by monochromatic paths. We also consider independence by monochromatic paths polynomial in well-covered by monochromatic paths graphs.

Keywords and phrases: monochromatic paths, independence, well-covered graphs.