×

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
PDF BibTeX XML Cite
Full Text: Link EuDML