Document Type

Article

Publication Date

2000

Keywords

Maximal number of paths of lengths s in a graph with m edges, maximal number of subgraphs isomorphic to a given graph

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.

Publication Title

Studia Scientiarum Mathematicarum Hungarica

Volume

38

Issue

1-4

First Page

115

Last Page

137

DOI

http://dx.doi.org/10.1556/SScMath.38.2001.1-4.8

Required Publisher's Statement

© Akadémiai Kiadó Zrt.

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

Included in

Mathematics Commons

Share

COinS