ON THE CAYLEY GRAPHS OF BOOLEAN FUNCTIONS

Lotfallah Pourfaraj, Modjtaba Ghorbani

DOI Number
https://doi.org/10.22190/FUMI2003873P
First page
873
Last page
885

Abstract


A Boolean function is a function $f:\Bbb{Z}_n^2 \rightarrow \{0,1\}$ and we denote the set of all $n$-variable Boolean functions by $BF_n$. For $f\in BF_n$ the vector $[{\rm W}_f(a_0),\ldots,{\rm W}_f(a_{2n-1})]$ is called the Walsh spectrum of $f$, where ${\rm W}_f(a)= \sum_{x\in V} (-1)^{f(x) \oplus ax}$, where $V_n$ is the vector space of dimension $n$ over the two-element field $F_2$. In this paper, we shall consider the Cayley graph $\Gamma_f$ associated with a Boolean function $f$. We shall also find a complete characterization of the bent Boolean functions of order $16$ and determine the spectrum of related Cayley graphs.In addition, we shall enumerate all orbits of the action of automorphism group on the set $BF_n$. 

Keywords

Boolean function; Walsh spectrum; Cayley graph; automorphism group.

Full Text:

PDF

References


References

A. R. Ashrafi and M. Ghorbani, MATCH Commun. Math. Comput. Chem. 60 (2008) 359.

A. R. Ashrafi, M. Ghorbani and M. Jalali, Digest Journal of Nanomaterials and Biostructures 3 (2008) 245.

A. R. Ashrafi, M. Jalali, M. Ghorbani and M. V. Diudea, MATCH Commun. Math. Comput. Chem. 60 (2008) 905.

M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi and M. Sudan, Linearity testing in characteristic two, IEEE Transactions on Information Theory 42 (1996) 1781-1795.

A. Bernasconi and B. Codenotti, Spectral analysis of Boolean functions as a graph eigenvalue problem, IEEE Transactions on Computers 48 (1999) 345-351.

N. Biggs, Algebraic Graph Theory, Cambridge Univ. Press, 1968.

J. F. Dillon, Elementary Hadamard difference sets, PhD thesis, University of Maryland, 1974.

P. W. Fowler and D. E. Manolopoulos, An Atlas of Fullerenes, Oxford Univ. Press, Oxford, 1995.

S. Fujita, Symmetry and Combinatorial Enumeration in Chemistry, Springer Verlag, Berlin, 1991.

M. Ghorbani, Enumeration of hetero-fullerenes: A survey, MATCH Commun. Math. Comput. Chem. 68 (2012) 381-414.

M. Ghorbani and A. R. Ashrafi, J. Comput. Theor. Nanosci. 3 (2006) 803-.

M. Ghorbani and M. Jalali, Digest Journal of Nanomaterials and Biostructures, 3 (2008) 269-.

H. W. Kroto, J. R. Heath, S. C. O’Brien, R.F. Curl and R. E. Smalley, Nature 318 (1985) 162-163.

G. Pólya and R. C. Read, Combinatorial enumeration of groups and chemical compounds, Springer, New York, 1987.

O. S. Rothaus, On bent functions, Journal of Combinatorial Theory 20A (1976) 300-305.

P. Sarkar, and S. Maitra, Nonlinearity bounds and constructions of resilient Boolean functions, In Advances in Cryptology-Crypto 2000, LNCS 1807 (2000) 515-532.

V. Taghvaei-Yazdelli and M. Ghorbani, Characterization of bipartite Cayley graphs in terms of Boolean functions, Journal of Information and Optimization Sciences 39 (2018) 1-18.




DOI: https://doi.org/10.22190/FUMI2003873P

Refbacks

  • There are currently no refbacks.




© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)