|
 
|
[CCP14] d-extensible sets of stable sets in bipartite graphs.
Conférence Internationale avec comité de lecture : GO IX, Ninth international colloquium on Graphs and Optimization, July 2014, pp.14,Mots clés: Extensible, stable, graph
Résumé:
In a graph G = (V, E) a subset F of V is a d-extensible set if for any stable set S
of F with |S|= d it exists a stable set S' of V-F
F such that SUS' is a maximum stable set of G.
We say that S can be extended to a maximum stable set with vertices outside of F, shortly S can be extended. We present a characterization of the d-extensible sets for the class of bipartite graphs and we determine, for some values of d, the maximum cardinality of a d-extensible set.
We also determine the maximum cardinality of a d-extensible set for a subclass of arborescences
where any vertex x of V belongs to a maximum stable set. This problem has some applications
in reliability where we consider vertex failures in the graph G : a d-extensible set is the set of
vertices that are not protected.
Equipe:
oc
BibTeX
| @inproceedings { | |||
| CCP14, | |||
| title | = | "{d-extensible sets of stable sets in bipartite graphs.}", | |
| author | = | " M.-C. Costa and G. Cotté and C. Picouleau ", | |
| booktitle | = | "{GO IX, Ninth international colloquium on Graphs and Optimization}", | |
| year | = | 2014, | |
| month | = | "July", | |
| pages | = | "14", | |
| } | |||
