Large Cayley digraphs and bipartite Cayley digraphs of odd diameters

DOI10.1016/J.DISC.2017.02.005MaRDI QIDQ2400546zbMATHOpenAlexFDO

Authors Marcel Abas, Tomáš Vetrík

Publication date 29 August 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

diameterdegreeCayley digraphbipartite digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07) Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: Let $C_{d,k}$ be the largest number of vertices in a Cayley digraph of degree $d$ and diameter $k$, and let $B{C}_{d,k}$ be the largest order of a bipartite Cayley digraph for given $d$ and $k$. For every degree $dgeq2$ and for every odd $k$ we construct Cayley digraphs of order $2kleft(lfloorfracd2flooright{)}^k$ and diameter at most $k$, where $kge3$, and bipartite Cayley digraphs of order $2(k-1)left(lfloorfracd2flooright{)}^{k-1}$ and diameter at most $k$, where $kge5$. These constructions yield the bounds $C_{d,k}ge2kleft(lfloorfracd2flooright{)}^k$ for odd $kge3$ and $dgefrac{3}^{k}2k+1$, and $B{C}_{d,k}ge2(k-1)left(lfloorfracd2flooright{)}^{k-1}$ for odd $kge5$ and $dgefrac{3}^{k-1}k-1+1$. Our constructions give the best currently known bounds on the orders of large Cayley digraphs and bipartite Cayley digraphs of given degree and odd diameter $kge5$. In our proofs we use new techniques based on properties of group automorphisms of direct products of abelian groups.

Recommendations

• Large Cayley digraphs of given degree and diameter
• Large Cayley graphs of small diameter
• Large bipartite Cayley graphs of given degree and diameter
• Cayley graphs of given degree and diameters 3, 4 and 5
• Large butterfly Cayley graphs and digraphs

Cites work

• scientific article; zbMATH DE number 597594 (Why is no real title available?)
• Approaching the mixed Moore bound for diameter two by Cayley graphs
• Cycle prefix digraphs for symmetric interconnection networks
• Large Cayley digraphs of given degree and diameter
• Which Faber-Moore-Chen digraphs are Cayley digraphs?

Cited in

(8)

• Large bipartite Cayley graphs of given degree and diameter
• Large Cayley graphs of small diameter
• Abelian Cayley digraphs with asymptotically large order for any given degree
• scientific article; zbMATH DE number 784887 (Why is no real title available?)
• A note on partial Cayley graphs
• Large butterfly Cayley graphs and digraphs
• Large Cayley digraphs of given degree and diameter
• On bipartite Cayley graphs of small diameter

This page was built for publication: Large Cayley digraphs and bipartite Cayley digraphs of odd diameters

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