Stability in CAN-free graphs (Q762505): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q3682509 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3328583 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On maximal independent sets of vertices in claw-free graphs / rank | |||
Normal rank | |||
Latest revision as of 15:56, 14 June 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
