Large Cayley digraphs and bipartite Cayley digraphs of odd diameters

Let Cd,k be the largest number of vertices in a Cayley digraph of degree d and diameter k, and let BCd,k be the largest order of a bipartite Cayley digraph for given d and k. For every degree d≥2 and for every odd k we construct Cayley digraphs of order 2k⌊d2⌋k and diameter at most k, where k≥3, and...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2017-06, Vol.340 (6), p.1162-1171
Main Authors: Abas, Marcel, Vetrík, Tomáš
Format: Article
Language:English
Subjects:
Bipartite digraph
Cayley digraph
Degree
Diameter
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let Cd,k be the largest number of vertices in a Cayley digraph of degree d and diameter k, and let BCd,k be the largest order of a bipartite Cayley digraph for given d and k. For every degree d≥2 and for every odd k we construct Cayley digraphs of order 2k⌊d2⌋k and diameter at most k, where k≥3, and bipartite Cayley digraphs of order 2(k−1)⌊d2⌋k−1 and diameter at most k, where k≥5. These constructions yield the bounds Cd,k≥2k⌊d2⌋k for odd k≥3 and d≥3k2k+1, and BCd,k≥2(k−1)⌊d2⌋k−1 for odd k≥5 and d≥3k−1k−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 k≥5. In our proofs we use new techniques based on properties of group automorphisms of direct products of abelian groups.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2017.02.005