On Iterated Image Size for Point-Symmetric Relations

DOI10.1017/S0963548307008620MaRDI QIDQ5448990zbMATH OpenOpenAlexFDO

Authors Yahya Ould Hamidoune

Publication date 10 March 2008

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0704.0459

zbMATH Keywords

connectivitydigraphiterated neighborhoodvertex-symmetricvertex-transitive

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25)

Abstract: Let $Gamma=(V,E)$ be a point-symmetric reflexive relation and let $vinV$ 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 $jinN$ be an integer such that $Gamm{a}^j(v)capGamm{a}^{-}(v)=v$. Our main result states that ${\displaystyle }$ |Gamma ^{j} (v)|ge | Gamma ^{j-1} (v)| + |Gamma (v)|-1.${\displaystyle }$ As an application we have $|Gamm{a}^j(v)|ge1+(|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.

Recommendations

• On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity
• Seymour's second neighborhood conjecture for \(m\)-free, \(k\)-transitive, \(k\)-anti-transitive digraphs and some approaches
• On the girth of digraphs
• On the Caccetta-Häggkvist conjecture
• A conjecture on k-transitive digraphs

Cites work

• An application of connectivity theory in graphs to factorizations of elements in groups
• On small sumsets in an abelian group
• On the Addition of Elements of a Sequence
• Quelques problèmes de connexite dans les graphes orientes
• Sur les atomes d'un graphe de Cayley infini. (On the atoms of an infinite Cayley graph)
• Vosperian and superconnected abelian Cayley digraphs

Cited in

(7)

• A generalization of a theorem of Diderrich in additive group theory to vertex-transitive graphs
• On Seymour's second neighborhood conjecture of \(m\)-free digraphs
• Yahya Ould Hamidoune's mathematical journey: a critical review of his work
• On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity
• On the equivalence of descriptions of iterated pictures
• Openly disjoint circuits through a vertex in regular digraphs
• Extensions of the Scherk-Kemperman theorem

This page was built for publication: On Iterated Image Size for Point-Symmetric Relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5448990)