Bounds on functionality and symmetric difference - two intriguing graph parameters

Result code in 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>

Alternative codes found

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

Result on the web

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

Result language

angličtina

Original language name

Bounds on functionality and symmetric difference - two intriguing graph parameters

Original language description

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

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10101 - Pure mathematics

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

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

Article name in the collection

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-031-43379-5

ISSN

0302-9743

e-ISSN

—

Number of pages

14

Pages from-to

305-318

Publisher name

Springer

Place of publication

Cham

Event location

Fribourg

Event date

Jun 28, 2023

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001162209000022