Mathematics – Combinatorics
Scientific paper
2009-03-24
Mathematics
Combinatorics
30 pages, 5 figures. This is the second version. Conjecture 4.1 from the previous version has been disproved, and the relevant
Scientific paper
One of the more recent generalizations of the Erd\"os-Ko-Rado theorem, formulated by Holroyd, Spencer and Talbot, defines the Erd\"os-Ko-Rado property for graphs in the following manner: for a graph G and a positive integer r, G is said to be r-EKR if no intersecting subfamily of the family of all independent vertex sets of size r is larger than the largest star, where a star centered at a vertex v is the family of all independent sets of size $r$ containing v. In this paper, we prove that if G is a disjoint union of chordal graphs, including at least one singleton, then G is r-EKR if $r\leq mu(G)/2$, where mu(G) is the minimum size of a maximal independent set. We will also prove Erd\"os-Ko-Rado results for chains of complete graphs, which are a class of chordal graphs obtained by blowing up edges of a path into complete graphs. We also consider similar problems for ladder graphs and trees, and prove preliminary results for these graphs.
Hurlbert Glenn
Kamat Vikram
No associations
LandOfFree
Erdös-Ko-Rado theorems for chordal and bipartite graphs 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 Erdös-Ko-Rado theorems for chordal and bipartite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Erdös-Ko-Rado theorems for chordal and bipartite graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-67718