合肥学院学报（自然科学版）
閤肥學院學報（自然科學版）
합비학원학보（자연과학판）
JOURNAL OF HEFEI UNIVERSITY(NATURAL SCIENCES)
2014年
1期
7-9,30
,共4页
笛卡尔乘积%全控制集%全控制数
笛卡爾乘積%全控製集%全控製數
적잡이승적%전공제집%전공제수
Cartesian product%total domination set%total domination number
令图G是无孤立点的无向图。 V(G)是图G的顶点集,D是V(G)的真子集。如果图G的每一个顶点至少与集合D中一点相邻,则集合D是图G的全控制集。 G中最小全控制集的顶点数称为G的全控制数,记为γt(G)。参考已有全控制数的知识及笛卡尔乘积 Cm□Cn、Pm□Pn 的全控制数的相关结论,利用γt(Cm□Cn )≤γt(Pm□Cn )≤γt(Pm□Pn )这一不等式给出了Cm□Pn(m =3,4)、Pm□Cn(n =2,4)的全控制数。
令圖G是無孤立點的無嚮圖。 V(G)是圖G的頂點集,D是V(G)的真子集。如果圖G的每一箇頂點至少與集閤D中一點相鄰,則集閤D是圖G的全控製集。 G中最小全控製集的頂點數稱為G的全控製數,記為γt(G)。參攷已有全控製數的知識及笛卡爾乘積 Cm□Cn、Pm□Pn 的全控製數的相關結論,利用γt(Cm□Cn )≤γt(Pm□Cn )≤γt(Pm□Pn )這一不等式給齣瞭Cm□Pn(m =3,4)、Pm□Cn(n =2,4)的全控製數。
령도G시무고립점적무향도。 V(G)시도G적정점집,D시V(G)적진자집。여과도G적매일개정점지소여집합D중일점상린,칙집합D시도G적전공제집。 G중최소전공제집적정점수칭위G적전공제수,기위γt(G)。삼고이유전공제수적지식급적잡이승적 Cm□Cn、Pm□Pn 적전공제수적상관결론,이용γt(Cm□Cn )≤γt(Pm□Cn )≤γt(Pm□Pn )저일불등식급출료Cm□Pn(m =3,4)、Pm□Cn(n =2,4)적전공제수。
Let G be a graph without isolated vertice. A subset D?V(G) of G is a total dominating set if every vertex x∈V(G) is adjacent to at least one vertex of D. The total domination number ,denoted byγt( G), is the minimum cardinality of a total dominating set of G. This paper determines the total domination number of the cartesian product of Cn and Pm for any n≥2 and m∈{2,4}, or, for any m≥2 and n∈{3,4}.
