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


Subgraphs smaller than the girth
Authors:Luca Simoncini  Herbert Taylor
Abstract:For graphs A, B, let (urn:x-wiley:03649024:media:JGT3190040111:tex2gif-stack-1) denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if (urn:x-wiley:03649024:media:JGT3190040111:tex2gif-stack-2) = (urn:x-wiley:03649024:media:JGT3190040111:tex2gif-stack-3) for every k-node tree T, then for every k-node forest F, (urn:x-wiley:03649024:media:JGT3190040111:tex2gif-stack-4) = (urn:x-wiley:03649024:media:JGT3190040111:tex2gif-stack-5). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of (urn:x-wiley:03649024:media:JGT3190040111:tex2gif-stack-6) depends only on n and d.
Keywords:
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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