运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2009年
4期
65-70
,共6页
运筹学%图论%独立集%独立数%循环图
運籌學%圖論%獨立集%獨立數%循環圖
운주학%도론%독립집%독립수%순배도
Operations research%graph theory%independent set%independence number%circulant graph
令G=(V(G),E(G))是一个简单有限无向图.如果V(G)的子集S中任意两个顶点均不相邻,则S是图G的一个独立集.顶点独立集大小的最大值,称为图G的独立数,记作α(G).本文研究了循环图C(n;{1,k})的独立数问题,并给出了当k=2,3,4,5时的准确值.
令G=(V(G),E(G))是一箇簡單有限無嚮圖.如果V(G)的子集S中任意兩箇頂點均不相鄰,則S是圖G的一箇獨立集.頂點獨立集大小的最大值,稱為圖G的獨立數,記作α(G).本文研究瞭循環圖C(n;{1,k})的獨立數問題,併給齣瞭噹k=2,3,4,5時的準確值.
령G=(V(G),E(G))시일개간단유한무향도.여과V(G)적자집S중임의량개정점균불상린,칙S시도G적일개독립집.정점독립집대소적최대치,칭위도G적독립수,기작α(G).본문연구료순배도C(n;{1,k})적독립수문제,병급출료당k=2,3,4,5시적준학치.
Let G=(V(G),E(G))be a simple finite undirected graph.A set S (∈)V(G)is an independent set if no two vertices of S are adjacent.The independence number α(G)is the maximum cardinality of an independent set in G.In this paper,we study the independence number of the circulant graphs,and give the exact values of C(n;{1,k})for k=2,3,4,5.
