کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649997 | 1342471 | 2008 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Graphs with the second largest number of maximal independent sets Graphs with the second largest number of maximal independent sets](/preview/png/4649997.png)
Let GG be a simple undirected graph. Denote by mi(G) (respectively, xi(G)xi(G)) the number of maximal (respectively, maximum) independent sets in GG. Erdős and Moser raised the problem of determining the maximum value of mi(G) among all graphs of order nn and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most rr cycles. In this paper we determine the second largest value of mi(G) and xi(G)xi(G) among all graphs of order nn. Moreover, the extremal graphs achieving these values are also determined.
Journal: Discrete Mathematics - Volume 308, Issue 23, 6 December 2008, Pages 5864–5870