THE CARDINALITY OF THE COLLECTION OF MAXIMUM INDEPENDENT SETS OF A FUNCTIONAL GRAPH

Authors
CHANG SC YEH YN
Citation
Sc. Chang et Yn. Yeh, THE CARDINALITY OF THE COLLECTION OF MAXIMUM INDEPENDENT SETS OF A FUNCTIONAL GRAPH, Advances in applied mathematics, 18(3), 1997, pp. 286-299
Citations number
12
Categorie Soggetti
Mathematics,Mathematics
Journal title
Advances in applied mathematics → ACNP
ISSN journal
01968858
Volume
18
Issue
3
Year of publication
1997
Pages
286 - 299
Database
ISI
SICI code
0196-8858(1997)18:3<286:TCOTCO>2.0.ZU;2-N
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 nu mber of vertices in a stable set of maximum cardinality; psi(G) is cal led the stability number of G. Stability numbers of a graph have been well studied, but little has been done on the number of independent su bsets 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. (C) 1997 Academic Press.