Cayley Cages

详细信息    查看全文

• 作者：Geoffrey Exoo (1)
  Robert Jajcay (1)
  Jozef ?iráň (2)
  
• 关键词：Cage ; Cayley graph ; Girth
• 刊名：Journal of Algebraic Combinatorics
• 出版年：2013
• 出版时间：August 2013
• 年：2013
• 卷：38
• 期：1
• 页码：209-224
• 全文大小：670KB
• 参考文献：1. Biggs, N.L.: Girth and residual finiteness. Combinatorica 8, 307-12 (1988) CrossRef
  2. Biggs, N.L.: Constructions for cubic graphs of large girth. Electron. J. Comb. 5, A1 (1998)
  3. Boben, M., Jajcay, R., Pisanski, T.: Generalized cages. Submitted for publication
  4. Erd?s, P., Sachs, H.: Regul?re Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Uni. Halle (Math. Nat.) 12, 251-57 (1963)
  5. Exoo, G., Jajcay, R.: Dynamic cage survey. Electron. J. Comb. 15, DS16 (2008)
  6. Gross, J.L.: Every connected regular graph of even degree is a Schreier coset graph. J. Comb. Theory, Ser. B 22(3), 227-32 (1977) CrossRef
  7. Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley, New York (1987)
  8. Jajcay, R., ?iráň, J.: Small vertex-transitive graphs of given degree and girth. Submitted for publication
  9. Loz, E., Ma?aj, M., Miller, M., ?iagiová, J., ?iráň, J., Tomanová, J.: Small vertex-transitive and Cayley graphs of girth six and given degree: an algebraic approach. To appear
  10. Massey, W.S.: Algebraic Topology: An Introduction. Graduate Texts in Mathematics, vol. 56. Springer, New York (1981)
  11. Nedela, R., ?koviera, M.: Which generalized Petersen graphs are Cayley graphs? J. Graph Theory 19(1), 1-1 (1995) CrossRef
  12. Sachs, H.: Regular graphs with given girth and restricted circuits. J. Lond. Math. Soc. 38, 423-29 (1963) CrossRef
  13. ?iagiová, J., Watkins, M.E.: Covalence sequences of planar vertex-homogeneous maps. Discrete Math. 307(3-), 599-14 (2007)
  14. ?iráň, J., ?koviera, M.: Quotients of connected regular graphs of even degree. J. Comb. Theory, Ser. B 38, 214-25 (1985) CrossRef
  
• 作者单位：Geoffrey Exoo (1)
  Robert Jajcay (1)
  Jozef ?iráň (2)
  
  1. Department of Mathematics and Computer Science, Indiana State University, Terre Haute, IN, 47809, USA
  2. Department of Mathematics, SvF, Slovak University of Technology, Radlinského 11, 813 68, Bratislava, Slovakia
  
• ISSN：1572-9192

文摘

A (k,g)-Cayley cage is a k-regular Cayley graph of girth g and smallest possible order. We present an explicit construction of (k,g)-Cayley graphs for all parameters k? and g? and generalize this construction to show that many well-known small k-regular graphs of girth g can be constructed in this way. We also establish connections between this construction and topological graph theory, and address the question of the order of (k,g)-Cayley cages.