关于图P3n优美性的研究

在n个顶点的路Pn上,当且仅当两点的距离为3时增加一条边,所得的图称为P3n,本文给出了图P3n(n≥4)的优美标号,从而证明了P3n都是优美图.     

P(n,2)的符号全加强数

图G的符号全加强数的定义为:对于E~c(G)中的任意一子集S,使得不等式γ_s~t(G+S)γ_s~t(G)成立的最小的集合S的势.给出了一般Petersen图P(n,2)的符号全加强数:对于任一正整数n≥6,当n三2(mod 3)时,R_s~t(P(n,2))=2;当n≡1(mod 3)时,R_s~t(P(n,2))=3;当n≡0(mod 3)时,R_s~t(P(n,2))=5.     

关于q-树二次整子图和n阶加点q-树色多项式的注记

在这篇文章中我们成功地仅用色多项式表征了最小度不等于q-3的q-树的二次整子图和n阶加点q-树,即当图的最小度δ(G)≠q-3时,n阶图G具有色多项式P(G;λ)=λ(λ-1)…(λ-q+2)(λ-q+1)~3(λ-q)~(n-q-2), n≥q+2,当且仅当G是n阶q-树的二次整子图或n阶加点q-树.     

连通的三重Kn-残差图

Erds P,Harary F和Klawe M研究了Kn-残差图,并对连通的m-Kn-残差图提出了一些结论和猜想．利用容斥原理以及集合的运算性质等方法,研究了连通的3-Kn-残差图,得到当顶点最小度为n时,3-Kn-残差图最小阶的计算公式以及相应的唯一极图．当n=2时,得到最小阶为ll以及相应的极图;当n=3时,得到最小阶为20并找到两个不同构的极图,不满足Erdos等提出的结论;当n=4时,得到最小阶为22及相应的极图;当n=8时,可以找到两个不同构的3-Kn-残差图,不满足Erdos等提出的结论;最后证明了当n=9,10时,最小阶分别为48和52以及相应的唯一极图,验证了Erdos等在文献（Residually-complete graphs[J]．Annals of Discrete Mathematics,1980,6：117．123）中提出的结论．     

关于一类立方图的可连通性

文献[1]中提出阶为n(n≥3)的路的立方图是可圈图当且仅当n为奇数,本文主要证明阶为n(n≥3)的路的立方图是可连通图当且仅当n为奇数,从而加强了文献[1]中的结论.     

连通的三重K_{n}-残差图

Erd\"{o}s P, Harary F和Klawe M研究了K_{n}-残差图, 并对连通的m-K_{n}-残差图提出了一些结论和猜想. 利用容斥原理以及集合的运算性质等方法, 研究了连通的3-K_{n}-残差图, 得到当顶点最小度为n时, 3-K_{n}-残差图最小阶的计算公式以及相应的唯一极图. 当n=2时, 得到最小阶为11以及相应的极图; 当n=3时, 得到最小阶为20并找到两个不同构的极图, 不满足Erd\"{o}s等提出的结论; 当$=4时, 得到最小阶为22及相应的极图; 当n=8, 可以找到两个不同构的3-K_{8_{}}-残差图, 不满足Erd\"{o}s等提出的结论; 最后证明了当n=9,10时, 最小阶分别为48和52以及相应的唯一极图, 验证了Erd\"{o}s等在文献~(Residually-complete graphs [J].Annals of Discrete Mathematics, 1980, 6: 117-123) 中提出的结论.     

一类完全三部图的色唯一性

用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想.     

连通的K_{n}-残差图

m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图.     

骨牌覆盖问题与一类递推数列

问题用n个2×1的矩形(这种矩形我们称之为骨牌或多米诺)覆盖2×n的棋盘,有多少种不同的盖法? 下面的讨论用图1表示一张骨牌. 1.原问题的解决 1.1特例探讨 当n=1时,显然只有一种盖法(图1); 当n=2时,有两种盖法(图2); 当n=3时,有三种盖法(图3);     

关于p3n的优美性

设G(V,E)是一个简单图,对自然数k,当V(Gk)=V(G),E(Gk)=E(G)∪{uv|d(u,v)=k},则称图Gk为k-次方图.本文证明了图P3n的优美性.     

具有匹配对网络模型的优美性

在当今网络研究中,人们需要将某些特殊的图分解为指定的结构.优美图可以被运用到图分解中.得到一些构造优美图的可算法化的方法,并构造较为复杂的优美图.     

图Cn及其r-冠的新的优美标号

研究了关于图的r-冠的优美标号的一个问题,证明了：当n≡0,3（mod 4）时,图Cn及其r-冠是优美图,所给出的新的优美标号不同于现有文献中得到的结果.进而证明了当n≡0（mod 4）时,图Cn及其r-冠也是交错图.     

一类偶阶图的边优美性

本文讨论了一类偶阶图的边优美性。同时得到了完全图是边优美图的充要条件。     

Simply sequentially additive labelings of 2-regular graphs

We conjecture that any 2-regular simple graph has an SSA labeling. We provide several special cases to support our conjecture. Most of our constructions are based on Skolem sequences and on an extension of it. We establish a connection between simply sequentially additive labelings of 2-regular graphs and ordered graceful labelings of spiders.     

关于联图P_1VP_n的k-强优美性

本文研究了联图P_1VP_n的k-强优美性问题.利用K-强优美图的定义,获得了联图P_1VP_n是k-强优美图的必要条件,还得到了当n:2k-1时联图P_1VP_n是k-强优美图,亦是k-优美图,及当n≥3时联图P_1VP_n是2-强优美图,也是2-优美图的结果,推广了联图P_1VP_n是优美图的结果.     

几类有趣图的奇优美性和奇强协调性

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4)|g(e)|e∈E}={1,3,5,…,2|E|-1},则称G为奇优美图,f称为G的奇优美标号.设G=〈V,E〉是一个无向简单图.如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1},满足:1)f是单射;2)■uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1,3,5,…,2|E|-1},则称G是奇强协调图,f称为G的.奇强协调标号或奇强协调值.给出了链图、升降梯等几类有趣图的奇优美标号和奇强协调标号.     

积图P_n×P_m的奇优美性和奇强协调性

给出了积图P_n×P_m的奇优美标号和奇强协调标号.     

关于P_(r,(2s-1))的奇优美标号

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2 |E|-1}满足1)对任意的u,v∈V,若u≠v,则(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4){g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇优美图,f称为G的奇优美标号.Gnanajoethi提出了一个猜想:每棵树都是奇优美的.证明了图P_(r,(2s-1)是奇优美图.     

一类优美图

设u、ν是两个固定顶点.用b条内部互不相交且长度皆为a的道路连接u、ν所得的图用P_a,b表示.KM.Kathiresan证实P_2,2m-1(r,m皆为任意正整数)是优美的,且猜想:除了(a,b)=(2r+1,4s+2)外,所有的P_a,b都是优美的.杨元生已证实P_2r+1,2m-1是优美的,并且证实了当r=1,2,3,4时的P_2r,2m也是优美的.本文证实r=5,6,7时P_{2r,2m相似文献}   

(向量)R_n和(向量)G_n的有向优美性

优美图可用在图论中的某些H-分解问题中,很多人研究无向图的优美标号.研究有向优美标号,通过对阶数奇偶性的讨论,给出了n(≥2)阶有向路(向量)P_n和n(≥3)阶有向(向量)C_n圈是有向优美的充分条件.