Abstract
[Alecu et al.: Graph functionality, JCTB2021] define functionality, a graph parameter that generalizes graph degeneracy. They research the relation of functionality to many other graph parameters (tree-width, clique-width, VC-dimension, etc.).
Extending their research, we prove a logarithmic lower bound for functionality of random graph G(n, p) for large range of p. Previously known graphs have functionality logarithmic in number of vertices.
We show that for every graph G on n vertices we have fun (Formula presented) and we give a nearly matching (Formula presented) -lower bound provided by projective planes. Further, we study a related graph parameter symmetric difference, the minimum of (Formula presented) over all pairs of vertices of the "worst possible" induced subgraph.
It was observed by Alecu et al. that (Formula presented) for every graph G. We compare fun and sd for the class INT of interval graphs and CA of circular-arc graphs.
We let INTn denote the n-vertex interval graphs, similarly for CAn. Alecu et al. ask, whether fun (INT) is bounded.
Dallard et al. answer this positively in a recent preprint. On the other hand, we show that (Formula presented).
For the related class (Formula presented) we show that (Formula presented). We propose a follow-up question: is (Formula presented) bounded?