On restricted edge-connectivity of replacement product graphs

作     者：HONG ZhenMu XU JunMing 

作者机构：School of Finance Anhui University of Finance & Economics School of Mathematical Sciences University of Science and Technology of China 

出 版 物：《Science China Mathematics》 (中国科学：数学（英文版）)

年 卷 期：2017年第60卷第4期

页      面：745-758页

核心收录：

学科分类：07[理学] 08[工学] 080203[工学-机械设计及理论] 070104[理学-应用数学] 0802[工学-机械工程] 0701[理学-数学] 

基　　金：supported by National Natural Science Foundation of China (Grant Nos. 61272008 and 11571044) University Natural Science Research Project of Anhui Province (Grant No. KJ2016A003) Scientific Research Fund of Anhui University of Finance & Economics (Grant No. ACKY1532) 

主　　题：graph theory connectivity restricted edge-connectivity replacement product Cayley graph 

摘      要：This paper considers the edge-connectivity and the restricted edge-connectivity of replacement product graphs, gives some bounds on edge-connectivity and restricted edge-connectivity of replacement product graphs and determines the exact values for some special graphs. In particular, the authors further confirm that under certain conditions, the replacement product of two Cayley graphs is also a Cayley graph, and give a necessary and sufficient condition for such Cayley graphs to have maximum restricted edge-connectivity. Based on these results, we construct a Cayley graph with degree d whose restricted edge-connectivity is equal to d + s for given odd integer d and integer s with d 5 and 1 s d- 3, which answers a problem proposed ten years ago.