The maximum number of copies of kr,s in graphs without long cycles or paths

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

The circumference of a graph is the length of a longest cycle of it. We determine the maximum number of copies of Kr,s, the complete bipartite graph with classes sizes r and s, in a 2-connected graph with circumference less than k. As corollaries of our main result, we determine the maximum number of copies of Kr,s in n-vertex Pk-free and Mk-free graphs for all values of n, where Pk is a path on k vertices and Mk is a matching on k edges.

Original languageEnglish
Article numberP4.4
JournalElectronic Journal of Combinatorics
Volume28
Issue number4
DOIs
StatePublished - 2021

Fingerprint

Dive into the research topics of 'The maximum number of copies of kr,s in graphs without long cycles or paths'. Together they form a unique fingerprint.

Cite this