首页 | 本学科首页   官方微博 | 高级检索  
     


Graphs with the second largest number of maximal independent sets
Authors:Zemin Jin
Affiliation:a Department of Mathematics, Zhejiang Normal University, Jinhua 321004, PR China
b Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, PR China
Abstract:Let G be a simple undirected graph. Denote by View the MathML source (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erd?s and Moser raised the problem of determining the maximum value of View the MathML source among all graphs of order n 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 r cycles. In this paper we determine the second largest value of View the MathML source and xi(G) among all graphs of order n. Moreover, the extremal graphs achieving these values are also determined.
Keywords:Maximal (maximum) independent set   Extremal graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号