go-v.orgdoi

A Multipartite Version of the Turán Problem – Density Conditions and Eigenvalues

Zoltán Lóránt Nagy · The Electronic Journal of Combinatorics · 2011

  • DOI 10.37236/533
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2011

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2011

Abstract

In this paper we propose a multipartite version of the classical Turán problem of determining the minimum number of edges needed for an arbitrary graph to contain a given subgraph. As it turns out, here the non-trivial problem is the determination of the minimal edge density between two classes that implies the existence of a given subgraph. We determine the critical edge density for trees and cycles as forbidden subgraphs, and give the extremal structure. Surprisingly, this critical edge density is strongly connected to the maximal eigenvalue of the graph. Furthermore, we give a sharp upper and lower bound in general, in terms of the maximum degree of the forbidden graph.

Open the resolved locator · 10.37236/533

Metadata licence: OpenAlex metadata (CC0)