Properties of Groups for the Cage and Degree/Diameter Problems

详细信息    查看全文

• 作者：Robert Jajcay ; Geoffrey Exoo
• 关键词：cage ; girth ; Cayley graph ; nilpotent group ; solvable group
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2009
• 出版时间：1 August 2009
• 年：2009
• 卷：34
• 期：Complete
• 页码：341-345
• 全文大小：160 K

文摘

A (k, g)-cage is a k-regular graph of girth g of minimum order. While many of the best known constructions of small k-regular graphs of girth g are known to be Cayley graphs, no general theory of the relation between the girth of a Cayley graph and the structure of the underlying group has been developed. We attempt to fill the gap by focusing on the girths of Caley graphs of nilpotent and solvable groups, and present a series of results supporting the intuitive idea that the closer a group is to being abelian, the less suitable it is for constructing Cayley graphs of large girths. Specifically, we establish the existence of upper bounds on the girths of Cayley graphs with respect to the nilpotency class and/or the length of the derived sequence of the underlying groups.