Complexes of graphs with bounded matching size

Details Complexes of graphs with bounded matching size Complexes of graphs with bounded matching size

2004-10-15

arxiv.org/abs/math/0410345v1

Mathematics

Combinatorics

20 pages

Scientific paper

For positive integers k,n, we investigate the simplicial complex NM_k(n) of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers r,s and k the simplicial complex BNM_k(n) of all bipartite graphs G on bipartition [r] \cup [\bar{s}] such that there is no matching of size k in G, and obtain results similar to those obtained for NM_k(n).

Affiliated with

Also associated with

No associations

Rating

Complexes of graphs with bounded matching size does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexes of graphs with bounded matching size, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexes of graphs with bounded matching size will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-290202