Article contents
On Iterated Image Size for Point-Symmetric Relations
Published online by Cambridge University Press: 01 January 2008
Abstract
Let Γ =(V,E) be a point-symmetric reflexive relation and let υ ∈ V such that |Γ(υ)| is finite (and hence |Γ(x)| is finite for all x, by the transitive action of the group of automorphisms). Let j ∈ℕ be an integer such that Γj(υ)∩ Γ−(υ)={υ}. Our main result states that
As an application we have |Γj(υ)| ≥ 1+(|Γ(υ)|−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äggkvist conjecture for vertex-symmetric graphs and generalizes an additive result of Shepherdson.
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2007
References
- 5
- Cited by