首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号