Graph functionality

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, \ldots, x_k}$,$A(y,z)=f(A(x_1,z),\ldots,A(x_k,z))$\mathrm{.}Thefunctionality$fun(y)$ofvertex$y$istheminimum$k$suchthat$y$isafunctionof$k$vertices\mathrm{.}Thefunctionality$fun(G)$ofthegraph$G$is$\max\limits_H\min\limits_{y\in V(H)}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.