G-2008-78
A Magnetic Procedure for the Stability Number
et référence BibTeX
A magnet is a pair u,v of adjacent vertices such that the proper neighbours of u are completely linked to the proper neighbours of v. It has been shown that one can reduce the graph by removing the two vertices u, v of a magnet and introducing a new vertex linked to all common neighbours of u and v without changing the stability number. We characterize a class of graphs such that by repeated use of magnets the graph is reduced to a stable set. A description in terms of forbidden subgraphs is given and a polynomial algorithm follows.
Paru en novembre 2008 , 15 pages
Axe de recherche
Publication
jan. 2009
A magnetic procedure for the stability number
et
Graphs and Combinatorics, 25, 707–716, 2009
référence BibTeX