Recognizing Relating Edges in Graphs without Cycles of Length 6
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914724582522880 |
|---|---|
| author | Levit, Vadim E. Tankus, David |
| author_facet | Levit, Vadim E. Tankus, David |
| contents | A graph $G$ is well-covered if all maximal independent sets are of the same cardinality. Let $w:V(G) \longrightarrow\mathbb{R}$ be a weight function. Then $G$ is $w$-well-covered if all maximal independent sets are of the same weight. An edge $xy \in E(G)$ is relating if there exists an independent set $S$ such that both $S \cup \{x\}$ and $S \cup \{y\}$ are maximal independent sets in the graph. If $xy$ is relating then $w(x)=w(y)$ for every weight function $w$ such that $G$ is $w$-well-covered. Relating edges play an important role in investigating $w$-well-covered graphs.
The decision problem whether an edge in a graph is relating is NP-complete. We prove that the problem remains NP-complete when the input is restricted to graphs without cycles of length $6$. This is an unexpected result because recognizing relating edges is known to be polynomially solvable for graphs without cycles of lengths $4$ and $6$, graphs without cycles of lengths $5$ and $6$, and graphs without cycles of lengths $6$ and $7$.
A graph $G$ belongs to the class $W_2$ if every two pairwise disjoint independent sets in $G$ are included in two pairwise disjoint maximum independent sets. It is known that if $G$ belongs to the class $W_2$, then it is well-covered. A vertex $v \in V(G)$ is shedding if for every independent set $S \subseteq V(G)-N[v]$, there exists a vertex $u \in N(v)$ such that $S \cup \{u\}$ is independent. Shedding vertices play an important role in studying the class $W_2$. Recognizing shedding vertices is co-NP-complete, even when the input is restricted to triangle-free graphs. We prove that the problem is co-NP-complete for graphs without cycles of length $6$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_14824 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Recognizing Relating Edges in Graphs without Cycles of Length 6 Levit, Vadim E. Tankus, David Combinatorics Discrete Mathematics 05C69 G.2.2 A graph $G$ is well-covered if all maximal independent sets are of the same cardinality. Let $w:V(G) \longrightarrow\mathbb{R}$ be a weight function. Then $G$ is $w$-well-covered if all maximal independent sets are of the same weight. An edge $xy \in E(G)$ is relating if there exists an independent set $S$ such that both $S \cup \{x\}$ and $S \cup \{y\}$ are maximal independent sets in the graph. If $xy$ is relating then $w(x)=w(y)$ for every weight function $w$ such that $G$ is $w$-well-covered. Relating edges play an important role in investigating $w$-well-covered graphs. The decision problem whether an edge in a graph is relating is NP-complete. We prove that the problem remains NP-complete when the input is restricted to graphs without cycles of length $6$. This is an unexpected result because recognizing relating edges is known to be polynomially solvable for graphs without cycles of lengths $4$ and $6$, graphs without cycles of lengths $5$ and $6$, and graphs without cycles of lengths $6$ and $7$. A graph $G$ belongs to the class $W_2$ if every two pairwise disjoint independent sets in $G$ are included in two pairwise disjoint maximum independent sets. It is known that if $G$ belongs to the class $W_2$, then it is well-covered. A vertex $v \in V(G)$ is shedding if for every independent set $S \subseteq V(G)-N[v]$, there exists a vertex $u \in N(v)$ such that $S \cup \{u\}$ is independent. Shedding vertices play an important role in studying the class $W_2$. Recognizing shedding vertices is co-NP-complete, even when the input is restricted to triangle-free graphs. We prove that the problem is co-NP-complete for graphs without cycles of length $6$. |
| title | Recognizing Relating Edges in Graphs without Cycles of Length 6 |
| topic | Combinatorics Discrete Mathematics 05C69 G.2.2 |
| url | https://arxiv.org/abs/2403.14824 |