Graph functionality

Abstract

Let $G=(V,E)$ be a graph and $A$ its adjacency matrix. We say that a vertex $y\in V$ is a function of vertices $x_1,\dots ,x_k\in V$ if there exists a Boolean function $f$ of $k$ variables such that for any vertex $z\in V-\{y,x_1,\dots ,x_k\}$, $A(y,z)=f(A(x_1,z),\dots ,A(x_k,z))$. The functionality $fun(y)$ of vertex $y$ is the minimum $k$ such that $y$ is a function of $k$ vertices. The functionality $fun(G)$ of the graph $G$ is $\underset{H}{\max }\underset{y\in V(H)}{\min }fun(y)$, where the maximum is taken over all induced subgraphs $H$ of $G$. In the present paper, we show that functionality generalizes simultaneously several other graph parameters, such as degeneracy or clique-width, by proving that bounded degeneracy or bounded clique-width imply bounded functionality. Moreover, we show that this generalization is proper by revealing classes of graphs of unbounded degeneracy and clique-width, where functionality is bounded by a constant. This includes permutation graphs, unit interval graphs and line graphs. We also observe that bounded functionality implies bounded VC-dimension, i.e. graphs of bounded VC-dimension extend graphs of bounded functionality, and this extension is also proper.