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 等数据库收录! |