The poset on connected induced subgraphs of a graph need not be Sperner |
| |
Authors: | Michael S Jacobson André E Kézdy Steve Seif |
| |
Institution: | (1) Department of Mathematics, University of Louisville, 40292 Louisville, KY, USA |
| |
Abstract: | SupposeG is a finite connected graph. LetC(G) denote the inclusion ordering on the connected vertex-induced subgraphs ofG. Penrice asked whetherC(G) is Sperner for general graphsG. Answering Penrice's question in the negative, we present a treeT such thatC(T) is not Sperner. We also construct a related distributive lattice that is not Sperner. |
| |
Keywords: | 06A06 |
本文献已被 SpringerLink 等数据库收录! |