运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2013年
2期
35-40
,共6页
团横贯数%团横贯集%无爪图%界
糰橫貫數%糰橫貫集%無爪圖%界
단횡관수%단횡관집%무조도%계
clique-transversal number%clique-transversal set%claw-free graph%bound
设G=(V,E)为简单图,图G的每个至少有两个顶点的极大完全子图称为G的一个团.一个顶点子集S(C)V称为图G的团横贯集,如果S与G的所有团都相交,即对于G的任意的团C有S ∩ V(C)≠(0).图G的团横贯数是图G的最小团横贯集所含顶点的数目,记为rG(G).证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半.
設G=(V,E)為簡單圖,圖G的每箇至少有兩箇頂點的極大完全子圖稱為G的一箇糰.一箇頂點子集S(C)V稱為圖G的糰橫貫集,如果S與G的所有糰都相交,即對于G的任意的糰C有S ∩ V(C)≠(0).圖G的糰橫貫數是圖G的最小糰橫貫集所含頂點的數目,記為rG(G).證明瞭稜柱圖的補圖(除5-圈外)、非奇圈的圓弧區間圖和Hex-連接圖這三類無爪圖的糰橫貫數不超過其階數的一半.
설G=(V,E)위간단도,도G적매개지소유량개정점적겁대완전자도칭위G적일개단.일개정점자집S(C)V칭위도G적단횡관집,여과S여G적소유단도상교,즉대우G적임의적단C유S ∩ V(C)≠(0).도G적단횡관수시도G적최소단횡관집소함정점적수목,기위rG(G).증명료릉주도적보도(제5-권외)、비기권적원호구간도화Hex-련접도저삼류무조도적단횡관수불초과기계수적일반.
