三路树P(m,n,t)是边幻图的证明(Ⅱ)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V ∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

三路树P(m,n,t)是边幻图的证明(II)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

偶数阶W(4,n)的κ-边优美的图标号

设k是一个非负整数,G是一个p点q边图.如果将G的边用k,k+1,k+2,…,k+q-1进行标号,而顶点标号模p运算后各不相同,那么称图G是后一边优美的.记EGI(G)是所有满足G是k-边优美的k的集合,称EGI(G)是G的边优美指标集.主要是研究n为偶数时W(4,n)的边优美指标集.     

关于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-树.     

关于图D(Cn),C2n,C3n的星全色数

图G的一个k-全着色满足G的任何路长为2的点,边着色均不相同.我们称它为G的k-星全着色.图G的全部k-星全着色中最小的k称为图G的星全色数,记为Xn(G).讨论一些圈的星全染色问题,得到了图D(Cn)(n=0(mod 3)和n=0(mod 5)),C2n(n=0(mod 20)和n=0(mod 28))以及C3n(n=0(mod 28)和n=0(mod 36))的星全色数.     

关于图中子图的（n,k）—正交因子分解

设G是一个具有顶点集V(G)和边集E(G)的图. 设g和f是定义在V(G)上的两个整数值函数,使得g(x)f(x)对所有的点x∈V(G)都成立.如果G是一个(mg+n,mf-n)-图,1n<m2k,且g(x)2k-1对所有的点x∈V(G)都成立,则对任意给定具有|E(H)|=nk边的G的子图H,存在G的一个子图G′使G′有一个(g,f)-因子分解(n,k)-正交H.     

边无关数为q的n阶树的谱半径

设G为n阶简单图,λ1（G)G的谱半径,本文主要证明了：若T是边无关数为q1的n阶树,q1≥q,则λ1（T≤λ1（K^q-11,n-q), 等号成立当且仅当T=K^q-1 1,n-q.这里K^q-1 1,n-q为K1,n-q的q-1个悬点各接出一条悬挂边而得到n阶树。     

关于p3n的优美性

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

关于图P3n优美性的研究

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

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

用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)是色唯一的.同时还给出了一个猜想.     

关于图是(r,n)-临界图的一个邻域条件

设n，m和r是满足r≥2，n≥0，m≥3的整数，且当r是奇数时，假设r≥m-1．称一个图为K1,m-free，如果它不包含以Kt,m为导出的子图．称一个图G为一个（r,n）-临界图，如果在删去G的任意n个点后，剩下G的子图都有一个r-因子,设G是一个Kl,m-free的（n＋1）-连通图，且阶为｜G｜以及r（｜G｜≥n）是偶数,证明了：如果G的最小度至少是r＋n＋m-1，阶｜G｜≥8r5＋n，并且对V（G）的任意独立点集{x1，x2}都有｜NG（x1）∪NG（x2）｜≥（｜G｜＋n）／2，那么G是一个（r,n）-临界图．关于G的最小度和｜NG（x1）∪NG（X2）｜的下界是紧的。     

模n剩余类环零因子图的一些性质

模n剩余类环Z_n的零因子图记为Γ(Z_n),其顶点为Z_n的所有非零零因子,两个不同的顶点x与y有一条边相连当且仅当xy=0.对Γ(Zn)和(?)的欧拉性及一笔画性进行了探讨,完全确定了当n为何值时,Γ(Z_n)和(?)为欧拉图或是一笔画图.     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009     

一个关于图是分数(k,n)-临界的邻域并条件

设G是一个图,以及k是满足1≤k的整数.一个图G在删除任意n个顶点后的子图均含有分数k-因子,则称G是一个分数(k,n)-临界图.给出了图是一个分数(k,n)-临界图的一个邻域并条件,并且该条件是最佳的.     

广义图K(n,m)的全色数

1965年,M.Behzad和Vizing分别提出了著名的全着色猜想:即对于简单图G有:XT(G)≤△+2,其中△是图G的最大度.本文确定了完全图Kn的广义图K(n,m)的全色数,并利用它证明了Lm×Kn(m≥3)是第Ⅰ型的.     

连通图的度序列及连通平面图的低度点个数

美国数学家Bondy给出了一个非负整数序列为简单图的度序列的充要条件.本文对此进行了发展,证明了一个正整数序列为连通简单图的度序列的充要条件;然后在此基础上又探讨了平面图的低度点个数问题并定义了描述连通平面图的低度点个数的一个概念φ(n,m),并对某些低阶平面图求出了φ(n,m)的值.最后给出了φ(n,m)的上下界.     

图P^3n的奇优美标号算法

本文讨论了图P^3n的奇优美性,给出了图只奇优美标号算法．     

关于联图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是优美图的结果.     

(a,b,n)-临界图的几个充分条件

设G是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 .     

关于图是(g,f,n)-临界图的充分条件

设G是一个图. 设g和f是两个定义在V(G)上的整值函数使得对V(G)所有的顶点x有g(x)f(x). 图G被称为(g,f,n)-临界图,如果删去G的任意n个顶点后的子图都含有G的(g,f)-因子. 本文给出了图是(a,b,n)-临界图几个充分条件. 进一步指出这些条件是最佳的. 例如,如果对V(G)所有的顶点x和y都有g(x)＜f(x), n+g(x)dG(x)和g(x)/(dG(x)-n)f(y)/dG(y),则G是(g,f,n)-临界图.