Contractions to k8

✍ Scribed by Leif K. Jørgensen

• Book ID: 102893203
• Publisher: John Wiley and Sons
• Year: 1994
• Tongue: English
• Weight: 847 KB
• Volume: 18
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190180502

✦ Synopsis

Abstract

It is proved that the maximal number of edges in a graph with n ≧ 8 vertices that is not contractible to K~8~ is 6__n__ − 21, unless 5 divides n, and the only graphs with n = 5__m__ vertices and more than 6__n__ − 21 edges that are not contractible to K~8~ are the K~5~(2)‐cockades that have exactly 6__n__ − 20 edges.