Journal of the Ramanujan Mathematical Society

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

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

Abstract

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.

Keywords

Triangulated Graph, Competition Number, Turan's Theorem.

Full Text