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.

05C75 Structural characterization of families of graphs
05C15 Coloring of graphs and hypergraphs
05C12 Distance in graphs
05C45 Eulerian and Hamiltonian graphs
Full Text: Link EuDML