Well-covered triangulations: Part IV

详细信息    查看全文

• 作者：Arthur S. Finbow^a ; ^{art.finbow@smu.ca" class="auth_mail" title="E-mail the corresponding author} ; Bert L. Hartnell^a ; ^{Bert.Hartnell@smu.ca" class="auth_mail" title="E-mail the corresponding author} ; Richard J. Nowakowski^b ; ^{r.nowakowski@dal.ca" class="auth_mail" title="E-mail the corresponding author} ; Michael D. Plummer^c ; ^{michael.d.plummer@vanderbilt.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Well-covered graph ; Maximal independent set ; 33-connected well-covered triangulation
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 December 2016
• 年：2016
• 卷：215
• 期：Complete
• 页码：71-94
• 全文大小：686 K

文摘

A graph G$G$ is said to be well-covered if every maximal independent set of vertices has the same cardinality. A plane (simple) graph in which each face is a triangle is called a (plane) triangulation  . In the first of a sequence of three papers the authors proved that there are no 5-connected plane well-covered triangulations. Clearly, the only plane triangulation which is exactly 2-connected is the triangle K₃$K_3$. Two subsequent papers culminated in the proof that there are exactly four well-covered plane triangulations which are exactly 4-connected.

It is the aim of the present paper to complete the characterization of well-covered plane triangulations by characterizing the infinite family of those well-covered triangulations of the plane which are exactly 3-connected.