期刊
JOURNAL OF COMBINATORIAL THEORY SERIES B
卷 157, 期 -, 页码 235-262出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2022.06.003
关键词
Surface; Quadrangular embedding; Minimal quadrangulation
类别
资金
- Simons Foundation [359516]
In this paper, we determine the order of a minimal quadrangulation of a surface Sigma, denoted as n(Sigma), for all types of surfaces. The calculations for n(Sigma) are provided for different surfaces using the introduced 'diagonal technique'. The general features of this method are explained.
A quadrangular embedding of a graph in a surface Sigma, also known as a quadrangulation of Sigma, is a cellular embedding in which every face is bounded by a 4-cycle. A quadrangulation of Sigma is minimal if there is no quadrangular embedding of a (simple) graph of smaller order in Sigma. In this paper we determine n(Sigma), the order of a minimal quadrangulation of a surface Sigma, for all surfaces, both orientable and nonorientable. Letting S-0 denote the sphere and N-2 the Klein bottle, we prove that n(S-0) = 4,n(N-2) = 6, and n(Sigma)= inverted right perpendicular (5 + root 25-16 chi(Sigma))/2inverted left perpendicular for all other surfaces Sigma, where chi(Sigma) is the Euler characteristic. Our proofs use a 'diagonal technique', introduced by Hartsfield in 1994. We explain the general features of this method. (C) 2022 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据