# zbMATH — the first resource for mathematics

On the Boolean function graph of a graph and on its complement. (English) Zbl 1110.05086
Summary: For any graph $$G$$, let $$V(G)$$ and $$E(G)$$ denote the vertex set and the edge set of $$G$$ respectively. The Boolean function graph $$B(G,L(G),\text{NINC} )$$ of $$G$$ is a graph with vertex set $$V(G)\cup E(G)$$ and two vertices in $$B(G,L(G),\text{NINC} )$$ are adjacent if and only if they correspond to two adjacent vertices of $$G$$, two adjacent edges of $$G$$ or to a vertex and an edge not incident to it in $$G$$. For brevity, this graph is denoted by $$B_1(G)$$. In this paper, structural properties of $$B_1(G)$$ and its complement including traversability and eccentricity properties are studied. In addition, solutions for Boolean function graphs that are total graphs, quasi-total graphs and middle graphs are obtained.

##### MSC:
 05C75 Structural characterization of families of graphs 05C15 Coloring of graphs and hypergraphs 05C12 Distance in graphs 05C45 Eulerian and Hamiltonian graphs
##### Keywords:
eccentricity; self-centered graph; middle graph
Full Text: