The Cardinality of the Collection of Maximum Independent Sets of a Functional Graph

Autor:	Yeong-Nan Yeh, Shu-Chu Chang
Rok vydání:	1997
Předmět:	Combinatorics Cantor's theorem Discrete mathematics symbols.namesake Independent set Applied Mathematics symbols Maximal independent set Graph Mathematics
Zdroj:	Advances in Applied Mathematics. 18(3):286-299
ISSN:	0196-8858
DOI:	10.1006/aama.1996.0509
Popis:	An independent set (or stable set) of a graphG(V,E) is a subsetSof the vertices setVin which no two are adjacent. Let ψ(G) be the number of vertices in a stable set of maximum cardinality; ψ(G) is called the stability number ofG. 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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::91007d481bfce0e57009af16eef2c507 Zobrazit plný text záznamu Full Text from ScienceDirect