图的倍图与补倍图(英文)  

The Double Graph and the Complement Double Graph of a Graph

作　　者：张忠辅[1] 仇鹏翔[1] 张东翰[1] 卞量[1] 李敬文[1] 张婷[1] 

机构地区：[1]兰州交通大学应用数学研究所,兰州甘肃730070

出　　处：《数学进展》2008年第3期303-310,共8页Advances in Mathematics（China）

基　　金：NSFC(No.10771091).

摘　　要：计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题.对简单图G,如果V(D(G))=V(G)∪V(G′),E(D(G))=E(G)∪E(G′)∪{v_iv_j′|v_i∈V(G),v_j′∈V(G′)且v_iv_j∈E(G)}那么,称D(G)是G的倍图,如果V((?)(G))=V(G)∪V(G′),E((?)(C))= E(G)∪E(G′)∪{v_iv_j′|v_i∈V(G),v_j′∈V(G′)and v_iv_j(?)E(G)},称(?)(C)是G的补倍图,这里G′是G的拷贝.本文研究了D(G)和(?)的色数,边色数,欧拉性,哈密顿性和提出了D(G)的边色数是D(G)的最大度等公开问题.In the relation of the database theory of the computer, we encounter some problems which can be translated into the problem for parameter and Hamilton cycle of double graphs or complement graphs. Let G（V, E） be a simple graph. If V（D（G）） = V（G） ∪ V（G＇）, E（D（G）） = E（G） ∪ E（G＇） ∪{ vivj′｜vi ∈ V（G）, vj′ V（G ） and vivj ∈ E（G）}, then we call D（G） is the double graph of G. If V（D（G）） = V（G）∪V（G＇）, E（D（C）） = E（G）∪E（G＇）∪{vi vj｜vi∈ V（G）, vj∈ V（G＇） andvivj∈ E（G）}, we call D（C） to be the complement graph of G, where G′ is the copy of G. In the paper, we studys the chromatic number, the edge chromatic number, the properties of Euler and Hamilton of D（G） and D of the simple graph G.

关 键 词：倍图 补倍图 色数 边色数 欧拉图 哈密顿图 

分 类 号：O157.5[理学—数学] TP311.13[理学—基础数学]