Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters

DOI10.1007/978-3-031-43380-1_22MaRDI QIDQ6427376zbMATH OpenOpenAlexFDO

Authors Pavel Dvořák, Lukáš Folwarczný, Michal Opler, Pavel Pudlák, Robert Šámal, Tung Anh Vu

Publication date 23 February 2023

Full work available at URL https://doi.org/10.1007/978-3-031-43380-1_22

Graph theory (including graph drawing) in computer science (68R10)

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 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

m a t h r m f u n (G) l e O (s q r t n l o g n)

and we give a nearly matching

O m e g a (s q r t n)

-lower bound provided by projective planes. Further, we study a related graph parameter emph{symmetric difference}, the minimum of

| N (u) D e l t a N (v) |

over all pairs of vertices of the ``worst possible induced subgraph. It was observed by Alecu et al. that $m a t h r m f u n (G) l e m a t h r m s d (G) + 1$ for every graph $G$ . We compare $m a t h r m f u n$ and $m a t h r m s d$ for the class $m a t h r m I N T$ of interval graphs and $m a t h r m C A$ of circular-arc graphs. We let $m a t h r m {I N T}_{n}$ denote the $n$ -vertex interval graphs, similarly for $m a t h r m {C A}_{n}$ . Alecu et al. ask, whether $m a t h r m f u n (m a t h r m I N T)$ is bounded. Dallard et al. answer this positively in a recent preprint. On the other hand, we show that $O m e g a (s q r t [4] n) l e q m a t h r m s d (m a t h r m {I N T}_{n}) l e q O (s q r t [3] n)$ . For the related class $m a t h r m C A$ we show that $m a t h r m s d (m a t h r m {C A}_{n}) = T h e t a (s q r t n)$ . We propose a follow-up question: is $m a t h r m f u n (m a t h r m C A)$ bounded?

Cited in

(1)

Graph problems and monotone classes

This page was built for publication: Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6427376)