中国科学技术大学学报
中國科學技術大學學報
중국과학기술대학학보
JOURNAL OF UNIVERSITY OF SCIENCE AND TECHNOLOGY OF CHINA
2009年
3期
225-228
,共4页
约束数%控制数%交叉数%平面图
約束數%控製數%交扠數%平麵圖
약속수%공제수%교차수%평면도
bondage number%domination number%crossing number%planar graph
非空图G的约束数b(G)是指使得图G的控制数γ(G)增大而删除的最少的边数.[Fischermann M, Rautenbach D, Volkmann L. Remarks on the bondage number of planar graphs. Discrete Math,2003,260:57-67\]已经证明,对于一个围长为g(G)的平面图G,如果g(G)≥4则b(G)≤6,如果g(G)≥5则b(G)≤5,如果g(G)≥6则b(G)≤4,如果g(G)≥8则b(G)≤3.我们把这个结果推广到连通的超环面图中.
非空圖G的約束數b(G)是指使得圖G的控製數γ(G)增大而刪除的最少的邊數.[Fischermann M, Rautenbach D, Volkmann L. Remarks on the bondage number of planar graphs. Discrete Math,2003,260:57-67\]已經證明,對于一箇圍長為g(G)的平麵圖G,如果g(G)≥4則b(G)≤6,如果g(G)≥5則b(G)≤5,如果g(G)≥6則b(G)≤4,如果g(G)≥8則b(G)≤3.我們把這箇結果推廣到連通的超環麵圖中.
비공도G적약속수b(G)시지사득도G적공제수γ(G)증대이산제적최소적변수.[Fischermann M, Rautenbach D, Volkmann L. Remarks on the bondage number of planar graphs. Discrete Math,2003,260:57-67\]이경증명,대우일개위장위g(G)적평면도G,여과g(G)≥4칙b(G)≤6,여과g(G)≥5칙b(G)≤5,여과g(G)≥6칙b(G)≤4,여과g(G)≥8칙b(G)≤3.아문파저개결과추엄도련통적초배면도중.
The bondage number b(G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with the domination number greater than the domination number γ(G) of G. [Fischermann M, Rautenbach D, Volkmann L. Remarks on the bondage number of planar graphs. Discrete Math,2003,260:57-67]showed that for a connected planar graph G with girth g(G), b(G)≤6 if g(G)≥4, b(G)≤5 if g(G)≥5, b(G)≤4 if g(G)≥6 and b(G)≤3 if g(G)≥8. This result was generalized to a connected toroidal graph that was embeddable on the torus.