Bounds on functionality and symmetric difference - two intriguing graph parameters

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F23%3A00579481" target="_blank" >RIV/67985840:_____/23:00579481 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21240/23:00369027 RIV/00216208:11320/23:10474496

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-031-43380-1_22" target="_blank" >https://doi.org/10.1007/978-3-031-43380-1_22</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-43380-1_22" target="_blank" >10.1007/978-3-031-43380-1_22</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bounds on functionality and symmetric difference - two intriguing graph parameters

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Bounds on functionality and symmetric difference - two intriguing graph parameters

Popis výsledku anglicky

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

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-031-43379-5

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

14

Strana od-do

305-318

Název nakladatele

Springer

Místo vydání

Cham

Místo konání akce

Fribourg

Datum konání akce

28. 6. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001162209000022