Premium
On the face touching number
Author(s) -
Sanders Daniel P.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199611)23:3<265::aid-jgt6>3.0.co;2-q
Subject(s) - klein bottle , combinatorics , planar graph , mathematics , projective plane , vertex (graph theory) , torus , graph , plane (geometry) , enhanced data rates for gsm evolution , discrete mathematics , computer science , geometry , artificial intelligence , correlation
Abstract In a 3‐connected plane graph, each pair of faces meet at at most either a vertex or an edge. Zha considered 3‐connected graphs embedded on the projective plane, torus, and Klein bottle, showing that they meet at at most two, at most four, and at most four vertices or edges, respectively, and demonstrated graphs that showed that these bounds were best possible. He asked the question on what the maximum number of times two faces can meet on a general surface. This paper solves that problem, showing that two faces of a graph embedded on a non‐planar surface of Euler characteristic ϵ meet at most 4–2ϵ times. The proof uses the Discharging Method, and seems to be the first application of this method to a problem which is wholly about graph embeddings. Also, graphs are demonstrated to show that this result is best possible. © 1996 John Wiley & Sons, Inc.