Threshold graphs, shifted complexes, and graphical complexes

DOI10.1016/J.DISC.2006.11.018MaRDI QIDQ2455583zbMATH OpenOpenAlexFDO

Authors Caroline Klivans

Publication date 25 October 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703114

zbMATH Keywords

dominant setindependent setneighborhood complexshifted complexThreshold graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Abstract: We consider a variety of connections between threshold graphs, shifted complexes, and simplicial complexes naturally formed from a graph. These graphical complexes include the independent set, neighborhood, and dominance complexes. We present a number of structural results and relations among them including new characterizations of the class of threshold graphs.

Recommendations

• A combinatorial shifting method on multicomplexes with applications to simplicial complexes and simple graphs.
• scientific article; zbMATH DE number 2218519
• Threshold hypergraphs
• Obstructions to shiftedness
• A class of threshold and domishold graphs: Equistable and equidominating graphs

Cites work

• Combinatorics and commutative algebra.
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Obstructions to shiftedness
• On a conjecture of milner on k-graphs with non-disjoint edges
• Shifted set families, degree sequences, and plethysm
• The topology of the independence complex
• Threshold graphs and related topics
• Threshold hypergraphs

Cited in

(22)

• Neighborhood and domination polynomials of graphs
• Obstructions to shiftedness
• \(b\)-vectors of chordal graphs
• Clique vectors of \(k\)-connected chordal graphs
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• Minkowski complexes and convex threshold dimension
• Erdős-Ko-Rado theorems for simplicial complexes
• A combinatorial shifting method on multicomplexes with applications to simplicial complexes and simple graphs.
• Vertex decomposable graphs and obstructions to shellability
• Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
• Linear separation of connected dominating sets in graphs
• Simplicial complexes obtained from qualitative probability orders
• On generalized shift graphs
• scientific article; zbMATH DE number 2218519 (Why is no real title available?)
• An effective solution to convex 1-body N-representability
• Weighted and roughly weighted simple games
• Shellable quasi-forests and their h-triangles
• Dominance complexes, neighborhood complexes and combinatorial Alexander duals
• Simplicial complexes with many facets are vertex decomposable
• Stanley-Reisner rings of neighborhood complexes and linear resolutions
• Shellable complexes and topology of diagonal arrangements
• Cores of simplicial complexes

This page was built for publication: Threshold graphs, shifted complexes, and graphical complexes

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