Stability in CAN-free graphs (Q762505): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q199001 |
||
Property / reviewed by | |||
Property / reviewed by: Vladimir D. Tonchev / rank | |||
Revision as of 17:41, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Stability in CAN-free graphs |
scientific article |
Statements
Stability in CAN-free graphs (English)
0 references
1985
0 references
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.
0 references
graph with forbidden subgraphs
0 references
CAN-free graph
0 references
stability number
0 references