对边幻图猜测的一个证明

令简单图Ｇ＝（Ｖ,Ｅ）是有ｐ个顶点ｑ条边的图。假设Ｇ的顶点和边由１,２,３．．．,ｐ＋ｑ所标号,且ｆ：Ｖ∪Ｅ＝「１,２,．．．,ｐ＋ｑ」是一个双射。如果对所有的边ｘｙ,ｆ（ｘ）＋ｆ（ｙ）＋ｆ（ｘｙ）是常量,则称图Ｇ是边幻图（ｅｄｇｅ－ｍａｇｉｃ）。毛毛虫图是一个树,移走它的所有端点产生一个路（称为Ｔ的脊或主干）。例如,路和星图是毛毛虫图。证明了毛毛虫图是边幻图,从而证明了顶点不超过８的树的边幻图。     

关于一类新的整和图

Ｈａｒａｒｙ提出了整和图的概念,设ｆ为整数集到图Ｇ（Ｖ（Ｇ）,Ｅ（Ｇ）的顶点集Ｖ（Ｇ）的一个单射,使得对于Ｇ的两个不同的顶点ｕ和ｖ,ｖｕ∈Ｅ（Ｇ）,当且仅当存在ｗ∈Ｖ（Ｇ）,使ｆ（ｕ）＋ｆ（ｖ）＝ｆ（ｗ）,则Ｇ称为整和图,并且他证明了所有路和星图是整和图。树中度数至少为３的项点称为叉点,Ｃｈｅｎ用粘合法证明了广义呈图和叉点距离至少为４的树是整和图,并同时猜测所有的树均为整和图。本文证明了所有叉点距     

两类联图的全着色

一个图Ｇ＝（Ｖ，Ｅ）的一个ｋ－全着色是从Ｖ∪Ｅ到Ｉｋ＝｛１，２…ｋ｝上的一个映射ψ；如果对Ｖ∪Ｅ中任意两个相邻或相关联的元素ｅ１，ｅ２，都有ψ（ｅ１）≠ψ（ｅ２）时，则称ψ为Ｇ的一个正规全着色。图Ｇ的全色数定义为ｘＴ（Ｇ）＝ｍｉｎ｛ｋ｜存在Ｇ的一个正规ｋ－全着色｝。令Ｃｎ为ｎ个点的图，Ｋ↑－ｍ为ｍ个点的独立集，Δ为图的最大度。本文证明了在ｍ≠ｎ时联图Ｃｍ＋Ｃｎ的全色数为Δ＋１；在ｍ＋２〈ｎ或ｍ〉ｎ     

关于一类新的整和图

Ｈａｒａｒｙ 提出了整和图的概念,设 ｆ 为整数集到图 Ｇ（ Ｖ（ Ｇ） , Ｅ（ Ｇ）） 的顶点集 Ｖ（ Ｇ） 之间的一个单射,使得对于 Ｇ 的两个不同的顶点ｕ 和ｖ ,ｕｖ ∈ Ｅ（ Ｇ） ,当且仅当存在 ｗ ∈ Ｖ（ Ｇ） ,使 ｆ（ ｕ） ＋ ｆ（ ｖ） ＝ｆ（ ｗ ） ,则 Ｇ 称为整和图,并且他证 明了所有路 和星图是整 和图。树 中度数至少 为３ 的 顶点称为 叉点, Ｃｈｅｎ 用粘合法证明了广义星图和叉点距离至少为４ 的树是整和图,并同时猜测所有的树均为整和图。本文证明了所有叉点距离至少为３ 的树是整和图,从而给出了一类新的整和图     

独立数,连通度与r—覆盖

设Ｇ是一个图,如果对Ｇ的任一条边ｅ,Ｇ中存在包含ｅ的ｒ－因子,则称Ｇ是ｒ－覆盖图。文中证明了：如果ｒ≥１是一奇数,Ｇ是一图,│Ｖ（Ｇ）│为偶数。若Ｋ（Ｇ）≥（ｒ＋１＾２／２,（ｒ＋１）＾２α（Ｇ）〈４ｒＫ（Ｇ）,那么,Ｇ是ｒ－覆盖的。如果ｒ≥２为偶数,图Ｇ满足：Ｋ（Ｇ）≥ｒ（ｒ＋２）／２,（ｒ＋２）α（Ｇ）〈Ｋ（Ｇ）,那么,Ｇ是ｒ－覆盖的。     

独立数、连通度与r-覆盖

设Ｇ是一个图,如果对Ｇ的任一条边ｅ,Ｇ中存在包含ｅ的ｒ－因子,则称Ｇ是ｒ－覆盖图．文中证明了：如果ｒ≥１是一奇数,Ｇ是一图,｜Ｖ（Ｇ）｜为偶数．若Ｋ（Ｇ）≥（ｒ＋１）２／２,（ｒ＋１）２α（Ｇ）＜４ｒＫ（Ｇ）,那么,Ｇ是ｒ－覆盖的．如果ｒ≥２为偶数,图Ｇ满足：Ｋ（Ｇ）≥ｒ（ｒ＋２）／２,（ｒ＋２）α（Ｇ）＜４Ｋ（Ｇ）,那么,Ｇ是ｒ－覆盖的．     

一类树的带宽和

设Ｇ＝Ｇ（Ｖ，Ｅ）是一ｐ阶简单图，一个１－１映射ｆ∶Ｖ→｛１，２，…，ｐ｝称为Ｇ的一个标号。Ｂｓｕｍ（Ｇ）＝ｍｉｎｆΣ（ｕ，ｖ）∈Ｅ｜ｆ（ｕ）－ｆ（ｖ）｜∶ｆ是Ｇ的一个标号｛｝叫做Ｇ的带宽和。本文确定了一类树的带宽和。     

关于Faudree—Schelp定理的改进

一个图Ｇ＝（Ｖ，Ｅ）是［ｌ，ｍ］－泛连通的，如果在Ｇ的任意一对节点ｘ与ｙ之间有长为Ｋ－１的路ＰＫ（ｘ，ｙ），Ｋ＝ｌ，ｌ＋１，…，ｍ。Ｇ具有性质Ｐ（Ｋ），如果对Ｇ的任何一对距离为２的节点ｘ和ｙ，有ｄ（ｘ）＋ｄ（ｙ）≥Ｋ。作者探讨了一类Ｐ（Ｋ）的路连通性，改进了Ｆａｕｄｒｅｅ－Ｓｃｈｅｌｐ定理，得到两个定理。定理１设Ｇ＝（Ｖ，Ｅ）是ｎ阶Ｐ（ｎ－１）图。如果Ｇ是［ｎ－１，ｎ］－泛连通的，则Ｇ是［８，ｎ］     

图的正交（g,f）——因子分解

设ｇ和ｆ分别是定义在图Ｇ的顶点集合Ｖ（Ｇ）上的整数值函数且对每一个ｘ∈Ｖ（Ｇ）有２≤ｇ（ｘ）≤ｆ（ｘ）,证明了若Ｇ是（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）－图,则对Ｇ中任意一个给定的有ｍ条边的子图Ｈ,Ｇ有一个（ｇ,ｆ）－因子分解与Ｈ正交。     

图的正交(g,f)-因子分解

设ｇ和ｆ分别是定义在图Ｇ的顶点集合Ｖ（Ｇ）上的整数值函数且对每一个ｘ∈Ｖ（Ｇ）有２≤ｇ（ｘ）≤ｆ（ｘ）．证明了若Ｇ是（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）—图,则对Ｇ中任意一个给定的有ｍ条边的子图Ｈ,Ｇ有一个（ｇ,ｆ）—因子分解与Ｈ正交．     

两类H-cordial图的构造

给出了图G是H-cordial图的一个必要条件,证明了基于两个正则图而构造的新图G*是H-cordial图,从而得到了两大类H-cordial图的构造方法,由此可推导出一系列图都是H-cordial图.     

两类不交并图的序列性

考察了m重-四角鲜人掌图的序列性,给出了两类不交并图,并且证明了它们是序列图。     

高阶循环图的构造与一族超能强正则图

根据图的能量的定义和直积的定义,用求两个图的直积的方法,将Bi-循环图推广到高阶循环图,给出其能量表达式,分析其能量特征,并在Igor对循环图的结论的基础上给出一族超能的强正则图.     

一种极大外平面图的构造法

提出了一种判定图同构的方法,其原理是赋予每个无标号极大外平面图一个n×(n-3)阶0-1矩阵.证明了矩阵与极大外平面图一一对应,矩阵相同的图彼此同构.构造所有可能的n阶极大外平面图,并用上述方法除去其中同构者,所有n阶无标号极大外平面图都被构造出来了,同时得到其总个数,解决了有关极大外平面图同构与计数问题.     

一类循环图的计数

讨论了4度循环图的结构。所有n阶4度非同构的连通循环图被分为两类:Ⅰ类和Ⅱ类。给出了计算Ⅰ类循环图的计算公式,改进了关于n阶4度非同构的循环图的计数公式。     

一个六点七边图的特殊图设计构造

六点七边图(不带孤立点的简单图)共有17个图，在讨论了其余12个图中一个特殊图的图设计存在性问题的基础上，可以用类似的方法解决其余六点七边图(当顶点数为奇数且(7，G1)-GD存在时)的图设计存在性问题。     

几何约束求解中分离图完备的充要条件

在基于图论的几何约束求解方法中,通常是先将恰当几何约束图分解为两个完备的分离图,然后再进行下一步分解。而一个恰当几何约束图关于其最小切割图的两个分离图往往是不定约束的。针对以上问题,通过对最小切割图与分离图的自由度分析,得出了分离图的完备化的一个充分必要条件,并推导出2D和3D中恰当约束图的最小分割图中顶点元素个数的一个下限,这也是恰当约束图连通度的一个下限。并通过实例验证了所提出的充分必要条件的正确性。     

二部图中有向不同构图的计算

应用有限群对集合的作用,以及轨道、图论、等价关系等相关知识,讨论了在2组点之间建立有向不同构图的问题,并给出了有向二部图的不同构图的计算方法及公式.     

基于 PROLOG 语言的电网图形编辑系统

介绍了一个基于ＴｕｂｏＰｒｏｌｏｇ语言开发的电网图形编辑系统。该统辑系统采用分层作图的思想，将图形编辑分为底图编辑、元件标注、电网图合成等步骤，可以方便地为以ＴｕｒｂｏＰｒｏｌｏｇ语言开发的专家系统编辑电网图形。文中阐述了该图形编辑系统的总体结构、数据库及主要功能。同时，介绍了用ＡｕｔｏＣＡＤ辅助编辑电网底图的思想，并用ＴｕｒｂｏＰｒｏｌｏｇ语言开发了图形接口软件。     

4度循环图的宽直径

研究了涉及图中两点间k条内部不交路的图的宽距离和宽直径。根据循环图的传递性和对称性,得到了n阶4度连通循环图的宽直径的上下限。所得结果可用来度量以循环图作为模型的一类具有高度对称性的网络的通信传输的延迟性能和容错性能。