
doi: 10.1007/bf02579154
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.
Extremal problems in graph theory, Coloring of graphs and hypergraphs, clique size, maximum degree, independence number, Butterflies
Extremal problems in graph theory, Coloring of graphs and hypergraphs, clique size, maximum degree, independence number, Butterflies
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 13 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
