The minimum genus of a two-point universal graph |
| |
Authors: | George B Purdy |
| |
Affiliation: | Texas A & M University, College Station, Texas 77843 USA |
| |
Abstract: | A graph G is two-point universal if, given any two vertices A and B, there is a vertex jointed to both, a vertex joined to neither, a vertex joined to A but not B, and a vertex joined to B but not A. Erdös asked whether there is an infinite family of such graphs of some genus γ. In this note, we show that the number of vertices of a two-point universal graph of genus γ satisfies n ≤ 216(2γ + 1)2 so that there are most finitely many of each genus. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|