Number Theoretic Designs for Directed Regular Graphs of Small Diameter

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

Type: Article

Publication Date: 2004-01-01

Citations: 0

DOI: https://doi.org/10.1137/s0895480101396676

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.

Locations

SIAM Journal on Discrete Mathematics - View
MOspace Institutional Repository (University of Missouri) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Cayley graphs generated by small degree polynomials over finite fields	2014	Igor E. Shparlinski
+	Cayley graphs generated by small degree polynomials over finite fields	2014	Igor E. Shparlinski
+	On the homogeneous algebraic graphs of large girth and their applications	2008	Tony Shaska Vasyl Ustimenko
+	Large graphs of diameter two and given degree	2011	Jozef Širáň‬ Jana Šiagiová Mária Ždímalová
+	Exponent of local ring extensions of Galois rings and digraphs of the $k$th power mapping	2017	Ittiwat TOCHAROENIRATTISAI Yotsanan Meemark
+	Distance-regular digraphs of girth 4	1986	H. Enomoto R.A Mena
+ PDF Chat	Diameter of some monomial digraphs	2016	Aleksandr Kodess Felix Lazebnik Steve Smith Joshua Sporre
+	Two Kinds of Constructions of Directed Strongly Regular Graphs from Partial Sum Families and Semi-direct Products of Groups	2020	Jingkun Zhou Zhiwen He Zhao Chai
+ PDF Chat	Exploring Ring Structures: Multiset Dimension Analysis in Compressed Zero-Divisor Graphs	2024	Nasir Ali Hafiz Muhammad Afzal Siddiqui Muhammad Imran Qureshi
+	Structures of power digraphs over the congruence equation $ x^p\equiv y\; (\text{mod}\; m) $ and enumerations	2021	Muhammad Haris Mateen Muhammad Khalid Mahmmod Dilshad Alghazzawi Jia Liu
+	Certain distance-regular digraphs and related rings of characteristic 4	1988	Robert A. Liebler R.A Mena
+	Parameters of Quadratic Residue Digraphs over Certain Finite Fields	2019	Louis Beaugris
+	Graph and number theoretic properties of certain maps over finite field	2020	Pratchayaporn Doemlim
+	Large "De Bruijn" Cayley graphs and digraphs	2015	David Bevan
+	Distance-regular digraphs of girth 4 over an extension ring of Z/4Z	1990	Mieko Yamada
+	Primitive graphs with small exponent and small scrambling index	2018	Ita Y Surbakti Saib Suwilo Ericha A Butar-butar Helda Oktaviani
+	The structure of the exponent set for finite cyclic groups	2008	Peter J. Dukes Sarada Herke
+ PDF Chat	Cayley Graphs Generated by Small Degree Polynomials over Finite Fields	2015	Igor E. Shparlinski
+	THE DIGRAPH OF THE SQUARE MAPPING ON QUOTIENT RINGS OVER THE GAUSSIAN INTEGERS	2011	Yotsanan Meemark NAWAPHON MAINGAM
+	The girth of a directed distance-regular graph(GROUPS AND COMBINATORICS)	1992	和正野村

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (9)

Action	Title	Year	Authors
+	Number theory with applications	1998	W C Winnie Li
+	Spectral Graph Theory	1996	Fan Chung
+	On Parameters of Some Graphs from Finite Fields	1993	Igor E. Shparlinski
+ PDF Chat	An estimate for character sums	1989	Nicholas M. Katz
+	Polynomial Factorisation and an Application to Regular Directed Graphs	1998	Stephen D. Cohen
+	ON THE DISTRIBUTION OF DIGITS IN PERIODIC FRACTIONS	1972	N. M. Korobov
+ PDF Chat	Diameters and eigenvalues	1989	Fan Chung
+	Basic Analytic Number Theory	1993	Anatolij A. Karatsuba Melvyn B. Nathanson
+	Number Theory with Applications	1996	W C Winnie Li