[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 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 $\mathrm{fun}(G) \le O(\sqrt{ n \log n})$ and we give a nearly matching $\Omega(\sqrt{n})$-lower bound provided by projective planes. Further, we study a related graph parameter \emph{symmetric difference}, the minimum of $|N(u) \Delta N(v)|$ over all pairs of vertices of the ``worst possible'' induced subgraph. It was observed by Alecu et al. that $\mathrm{fun}(G) \le \mathrm{sd}(G)+1$ for every graph $G$. We compare $\mathrm{fun}$ and $\mathrm{sd}$ for the class $\mathrm{INT}$ of interval graphs and $\mathrm{CA}$ of circular-arc graphs. We let $\mathrm{INT}_n$ denote the $n$-vertex interval graphs, similarly for $\mathrm{CA}_n$. Alecu et al. ask, whether $\mathrm{fun}(\mathrm{INT})$ is bounded. Dallard et al. answer this positively in a recent preprint. On the other hand, we show that $\Omega(\sqrt[4]{n}) \leq \mathrm{sd}(\mathrm{INT}_n) \leq O(\sqrt[3]{n})$. For the related class $\mathrm{CA}$ we show that $\mathrm{sd}(\mathrm{CA}_n) = \Theta(\sqrt{n})$. We propose a follow-up question: is $\mathrm{fun}(\mathrm{CA})$ bounded?
翻译:[Alecu 和 Al. : 图表功能, JCT2021] 定义功能, 是一个图形参数, 能够将图形变异化。 它们研究功能与许多其他图形参数( Tree- width, clique- width, VC- dimension 等) 的关系。 扩展它们的研究, 我们证明随机图形$G( n, p) 功能在大范围内的对数值。 之前已知的图形在数量上具有对数值的对数 。 我们显示, 对于每张G( $ $ ) 的对数, 我们显示 美元 美元( 美元 美元 美元 ) 的对数 。 ( 美元 美元 美元 美元 美元 ) 的对数 。