G.M.(n 1个顶点)的同胚类个数的计算公式

所谓“图式流形”即将一个图的每个顶点都换为流形 ,把每个边都换为相应流形与单位闭区间的拓扑积。本文所论“图式流形”,是将顶点都换为圆周 ,把每个边都换为管 ( S1 × I)。管与圆周“衔接”时 ,映射度规定为 1或 - 1。我们把原来的图称为该图式流形的缩影。把缩影为 f的图式流形简记为 G.M.f .对于本文所论及的这类图式流形 ,可规定边的符号 (正号或负号 ) ,它取决于其两端的映射度 (相同或相异 )。已经证明 [1 ] ,将某个顶点圆改变方向 ,是一个同胚变形 ,且相当于把与该顶点 (圆 )相关联的所有边改变符号。且称此同胚变形为顶点的…     

G.M.⨂(n+1个顶点)的同胚类个数的计算公式

所谓"图式流形"即将一个图的每个顶点都换为流形,把每个边都换为相应流形与单位闭区间的拓扑积。本文所论"图式流形",是将顶点都换为圆周,把每个边都换为管(S¹ > I)。     

具有缩影W_8和W_9的图式流形

图式流形是将简单无向图中的所有边用管取代、所有顶点用圆周替换而得到的一种新管型曲面。这些管型曲面即是图式流形,而简单无向图则称为相应图式流形的缩影。若图式流形的圆周采取不同的覆盖映射,则可得到不同的图式流形。这些图式流形有无限多个,而计算所有这些图式流形同胚分类的个数,并给每一种同胚类型指定一个图式流形的代表,即为图式流形的拓扑分类问题。本文从图染色理论出发,对收缩为n个顶点的轮图Wn进行了研究,探讨收缩为Wn的图式流形同胚等价类的个数,以及所有互不同构的着色构成代表系需要满足的条件。利用图论中的边染色理论结合扭转运算,在同胚的意义下得到并绘出了具有收缩W8、W9的图式流形的代表图形,它们分别只有18和30个。     

图式流形_(2n个顶点 ,n≥3)的一个同胚分类定理(英文)

介绍计算缩影为 　 2 n个顶点 ,n≥ 3的图式流形的同胚类的一个简单方法 .     

缩影为Kn的图式流形同胚分类算法

讨论了缩影为Kn的图式流形的2种同胚分类算法,提出了最小方阵判断法和最小方阵计算法,并使用这2种方法,计算出了缩影为3到9个顶点的完全无向图的同胚类型的个数,给出了各个类型的图式流形代表元.     

图式流形▲2n个顶点,n≥3的一个同胚分类定理

介绍计算缩影为▲2n个顶点,n≥3的图式流形的同胚类的一个简单方法.     

两类联图的符号控制数

设图G=(V,E)为一个图,一个双值函数f:V→{1,-1},若S?V,则记f(S)=Σ_(v∈s) f(v).如果对任意的顶点v∈V,均有f(N[v])≥1成立,则称f为图G的一个符号控制函数.图G的符号控制数定义为γ_S(G)=min{f(V) f是图G的一个符号控制函数}.联图G=■∨H是空图■的每个顶点都与图H的每个顶点相连接而成的图.本文主要利用讨论图中-1顶点个数的方法得到下界和用标号法得到上界,从而确定两类联图的符号控制数的精确值,即确定了γ_S(■∨Kn)和γ_S(■∨W_(1·n)).     

具有缩影Kn的图式流形

给出了以Kn(n≥3)为缩影的图式流形的伴随矩阵所有特征多项式个数的算法,并利用Matlab软件求出了缩影为K8和K9的图式流形的伴随矩阵不同特征多项式为235和1824个,从而得到它们同胚分类的下界为235和1 824.     

关于n-可扩图的一些新充分条件

若图G包含一个经过G的每个顶点的圈,则称图G为Hamilton图.若一个连通图G有n条独立边,且任意n条独立边都可扩展为G的完美匹配,则称G为n-可扩图.利用判别Hamilton图的Fan-型条件和Chvatal-Erdos型条件,分别得到两个新的判别n-可扩图的充分条件.     

框架为Petersen图的图式流形拓扑分类

提出了"梳子树"的概念,引入新的编码的方法来标记图的H-等价类代表系,研究图式流形的同胚等价类计数问题,得到了以Petersen图为框架的图式流形Μ(G)的H-等价类的个数是6个的新结果.     

图的双罗马控制数的界

定义在图G的顶点集V(G)上的函数f:V(G)→{0,1,2,3}称为G的双罗马控制函数,如果每个赋值为0的顶点至少与一个赋值为3或两个赋值为2的顶点相邻,并且每个赋值为1的顶点至少与一个赋值为2或3的顶点相邻。图的双罗马控制函数的权为所有顶点的赋值之和。双罗马控制函数的最小权称为双罗马控制数。利用顶点数、围长、周长以及最小度得到了含圈图的双罗马控制数的若干上下界。     

Kn,n的限制均匀边染色

给出图G和一个正整数r,令f‘r(G)为图G边染色的最大色数,使得每个顶点最多关联r种颜色,并且每个顶点关联的颜色中任两种颜色所染的边数相差最多为1．对所有的正整数n和r,给出了f‘r(Kn,n)的下界和上界;在r|n和r=2,3,n-1的情形,得到f‘r(Kn,n)的值。     

图的稳定数和(g,f)-因子（英文）

设f,g:V→Z是定义在顶点集V上的两个整数函数.(g,f)-因子是图G的一个生成子图H使得g(v)≤dH(v)≤f(v)对每个顶点v∈V成立.本文给出存在(g,f)-因子的一个充分条件.     

一类整和图

一个图G称为整和图,若它有一组互异的整数标号f,使得G中任意两个不同点u、v,uv是G中的一条边当且仅当f(u) f(v)=f(w)(其中w是G中的一点).一个图称为星和图,若它不含与其它顶点都邻接的顶点且有一组整和标号含有负标号和唯一绝对值最大点.广义星是将星的每一边都扩展为一条路的图.粘合是将两个图G1、G2中的各一个点r1、r2合为一个点r的运算.该文考虑了一类新图——星和图与广义星的粘合图,证明了它的整和性.     

C5的刺图的Pebbling数和2-Pebbling性质

连通图G的Pebbling数f(G)是最小的整数n,使得不论n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个Pebble移到图G任意一个目标顶点上.其中,1个Pebbling移动是从一个顶点上移走2个Pebble,而把其中一个移到与其相邻的一个顶点上,获得了C5的刺图的Pebbling...     

关于圆周自映射的一个注记

设S1是一个圆周,f:S1→S1是连续映射.我们证明以下结论不仅对含有周期点的圆周映射成立,也对一般的圆周映射f成立,这个结论是R(f)Λ(R(f))Λ(Λ(f))Λ(Ω(f))(R(f))Λ(f)Ω(f).这里我们利用了图映射的某些性质.     

随机(m,k)-正交的(g,f)-可因子化图的一个充分条件

设g和f分别是定义在图G的顶点集合V(G)上的整数值函数,且对每个x∈V(G)有k-1≤g(x)＜f(x).给出了(mg+m-1,mf-m+1)-图是随机(m,k)-正交的(g,f)-可因子化图的一个充分条件.     

轮图中间图的pebbling数

图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的一个移到与其相邻的一个顶点上.图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.文章研究轮图中间图的pebbling数.     

几类特殊图的一般指标集

令G=(V(G),E(G))为一简单连通图,V(G)和E(G)分别是图G的顶点集和边集.一个顶点标号函数f:V(G)→Z2诱导出一个边标号函数f*:E(G)→Z2,其中?v1 v2∈E(G),有f*(v1v2)=f(v1)+f(v2).当标1和标0的顶点数相差m(m<|V(G)|)时,标号为1和0的边数差的集合称为图G...     

两类图的序列性

图G的标号指f是V(G)到整数集合的一个映射,然后边xy∈E(G)由f(x),f(y)导出标号.本文利用一类具有序列平衡标号的树的性质,通过"连结"与"粘接"方式,构造更多顶点的序列树;证明了C2n+1∨Km是序列图.