In this paper we introduce a new graph class denoted as Gen( ∗ ;P3,C3,C5). It contains all graphs that can be generated via split composition by using paths P3 and cycles C3 and C5 as components. This new graph class extends the well known class of distance-hereditary graphs, which corresponds to Gen( ∗ ;P3,C3). For the new class we provide efficient algorithms for several basic combinatorial problems: recognition, stretch number, stability number, clique number, domination number, chromatic number, graph isomorphism, and clique width.
Using Split Composition to Extend Distance-Hereditary Graphs in a Generative Way - (Extended Abstract).
CICERONE, SERAFINO
2011-01-01
Abstract
In this paper we introduce a new graph class denoted as Gen( ∗ ;P3,C3,C5). It contains all graphs that can be generated via split composition by using paths P3 and cycles C3 and C5 as components. This new graph class extends the well known class of distance-hereditary graphs, which corresponds to Gen( ∗ ;P3,C3). For the new class we provide efficient algorithms for several basic combinatorial problems: recognition, stretch number, stability number, clique number, domination number, chromatic number, graph isomorphism, and clique width.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
