|
|||||
|
|
On well-covered triangulations: Part II |
|
| Authors: | Arthur S. Finbow Bert L. Hartnell |
| Affiliation: | a Department of Mathematics and Computing Science, Saint Mary’s University, Halifax, Canada B3H 3C3 b Department of Mathematics and Statistics, Dalhousie University, Halifax, Canada B3H 3J5 c Department of Mathematics, Vanderbilt University, Nashville, TN 37240, USA |
| Abstract: | A graph G 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 [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part I, Discrete Appl. Math., 132, 2004, 97-108] that there are no 5-connected planar well-covered triangulations. It is the aim of the present paper to completely determine the 4-connected well-covered triangulations containing two adjacent vertices of degree 4. In a subsequent paper [A. Finbow, B. Hartnell, R. Nowakowski, M. Plummer, On well-covered triangulations: Part III (submitted for publication)], we show that every 4-connected well-covered triangulation contains two adjacent vertices of degree 4 and hence complete the task of characterizing all 4-connected well-covered planar triangulations. There turn out to be only four such graphs. This stands in stark contrast to the fact that there are infinitely many 3-connected well-covered planar triangulations. |
| Keywords: | Well-covered graph Independent domination Planar triangulation |
| 本文献已被 ScienceDirect 等数据库收录！ | |