Paths in graphs
Paths in graphs
复制标题
DOI：
10.1556/sscmath.38.2001.1-4.8
复制
发表时间：
2001-05
影响因子：
0.7
通讯作者：
B. Bollobás;Amites Sarkar
中科院分区：
文献类型：
--
作者：
B. Bollobás;Amites Sarkar
证明了如果2 2，则m的图G中长为3的路的个数至多为2m(m-k)(k-2)=k.如果G是Kk和孤立顶点的并，则G是相等的.我们还给出了长为S的最大路数在m阶图中的渐近最佳上界。最后，我们讨论了在m阶图中最大化与给定图H同构的子图的个数的更一般问题。
We prove that if 2 2 then the number of paths of length three in a graphGof size m is at most 2m(m - k)(k - 2)=k. Equality is attained if G is the union of Kk and isolated vertices. We also give asymptotically best possible bounds for the maximal number of paths of length s, for arbitrary s, in graphs of size m. Lastly,we discuss the more general problem of maximizing the number of subgraphs isomorphic to a given graph H in graphs of size m.