Accession Number : ADA262423


Title :   A Class of Well-Covered Graphs With Girth Four


Corporate Author : VANDERBILT UNIV NASHVILLE TN DEPT OF MATHEMATICS


Personal Author(s) : Pinter, Michael R


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a262423.pdf


Report Date : Jan 1991


Pagination or Media Count : 22


Abstract : A graph is well-covered if every maximal independent set is also a maximum independent set. A 1-well-covered graph G has the additional property that G-v is also well-covered for every point v in G. Thus, the 1-well-covered graphs form a subclass of the well-covered graphs. We examine triangle-free 1- well-covered graphs. Other than C5 and K2, a 1-well-covered graph must contain a triangle or a 4-cycle. Thus, the graphs we consider have girth 4. Two constructions are given which yield infinite families of 1-well-covered graphs with girth 4. These families contain graphs with arbitrarily large independence number.


Descriptors :   *GRAPHS , CYCLES , TRIANGLES


Subject Categories : Numerical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE