Fault diameter of Cartesian product graphs |
| |
Authors: | Min Xu Xin-Min Hou |
| |
Affiliation: | Department of Mathematics, University of Science and Technology of China, Hefei, Anhui 230026, China |
| |
Abstract: | The (k−1)-fault diameter Dk(G) of a k-connected graph G is the maximum diameter of G−F for any F⊂V(G) with |F|<k. Krishnamoorthy and Krishnamurthy first proposed this concept and gave Dκ(G1)+κ(G2)(G1×G2)?Dκ(G1)(G1)+Dκ(G2)(G2) when κ(G1×G2)=κ(G1)+κ(G2), where κ(G) is the connectivity of G. This paper gives a counterexample to this bound and establishes Dk1+k2(G1×G2)?Dk1(G1)+Dk2(G2)+1 for any ki-connected graph Gi and ki?1 for i=1,2. |
| |
Keywords: | Diameter Connectivity Fault diameter Cartesian product graph Interconnection networks |
本文献已被 ScienceDirect 等数据库收录! |
|