无向图可迹的一个充分条件

无向图G是简单连通图,且最小度为δ.如果G中包含一条生成路,则G是可迹的.无向图G的叶子数L(G)是G中生成树所含的叶子数的最大数.基于L(G)和δ,证明了一个充分条件使得无向图G是可迹的,即设G为连通图,最小度为δ≤4.若δ≥(1/2)(L(G)+2),G是可迹的.     

星匹配数与(无符号)拉普拉斯特征值

设G是一个简单无向图,s 3是一个正整数.文章中,若K1,s-匹配数为m(G)的n阶连通图G满足n(s+1)m(G),则G的第m(G)大L-特征值μm(G)s+1,然后证明了类似结论对于Q-谱也成立.最后给出了几个判断图的哈密顿性的Q-特征值条件.     

关于图的连通DOMINATION的若干结果

设G是n阶连通图.γ_c(G),d_c(G),i(G)和ir(G)分别表示G图的连通Domination数,连通Domatic数,独立Domination数和Irredundance数,k(G)表示G的连通度.本文证明了下列结论. (1) 如n≥3,则i(G) γ_c(G)≤n [n/3]-2; (2) γ_c(G)≤4ir(G)-2; (3) γ_c(G)≤k(G) 1; (4) 如G≠K_n,则d_c(G)≤k(G). 此外,本文给出了满足等式γ_c(G) γ_c(G)=n和γ_c(G) γ_c(G)=n 1的图G的一个特征.     

关于图的连通Domination

设G是连通图。用r_c(G)、r_c(G)和ir(G)分别表示G的连通Domination数、全Domination数和Irredundance数,本文证明了下列结论: (1) r_c(G)≤3ir(G)-2 (2)r_c(G)≤2r_t(G)-2     

折叠交叉立方体的分支边连通度

r-分支连通度(边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且r是非负整数,如果G中存在某种点子集(边子集)使得G删除这种点子集(边子集)后得到的图至少有r个连通分支.则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的r-分支连通度(边连通度).n-维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得.该文利用r-分支边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到了折叠交叉立方体网络的2-分支边连通度,3-分支边连通度,4分支边连通度.确定了折叠交叉立方体FCQn的r-分支边连通度.     

几族3-优图

一个图 G中含有的三个结点的导出连通子图的个数 S3( G)在网络可靠性中起着重要作用 .在同点数同边数图类中具有最大 S3( G)的图称为 3-优图 ,它所代表的网络是点故障概率接近 1时的最可靠网络 .本文在已有的结果上进一步证明补图为 a K3∪ b K2 ∪ K1和 a K3-x的图分别是各自图类中唯一的 3-优图 ;补图为 a K3∪ ( b-1 ) K2 ∪ 2 K1和 ( a-1 ) K3∪ b K2 ∪ P3的图是该图类中仅有的两个 3-优图 .     

几类新的上可嵌入图

讨论了几类上可嵌入的边连通简单图,得到了如下结果:若G为简单连通图,且满足以下条件1)-3)之一:1)G为1-边连通的,且不含完全图K_3,α(G)≤3,2)G为2-边连通的,且不含完全图K_3,α(G)≤5,3)G为3-边连通的,且不含完全图K_3,α(G)≤10,则G是上可嵌入的,且在上述相应条件下,独立数上界都分别是最好的.     

关于3连通图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数．对任意k连通图，它的容错直径Dk不超过宽直径dk,本证明：当D2=2时，d3≤max{D， l，2D3-2}；当D2≥3时，d3≤(D2-1)[2(D2-1)(D3-1)-D2-2] 1．     

完全对换网络的限制连通度

完全对换网络是基于 Cayley 图模型的一类重要互连网络. 一个图 G 的 k-限制点(边)连通度是使得 G-F 不连通且每个分支至少有 k 个顶点的最小点(边)子集 F 的基数, 记作 \kappa_{k}(\lambda_{k}). 它是衡量网络可靠性的重要参数之一, 也是图的容错性的一种精化了的度量. 一般地, 网络的 k-限制点(边)连通度越大, 它的连通性就越好. 证明了完全对换网络 CT_{n} 的 2-限制点(边)连通度和 3-限制点(边)连通度, 具体来说: 当 n\geq4 时, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6; 当 n\geq3 时, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.     

K_(n,n)的局部最优可靠性

假设n点m边的简单无向图G=(V,E)的每个顶点完全可靠,各边相互独立地以同一概率q(0q1)发生故障,则用G不连通的概率P(G,q)作为衡量网不可靠程度的指标.如果对于充分接近q0的所有q都有P(G,q)P(H,q),则称在边故障概率q～q0时,网络G比H可靠.证明了当q～0时,Kn,n(n4)是2n点n2边图中局部最优可靠的.     

广义Petersen图的宽直径

Generalized Petersen graphs are commonly used interconnection networks,and wide diameter is an important parameter to measure fault-tolerance and efficiency of parallel pro- cessing computer networks.In this paper,we show that the diameter and 3-wide diameter of generalized Petersen graph P (m,a) are both O( m 2a ),where a ≥ 3.     

5连通图中的可去边

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least （3│G│ ＋ 2）/2 removable edges.     

无爪图中不相邻子图P_4和K_1的度和条件下的哈密尔顿性

研究子图的度和图的哈密尔顿性的关系,证明图~$G$ 是一个~$n$ 阶~3-\,连通无爪图且最小度~$\delta(G)\geq4$, 如果图~$G$ 中任意两个分别同构于~$P_4$, $K_1$ 的不相邻子图~$H_1$, $H_2$ 满足~$d(H_1)+d(H_2)\geq n$, 则图~$G$ 是哈密尔顿连通.     

张量对称类上诱导线性算子的数值半径

设V是一个n维线性空间,V_x~m(G)为V上的张量对称类.A为V的线性算子T的矩阵,K(A)为V_x~m(G)上的诱导线性算子K(T)的矩阵.本文从K(A)的数值半径Υ(K(A))和可分数值半径Υ_x(K(A))定义出发,研究了Υ(K(A))、Υ_x(K(A))与范数||A||_p(1≤p≤2)、广义矩阵函数d_x~G(A)的关系,得到了它们之间的两个不等式.     

Halin-图的点强全染色

图G(V,E)的一个k-正常全染色f叫做一个k-点强全染色当且仅当对任意v∈V(G), N[v]中的元素被染不同色,其中N[v]={u|uv∈V(G)}∪{v}．χTvs(G)=min{k|存在图G的k- 点强全染色}叫做图G的点强全色数．对3-连通平面图G(V,E),如果删去面fo边界上的所有点后的图为一个树图,则G(V,E)叫做一个Halin-图．本文确定了最大度不小于6的Halin- 图和一些特殊图的的点强全色数XTvs(G),并提出了如下猜想:设G(V,E)为每一连通分支的阶不小于6的图,则χTvs(G)≤△(G) 2,其中△(G)为图G(V,E)的最大度．     

K1,4-自由的模κ泛圈图

设G是2-连通的K1，4自由图．本文证明了当δ(G)≥κ 1时，G是模κ泛圈图．这一结果肯定了猜想2，继而也肯定了Thomassen猜想在2-连通图中的正确性．     

3连通平面图的可去边数

设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。     

Maximum chromatic polynomials of 2-connected graphs

In this paper we obtain chromatic polynomials P(G; λ) of 2-connected graphs of order n that are maximum for positive integer-valued arguments λ ≧ 3. The extremal graphs are cycles C_n and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{P(G; λ): G is 2-connected of order n and G ≠ C_n} and all extremal graphs relative to this property, with some consequences on the maximum number of 3-colorings in the class of 2-connected graphs of order n having _X(G) = 2 and _X(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2-connected graphs are determined.     

直径不超过2的2连通无爪图是哈密顿图

不包含2K_2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K_2并且不同构与K_2,P_3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryjá(?)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.     

恰有k条非基本边的极小3连通图

设G是简单3连通图．G\e(删除边e)和G/e(收缩边e)都不是简单3连通图,则e称为G的基本边．对于3连通图中的非基本边．Tutte证明了：唯一没有非基本边的简单3连通图是轮．Oxley和Wu确定了至多有3条非基本边的所有极小3连通图以及恰有4条非基本的极小3连通图．Reid与Wu确定了至多有5条非基本边的极小3连通图．在本文中,我们在极小3连通图中定义了三种运算,然后通过轮利用这些运算的逆运算给出恰有k(k■2)条非基本边的极小3连通图的一种构造方法．