数学物理学报
數學物理學報
수학물이학보
ACTA MATHEMATICA SCIENTIA
2007年
1期
166-170
,共5页
对控制数%立方图%私有邻域
對控製數%立方圖%私有鄰域
대공제수%립방도%사유린역
设G=(V,E)是一个简单图,对任意的顶点子集合S(∩)V,G[S]表示图G中由S所导出的子图.如果S是G的一个控制集并且G[S]包含至少一个完备匹配,则称S是G的一个对控制集.G中对控制集的最少的顶点数称为G的对控制数,记为γp(G).该文证明了对任意有n点的连通立方图G,γp(G)≤3n/5.
設G=(V,E)是一箇簡單圖,對任意的頂點子集閤S(∩)V,G[S]錶示圖G中由S所導齣的子圖.如果S是G的一箇控製集併且G[S]包含至少一箇完備匹配,則稱S是G的一箇對控製集.G中對控製集的最少的頂點數稱為G的對控製數,記為γp(G).該文證明瞭對任意有n點的連通立方圖G,γp(G)≤3n/5.
설G=(V,E)시일개간단도,대임의적정점자집합S(∩)V,G[S]표시도G중유S소도출적자도.여과S시G적일개공제집병차G[S]포함지소일개완비필배,칙칭S시G적일개대공제집.G중대공제집적최소적정점수칭위G적대공제수,기위γp(G).해문증명료대임의유n점적련통립방도G,γp(G)≤3n/5.
