路与圈直积的直径与容错直径研究

Diameter and Fault-Tolerant Diameter of the Direct Product of Path and Cycle

摘要: 本文研究了路径图$P_n$ ，圈图$C_m$ 及其直积图$P_n\times P_m,P_n\times C_m$ 和$C_n\times C_m$ 的直径与容错直径，其中$n$ 和$m$ 为正整数。对于给定的正整数$k$ ，通过分析图的结构特性，我们给出了这些图的直径与$k$ -容错直径的精确表达式，并建立了若干关于直积图中两点间距离的计算公式。特别地，我们证明了$P_n\times P_m$ 的容错直径等于其直径，而在$P_n\times C_m$ 和$C_n\times C_m$ 中，容错直径随图的结构参数变化而呈现出不同特性。本文的结果为图在网络容错性分析与通信延迟建模中的应用提供了理论依据。

Abstract: This paper investigates the diameter and fault-tolerant diameter of path $P_n$ , cycle $C_m$ , and their direct products $P_n\times P_m$ , $P_n\times C_m$ and $C_n\times C_m$ , where $n$ and $m$ are positive integers. For a given positive integer $k$ , by analyzing the structural properties of these graphs, we derive exact expressions for their diameters and $k$ -fault-tolerant diameters, and establish several formulas for computing distances between two vertices in the direct product graphs. In particular, we prove that the fault-tolerant diameter of $P_n\times P_m$ equals its diameter, while in $P_n\times C_m$ and $C_n\times C_m$ , the fault-tolerant diameter varies with the structural parameters of the graphs. The results of this study provide a theoretical foundation for the application of graphs in network fault-tolerance analysis and communication latency modeling.