The Cardinality of the Collection of Maximum Independent Sets of a Functional Graph
Source: Advances in Applied Mathematics, Volume 18, Number 3, April 1997 , pp. 286-299(14)
Publisher: Academic Press
Abstract:An independent set (or stable set) of a graph G ( V , E ) is a subset S of the vertices set V in which no two are adjacent. Let psi( G ) be the number of vertices in a stable set of maximum cardinality; psi( G ) is called the stability number of G . Stability numbers of a graph have been well studied, but little has been done on the number of independent subsets whose cardinality is the stability number. In this paper we will provide an algorithm to find the number of independent subsets whose cardinality is the stability number.
Document Type: Research Article
Affiliations: 1: Department of Mathematics, National Changhua University of Education, Changhua, Taiwan, Republic of China 2: Institute of Mathematics, Academia Sinica, Taipei, Taiwan, Republic of China
Publication date: 1997-04-01