Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419559 | Discrete Applied Mathematics | 2010 | 19 Pages |
Abstract
A graph GG is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper Finbow et al. (2004) [3] that there are no 5-connected planar well-covered triangulations, and in Finbow et al. (submitted for publication) [4] that there are exactly four 4-connected well-covered triangulations containing two adjacent vertices of degree 4. It is the aim of the present paper to complete the characterization of 4-connected well-covered triangulations by showing that each such graph contains two adjacent vertices of degree 4.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Arthur S. Finbow, Bert L. Hartnell, Richard J. Nowakowski, Michael D. Plummer,