Getting new algorithmic results by extending distance-hereditary graphs via split composition

Serafino Cicerone; Gabriele Di Stefano

doi:10.7717/peerj-cs.627

Getting new algorithmic results by extending distance-hereditary graphs via split composition

PeerJ Comput Sci. 2021 Jul 7:7:e627. doi: 10.7717/peerj-cs.627. eCollection 2021.

Authors

Serafino Cicerone¹, Gabriele Di Stefano¹

Affiliation

¹ Department of Information Engineering, Computer Science and Mathematics, University of L'Aquila, L'Aquila, Italy.

Abstract

In this paper, we consider the graph class denoted as Gen(∗;P₃,C₃,C₅). It contains all graphs that can be generated by the split composition operation using path P₃, cycle C₃, and any cycle C₅ as components. This graph class extends the well-known class of distance-hereditary graphs, which corresponds, according to the adopted generative notation, to Gen(∗;P₃,C₃). We also use the concept of stretch number for providing a relationship between Gen(∗;P₃,C₃) and the hierarchy formed by the graph classes DH(k), with k ≥1, where DH(1) also coincides with the class of distance-hereditary graphs. For the addressed graph class, we prove there exist efficient algorithms for several basic combinatorial problems, like recognition, stretch number, stability number, clique number, domination number, chromatic number, and graph isomorphism. We also prove that graphs in the new class have bounded clique-width.

Keywords: Distance-hereditary graphs; Graph algorithms; Graph classes; Split decomposition; Stretch number.

Grants and funding

The authors received no funding for this work.