Using split composition to extend distance-hereditary graphs in a generative way
S Cicerone - Theory and Applications of Models of Computation: 8th …, 2011 - Springer
Theory and Applications of Models of Computation: 8th Annual Conference, TAMC …, 2011•Springer
In this paper we introduce a new graph class denoted as Gen (∗; P 3, C 3, C 5). It contains
all graphs that can be generated via split composition by using paths P 3 and cycles C 3 and
C 5 as components. This new graph class extends the well known class of distance-
hereditary graphs, which corresponds to Gen (∗; P 3, C 3). 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 …
all graphs that can be generated via split composition by using paths P 3 and cycles C 3 and
C 5 as components. This new graph class extends the well known class of distance-
hereditary graphs, which corresponds to Gen (∗; P 3, C 3). 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 …
Abstract
In this paper we introduce a new graph class denoted as Gen( ∗ ;P 3,C 3,C 5). It contains all graphs that can be generated via split composition by using paths P 3 and cycles C 3 and C 5 as components. This new graph class extends the well known class of distance-hereditary graphs, which corresponds to Gen( ∗ ;P 3,C 3). 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.
Springer
Showing the best result for this search. See all results
