Author： Bollobás B. Sarkar A.
Publisher： Akademiai Kiado
ISSN： 0081-6906
Source： Studia Scientiarum Mathematicarum Hungarica, Vol.38, Iss.1-4, 2001-12, pp. : 115-137
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
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.
Related content
Access to resources
Recommend
Relative Length of Longest Paths and Cycles in Graphs
By Liu Huiqing Lu Mei Tian Feng
Graphs and Combinatorics, Vol. 23, Iss. 4, 2007-08 ,pp. :
Paths of homomorphisms from stable Kneser graphs
Combinatorica, Vol. 33, Iss. 5, 2013-10 ,pp. :
Selecting vertex disjoint paths in plane graphs
NETWORKS: AN INTERNATIONAL JOURNAL, Vol. 66, Iss. 2, 2015-09 ,pp. :
An algorithm for packing non-zero A -paths in group-labelled graphs
Combinatorica, Vol. 28, Iss. 2, 2008-03 ,pp. :