research article
The struction of a graph: Application toCN-free graphs
June 1985
We consider the class of graphs characterized by the forbidden subgraphsC andN:C is the claw (unique graph with degree sequence (3, 1, 1, 1)) andN the net (unique graph with degree sequence (3, 3, 3, 1, 1, 1)). For this class of graphs (calledCN-free) an algorithm is described for determining the stability numberα(G). It is based on a construction associating with anyCN-free graphG anotherCN-free graphG′ such thatα(G′)=α(G)−1. Such a construction reducing the stability number is called a struction.
Type
research article
Author(s)
Hammer, P. L.
Rutgers, The State University of New Jersey
Mahadev, N. V. R.
University of Winnipeg
École Polytechnique Fédérale de Lausanne
Date Issued
1985-06
Publisher
Published in
Volume
5
Issue
2
Start page
141
End page
147
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
February 5, 2026
Use this identifier to reference this record