Extremal Competition Numbers as a Generalization of Turin's Theorem

Frank Harary; Suh-Ryung Kim; Fred S. Roberts

Extremal Competition Numbers as a Generalization of Turin's Theorem

Frank Harary ¹, Suh-Ryung Kim ², Fred S. Roberts ³

Affiliations
1 Department of Computer Science, New Mexico State University, Las Cruces, NM 88003, United States
2 Math and Science Division, St. John's University, Staten Island, NY 10301, United States
3 Department of Mathematics, Rutgers University, New Brunswick, N.J. 08903, Canada

Turan's famous theorem says that a graph of n points and no triangles can have no more than [n²/4] lines, and this bound is achieved only by the complete bipartite graph K in([n/2j, [n/2]). We now show that any graph of n points can have competition number no higher than [n² /4] - n + 2, and this bound is achieved only by K ([n/2],[n/2]), and K₃. Turan's Theorem follows as a special case.