Article
Paths in Graphs
Studia Scientiarum Mathematicarum Hungarica
Document Type
Article
Publication Date
12-31-2000
Keywords
- Maximal number of paths of lengths s in a graph with m edges,
- maximal number of subgraphs isomorphic to a given graph
Disciplines
Abstract
We prove that if 10 ≦ (k2) ≦ m < (k+12) then the number of paths of length three in a graph G of 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.
DOI
http://dx.doi.org/10.1556/SScMath.38.2001.1-4.8
Comments
This is the authors' refereed version of the article.
Subjects - Topical (LCSH)
Paths and cycles (Graph theory)
Genre/Form
articles
Type
Text
Rights
Copying of this document in whole or in part is allowable only for scholarly purposes. It is understood, however, that any copying or publication of this document for commercial purposes, or for financial gain, shall not be allowed without the author’s written permission.
Language
English
Format
application/pdf
Citation Information
Béla Bollobás and Amites Sarkar. "Paths in Graphs" Studia Scientiarum Mathematicarum Hungarica Vol. 38 Iss. 1-4 (2000) p. 115 - 137 Available at: http://works.bepress.com/amites_sarkar/6/
This is the authors' refereed version of the article.