The struction of a graph: Application to CN-free graphs (Q1068855)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The struction of a graph: Application to CN-free graphs |
scientific article; zbMATH DE number 3931065
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The struction of a graph: Application to CN-free graphs |
scientific article; zbMATH DE number 3931065 |
Statements
The struction of a graph: Application to CN-free graphs (English)
0 references
1985
0 references
A graph is CN-free if it contains neither C, the claw, nor N, the net (unique graphs with degree sequences \((3,1,1,1)\) and \((3,3,3,1,1,1),\) respectively) as subgraphs. For the class of CN-free graphs, a polynomial time algorithm is described for determining the stability number a(G). The basic idea of the algorithm consists in a reduction procedure (called here struction) associating to any CN-free graph G another such a graph G' with \(a(G')=a(G)-1\).
0 references
claw
0 references
net
0 references
CN-free graphs
0 references
polynomial time algorithm
0 references
stability number
0 references
