单圈共轭图的最小广义Randic指标R-1

图G的广义Randic指标定义为Rα=Rα（G）=∑uv∈E（G）（d（u）d（v））^α,其中d（u）是G的顶点u的度,α是任意实数．本文确定了单圈共轭图的广义Randic指标R-1的严格下界,并刻划了达到最小R-1的极图,这类极图还是化学图．     

最大Randid指标的k悬挂点化学树的性质

化学分子图G的Randie指标为R（G）=∑wv（dG（u）dG（v））^2/1．其中uv是G的边，dG（u）表示的顶点u的度．本文刻画了具有最大Randie指标的k悬挂点化学树的一些性质．     

利用计算机计算n阶图的特征多项式的方法

1引言设G=（V,E）为n阶无向的简单连通图.记N（v）为v的所有相邻点的集合,则d（v）=|N（v）|称为顶点v的度.若d（v）=1,则称v为G的一个悬挂点.设D（G）=diag（d（v₁）,d（v₂）,…,d（v_n））和A（G）分别表示图G的度对角矩阵和邻接矩阵,则L（G）=D（G）-A（G）称为图G的Laplace矩阵,而Q（G）=D（G）+A（G）称为图G的SignlessLaplace矩阵.用符号N_m×n表示一个m行n列的矩阵,M_n表示一个n阶的方阵.特     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

哈密顿线图的一个新结果

设G是一个简单图,G1∈G,G1在G中的度定义为d（G1）=∑v∈V（G）d（v）,其中d（v）为v在G中的度数．主要结果是：设G是n≥3阶几乎无桥的简单连通图,且G≠K（1,n-1）、Q1和Q2,若对G中任何同构于四个顶点路的导出子图I,有d（I）≥2n-6,则G有一个D-闭迹,从而G的线图L（G）是哈密顿图．     

哈密顿线图的一个充分条件

对于图G的任意边e=uv,边的度定义为d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v的度.本文的主要结果是: 设G是几乎无桥的p≥2阶简单连通图,且G(?)K_(1,p-1),若对任意相距为2的两边e_1和e_2,d(e_1)+d(e_2)≥2p-6,则G有一个D—闭迹,从而G的线图L(G)是哈密顿的.     

最大Randi(c)指标的k悬挂点化学树的性质

化学分子图G的Randic指标为R(G)=E(dG(u)dG(v))-(1/2).其中uv是G的边,dG(u)表示G的顶点u的度.本文刻画了具有最大Randic指标的K悬挂点化学树的一些性质.     

固定直径的树的Wiener指数

图G的wiener指数定义为图中所有点对u,v的距离之和∑d（u,v）. 在这篇文章中,我们刻画了在n个顶点直径为d的所有树中具有第三小wiener指数的树的特征以及介绍了得到这类树的wiener指数排序的方法.     

导出子图和周长的局部定理

设G是n阶2-连通图，3≤c≤n.本文绘出对于图G的每一个同构于K1.3或Z1的导出子图L，若d（u）且如果dL（u，v）=2有（v）=min{，|M3（u）|/2}这里M3（u）={v|dc（u,v）≤3}，则G包含长至少为c的圈．     

可圈的一个充分条件

本文我们证明如下结果:设G=(V,E)是一个n(n≥3)阶k-连通(k≥2)图,记X1,X2,…,Xk为V的子集,X=X1∪X2∪…∪Xk.若对每个I,I=1,2,…,k,满足:对任意的u,v∈Xi,有d(u) d(v)≥n或|N(u)∪N(v)|≥n-δ或|N(u)∩N(v)|≥α,这里δ是G的最小度,α是G的独立数,则G是X-可圈的.     

点度与图的上可嵌入性

本文证明了:(1) 设G是2-连通简单图,且不含K_3,若对任意一对距离为2的点u,u,有max{d(u),d(u)}>n/3-1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/3-1"是不可达的;(2) 设G是3-连通简单图,若对任意依次相邻的三点u,u,W,有max{d(u),d(u),d(w)}≥n/6+1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/6+1"是最好的.     

广义de Bruijn和Kautz有向图的双向控制集

设G=(V,A)是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV(G),如果对于任意点v∈V(G)\T,都存在点u,w∈T(u,w可能是同一点)使得(u,v),(v,w)∈A(G),则称T是G的一个双向控制集.有向图G的双向控制数γ~*(G)是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.     

图的度和与扩路

本文讨论了两顶点的度和与路可扩之间的关系,得到了如下结果:设G是n阶图,如果G中任意一对不相邻的顶点u,v满足d(u)+d(v)≥n+n/k(2≤k≤n-2),则G中任意一个满足k+1≤|P|相似文献   

广义de Bruijn和Kautz有向图的距离控制数

对于任意的正整数(?),强连通图G的顶点子集D被称为距离(?)-控制集,是指对于任意顶点v(?)D,D中至少含有一个顶点u,使得距离dG(u,v)≤(?)．图G距离(?)- 控制数γe(G)是指G中所有距离(?)-控制集的基数的最小者．本文给出了广义de Bruijn 和广义Kautz有向图的距离(?)-控制数的上界和下界,并且给出当它们的距离2-控制数达到下界时的一个充分条件．从而得到对于de Bruijn有向图B(d,k)的距离2-控制数γ2(B(d,k))= ．在该文结尾,我们猜想Kautz有向图K(d,k)的距离2-控制数γ2(K(d,k))= .     

偶图的K3.3剖分

设G＝（X，Y；E）是一个偶图。如果|X|≥2|Y|-3且d(v)=3对任意v∈X,那么G含有K3.3的剖分。有例子表明|X|的下界在一定程度上是不可改进的。     

图的f-边覆盖染色

设G(V,E)是至少含有一条边的无环图,f厂是定义在V上的整值函数且对任意的v∈V,有1≤f(v)≤d(v).若边染色C使所用的每一种颜色在任一顶点v上至少出现f(v)次,则称该染色C为,f-边覆盖染色.能对图G进行,f-边覆盖k-边染色的最大颜色数k,称为图G的,f-边覆盖色数,记为X'fc(G).本文提供了一个关于X'fc(G)的Vizing型定理,使一些已有重要结论得以推广;研究了一些使X'fc(G)达到该Vizing型定理上界的几类图或函数f,还讨论了f-边覆盖染色的变型,提出了一些可进一步研究的问题.     

On $f$-Edge Cover Chromatic Index of Multigraphs

Let $G$ be a multigraph with vertex set $V(G)$. Assume that a positive integer $f(v$) with $1 ≤ f(v) ≤ d(v)$ is associated with each vertex $v ∈ V$. An edge coloring of $G$ is called an $f$-edge cover-coloring, if each color appears at each vertex $v$ at least $f(v)$ times. Let $χ′_{fc}(G)$ be the maximum positive integer $k$ for which an $f$-edge cover-coloring with $k$ colors of $G$ exists. In this paper, we give a new lower bound of $χ′_{fc}(G)$, which is sharp.     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.     

图的半强积的邻点可区别染色

两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a~((r))(G),其中r=1,2,且X_a~((1))(G)与X_a~((2))(G)分别表示G的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.