{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:56:32Z","timestamp":1760234192780,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T00:00:00Z","timestamp":1616630400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Cicerone and Di Stefano defined and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k 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 k-distance-hereditary graphs such that k&lt;2. 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.<\/jats:p>","DOI":"10.3390\/a14040105","type":"journal-article","created":{"date-parts":[[2021,3,25]],"date-time":"2021-03-25T14:51:12Z","timestamp":1616683872000},"page":"105","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Quasi-Hole Detection Algorithm for Recognizing k-Distance-Hereditary Graphs, with k &lt; 2"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8893-9335","authenticated-orcid":false,"given":"Serafino","family":"Cicerone","sequence":"first","affiliation":[{"name":"Department of Information Engineering, Computer Science and Mathematics, University of L\u2019Aquila, I-67100 L\u2019Aquila, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2021,3,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","article-title":"Distance-hereditary graphs","volume":"28","author":"Howorka","year":"1977","journal-title":"Q. J. Math."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","article-title":"Distance-hereditary graphs","volume":"41","author":"Bandelt","year":"1986","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., and Spinrad, J.P. (1999). Graph Classes: A Survey, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898719796"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/(SICI)1097-0037(199805)31:3<177::AID-NET4>3.0.CO;2-C","article-title":"A linear-time algorithm for connected r-domination and Steiner tree on distance-hereditary graphs","volume":"31","author":"Dragan","year":"1998","journal-title":"Networks"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1007\/3-540-63890-3_37","article-title":"Dynamic Programming on Distance-Hereditary Graphs","volume":"Volume 1350","author":"Chang","year":"1997","journal-title":"International Symposium on Algorithms and Computation"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-540-77120-3_6","article-title":"Dynamic distance hereditary graphs using split decomposition","volume":"Volume 4835","author":"Gioan","year":"2007","journal-title":"International Symposium on Algorithms and Computation"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2809","DOI":"10.1007\/s00453-020-00705-7","article-title":"Paired-Domination Problem on Distance-Hereditary Graphs","volume":"82","author":"Lin","year":"2020","journal-title":"Algorithmica"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1002\/net.1","article-title":"Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs","volume":"37","author":"Nicolai","year":"2001","journal-title":"Networks"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"6157","DOI":"10.1016\/j.disc.2007.11.039","article-title":"Clique-width of graphs defined by one-vertex extensions","volume":"308","author":"Rao","year":"2008","journal-title":"Discret. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1472","DOI":"10.1006\/jpdc.2001.1728","article-title":"Compact-Port Routing Models and Applications to Distance-Hereditary Graphs","volume":"61","author":"Cicerone","year":"2001","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_11","first-page":"213","article-title":"Distance-hereditary graphs and multidestination message-routing in multicomputers","volume":"13","author":"Esfahanian","year":"1993","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0166-218X(00)00227-4","article-title":"Graphs with bounded induced distance","volume":"108","author":"Cicerone","year":"2001","journal-title":"Discret. Appl. Math."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/j.endm.2011.05.064","article-title":"Characterizations of Graphs with Stretch Number less than 2","volume":"37","author":"Cicerone","year":"2011","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/j.jda.2004.04.002","article-title":"Networks with small stretch number","volume":"2","author":"Cicerone","year":"2004","journal-title":"J. Discret. Algorithms"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s00453-006-1225-y","article-title":"Detecting Holes and Antiholes in Graphs","volume":"47","author":"Nikolopoulos","year":"2007","journal-title":"Algorithmica"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","article-title":"Completely separable graphs","volume":"27","author":"Hammer","year":"1990","journal-title":"Discret. Appl. Math."},{"key":"ref_17","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2001). Introduction to Algorithms, The MIT Press and McGraw-Hill Book Company. [2nd ed.]."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-642-20877-5_29","article-title":"Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way\u2014(Extended Abstract)","volume":"Volume 6648","author":"Cicerone","year":"2011","journal-title":"International Conference on Theory and Applications of Models of Computation"},{"key":"ref_19","first-page":"926","article-title":"On Building Networks with Limited Stretch Factor","volume":"Volume 1150","author":"Cicerone","year":"2020","journal-title":"Web, Artificial Intelligence and Network Applications, Proceedings of the Workshops of the 34th International Conference on Advanced Information Networking and Applications, AINA, Caserta, Italy, 15\u201317 Aprli 2020"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/105\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:41:06Z","timestamp":1760161266000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,25]]},"references-count":19,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["a14040105"],"URL":"https:\/\/doi.org\/10.3390\/a14040105","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,3,25]]}}}