On iterated image size for point-symmetric relations

Details On iterated image size for point-symmetric relations On iterated image size for point-symmetric relations

2007-04-03

arxiv.org/abs/0704.0459v1

Mathematics

Combinatorics

Scientific paper

Let $\Gamma =(V,E)$ be a point-symmetric reflexive relation and let $v\in V$ such that $|\Gamma (v)|$ is finite (and hence $|\Gamma (x)|$ is finite for all $x$, by the transitive action of the group of automorphisms). Let $j\in \N$ be an integer such that $\Gamma ^j(v)\cap \Gamma ^{-}(v)=\{v\}$. Our main result states that $$ |\Gamma ^{j} (v)|\ge | \Gamma ^{j-1} (v)| + |\Gamma (v)|-1.$$ As an application we have $ |\Gamma ^{j} (v)| \ge 1+(|\Gamma (v)|-1)j.$ The last result confirms a recent conjecture of Seymour in the case of vertex-symmetric graphs. Also it gives a short proof for the validity of the Caccetta-H\"aggkvist conjecture for vertex-symmetric graphs and generalizes an additive result of Shepherdson.

Affiliated with

Also associated with

No associations

Rating

On iterated image size for point-symmetric relations 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 On iterated image size for point-symmetric relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On iterated image size for point-symmetric relations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-213170