S_m+K_1及其相关图的协调性

一个含e条边的简单图G被称为是一个强协调图,若存在V(G)到{0,1,…,e-1}的一个单射h,使导出映射h~*:h~*(uv)=h(u)+h(v)是E(G)到{1,2,…,e}的一个双射。本文证明了图S_m+K_n与S_m+K_2都是强协调图。从而回答了[3]中的一个open问题。     

齿轮图都是调和图

称一个含q条边的简单图G是一个调和图,若存在单射h:v(G)→{0,1,…q-1}使得导出映射h~*:E(G)→{0,1,…,q-1},h~*(uv)≡h(u)+h(v)(modq)是一个双射。这里u,v∈V(G),uv∈E(G)。在轮W_n的轮圈C_n上每两个相邻点之间加入一顶点所得之图称为齿轮图(?)_n。本文将证明,所有齿轮图(?)_n都是调和图。从而回答了[4]中提出了一个open问题。     

一类二部图的奇优美性

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足:1)L为G的顶点集V到{0,1,…,2|E|-1}的一个单射;2)由L'(e)=|L(u)-L(v)|(其中e=uv)决定的边标号L'是从G的边集E到{1,3,…,2|E|-1}的一个双射.根据奇优美图的定义,研究了一类二部图G*的奇优美标号.     

轮形图和扇形图的优美性

设L为简单无向图G的一个顶点标号,若L满足:(1)L为G的顶点集V到{0,1,…,|E|}的一个单射;(2)由L(′e)=|L(u)-L(v)|(其中e=uv)决定的边标号L′是从G的边集E到{0,1,…,|E|}的一个双射,则L称为图G的优美标号.论文研究了轮形图和扇形图的优美性,并给出它们的优美标号.     

一类新图的奇优美性的研究

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足以下两条:(1)L为G的顶点集V到{0,1,…,2 ︱E︱-1}的一个单射;(2)由L′(e)=︳L(u)-L(v)︳(其中e=uv)决定的边标号L′是从G的边集E到{1,3,…,2 ︱E︱-1}的一个双射.本文给出了一类特殊简单图G*的奇优美标号,并给出了相应的标号算法及相关的一些证明.     

关于分数(g,f)-2-覆盖图

设G是一个图,并设h是定义在图G的边集E(G)上的一个函数,使对任意的e∈E(G),有h(e)∈[0,1]。令dhG(x)= x瘕?h(e),则称dhG(x)是G中顶点x的分数度。若h满足对任意的x∈V(G),有g(x)≤dhG(x)≤f(x),则称h是G的一个分数(g,f)-因子。一个图称为分数(g,f)-2-覆盖图,如果对图G中的任何两条边e1和e2,G都有一个分数(g,f)-因子h满足h(e1)=1和h(e2)。本文给出了一个图是分数(g,f) 2 覆盖图的充分必要条件。     

一类上可嵌入图

本文主要证明了如下结果 :设G为 3-连通图 ,若G的顶点集存在一个C一划分 {V1,V2 ,… ,Vn} ,使得对每个 1≤i≤n ,|Vi|≡ 0 (mod 2 ) ,且对任意的v∈V(G) ,dG=(v)≡ 1(mod 2 ) ,则G是上可嵌入的 .     

广义棱柱和补棱柱中的超欧拉图

对于一个图G,它的顶点标号为1,2,…,n,S_n是在{1,2,…,n}上的n次对称群,α∈S_n是一个置换,图G的α-广义棱柱,记作α(G),是指图G的2个复制,G_x和G_y,连同所有置换边(x_i,y_(α(i))(1≤i≤n)所构成的图.图G的补棱柱,记作G G,同构于由G和G的补图G的不交并,再加上一个连接G和G对应顶点的完美匹配构成的图.如果图G有一个生成欧拉子图,那么称G是超欧拉图.研究了完全二部图、路和圈的广义棱柱和补棱柱是超欧拉图的充要条件.     

笛卡尔乘积和直积图的全{k}控制划分数（英文）

给定正整数k,不含孤立点的图G的全{k}控制函数(T{k}DF)是从顶点集V(G)到{0,1,2,…,k}的映射f使得对任意的v∈V(G),与v相邻的点在f下的赋值之和至少为k.若元素两两不同的全{k}控制函数集合{f_1,f_2,…,f_d}满足d∑i=1f_i(v)≤k对任意v∈V(G),则称该集合为G的全{k}控制族(T{k}D族).含有函数最多的G的全{k}控制族的函数数量成为全{k}控制划分数,记为d_t~({k})(G).2013年,Aram等提出了以下问题:是否当4nmk时d_t~({k})(C_m□C_n)=3,当4nmk时d_t~({k})(C_m□C_n)=4.这里证明了当4nmk且k≥2或4nmk且2nk时d{k}t(C_m□C_n)=3.该结论部分回答了上述问题.更进一步,确定了路和圈、路和路、圈和圈的全{k}控制划分数.     

哈密尔顿图的局部化临域并条件

采用图的局部化临域并条件 ,本文证明了下述结果 :设G是一个p阶 2 -连通图 ,Li- 相似文献   

双Cayley图的自同构群

设G是有限群，S是G的一个子集（可能含有单位元）。群G关于S的双Cayley图BCay(G,S)是以Gx｛0，1｝为点集而以｛｛（g,0），（sg,1）｝|g∈G,s∈S｝为边集的二部图。考查了双Cayley图BCay(G,S)的自同构群A，并决定了NA(Rι^r(G)）的结构。     

自同构群作用下具有两个轨道的连通图的连通性(英文)

若连通图G在自同构群作用下具有两个轨道V1和V2且满足|V1|=|V2|;G[V1]是k-正则图;G[V2]是r-正则图且G[V1V2]是l-正则图,则K(G)≥min{k,r}+1.构造的例子表明上述结果是最好可能的.     

几类特殊图的一般指标集

令G=(V(G),E(G))为一简单连通图,V(G)和E(G)分别是图G的顶点集和边集.一个顶点标号函数f:V(G)→Z2诱导出一个边标号函数f*:E(G)→Z2,其中?v1 v2∈E(G),有f*(v1v2)=f(v1)+f(v2).当标1和标0的顶点数相差m(m<|V(G)|)时,标号为1和0的边数差的集合称为图G...     

关于（g,f）-3-消去图

设G是一个图,用V（G）和E（G）表示顶点集和边集,并设g和f是定义在V（G）上的两个非负整数值函数且g〈f。图G的一个（g,f）-因子是G的一个支撑子图F使对任意的x∈V（G）有g（x）≤dF（x）≤f（x）。如果过图G的任何三条边不属于它的一个（g,f）-因子,则称图G是一个（g,f）-3-消去图,本文给出了一个图是（g,f）-3-消去图的一个充分条件。     

轮图中间图的pebbling数

图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的一个移到与其相邻的一个顶点上.图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.文章研究轮图中间图的pebbling数.     

泛圈图的一个新的充分条件

设G是一个阶为n的2－连通简单图,αv表示G中包含点v的最大独立集的点数,对任意uv不属于E,设Tuv=V\(N(u)∪N（v)),αuv=min{αu,αv}。本文证明了：如果对于任一对不相邻点u,v,｜N（u)∩N(v)｜≥min{αuv-1,｜Tuv｜},则除了一些特殊图外,对于G的任一点x和任意整数k(4≤k≤n),G包含长度为k县包含点x的圈。     

伞状树的奇强协调性

设G=V,E是一个简单图,若存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足(1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);(2)对任意的e1,e2∈E,若e1≠e2则g(e1)≠g(e2),此处g(e)=f(u)+f(v),e=uv,且{g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇强协调图,f为G的奇强协调标号,讨论了一类树的奇强协调性.     

一类单圈图的优美性和平衡性

设L为简单无向图G的一个顶点标号,L称为图G的优美标号,若L满足以下两条：（1）L为G的顶点集V到{0,1,2,…,｜EI｜}的一个单射;（2）由L’（e）=｜L（u）-L（v）｜（其中e=uv）决定的边标号L’是G的边集E到{1,2,…,｜EI｜}的一个双射．进一步,若存在正整数c,使得对每一个uv ∈ E（G）满足L（u）≤c〈L（v）或L（w）≤c〈L（u）,则称L为图G的平衡标号,其中c为平衡特征．主要研究一类单圈图的平衡性并给出相应的平衡标号及其特征．     

几类图的pebbling数

图G的pebbling数 f （G ）是最小的整数n ,使得不论n个pebbles如何放置在图G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebbles,而把其中的一个移到与其相邻的一个顶点上。文章给出图Fn？Pk、Wn？Pk和双轮图Wm？Pk-1？Wn的peb？bling数。