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

对于简单图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的奇优美标号和奇强协调标号.     

太阳图的奇优美性和奇强协调性

设k_1,k_2,…,k_n是非负整数,C_n=v_v_2…v_nv_1是有n个顶点n条边的圈,则称图C_n+{v_1v_(11),v_1v_(12),…,v_1v_1k_1,v_2v_(21),…,v_2k_2,…,v_nv_(n1),…,v_nk_n}为(k_1,k_2,…,k_n)轮环图,简记为C(k_1,k_1,…,k_n).研究了太阳图1C_n的奇优美性及其奇强协调性,得到了太阳图1C_n在n为偶数时的奇优美标号算法和奇强协调标号算法,从而证明了太阳图1C_n在n为偶数时是奇优美图和奇强协调图的结论.     

关于奇强协调图的一些结果

对于一个(p,q)-图G,如果存在一个单射f:V(G)→{0,1,…,2q-1},使得边标号集合{f(uv)|uv∈E(G)}={1,3,5,…,2q-1},其中边标号为f(uv)=f(u)+f(v),那么称G是奇强协调图,并称f是G的一个奇强协调标号.通过研究若干奇强协调图,得出一些奇强协调图的性质.     

直径为4的整树

本文给出了直径为4的整树的一个充分条件，并由此给出了直径为4的整树的许多新类．最后提出一些基本的公开问题．     

图(C)2n的奇优美及其奇强协调性

该文定义了图(C)2n,并研究了该图的奇优美和奇强协调性.利用构造法分别给出了图(C)2n在n=4k(k≥2)、n=4k+2时的奇优美算法,在n=4kk≥2)时,的奇强协调算法,进而证明了图(C)2n在n=2k(k≥3)时是奇优美图,在n=4k(k≥2)时是奇强协调图等结论,从而推动了对图的奇优美性和奇强协调性的研究.最后提出猜想:当n=4k+2时,图(C)2n不是奇强协调图.     

关于直径为4的整树

给出了直径为4的整树的一个实用的充要条件,讨论了几个基本的公开问题, 并给出了直径为4的整树的一些新类.     

树的Hk-cordial性

如果可以给图G的边用集合（±1,±2,.. ,±k）中的元素标号,使得对G每个顶点u,其标号,即所有与其相邻的边的标号之和,都落在集合（±1,±2,.. ,±k）中,且Ie（i）-e（-i）I≤1和lu（i）-u（-i）1≤1,其中t心）和e（i）（1≤i≤k）分别是标号为i的顶点数和边数,那么就称该图G为Hk-cordial的．本文证明了除了尥以外,每棵树都是H3-cordial的．     

直径为d的n阶树的谱半径

二分图的特征值在量子化学中有意义，因此研究其图论性质和其特征值间的关系是有背景的，设Pd＋1（[d＋2/2],n-d-1,Pd＋1（[d＋4/2],n-d-1）分别为路Pd＋1的第[d＋2/2]和第[d＋4/2]个顶点上接出n-d-1条悬挂边所得到的树，本文证明了：若把所有直径为d（d≥1）的n阶树按其最大特征值从大到小的顺序排列，则排在前两位的依次是Pd＋1（[d＋2/2],n-d-1,Pd＋1（[d＋4/2],n-d-1） 。     

关于等高k-毛虫树的带宽

图的带宽问题是图论的一个重要课题。然而 ,即使对毛长不等的单毛虫树 ,其带宽问题也是NP_完全的。利用Chv偄ｔａｌ的直径型带宽下界为工具 ,我们可以确定等高k_毛虫树的带宽     

关于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)是奇优美图.     

(n,m)-p-蜘蛛树的强优美性

给出了优美树、强优美树、边对称树以及对偶标号的概念,定义了一类蜘蛛树.证明了此类蜘蛛树是强优美树,蜘蛛树的强优美标号是对偶标号,并证明了蜘蛛树的边对称树仍然是强优美树.     

Explicit 2-Factorisations of the Odd Graph

In this note we show how 1-factors in the middle two layers of the discrete cube can be used to construct 2-factors in the Odd graph (the Kneser graph of (k − 1)-sets from a (2k − 1)-set). In particular, we use the lexical matchings of Kierstead and Trotter, and the modular matchings of Duffus, Kierstead and Snevily, to give explicit constructions of two different 2-factorisations of the Odd graph. This revised version was published online in September 2006 with corrections to the Cover Date.     

Strong labelings of linear forests

A （p, q）-graph G is called super edge-magic if there exists a bijective function f ： V（G） U E（G） →{1, 2 p＋q} such that f（u）＋ f（v）＋f（uv） is a constant for each uv C E（G） and f（Y（G）） = {1,2,...,p}. In this paper, we introduce the concept of strong super edge-magic labeling as a particular class of super edge-magic labelings and we use such labelings in order to show that the number of super edge-magic labelings of an odd union of path-like trees （mT）, all of them of the same order, grows at least exponentially with m.     

Odd 4‐edge‐colorability of graphs

An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2.     

直径为4的整树新类

整图是指图的邻接矩阵的特征值全为整数的图. 研究了直径为4的整树.通过求解某些确定的丢番图方程,构造了具有无穷多个这样的整树新类,推广了王力工、李学良和张胜贵发表的文章(见Families of integral trees with diameters 4,6 and 8, it Discrete Applied Mathematics, 2004, 136: 349-362)的一些结论.     

直径≤d的对称本原矩阵类的指数集

证明了直径≤[d≤d[n/2]]的全体n阶对称本原矩阵类的本原指数集是Ed={1,2,…,2d}.