A CAN-free graph is defined to be a graph not containing subgraphs isomorphic to \(K_{1,3}\), the graph with degree sequence (1,2,2,3,3,3) which does not contain \(K_{1,3}\), or the graph with degree sequence (1,1,1,3,3,3). Every CAN-free graph G can be associated with another such graph G' with fewer nodes and having stability number exactly one less than that of G. This gives an efficient algorithm for determining the stability number of CAN-free graphs.
Recommendations
- Stability of graphs
- Stability of circulant graphs
- A note on stability of graphs
- scientific article; zbMATH DE number 4075101
- ON STABLE GRAPHS
- Stability results for graphs with a critical edge
- scientific article; zbMATH DE number 3933235
- Stability of graph pairs
- Stable properties of graphs
- Total domination stability in graphs
Cites work
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3904619 (Why is no real title available?)
- On maximal independent sets of vertices in claw-free graphs
Cited in
(19)- The struction of a graph: Application to CN-free graphs
- Hamiltonicity in claw-free graphs
- The struction algorithm for the maximum stable set problem revisited
- Claw-free graphs---a survey
- On the use of Boolean methods for the computation of the stability number
- Struction revisited
- Polynomially solvable cases for the maximum stable set problem
- On the complexity of the independent set problem in triangle graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Local transformations of graphs preserving independence number
- On the stability number of AH‐free graphs
- Diagonal Stability on Cactus Graphs and Application to Network Stability Analysis
- Weighted stability number of graphs and weighted satisfiability: the two facets of pseudo-Boolean optimization
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Stability preserving transformations of graphs
- The problem of independent sets in course schedule selection
- Pseudo-Boolean optimization
- Consensus algorithms for the generation of all maximal bicliques
- New applications of clique separator decomposition for the maximum weight stable set problem
This page was built for publication: Stability in CAN-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q762505)
