首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Enumeration of connected invariant graphs
Authors:Edward A Bender  ERodney Canfield
Institution:University of California at San Diego, La Jolla, California 92093 USA;University of Georgia, Athens, Georgia 30602 USA
Abstract:Let h be a finite group acting on unlabeled graphs which does not change connectivity. Examples include edge reversal in directed graphs and permutations of colors in edge and/or vertex colored graphs. The generating functions of h-invariant (directed) graphs and h-invariant (weakly) connected (directed) graphs are discussed. This leads to a recursive formula for calculating the number of connected graphs when the total number of graphs is known. This is then applied to self-dual signed graphs, self-converse digraphs, and color cyclic graphs. Asymptotic expansions are also obtained. As expected, almost all of the above h-invariant graphs are connected and the asymptotic number of disconnected graphs has a simple interpretation.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号