Premium
An upper bound on the size of a largest clique in a graph
Author(s) -
Geoffroy Dennis P.,
Sumner David P.
Publication year - 1978
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190020305
Subject(s) - combinatorics , mathematics , bound graph , graph , clique , upper and lower bounds , clique number , discrete mathematics , graph power , line graph , mathematical analysis
A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point‐determining graph is the set G O of all vertices, v , such that G – v 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.