以子图为根的k距局部子图的可重构性

本文定义了图中以某个图为根的k距局部子图，证明了图中同构于上述 k距局部子图的子图的数目是可重构的，从而给出了一个新结果并推广了文献^[5]中的定理。     

关于局部子图可重构性的一个新结果

本文研究局部子图的可重构性。一个图Ｇ在一顶点ｖ处的ｋ－局部子图是到ｖ距离小于等于ｋ的顶点导出且以ｖ为根的子图，记为ＬＧ＾ｋ（ｖ）。本文通过引进核子图的结构证明了ｋ－局部子图是可重构的，如果每一个ｋ－局部子图所含的顶点数都小于等于│Ｖ（Ｇ）│－１。这个结果改进了原有的结果。由这个新结果可知，图的半径这个参数是可重构的。本文还提出了点距序列的概念，并进一步讨论了点距序列与局部子图的关系和一些未解决的问     

关于可重构的局部子图

一个图Ｇ在一顶点ｘ处的局部子图Ｌ｛ｘ｝是由Ｇ的给定性质定义的包含ｘ的子图Ｌ１，并以ｘ为根，例如在点ｘ处的ｋ－局部子图是以ｘ为根，以所有到ｘ距离不超过ｋ的顶点集合｛ｕ∈Ｖ（Ｇ）：ｄＧ（ｖ，ｘ）≤ｋ｝为顶点集；以｛ｕｖ∈Ｅ（Ｇ）：ｄＧ（ｕ，ｘ）〈ｋ，或ｄＧ（ｖ，ｘ）〈ｋ｝为边集的带根子图。本文证明了：对于Ｇ的局部子图Ｌ｛ｘ｝，如果每个Ｌ｛ｘ｝，ｘ∈Ｖ（Ｇ），的顶点数（或边数）都小于Ｇ的顶点数（边数）减     

图的去点主子图相对同调群的可重构性

本文证明了图与其去点主子图的独立集复形构成的相对同调群族是可重构的；当图满足一定的条件时，图与其去点主子图的邻域复形构成的相对同调群族也是可重构的．     

邻域伪相似点的可重构性

设G是一个简单图，υ是G的任一个顶点．该文证明了G中与点G邻城伪相似的点数是可以重构的，并提出一些进一步可研究的问题．     

论简单图所含k阶i爪独立集个数的可重构性

设犐是图犌的一个含有犽个点的独立集（简称犽独立集）．如果犐不是犌的其它任何独立集的真子集,则称犐为犌的一个极大独立集．犌中所含的极大犽独立集的个数记为犿（犵犽,犌）．设犵犽是图犌的任一个犽独立集,如果存在｛狏１,狏２,…,狏犻｝犞（犌）－犵犽,犻≥１,使得（１）对任意犼∈ ｛１,２,…,犻｝,犵犽＋｛狏犼｝的都是犌的（犽＋１） 独立集;（２）对任意狌∈犞（犌）－犵犽－｛狏１,狏２,…,狏犻｝,犵犽＋｛狌｝的都不是犌的独立集;则称犵犽为犌的一个犻爪犽独立集,犌所含的犻爪犽独立集的个数记为犿犻（犵犽,犌）．该文证明了对简单图犌,犿犻（犵犽,犌）和犿（犵犽,犌）都是可重构的．另外,用同样的方法可以证明犌中的极大犽团的个数及犻爪犽团的个数也是可重构的．     

连通的顶点可迁图的色唯一性

本文给出从一个已知的顶点可迁的非色唯一图出发,构造无穷多个顶点可迁的非色唯一图的一种方法,据此给出若干类无穷多个连通的顶点可迁,但不是色唯一的图簇,从而进一步否定地回答了Chia在[1]中提出的问题.     

三正则连通图的Cordial性

用调整顶点标号的方法确定了3正则连通图的Cordial性．     

极小3边连通可折图

本文证实了Catlin和赖虹建的猜想:设G是非平凡连通简化图,如果F(G)=2,则G∈{K_2,t;t≥1}.     

3—连通局部连通无爪图是泛连通图

本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立.     

ON MAXIMAL MATCHINGS OF CONNECTED GRAPHS

Let I with |I| = k be a matching of a graph G (briefly, I is called a k-matching). If I is not a proper subset of any other matching of G, then I is a maximal k-matching and m(gk, G) is used to denote the number of maximal k-matchings of G. Let gk be a k-matching of G, if there exists a subset {e1, e2,…, ei} of E(G) \ gk, i (?)1, such that (1) for any j ∈ {1, 2,…,i}, gk + {ej} is a (k + l)-matching of G; (2) for any f ∈ E(G) \ (gk ∪ {e1,e2,…,ei}), gk + {f} is not a matching of G; then gk, is called an i wings k-matching of G and mi(gk,G) is used to denote the number of i wings k-matchings of G. In this paper, it is proved that both mi(gk,G) and m(gk,G) are edge reconstructible for every connected graph G, and as a corollary, it is shown that the matching polynomial is edge reconstructible.     

联接图中的最长链

一、引言文中未加说明的述语均同于[1]。给定图 G,以 c(G)记其联通分支数,定义h(G)=min{|s|-c(G\S):S(?)V(G),c(G\S)>1},f(G)=min{d(u) d(v):u、v∈v(G),u=v,uv(?)E}。1978年 H.A.Jung 在[2]中证明了,当 f(G)≥n(G)-4,n(G)≥11,h(G)≥0时,G 含哈密顿圈。本文研究了上述参数与图中最长链所含点数 l(G)之间的关系,得到下述结果:     

关于连通图幂中边不交1-因子

本文讨论连通图幂G~n 存在 n 个边不交1-因子的条件.本文中所指图均为简单图.除特别强调外,所用术语、记号均与[1]中一致。定义.设 G 为简单连通图,n 为自然数,则 G~n 为 V(G~n)=V(G),E(G~n)={uv:d_G(u,v)≤n,u,v,∈V(G)}.对 G~n 的因子已有不少结果.主要有以下几个:     

具有与任意图正交的(g,f)-因子分解的子图

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

完全图圈分解的一种新方法

本文给出完全图圈分解的一种新方法，设Ｋｎ（ｎ≥３）是一个ｎ阶完全图，我们得到下列结果：（１）若ｎ为奇数，Ｇ是ｎ阶群，并且｛ｏ（ｘ）│∈Ｇ，ｏ（ｘ）≥３｝＝｛ａ１，…，ａｔ｝，则Ｋｎ＝ｍ１Ｃａ１＋…＋ｍｔＣａｔ。（２）若ｎ为偶数，Ｇ是ｎ阶群，Ｔ＝｛ｘ│ｘ∈Ｇ，ｏ（ｘ）＝２｝＝｛ｘ０，ｘ１，ｙ１，…，ｘｓ，ｙｓ｝，ｏ（ｘｉｙｉ）＝ｂｉ，ｉ＝１，…，ｓ及｛ｏ（ｘ）│ｘ∈Ｇ，ｏ（ｘ）≥｝＝｛ａ１，…，ａｔ     

消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

关于给定控制数的连通二部图的极大图的刻画

本文研究了给定控制数的连通二部图的极大图的结构问题.利用分类讨论思想和数学归纳法,刻画了控制数等于3和大于等于4这两类边数达到极值时的连通二部图.本文所得结果可用于进一步研究给定全控制数的连通二部图的极大图问题.     

三正则平面图的对偶图的哈密顿性的注记

本文给出了三正则平面图的对偶图为哈密顿图的一个充分条件。     

图的割宽问题

本文建立了Ｈａｒｐｅｒ型割宽下界估计式，由此求出了轮形图Ｗｎ、完全二部图Ｋ（ｍ，ｎ）、圈幂Ｃｎｒ、格子图：Ｐｍ×Ｐｎ、Ｐｍ×Ｃｎ、Ｃｍ×Ｃｎ以及乘积图：Ｋｍ×Ｐｎ、Ｋｍ×Ｃｎ、Ｃｍｓ×Ｃｎｒ、Ｋｍ×Ｋｎ和强乘积图Ｐｍ　Ｐｎ的割宽。     

关于图的导出森林独立系统

本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法.