边型带权核子图的边可重构性

定义了图的边型带权核子图，证明了图中同构于边型核子图的数目是可重构的，从而给出了关于边重构的新结果。     

图的边重构性

提出图的小次、大次和特殊路长S(G)等概念来研究图的边重构性,并得到如下两个重要结论:若图G存在次为δ_p k的顶点至少和k 1个小次顶点相邻,则G是边可重构的(δ_p为某小次,k为非负整数);若S(G)≠0,3, ∞,则G是边可重构的。     

三次图的结构特征

通过对三次图结构的研究给出了两个主要结论：（１）对连通度μ（Ｇ）＝０，１，２，３，分别给出点数Ｐ＝｜Ｖ（Ｇ）｜的可达到的下界；（２）２—连通图Ｇ，存在２—连通三次图Ｇ′，Ｇ′可收缩到Ｇ。     

三次图的完全扩容图的连通度

目的研究三次图的完全扩容图的连通度。方法利用反证法。结果与结论3-连通三次图的完全扩容图也是3-连通三次图。     

图可重构性的一点注记

设图G的顶点集为{u_1,u_2,…,u_n}。G的途径矩阵D(G):(d_(ij)是n阶方阵,此处d_(ij)是G中从u_i出发长为j的途径数,D(G)的行向量集X的子集{x_1,x_2,…,x_r}称为X的最小线性相关集,如果{x_1,x_2,…x_r}线性相关且对x的任一(r-1)之子集均是线性无关。称数r为G的最小线性相关数。当X线性无关时,定义G的最小线性相关数r=∞。对1≤i≤n,记d_i为点u_i在G中的次,G_i是图G剔除点u_i以及与u_i关联的边而得到子图。设r_i是G_i的最小线性相关数,我们有下列定理:如果存在某一数i使r_i>2d_i,则G是可重构的。特别,我们重新得到下述结果:如果存在某一子图G_,使得G_i的所有特征向量均不与C=(1,…,1)~t正交,则G是可重构的。     

图可重构性的一点注记

设图G的顶点集为{v_1,v_2,…,v_n}.G的途径矩阵D(G)=(d_(ij)是n阶方阵,此处d_(ij)是G中从v_i出发长为j的途径数,D(G)的行向量集X的子集{x_1,x_2,…,x_r}称为X的最小线性相关集,如果{x_1,x_2,…x_r}线性相关且对X的任一(r-1)之子集均是线性无关.称数r为G的最小线性相关数.当X线性无关时,定义G的最小线性相关数r=∞.对1≤i≤n,记d_i为点v_i在G中的次,G_i是图G剔除点v_i以及与v_i关联的边而得到子图.设r_i是G_i的最小线性相关数,我们有下列定理:如果存在某一数i使r_i>2d_i,则G是可重构的.特别,我们重新得到下述结果:如果存在某一子图G_i,使得G_i的所有特征向量均不与C=(1,…,1)_t正交,则G是可重构的.     

平面图边可重构的几个结果

本文得出几个平面图边可重构的结论:1.若 G 是平面图,δ(G)=4,且 G 没有次为5的点,则 G 是边可重构的。2.若 G 是平面图,δ(G)≥3,且 S_3为 G 中次为3的集合,又设 G—S_3为3连通的,G 无次为4的点。则 G 是边可重构的。     

一类1-边可删的导出匹配可扩图的刻画

设图G是有2n个顶点的简单图,如果删去G的任意k条边后得到的图是导出匹配可扩的,则称G是k-边可删的导出匹配可扩图.给出了4-正则、不包含K1,4作为导出子图、1-边可删的导出匹配可扩图的完全刻画.     

三次图中大子集的可迹性

证明了如何Ｘ是３－连通三次图Ｇ的任间１９－点子集，那么或者Ｘ的任意１３－点子集在Ｇ中可迹，或者Ｘ与Ｇ中可迹。     

关于图的同构不动边

图G的一条边e称为G的同构不动边,如果G—e+e’≌G当且仅当e’=e.若e=uv是G的同构不动边,那么对G—e的任意自同构映射π有π({u,v})={u,v}.图的同构不动边反映了二元关系系统中的定性关系,改变这种关系将改变系统的结构.这种关系的存在对系统的重构有重要的意义.本文中猜想:几乎所有的图含同构不动边.为支持这个猜想,列出了所有不含同构不动边的树形图和单圈图.     

寻边问题

本文的目的是求有限、简单、非定向图的复杂性,即寻找图中一条未知边所必须的检查次数。文章给出了求复杂性的一般公式,从而大大简化了求复杂性的计算。     

在非单连通域上曲线积分问题的注释

本文广义地定义了循环常数，并对含有无穷多个“洞”的非单连通域上的曲线积分进行了讨论。     

关于算术图的一个猜想

一个(p,q)—图G被称为是(k,d)—算术的,如果它所有顶点可以被分配到不同的非负整数,使得它的边值可以排列成算术级数k,k+d,k+2d,…,k+(q-1)d,其中一条边的值是分配到它的两个端点的数的和。一个图G被称为是算术的,如果存在两个正整数k和d使得它是(k,d)—算术的。本文证明了Acharya和Hegde提出的下述猜想:对任意正整数n≥5,K不是算术图。     

有向图存在Hamilton圈的必要条件

应用随机过程理论——马尔柯夫链,我们得到有向图存在Hamilton圈的必要条件。一个不可约有向图(?)=(V,E)具有周期d,|V|=n,V能分解成V=C_1+C_2+…+C_d且C_k,K=1,2,…,d,是不相交的非空循环类。如果|C_k|不等于n/d,那么有向图不是一个有向的Hamilton图。     

完全多部图的G-填充和覆盖

设图G是由P4带一条悬边所组成的五点四边图，本文确定了完全图Kv和完全多部图Kn(t)的图G填充数和覆盖数。     

关于图角与图变换的注记

利用对图施行某些变换所得到的图的特征值可由施行变换的图的特征值和角进行刻画的方法,得到了两个公式,并将一个命题推广到更一般的情形.     

MBIUS梯图和梯图的升分解

本文证明了Mobius梯图和梯图是可以升分解的。     

群图的基本理论及置换群图的构造

建立了群图与可靠通信网之间的关系及群图构造的基本理论 ,在此基础上得到构造置换群图的两种实用方法——最小生成元法和轮换群图法 ,并应用这两种方法得出置换群可以生成任意 n节点和大于其最小连通度的连通群图的结论