Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2302.11862 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912402694471680 |
|---|---|
| author | Dvořák, Pavel Folwarczný, Lukáš Opler, Michal Pudlák, Pavel Šámal, Robert Vu, Tung Anh |
| author_facet | Dvořák, Pavel Folwarczný, Lukáš Opler, Michal Pudlák, Pavel Šámal, Robert Vu, Tung Anh |
| contents | Functionality ($\mathrm{fun}$) is a graph parameter that generalizes graph degeneracy defined by Alecu et al. [JCTB, 2021]. They research the relation of functionality to many other graphs parameters (tree-width, clique-width, VC-dimension, etc.). Extending their research, we completely characterize the functionality of random graph $G(n,p)$ for all possible $p$. We provide matching (up to a constant factor) lower and upper bound for a large range of $p$. It follows from our bounds for $G(n,p)$, that the maximum functionality (roughly $\sqrt{n}$) is achieved for $p \approx 1/\sqrt{n}$. We complement this by showing that every graph $G$ on $n$ vertices have $\mathrm{fun}(G) \le O(\sqrt{ n \ln n})$ and we give a nearly matching $Ω(\sqrt{n})$-lower bound provided by incident graphs of projective planes. Previously known lower bounds for functionality were only logarithmic in the number of vertices.
Further, we study a related graph parameter symmetric difference ($\mathrm{sd}$), the minimum of $|N(u) ~Δ~ 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$. They asked whether the functionality of interval graphs is bounded. Recently, Dallard et al. [RiM, 2024] answered this positively and they constructed an interval graph $G$ with $\mathrm{sd}(G) = Θ(\sqrt[4]{n})$ (even though they did not mention the explicit bound), i.e., they separate the functionality and symmetric difference of interval graphs. We show that $\mathrm{sd}$ of interval graphs is at most $O(\sqrt[3]{n})$ and we provide a different example of an interval graph $G$ with $\mathrm{sd}(G) = Θ(\sqrt[4]{n})$. Further, we show that $\mathrm{sd}$ of circular arc graphs is $Θ(\sqrt{n})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_11862 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters Dvořák, Pavel Folwarczný, Lukáš Opler, Michal Pudlák, Pavel Šámal, Robert Vu, Tung Anh Combinatorics Discrete Mathematics Functionality ($\mathrm{fun}$) is a graph parameter that generalizes graph degeneracy defined by Alecu et al. [JCTB, 2021]. They research the relation of functionality to many other graphs parameters (tree-width, clique-width, VC-dimension, etc.). Extending their research, we completely characterize the functionality of random graph $G(n,p)$ for all possible $p$. We provide matching (up to a constant factor) lower and upper bound for a large range of $p$. It follows from our bounds for $G(n,p)$, that the maximum functionality (roughly $\sqrt{n}$) is achieved for $p \approx 1/\sqrt{n}$. We complement this by showing that every graph $G$ on $n$ vertices have $\mathrm{fun}(G) \le O(\sqrt{ n \ln n})$ and we give a nearly matching $Ω(\sqrt{n})$-lower bound provided by incident graphs of projective planes. Previously known lower bounds for functionality were only logarithmic in the number of vertices. Further, we study a related graph parameter symmetric difference ($\mathrm{sd}$), the minimum of $|N(u) ~Δ~ 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$. They asked whether the functionality of interval graphs is bounded. Recently, Dallard et al. [RiM, 2024] answered this positively and they constructed an interval graph $G$ with $\mathrm{sd}(G) = Θ(\sqrt[4]{n})$ (even though they did not mention the explicit bound), i.e., they separate the functionality and symmetric difference of interval graphs. We show that $\mathrm{sd}$ of interval graphs is at most $O(\sqrt[3]{n})$ and we provide a different example of an interval graph $G$ with $\mathrm{sd}(G) = Θ(\sqrt[4]{n})$. Further, we show that $\mathrm{sd}$ of circular arc graphs is $Θ(\sqrt{n})$. |
| title | Bounds on Functionality and Symmetric Difference -- Two Intriguing Graph Parameters |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2302.11862 |