Number theoretic designs for directed regular graphs of small diameter

William D. Banks; Alessandro Conflitti; Igor E. Shparlinski

doi:10.1137/S0895480101396676

Number theoretic designs for directed regular graphs of small diameter

William D. Banks^*, Alessandro Conflitti, Igor E. Shparlinski

^*Corresponding author for this work

School of Computing

Research output: Contribution to journal › Article › peer-review

22 Downloads (Pure)

Abstract

In 1989, F. R. K. Chung gave a construction for certain directed h-regular graphs of small diameter. Her construction is based on finite fields, and the upper bound on the diameter of these graphs is derived from bounds for certain very short character sums. Here we present two similar constructions that are based on properties of discrete logarithms and exponential functions in residue rings modulo a prime power. Accordingly, we use bounds for certain sums with additive and multiplicative characters to estimate the diameter of our graphs. We also give a third construction that avoids the use of bounds for exponential sums.

Original language	English
Pages (from-to)	377-383
Number of pages	7
Journal	SIAM Journal on Discrete Mathematics
Volume	17
Issue number	3
DOIs	https://doi.org/10.1137/S0895480101396676
Publication status	Published - Jan 2004

Access to Document

10.1137/S0895480101396676

Publisher version (open access).pdfFinal published version, 213 KB

Cite this

@article{c4a527b96c49414797c2ed90fd8f9cea,

title = "Number theoretic designs for directed regular graphs of small diameter",

abstract = "In 1989, F. R. K. Chung gave a construction for certain directed h-regular graphs of small diameter. Her construction is based on finite fields, and the upper bound on the diameter of these graphs is derived from bounds for certain very short character sums. Here we present two similar constructions that are based on properties of discrete logarithms and exponential functions in residue rings modulo a prime power. Accordingly, we use bounds for certain sums with additive and multiplicative characters to estimate the diameter of our graphs. We also give a third construction that avoids the use of bounds for exponential sums.",

author = "Banks, \{William D.\} and Alessandro Conflitti and Shparlinski, \{Igor E.\}",

year = "2004",

month = jan,

doi = "10.1137/S0895480101396676",

language = "English",

volume = "17",

pages = "377--383",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Number theoretic designs for directed regular graphs of small diameter

AU - Banks, William D.

AU - Conflitti, Alessandro

AU - Shparlinski, Igor E.

PY - 2004/1

Y1 - 2004/1

N2 - In 1989, F. R. K. Chung gave a construction for certain directed h-regular graphs of small diameter. Her construction is based on finite fields, and the upper bound on the diameter of these graphs is derived from bounds for certain very short character sums. Here we present two similar constructions that are based on properties of discrete logarithms and exponential functions in residue rings modulo a prime power. Accordingly, we use bounds for certain sums with additive and multiplicative characters to estimate the diameter of our graphs. We also give a third construction that avoids the use of bounds for exponential sums.

AB - In 1989, F. R. K. Chung gave a construction for certain directed h-regular graphs of small diameter. Her construction is based on finite fields, and the upper bound on the diameter of these graphs is derived from bounds for certain very short character sums. Here we present two similar constructions that are based on properties of discrete logarithms and exponential functions in residue rings modulo a prime power. Accordingly, we use bounds for certain sums with additive and multiplicative characters to estimate the diameter of our graphs. We also give a third construction that avoids the use of bounds for exponential sums.

UR - https://www.scopus.com/pages/publications/4344621106

U2 - 10.1137/S0895480101396676

DO - 10.1137/S0895480101396676

M3 - Article

AN - SCOPUS:4344621106

SN - 0895-4801

VL - 17

SP - 377

EP - 383

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

Number theoretic designs for directed regular graphs of small diameter

Abstract

Access to Document

Other files and links

Fingerprint

Cite this