The poset on connected induced subgraphs of a graph need not be Sperner
Order, 1995•Springer
Suppose G is a finite connected graph. Let C (G) denote the inclusion ordering on the
connected vertex-induced subgraphs of G. Penrice asked whether C (G) is Sperner for
general graphs G. Answering Penrice's question in the negative, we present a tree T such
that C (T) is not Sperner. We also construct a related distributive lattice that is not Sperner.
connected vertex-induced subgraphs of G. Penrice asked whether C (G) is Sperner for
general graphs G. Answering Penrice's question in the negative, we present a tree T such
that C (T) is not Sperner. We also construct a related distributive lattice that is not Sperner.
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.
Springer