On interval number in cycle convexity
Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. R...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2018-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3812/pdf |
| _version_ | 1811153598142218240 |
|---|---|
| author | Julio Araujo Guillaume Ducoffe Nicolas Nisse Karol Suchan |
| author_facet | Julio Araujo Guillaume Ducoffe Nicolas Nisse Karol Suchan |
| author_sort | Julio Araujo |
| collection | DOAJ |
| description | Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by $in_{cc} (G)$, is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S.In this work, first we provide bounds on $in_{cc} (G)$ and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether $in_{cc} (G)$ ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtainthat $in_{cc} (G)$ cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = N P ).On the positive side, we present polynomial-time algorithms to compute $in_{cc} (G)$ for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q − 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G.Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems. |
| first_indexed | 2024-04-25T01:59:04Z |
| format | Article |
| id | doaj.art-f61ba853d71e4b7780b66619d792d4b1 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:59:04Z |
| publishDate | 2018-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-f61ba853d71e4b7780b66619d792d4b12024-03-07T15:36:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502018-05-01Vol. 20 no. 1Graph Theory10.23638/DMTCS-20-1-133812On interval number in cycle convexityJulio Araujo0Guillaume Ducoffe1Nicolas Nisse2https://orcid.org/0000-0003-4500-5078Karol Suchan3https://orcid.org/0000-0003-0793-0924Parallelism, Graphs and Optimization Research GroupCombinatorics, Optimization and Algorithms for TelecommunicationsCombinatorics, Optimization and Algorithms for TelecommunicationsFacultad de Ingeniería y Ciencias [Santiago]Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by $in_{cc} (G)$, is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S.In this work, first we provide bounds on $in_{cc} (G)$ and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether $in_{cc} (G)$ ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtainthat $in_{cc} (G)$ cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = N P ).On the positive side, we present polynomial-time algorithms to compute $in_{cc} (G)$ for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q − 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G.Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems.https://dmtcs.episciences.org/3812/pdfconvexitydomination problems in graphsinterval numbergraph convexitycomplexitycomplexity and algorithmsdominating setgraph[ info.info-cc ] computer science [cs]/computational complexity [cs.cc][ info.info-dm ] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Julio Araujo Guillaume Ducoffe Nicolas Nisse Karol Suchan On interval number in cycle convexity Discrete Mathematics & Theoretical Computer Science convexity domination problems in graphs interval number graph convexity complexity complexity and algorithms dominating set graph [ info.info-cc ] computer science [cs]/computational complexity [cs.cc] [ info.info-dm ] computer science [cs]/discrete mathematics [cs.dm] |
| title | On interval number in cycle convexity |
| title_full | On interval number in cycle convexity |
| title_fullStr | On interval number in cycle convexity |
| title_full_unstemmed | On interval number in cycle convexity |
| title_short | On interval number in cycle convexity |
| title_sort | on interval number in cycle convexity |
| topic | convexity domination problems in graphs interval number graph convexity complexity complexity and algorithms dominating set graph [ info.info-cc ] computer science [cs]/computational complexity [cs.cc] [ info.info-dm ] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/3812/pdf |
| work_keys_str_mv | AT julioaraujo onintervalnumberincycleconvexity AT guillaumeducoffe onintervalnumberincycleconvexity AT nicolasnisse onintervalnumberincycleconvexity AT karolsuchan onintervalnumberincycleconvexity |