Nontrivial independent sets of bipartite graphs and cross-intersecting families

preprint2011arXivOpen access

Abstract

Let G(X,Y)G(X,Y) be a connected, non-complete bipartite graph with ∣X∣≤∣Y∣|X|\leq |Y|. An independent set AA of G(X,Y)G(X,Y) is said to be trivial if A⊆XA\subseteq X or A⊆YA\subseteq Y. Otherwise, AA is nontrivial. By α(X,Y)α(X,Y) we denote the size of maximal-sized nontrivial independent sets of G(X,Y)G(X,Y). We prove that if the automorphism group of G(X,Y)G(X,Y) is transitive on XX and YY, then α(X,Y)=∣Y∣−d(X)+1α(X,Y)=|Y|-d(X)+1, where d(X)d(X) is the common degree of vertices in XX. We also give the structures of maximal-sized nontrivial independent sets of G(X,Y)G(X,Y). As applications of this result, we give the upper bound of sizes of two cross-tt-intersecting families of finite sets, finite vector spaces and permutations.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.