A Quasi-Hole Detection Algorithm for Recognizing <i>k</i>-Distance-Hereditary Graphs, with <i>k</i> < 2
Cicerone and Di Stefano defined and studied the class of <i>k</i>-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most <i>k</i> times the distance in the whole graph. The defined graphs represent a generalization of the wel...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/4/105 |
| _version_ | 1797539998804738048 |
|---|---|
| author | Serafino Cicerone |
| author_facet | Serafino Cicerone |
| author_sort | Serafino Cicerone |
| collection | DOAJ |
| description | Cicerone and Di Stefano defined and studied the class of <i>k</i>-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most <i>k</i> times the distance in the whole graph. The defined graphs represent a generalization of the well known distance-hereditary graphs, which actually correspond to 1-distance-hereditary graphs. In this paper we make a step forward in the study of these new graphs by providing characterizations for the class of all the <i>k</i>-distance-hereditary graphs such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo><</mo><mn>2</mn></mrow></semantics></math></inline-formula>. The new characterizations are given in terms of both forbidden subgraphs and cycle-chord properties. Such results also lead to devise a polynomial-time recognition algorithm for this kind of graph that, according to the provided characterizations, simply detects the presence of quasi-holes in any given graph. |
| first_indexed | 2024-03-10T12:53:50Z |
| format | Article |
| id | doaj.art-09180fdcc2144c0e860cfe602fdf8d66 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T12:53:50Z |
| publishDate | 2021-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-09180fdcc2144c0e860cfe602fdf8d662023-11-21T12:01:57ZengMDPI AGAlgorithms1999-48932021-03-0114410510.3390/a14040105A Quasi-Hole Detection Algorithm for Recognizing <i>k</i>-Distance-Hereditary Graphs, with <i>k</i> < 2Serafino Cicerone0Department of Information Engineering, Computer Science and Mathematics, University of L’Aquila, I-67100 L’Aquila, ItalyCicerone and Di Stefano defined and studied the class of <i>k</i>-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most <i>k</i> times the distance in the whole graph. The defined graphs represent a generalization of the well known distance-hereditary graphs, which actually correspond to 1-distance-hereditary graphs. In this paper we make a step forward in the study of these new graphs by providing characterizations for the class of all the <i>k</i>-distance-hereditary graphs such that <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo><</mo><mn>2</mn></mrow></semantics></math></inline-formula>. The new characterizations are given in terms of both forbidden subgraphs and cycle-chord properties. Such results also lead to devise a polynomial-time recognition algorithm for this kind of graph that, according to the provided characterizations, simply detects the presence of quasi-holes in any given graph.https://www.mdpi.com/1999-4893/14/4/105distance-hereditary graphsstretch numberrecognition problemforbidden subgraphshole detection |
| spellingShingle | Serafino Cicerone A Quasi-Hole Detection Algorithm for Recognizing <i>k</i>-Distance-Hereditary Graphs, with <i>k</i> < 2 Algorithms distance-hereditary graphs stretch number recognition problem forbidden subgraphs hole detection |
| title | A Quasi-Hole Detection Algorithm for Recognizing <i>k</i>-Distance-Hereditary Graphs, with <i>k</i> < 2 |
| title_full | A Quasi-Hole Detection Algorithm for Recognizing <i>k</i>-Distance-Hereditary Graphs, with <i>k</i> < 2 |
| title_fullStr | A Quasi-Hole Detection Algorithm for Recognizing <i>k</i>-Distance-Hereditary Graphs, with <i>k</i> < 2 |
| title_full_unstemmed | A Quasi-Hole Detection Algorithm for Recognizing <i>k</i>-Distance-Hereditary Graphs, with <i>k</i> < 2 |
| title_short | A Quasi-Hole Detection Algorithm for Recognizing <i>k</i>-Distance-Hereditary Graphs, with <i>k</i> < 2 |
| title_sort | quasi hole detection algorithm for recognizing i k i distance hereditary graphs with i k i 2 |
| topic | distance-hereditary graphs stretch number recognition problem forbidden subgraphs hole detection |
| url | https://www.mdpi.com/1999-4893/14/4/105 |
| work_keys_str_mv | AT serafinocicerone aquasiholedetectionalgorithmforrecognizingikidistancehereditarygraphswithiki2 AT serafinocicerone quasiholedetectionalgorithmforrecognizingikidistancehereditarygraphswithiki2 |