Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. The struction of a graph: Application toCN-free graphs
 
research article

The struction of a graph: Application toCN-free graphs

Hammer, P. L.
•
Mahadev, N. V. R.
•
de Werra, D.  
June 1985
Combinatorica

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.

  • Details
  • Metrics
Type
research article
DOI
10.1007/bf02579377
Author(s)
Hammer, P. L.

Rutgers, The State University of New Jersey

Mahadev, N. V. R.

University of Winnipeg

de Werra, D.  

École Polytechnique Fédérale de Lausanne

Date Issued

1985-06

Publisher

Springer-Verlag

Published in
Combinatorica
Volume

5

Issue

2

Start page

141

End page

147

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Available on Infoscience
February 5, 2026
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/258943
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés