Informatics Publishing Limited

Herbert J. Fleischner ¹, Dennis P. Geller ², Frank Harary ³

Affiliations
1 Institute for Advanced Study, IN
2 Austrian Academy of Sciences, SUNY at Binghamton, US
3 University of Oxford, GB

Abstract

A planar graph is outer planar if it can be embedded irr the plane so that every point lies on the exterior region. Outerplanar graphs were characterized by Chartrand and Harary [1] as those graphs containing subgraphs homeomorphic onto K₄ or K_2,3. In this paper we present an alternate characterization of outerplanar graphs in terms of duals, and discuss some relationships between the degrees of the points of outerplanar graphs and the lengths of the boundaries of their interior regions.

Full Text

     

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