<abstract xmlns="http://www.w3.org/1999/xhtml"><p>In the last decades many results have been proved on pseudo-randomness of binary sequences. In this series our goal is to show that using many of these results one can also construct large families of quasi-random, pseudo-random and strongly pseudo-random graphs. Indeed, it will be proved that if the first row of the adjacency matrix of a circulant graph forms a binary sequence which possesses certain pseudorandom properties (and there are many large families of binary sequences known with these properties), then the graph is quasi-random, pseudo-random or strongly pseudo-random, respectively. In particular, here in Part I we will construct large families of quasi-random graphs along these lines. (In Parts II and III we will present and study constructions for pseudo-random and <italic>strongly</italic> pseudo-random graphs, respectively.)</p></abstract>

In the last decades many results have been proved on pseudo-randomness of binary sequences. In this series our goal is to show that using many of these results one can also construct large families of quasi-random, pseudo-random and strongly pseudo-random graphs. Indeed, it will be proved that if the first row of the adjacency matrix of a circulant graph forms a binary sequence which possesses certain pseudorandom properties (and there are many large families of binary sequences known with these properties), then the graph is quasi-random, pseudo-random or strongly pseudo-random, respectively. In particular, here in Part I we will construct large families of quasi-random graphs along these lines. (In Parts II and III we will present and study constructions for pseudo-random and strongly pseudo-random graphs, respectively.)

Quasi-Random Graphs, Pseudo-Random Graphs and Pseudorandom Binary Sequences, I. (Quasi-Random Graphs)

Uniform distribution theory

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

In the last decades many results have been proved on pseudo-randomness of binary sequences. In this series our goal is to show that using many of these results...

Quasi-Random Graphs, Pseudo-Random Graphs and Pseudorandom Binary Sequences, I. (Quasi-Random Graphs)

Pubblicato online: 27 mar 2020

Pagine: 103 - 126

Ricevuto: 08 lug 2019

Accettato: 25 ott 2019

DOI: https://doi.org/10.2478/udt-2019-0017

Parole chiave
quasi-random graph, pseudo-random graph, pseudorandom binary sequence. Research partially supported by Hungarian National Research Development and Innovation Fund K119528

© 2019 József Borbély et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Quasi-Random Graphs, Pseudo-Random Graphs and Pseudorandom Binary Sequences, I. (Quasi-Random Graphs)

Pubblicato online: 27 mar 2020

Pagine: 103 - 126

Ricevuto: 08 lug 2019

Accettato: 25 ott 2019

DOI: https://doi.org/10.2478/udt-2019-0017

Parole chiavequasi-random graph, pseudo-random graph, pseudorandom binary sequence. Research partially supported by Hungarian National Research Development and Innovation Fund K119528

© 2019 József Borbély et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Parole chiave
quasi-random graph, pseudo-random graph, pseudorandom binary sequence. Research partially supported by Hungarian National Research Development and Innovation Fund K119528