排列图的若干k~*-连通性

排列图An,k是星图的推广,但它的阶却比星图有更好的灵活性.证明了:当n5,n-k3时,排列图An,k为3*-连通图;当n6,n-k3时,排列图An,k为4*-连通图.     

图的Wiener指数的逆区间

连通图G的Wiener指数是指图中所有点对的距离之和。图的Wiener指数逆问题是指给定一个正整数k,刻画图G使得其Wiener指数等于k。n阶图的Wiener指数的最大逆区间问题是指:寻找一个长度最大的正整数区间[a,b],使得对于该区间内任意正整数c,均存在一个n阶连通图G使其Wiener指数为c。在此情况下,主要研究n阶连通图的Wiener指数的逆区间问题,刻画了双星图;通过移除星图上的悬挂点,以及连接星图悬挂点的方法,使得图的Wiener指数达到连续的目的,从而增大了Wiener指数的逆区间,并提出了相关定理与推论。     

乘积形式的离心连通指数

设G=（V,E）是一个图,定义ηc（G）=∏uv∈E（G）（eu＋ev）,eu表示u点在G中的离心率,ηc（G）表示图G的乘积形式的离心连通指数,该指数对有机分子的结构、性质具有良好的预测作用.通过计算,给出用其他图的不变量对离心连通指数建立上界和下界的方法.此外,还找出了在直径为d、顶点数为n的树（2≤d≤n-2,n〉5）中,乘积形式的离心连通指数的最小值,并推断出顶点数为n的树中,倒数前3位的乘积形式的离心连通指数的3种树如下：1）Sn;2）n个顶点的双星图;3）对有5个顶点道路的中心添加（n-5）条悬挂边而成的树.     

关于Fibonacci三角形与Lucas三角形

设F_n为第n个Fibonacci数,即f_0=0,F_1=1,F_n=F_(n-1)+F_(n-2)(n≥2),边长为Fibonacci数的Heron三角形称为Fibonacci三角形,文[1]中有如下猜想,当1≤k相似文献   

图的升分解的一些充分条件

A Lavi等人在[1]中定义了图的升分解,并提出猜想:设自然数n≥2,G是星S1,S2,…,Sk的并图,Si含有ai条边,n ≤ ai ≤2n-2,∑ai=((n+1)/2),则G可升分解为星图的并。本文说明n=2时猜想不成立。当猜想中的n≥2修改为n≥3时，并不妨假设 ，本文证明了只要下列条件之一满足时猜想就成立:(1) > n+2K一2，且4(n一K+2)≤2 < +3n一4K+8;(2) ≥n+3K-6且     

关于G∪(m_i-C_4) from i=1 to n的优美性

对于自然数mi,n给出一类非连通图C4 蛇并图∪ni=1mi-C4,并证明了当mi≥2,i=1, 2,…,n这类图是优美图,也是交错图,从而给出一类图G和G∪ni=1mi-C4 的并图是优美图的一种方法。     

路和圈的弱直积图的星边色数

若图G的一个正常染色使得G中没有长为4的路是2-边染色的,则称此染色是G的一个星边染色,使得图G有星边染色的最小颜色数为星边色数,记作x′s(G).文章给出了路和圈的弱直积图的星边色数:对于图Pm×Cn(m≥2,n≥3)的星边色数分以下三种情形:x′s(P2×Cn)=3(n≥3);5≤x′s(Pm×Cn)≤6(m=3,4;n≥3);6≤x′s(Pm×Cn)≤8(m≥5,n≥3).     

Halin图的均匀染色

Halin图是最小度不小于3的3－连通平面图,且存在一个面,删除关联于该面的所有边后是一棵树。称图G为均匀k-可着色的,如G的顶点集V可分划成K个独立集V1、V2、…Vk,使||Vi|-|Vj||≤1（0≤i＜j≤k）;称使图G的均匀k-可着色的最小整数k为G的均匀色数,记为xe（G）。本文对非K4的Halin图证明△（G）≠4时,对任意的整数k≥［△（G）／2]＋1;当△（G）＝4时,对任意整数的k≥4,G是均匀k-可着色的。从而对Halin图证明了均匀染色猜想（ECC）。     

2类非连通图的优美性

本文利用构造法,研究了2类非连通图图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1的优美性.证明了下面的结论:设m为任意的正整数,Gm-1是表示边数为m-1的优美图,则当m≥2时,图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1都是优美图.其中,C3是表示三个顶点的回路图,P2∨K2—是两个顶点的路P2与两个孤立顶点的图K2—的联图,m·C3是m个图C3恰有一个公共点的图,m·(P2∨K2—)是m个图P2∨K2—恰有一个公共点的图,G∪Gm-1是把图G与Gm-1不相交并起来所得的非连通图.     

线图连通度的界

首先给出了线图连通度κ_L的一个上界;κ_L≤δ+△-2;其次得出了在条件δ≥[n/2]+1下κ_L的一个很好的下界;κ_L≥2δ-2;由此得到当δ≥[n/2]+1时,若G为正则图,则κ_L=2δ-2,若G为拟正则图,则κ_L=2δ-2或2δ-1。