On restricted edge-connectivity of replacement product graphs

• 来源期刊: 中国科学：数学（英文版）
• 年，卷（期）: 2017,（4）
• 页码范围: 745-758
• 页数: 14页
• 语种: 英文
• DOI: 10.1007/s11425-015-0862-0

摘要

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 somespecial 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.