关于两类图的整和数  

作　　者：于洪全[1] 王天明[1] 

机构地区：[1]大连理工大学数学科学研究所,大连116024

出　　处：《科学通报》1997年第18期2016-2016,共1页Chinese Science Bulletin

基　　金：辽宁省博士启动基金资助项目

摘　　要：<正>本文中的图均指无向简单图,以N,Z分别表示全体自然数及全体整数集合.对子集S(?)Z(N),S上的整和(和)图定义为图G=(S,E),满足条件对u,v∈S,uv∈E当且仅当u+v∈s.此时,S称为G的一个整和(和)标号.一个图称为整和(和)图,如果它同构于某一子集S(?)Z(N)上的整和(和)图.容易验证,对一个有m条边的n阶图G,G∪mK_1是一个和图,只需标定G的顶点为2~i,1≤i≤n,同时对v_i,v_j∈E(G),标定对应的孤立点2~i+2~j即可.因此,对每一个图G,存在一个最小的非负整数r,使G∪rK_1为和图,记σ(G)=r,并称为G的和数.图的整和数ξ(G)类似定义,只是标号范围放宽到整数集上.容易看到ξ(G)≤σ(G).

关 键 词：简单图 整和数 整和图 树 

分 类 号：O157.5[理学—数学]