The complement of a connected bipartite graph is vertex decomposable

Authors Mohammad Mahmoudi, Amir Mousivand, Siamak Yassemi

Publication date 25 February 2009

Structural characterization of families of graphs (05C75) Special types (Cohen-Macaulay, Gorenstein, Buchsbaum, etc.) (13H10)

Abstract: Associated to a simple undirected graph

G

is a simplicial complex

D e l t a_{G}

whose faces correspond to the independent sets of

G

. A graph

G

is called vertex decomposable if

D e l t a_{G}

is a vertex decomposable simplicial complex. We are interested in determining what families of graph have the property that the complement of

G

, denoted by

o v e r l i n e G

, is vertex decomposable. We obtain the result that the complement of a connected bipartite graph is vertex decomposable and so it is Cohen-Macaulay due to pureness of

D e l t a_{o v e r l i n e G}

.

This page was built for publication: The complement of a connected bipartite graph is vertex decomposable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6212904)