摘要
本文证明了两个关于最大度为4的平面连通图的存在性定理,并确定了此图类的三种类型的分布区域。
Let G be any loopless undirected connected planar graph with maximum degree 4, vertices n and cycle rank v. Such a kind of graph is denoted by G(4). Denote by δ(i) the number of vertices of degree i in G. Then (δ(1), δ(2), δ(3), δ(4)) is called the frequency sequence of G. We have the following main theorem: Theorem 1. The non-negative integer sequence (δ(1), δ(2), δ(3), φ(4)) is the frequency sequence of a graph G if and only if that n and v satisfy the following conditions: when v=0, n≥5; when v=l,n≥4; when v = 2, n≥3;δ(4)≥1; and for any pair of n and v, there existδ(2) =n + 2v-2-3 δ(4) -2δ(3)≥0, and δ(1) =2δ(4) +δ(3) +2-2v≥0.
出处
《华中理工大学学报》
CSCD
北大核心
1990年第1期161-166,共6页
Journal of Huazhong University of Science and Technology
关键词
平面连通图
最大度
圈秩
分布区域
Connected planar graph
Maximum degree
Cycle rank
Frequency sequence
Initial value
Lattice point
Distribution domain.
