关于Double图的符号控制数

图的符号控制数在现实生活中有许多应用背景,但图的符号控制数的计算是NP完全问题.给出了一般图G的Double图的符号控制数下界,确定了圈和路的Double图的符号控制数.

若干Double图的点可区别边染色

对一个正常的边染色满足不同点的点所关联边色集合不同,称为点可区别边染色(VDEC),其所用最少染色数称为点可区别边色数。就此用构造法研究了一些Double图的点可区别边染色,得到了星、扇和轮的Double图的点可区别边色数,验证了它们满足点可区别边染色猜想(VDECC)。

一些图的Double图的点可区别全色数

文献[2]定义点可区别全染色,对一个图其所用最少染色数称为它的点可区别全色数.本文得到了星、扇和轮的Double图的点可区别全色数.

Double图的Kirchhoff指标

一个图的Kirchhoff指标定义为Kf(G)=∑ni=1∑nj=1rij/2,其中rij是顶点vi和vj之间的电阻距离.首先得到了一个图的Kirchhoff指标与其double图的Kirchhoff指标之间的关系式,然后利用此关系式分别确定了具有前三大和前三小Kirchhoff指标的double树.

关于一些图的Double图的全色数

图的全染色是指对顶点和边同时染色,使得相邻或相关联的元素染不同的颜色,其所用最少染色数称为全色数,记为ΧT(G).本文得到了星、扇和轮的Double图的全色数.

Double图的撞击时间的期望值

令G为简单连通图,DG为其double图,称图G的随机游走从点u首次到达点v所需步数的期望值为点u到点v的撞击时间的期望值。本文给出了DG和G中任意两点撞击时间的期望值之间的关系。

Double图的广义特征多项式

利用代数方法得到了Double图的广义特征多项式的一个表达式,在此基础上得到了正则Double图的广义特征多项式及其一系列谱,以及其谱关于其生成树数目和Kirchhoff指数的应用。

n-double图的连通性

设G_1=(V_1,E_1),G_2=(V_2,E_2)是两个连通图,直积(direct product)(也称为Kronecker product,tensor product和cross product)G_1G_2的点集为V(G_1G_2)=V(G_1)V(G_2),边集为E(G_1G_2)={(u_1,v_1)(u_2,v_2):u_1u_2∈E(G_1),v_1v_2∈E(G_2)).简单图G的n-double图D_n[G]=GT_n,其中n个点的全关系图T_n是完全图K_n在每个点加上一个自环得到的图.在本文中,我们研究了D_n[G]的(边)连通性,超(边)连通性.

图的符号全控制数

设图G=(V,E)为一个图,一个双值函数f:v→{-1,+1},若S?V,则记f(S)=∑V∈Sf(V)。如果对任意的顶点ν∈V,均有f(N(ν))≥1成立,则称f为图G的一个符号全控制函数。图G的符号全控制数定义为γst(G)=min{f(V)|f是图G的一个符号全控制函数}。本文首先给出一般图的符号全控制数的下界,然后用分类讨论和穷标法得到了两类图广义Petesen图P(n,k)和Double广义Petesen图DP(n,k)的符号全控制数的精确值,这里n≡0(mod3),k≠0(mod3)。

图的无符号拉普拉斯特征值α次幂总和的界

令G为简单图.sα（G）等于图G的无符号拉普拉斯特征值α次幂的总和,其中α为实数且α≠0,1.本文我们得到一些连通图的sα（G）的新的界,并给出了正则图的Mycielskian图、正则图及半正则二部图的Double图这些特殊图类的sα（G）的新的界.由这些结论的特殊情况可得到相应图的关联能量的界.