| STABILITY NUMBER IN SUBCLASSES OF P_5~-FREE GRAPHS |
| |
| 引用本文： | Zverovich I E ,Zverovich O I. STABILITY NUMBER IN SUBCLASSES OF P_5~-FREE GRAPHS[J]. 高校应用数学学报(英文版), 2004, 0(2) |
| |
| 作者姓名： | Zverovich I E Zverovich O I |
| |
| 作者单位： | RUTCOR——Rutgers Center for Operations Research，RUTCOR——Rutgers Center for Operations Research Rutgers，The State University of New Jersey，640 Bartholomew Rd，Piscataway，NJ 08854-8003，USA.，Rutgers，The State University of New Jersey，640 Bartholomew Rd，Piscataway，NJ 08854-8003，USA. |
| |
| 基金项目： | The first author was supported by DIMACS Summer2 0 0 3Award |
| |
| 摘 要： | §1 IntroductionLet Pn,Cn,and Kn be the path,the cycle,and the complete graph of order n,respectively.The complete bipartite graph with cardinalities ofparts m and n is denoted byKm,n.Disjoint union of n copies of a graph G is denoted by n G;Gis the complement of agraph G.A setof pairwise non-adjacent vertices in a graph is called stable.A maximum stableset of a graph G has the largest cardinalityα( G) among all stable sets of G;α( G) is calledthe stability number of G.Let Z be a s…
|
STABILITY NUMBER IN SUBCLASSES OF P_5~-FREE GRAPHS |
| |
| Abstract: | Two new hereditary classes of P 5-free graphs where the stability number can be found in polynomial time are proposed.They generalize several known results. |
| |
| Keywords: | hereditary classes of graphs stability number forbidden induced subgraph |
| 本文献已被 CNKI 等数据库收录！ |
