Cayley graph of a Boolean function

The boolean_cayley_graph module defines a function that contructs the Cayley graph of a Boolean function.

AUTHORS:

Paul Leopardi (2016-08-21): initial version

EXAMPLES:

sage: from boolean_cayley_graphs.boolean_cayley_graph import boolean_cayley_graph
sage: f = lambda n: (n // 2) % 2
sage: [f(i) for i in range(4)]
[0, 0, 1, 1]
sage: g = boolean_cayley_graph(2, f)
sage: g.adjacency_matrix()
[0 0 1 1]
[0 0 1 1]
[1 1 0 0]
[1 1 0 0]

REFERENCES:

Bernasconi and Codenotti [BC1999].

boolean_cayley_graphs.boolean_cayley_graph.boolean_cayley_graph(dim, f)[source]

Construct the Cayley graph of a Boolean function.

Given the non-negative integer dim and the function f, a Boolean function that takes a non-negative integer argument, the function Boolean_Cayley_graph constructs the Cayley graph of f as a Boolean function on \(\mathbb{F}_2^{dim}\), with the lexicographica ordering. The value f(0) is assumed to be 0, so the graph is always simple.

INPUT:

dim – integer. The Boolean dimension of the given function.
f – function. A Boolean function expressed as a Python function taking non-negative integer arguments.

OUTPUT:

A Graph object representing the Cayley graph of f.

EXAMPLES:

The Cayley graph of the function f where \(f(n) = n \mod 2\).

sage: from boolean_cayley_graphs.boolean_cayley_graph import boolean_cayley_graph
sage: f = lambda n: n % 2
sage: g = boolean_cayley_graph(2, f)
sage: g.adjacency_matrix()
[0 1 0 1]
[1 0 1 0]
[0 1 0 1]
[1 0 1 0]