A finiteness theorem for maximal independent sets
| dc.citation.epage | 326 | en_US |
| dc.citation.issue | 4 | en_US |
| dc.citation.spage | 321 | en_US |
| dc.citation.volume | 12 | en_US |
| dc.citation.woscount | 8 | |
| dc.contributor.author | Jou, MJ | en_US |
| dc.contributor.author | Chang, GJ | en_US |
| dc.contributor.author | Lin, C | en_US |
| dc.contributor.author | Ma, TH | en_US |
| dc.contributor.department | 應用數學系 | zh_TW |
| dc.contributor.department | Department of Applied Mathematics | en_US |
| dc.date.accessioned | 2014-12-08T15:02:57Z | |
| dc.date.available | 2014-12-08T15:02:57Z | |
| dc.date.issued | 1996 | en_US |
| dc.description.abstract | Denote by mi(G) the number of maximal independent sets of G. This paper studies the set S(k) of all graphs G with mi(G) = k and without isolated vertices (except G congruent to K-1) or duplicated vertices. We determine S(1), S(2), and S(3) and prove that V(G) less than or equal to 2(k-1) + k - 2 for any G in S(k) and k greater than or equal to 2; consequently, S(k) is finite for any k. | en_US |
| dc.identifier.doi | 10.1007/BF01858464 | en_US |
| dc.identifier.issn | 0911-0119 | en_US |
| dc.identifier.journal | GRAPHS AND COMBINATORICS | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1007/BF01858464 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/1556 | |
| dc.identifier.wosnumber | WOS:A1996VV68100002 | |
| dc.language.iso | en_US | en_US |
| dc.title | A finiteness theorem for maximal independent sets | en_US |
| dc.type | Article | en_US |