Stability in CAN-free graphs (Q762505): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 02:08, 5 March 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
