Large Cayley digraphs and bipartite Cayley digraphs of odd diameters

DOI10.1016/J.DISC.2017.02.005zbMATH Open1369.05099arXiv1603.06013OpenAlexW2304273858MaRDI QIDQ2400546FDOQ2400546

Authors: Marcel Abas, Tomáš Vetrík 

Publication date: 29 August 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Which Faber-Moore-Chen digraphs are Cayley digraphs?
• Title not available (Why is that?)
• Cycle prefix digraphs for symmetric interconnection networks
• Title not available (Why is that?)
• Large Cayley digraphs of given degree and diameter

Cited In (6)

• Large Cayley graphs of small diameter
• Large bipartite Cayley graphs of given degree and diameter
• A note on partial Cayley graphs
• Large butterfly Cayley graphs and digraphs
• Title not available (Why is that?)
• Large Cayley digraphs of given degree and 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)