路和圈的笛卡尔积图的粘连度

Tenacity of the cartesian product graphs of paths and cycles

一个简单连通图G=(V,E)的粘连度定义为T(G)=min{(|S|+τ(G-S))/ω(G-S):S■V(G)为G的割集},其中τ(G-S)和ω(G-S)分别表示G-S中最大连通分支的阶和G-S的连通分支数.粘连度是一个重要的描述网络抗毁性的参数,它同时考虑了G-S的分支数和大小.对于路和圈的笛卡尔积图,通过分情形讨论得到了它的粘连度的计算公式.

Let O= （V,E） be a simple connected graph,the tenacity of G is defined as T（G）=rain{ （]SI ＋ r（G--S））/（oJ（G--S）） .S_V（G） is a cut set of G） ,where r（G--S） and o（G--S） denote the order of the largest component and the number of components in G--S, respectively. Tenacity is an important param- eter to measure the invulnerability of networks, as it takes into account both the quantity and order of components of G--S. The formula of the tenacity of the Cartesian product graphs of paths and cycles are given.