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


An upper bound on the size of a largest clique in a graph
Authors:Dennis P Geoffroy  David P Sumner
Abstract:A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point-determining graph is the set GO of all vertices, v, such that Gv is point determining. In this paper we show that the size, ω(G), of a maximum clique in G satisfies ω(G) ? 2|π (G)O|, where π(G) (the point determinant of G) is obtained from G by identifying vertices which have the same neighborhood.
Keywords:
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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