Independence, clique size and maximum degree (Q1065018): Difference between revisions

Given a graph G with n vertices, maximum degree p, clique size (q-1), and independence number \(\alpha\), the author has previously shown that \(\alpha /n\geq 2/(p+q)\) [Proc. 9th Southeast. Conf. Comb., Graph Theory, Comput., Boca Raton 1978, 269-274 (1978; Zbl 0434.05044)]. Furthermore, if equality holds, then 3q-2p\(\leq 5\); such graphs are called butterflies. Butterflies occur in Ramsey theory, as \textit{P. A. Catlin}'s counterexamples to the Hajós conjecture [J. Comb. Theory, Ser. B 26, 268-274 (1979; Zbl 0385.05033)] and in an article by \textit{B. Bollobás, S. Tucker} and the reviewer [Proc. 7th Southeast. Conf. Comb., Graph Theory, Comput., Baton Rouge 1976, 43-50 (1976; Zbl 0344.05156)]. Here the author proves that given natural numbers p and q with \(3q-2p=5\), there exists a unique butterfly with these parameters.