A multipartite version of the Turan problem - density conditions and eigenvalues
The electronic journal of combinatorics, Tome 18 (2011) no. 1
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl EuDML
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.
Zoltán Lóránt Nagy. A multipartite version of the Turan problem - density conditions and eigenvalues. The electronic journal of combinatorics, Tome 18 (2011) no. 1. doi: 10.37236/533
@article{10_37236_533,
author = {Zolt\'an L\'or\'ant Nagy},
title = {A multipartite version of the {Turan} problem - density conditions and eigenvalues},
journal = {The electronic journal of combinatorics},
year = {2011},
volume = {18},
number = {1},
doi = {10.37236/533},
zbl = {1217.05127},
url = {http://geodesic.mathdoc.fr/articles/10.37236/533/}
}
Cité par Sources :