A new class of antimagic join graphs

A labeling/of a graph G is a bijection from its edge set E(G) to the set {1,2,…,|E(G)|},which is antimagic if for any distinct vertices x anAy,the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y.A graph G is antimagic if G has an f which is antimagic.Hartsfield and Ringel conjectured in 1990 that every connected graph other than K_2 is antimagic.In this paper,we show that if G_1 is an m-vertex graph with maximum degree at most 6r+l,and G_2 is an n-vertex(2r)-regular graph(m≥n≥3),then the join graph G_1 v G_2 is antimagic.     

轮图的（2，1）-全标号

图G的一个后-（d,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同的值,且任一对相关联的点和边的值的差的绝对值至少为d．G的（d,1）-全标号数λd^T（G）定义为G有一个K-（d,1）-全标号的最小的k值,得到了轮图的（2,1）-全标号．     

两类图的（d，1）-全标号

图G的一个k-（d,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同值,且任一对相关联的点和边的值差的绝对值至少为d．G的（d,1）-全标号数λ^Td（G）定义为G有一个k-（d,1）-全标号的最小的k值,得到了扇图与轮图的（d,1）-全标号数。     

Almost every graph has a fixed edge

An edge e of a graph G is called a fixed edge if G-e+e′ G implies e′=e, and an isomorphic fixed edge if G-e+e′ G implies that there exists an automorphism of G-e, which maps the ends of e to the ends of e′. It is proved that almost every graph is with all its edges as fixed edges and isomorphic fixed edges, and it is conjectured that all graphs contain isomorphic fixed edges.     

Orlik-Solomon代数的NBC基的一个算法

文中给出了Orlik-Solomon代数NBC基的一个算法,并在计算机上进行了实现。用此算法对顶点数小于7的带号完全n点形图构形做了π-分类,计算了各类的Poincaré多项式。最后,给出猜想“带号完全n点形的相反图构形A(G)是不自由的,则完全n点形图构形A(G)是自由的”的一个反例。     

关于模和图问题的几个新结果

模和图是和图的一种推广.采用一般标号法,分别给出由n个C4、C5、C6构成的多重复合圈图〈C4;n〉、〈C5;n〉、〈C6;n〉的模和标号,从而证明其为模和图;然后,证明由m条长度为n的道路构成的并图mPn也是模和图;最后给出了二部图K2,n的另一种模和图标号.     

Super-Edge-Connectivity of G(k,d,s)(s≥k/2)

A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G(k,d,s)is undirected,simple graph with vertex set V={v|v=1()kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=(u1…uk)and v=(v1…vk)are adjacent if and only if us+i=vi or vs+i=ui(i=1,…,k-s).In particular G(k,d,1)is just an undirected de Bruijn graph.In this paper,we show that the diameter of G(k,d,s)is k s,the girth is 3.Finally,we prove that G(k,d,s)(s≥k/2)is super-λ.     

关于图的边染色方面的一些结果

改进了一些边染色临界图的边数的下界．同时证明了：对没有４圈或任何两个３面都不同时关联于一个点的平面图,关于边染色的平面图猜想成立．     

几类有趣图的邻点可区别全染色

在正常全染色的定义下,使得任两相邻顶点的色集不同,这就是邻点可区别全染色.顶点v的色集是v的颜色其与及v关联的所有边的颜色.我们给出了几类有趣图的邻点可区别全色数.     

无向图同构的快速算法

规范标记算法和顶点划分算法是判断无向图同构的两种重要途径,其缺点是要么无法对图进行规范标记,从而不能进行判断；要么必须进行不断地回溯和试探,从而造成指数阶时间开销.对于任何两个同构的无向图,各自新增一个顶点和若干条关联边,可获得父图.当且仅当新增顶点的邻接点在原同构图中保持同构关系时,父图同构.根据这个充要条件,文中使...     

两类图的Mycielski图的均匀全色数

设G是简单图，G的点和边称为G的元素。如果G的点和边的染色满足相邻或关联的元素得到不同的颜色，则称为G的正常全染色。如果G的一个正常全染色满足任意两种颜色所染元素数目相差不超过1，则称为G的均匀全染色，其所用量少染色数称为G的均匀全色数。本文确定了轮和扇的Mycielski图的均匀全色数。     

Binding number,minimum degree and bipancyclism in bipartite graphs

Let G =(V_1,V_2,E) be a balanced bipartite graph with2 n vertices.The bipartite binding number of G,denoted by B(G),is defined to be n if G =K_n and min i∈{1,2}|N(S)|n min |N(S)|/|S|otherwise.We call G bipancyclic if it contains a cycle of every even length m for 4 ≤ m ≤ 2n.A theorem showed that if G is a balanced bipartite graph with 2n vertices,B(G) 3 / 2 and n 139,then G is bipancyclic.This paper generalizes the conclusion as follows:Let 0 c 3 / 2 and G be a 2-colmected balanced bipartite graph with 2n(n is large enough) vertices such that B(G) c and δ(G)(2-c)n/(3-c)+2/3.Then G is bipancyclic.     

非连通图(P1∨Pn)∪Gr和(P1∨Pn)∪(P3∨r)及Wn∪St(m)的优美性

讨论非连通图((P₁∨P_n)∪G_r和(P₁∨P_n)∪(P₃∨_r)及W_n∪St(m)的优美性, 证明了如下结论： 设n,m为任意正整数, s=［n/2］, r=s-1, G_r是任意具有r条边的优美图, 则当n≥4时, 非连通图((P₁∨P_n)∪G_r和(P₁∨P_n)∪(P₃∨_r)是优美图； 当n≥3, m≥s时, 非连通图W_n∪St(m)是优美图. 其中, P_n是n个顶点的路, K_n是n个顶点的完全图, n是K_n的补图, G₁∨G₂是图G₁与G₂的联图, W_n是n+1个顶点的轮图, St(m)是m+1个顶点的星形树.     

图mP2∪mCt（3≤t≤10）的点可区别正常边染色

图G的正常边染色称为是点可区别的,如果对G的任意两个不同的顶点u,v,与u关联的边的颜色构成的集合异于与v关联的边的颜色构成的集合.对图G进行点可区别正常边染色所需要的最少颜色数称为是G的点可区别正常边色数,记为χ′s(G).通过将路和圈填装到完全图,我们给出了mP2∪mCt的点可区别正常边色数的一个刻画,并利用递归染色的方式,得到了χ′s(mP2∪mCt)(3≤t≤10).     

非连通图(K1∨(P(1)n∪ P(2)n)) ∪ P(3)n及(K1∨(P(1)n∪ P(2)n)) ∪ P(3)n∪ St(n)的优美性

 给出了非连通图(K₁∨(P⁽¹⁾_n∪ P⁽²⁾_n)) ∪ P⁽³⁾_n和(K₁∨(P⁽¹⁾_n∪ P⁽²⁾_n)) ∪ P⁽³⁾_n∪ St(n),且对其优美性进行了研究。证明了如下结论：设 n 为任意正整数,则当n≥4时,非连通图 (K₁∨(P⁽¹⁾_n∪ P⁽²⁾_n)) ∪ P⁽³⁾_n和(K₁∨(P⁽¹⁾_n∪ P⁽²⁾_n)) ∪ P⁽³⁾_n∪ St(n)均是优美图;其中,Pn 是 n 个顶点的路,Kn 是n个顶点的完全图, St(n) 是 n+1 个顶点的星形树,G₁ ∨ G₂ 是图 G1 与 G2 的联图。     

某些特殊图类的非正常(p,1)-全标号

本文给出了图G的一个非正常(r,s,t)-(p,1)-全标号的定义,该标号基于图G的(p,1)-全标号,允许有破坏此限制条件的顶点和边.非正常(r,s,t)-(p,1)-全标号的跨度是指两个标号差的最大值.图G的非正常(r,s,t)-(p,1)-全标号的最小跨度称为图G的非正常(r,s,t)-(p,1)-全标号数,记作λT(r,s,t)(G;p,1).这里主要给出了某些特殊图类的非正常(2,2,0)-(p,1)-全标号的上界.     

双圈图边幻和全标号

图的边幻和全标号是指图G(p，q)中任意一条边与其关联顶点的标号之和等于常数，且点和边的所有标号值一一映射到集合.该文针对双圈图，设计了一种边幻和标号判定算法，利用该算法可以得到15个点内的所有双圈图边幻和全标号.通过结果分析，找到了两类双圈图的标号规律，定义了新的图运算符号CnΔCl SymbolQCpSm和CnΔCl ΔSm来刻画这两类图，总结了若干定理并给出证明，进一步猜测当顶点数p≥16时，相关结论仍然成立.     

关于不连通优美图及优美图的构造

在本文中,我们称G是不连通图,如果G至少具有两个不是孤立点的分支。迄今为止,许多作者对优美图问题进行了大量的研究,但对不连通图的优美性讨论尚少。本文首先研究不连通图的优美性,给出了几类不连通的优美图,并提出两个猜想。其次讨论优美矩阵,得到了几个有意义的结果。最后给出几类新优美图的构造方法。     

和轮相关图的优美性

 证明了对任意自然数n≥1,p≥1,当m=2p+3,2p+4时,非连通图W_m∪K_n,p和W_m,2m+1∪K_n,p是优美图;当i=1,2时,图W_2p+2+i∪G⁽ⁱ⁾_p是优美图。当m≥3,n≥s时,W_m,2m+1∪St(n)是优美图;当m=2n+5时,图W_m,2m+1∪(C₃∨K_n)是优美图。     

无赋权的LEW嵌入的图

研究网格图G(a,b)(a≥2,b≥2)和M(o|¨)bius梯子图G_n≥4)赋权的LEW(大边宽度)嵌入问题,证明这两类图分别在环面和射影平面上无赋权的LEW嵌入,运用拓扑手术方式构造出可定向曲面S_n和不可定向曲面N_n上的无赋权的LEW嵌入图.