数学物理学报
數學物理學報
수학물이학보
ACTA MATHEMATICA SCIENTIA
2010年
4期
968-983
,共16页
整数距离图%点荫度%树着色
整數距離圖%點蔭度%樹著色
정수거리도%점음도%수착색
图G的点荫度va(G)是顶点集合V(G)能划分成的这样一些子集的最少数目,其中任一子集的点导出子图都是森林.整数距离图G(D)以全体整数作为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集.对于m>2k≥2,令Dm,k,2=[1,m]\{k,2k}.该文得出了整数距离图G(Dm,k,2)的点荫度的几个上、下界;进而,对于m≥4,有va(G(Dm,1,2))=[m+4/5];对于m=10q+j,j=0,1,2,3,5,6,有va(G(Dm,2,2))=[m+1/5].
圖G的點蔭度va(G)是頂點集閤V(G)能劃分成的這樣一些子集的最少數目,其中任一子集的點導齣子圖都是森林.整數距離圖G(D)以全體整數作為頂點集,頂點u,v相鄰噹且僅噹|u-v|∈D,其中D是一箇正整數集.對于m>2k≥2,令Dm,k,2=[1,m]\{k,2k}.該文得齣瞭整數距離圖G(Dm,k,2)的點蔭度的幾箇上、下界;進而,對于m≥4,有va(G(Dm,1,2))=[m+4/5];對于m=10q+j,j=0,1,2,3,5,6,有va(G(Dm,2,2))=[m+1/5].
도G적점음도va(G)시정점집합V(G)능화분성적저양일사자집적최소수목,기중임일자집적점도출자도도시삼림.정수거리도G(D)이전체정수작위정점집,정점u,v상린당차부당|u-v|∈D,기중D시일개정정수집.대우m>2k≥2,령Dm,k,2=[1,m]\{k,2k}.해문득출료정수거리도G(Dm,k,2)적점음도적궤개상、하계;진이,대우m≥4,유va(G(Dm,1,2))=[m+4/5];대우m=10q+j,j=0,1,2,3,5,6,유va(G(Dm,2,2))=[m+1/5].