Isolation critical graphs under multiple edge subdivision
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914414170472448 |
|---|---|
| author | Bartolo, Karl Borg, Peter Dettlaff, Magda Lemańska, Magdalena Żyliński, Paweł |
| author_facet | Bartolo, Karl Borg, Peter Dettlaff, Magda Lemańska, Magdalena Żyliński, Paweł |
| contents | This paper introduces the notion of an $(ι,q)$-critical graph. The isolation number of a graph $G$, denoted by $ι(G)$ and also known as the vertex-edge domination number of $G$, is the size of a smallest subset $D$ of the vertex set of $G$ such that the subgraph induced by the set of vertices that are not in the closed neighbourhood of $D$ has no edges. A graph $G$ is $(ι,q)$-critical if every subdivision of $q$ edges of $G$ gives a graph whose isolation number is greater than $ι(G)$, and $G$ has $q-1$ edges such that subdividing them gives a graph whose isolation number is $ι(G)$. We show that an $(ι,q)$-critical graph exists for every integer $q \ge 1$. We prove that if $G$ is a connected $m$-edge non-star graph, then $G$ is $(ι,q)$-critical for some $q \le m - 1$. We show that this bound is best possible. We provide a general characterization of $(ι,1)$-critical graphs as well as a constructive characterization of $(ι,1)$-critical trees, demonstrating that $(ι,1)$-criticality can be checked in linear time for trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_22980 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Isolation critical graphs under multiple edge subdivision Bartolo, Karl Borg, Peter Dettlaff, Magda Lemańska, Magdalena Żyliński, Paweł Combinatorics Discrete Mathematics Data Structures and Algorithms 05C05, 05C35, 05C69 This paper introduces the notion of an $(ι,q)$-critical graph. The isolation number of a graph $G$, denoted by $ι(G)$ and also known as the vertex-edge domination number of $G$, is the size of a smallest subset $D$ of the vertex set of $G$ such that the subgraph induced by the set of vertices that are not in the closed neighbourhood of $D$ has no edges. A graph $G$ is $(ι,q)$-critical if every subdivision of $q$ edges of $G$ gives a graph whose isolation number is greater than $ι(G)$, and $G$ has $q-1$ edges such that subdividing them gives a graph whose isolation number is $ι(G)$. We show that an $(ι,q)$-critical graph exists for every integer $q \ge 1$. We prove that if $G$ is a connected $m$-edge non-star graph, then $G$ is $(ι,q)$-critical for some $q \le m - 1$. We show that this bound is best possible. We provide a general characterization of $(ι,1)$-critical graphs as well as a constructive characterization of $(ι,1)$-critical trees, demonstrating that $(ι,1)$-criticality can be checked in linear time for trees. |
| title | Isolation critical graphs under multiple edge subdivision |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C05, 05C35, 05C69 |
| url | https://arxiv.org/abs/2602.22980 |