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

The Double Graph and the Complement Double Graph of a Graph

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题.对简单图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.