Induced subgraphs of given sizes
type: Item
instance of: scholarly article
title: Induced subgraphs of given sizes
zbMATH Open document ID: 0930.05052
DOI: 10.1016/S0012-365X(98)00387-2
author: Bruce Rothschild
author: Vera T. Sós
author: Zoltán Füredi
author: P. Erdős
published in: Discrete Mathematics
publication date: 2000-01-30T00:00:00Z
review text: This paper considers certain ``natural'' generalizations of ``Turán-type'' extremal problems investigated earlier by \textit{P. Erdős} [Extremal problems in graph theory. Theory Graphs Appl., Proc. Symp. Smolenice 1963, 29-36 (1964; Zbl 0161.20501)] and by \textit{P. Erdős, V. T. Sós}, and the reviewer [Some extremal problems on \(r\)-graphs. New Direct. Theory Graphs, Proc. Third Ann Arbor Conf., Univ. Michigan 1971, 53-63 (1973; Zbl 0258.05132); On the existence of triangulated spheres in \(3\)-graphs, and related problems. Period. Math. Hung. 3, No. 3-4, 221-228 (1973; Zbl 0269.05111)]. An ordered pair \((m,f)\) is said to belong to the spectrum of a graph \(G\) (written \((m,f)\in\text{Sp}(G)\) or \(G\rightarrow(m,f)\)) if there exists in \(G\) an \(m\)-element subset \(M\) of vertices whose induced subgraph has exactly \(f\) edges; an \((m,f)\)-subgraph is then said to be forced; \({\mathcal G}(n,e;m,f)\) denotes the class of \(n\)-vertex \(e\)-edged graphs such that \(G\not\rightarrow(m,f)\). Where \({\mathcal G}(n,e;m,f)=\varnothing\), the authors write \((n,e)\rightarrow(m,f)\); they denote the set \(\{e:(n,e)\rightarrow(m,f)\}\) by \(S(n;m,f)\), and define \(\sigma(m,f):=\limsup_{n\to\infty}\frac{|S(n;m,f)|}{{n\choose 2}}\), which they conjecture ``is actually a limit for all fixed \(m\) and \(f\).'' The set \(\{f:G\rightarrow(m,f)\}\) is denoted by \(\text{Sp}_m(G)\) (cf. \textit{P. Erdős, V. T. Sós} and \textit{R. J. Faudree} [The \(k\)-spectrum of a graph. Graph theory, combinatorics, and algorithms, Vol. 1 (Kalamazoo, MI, 1992), 377-389 (1995; Zbl 0843.05056)]; \textit{R. J. Faudree, R. J. Gould, M. S. Jacobson, J. Lehel}, and \textit{L. M. Lesniak} [Graph spectra. Discrete Math. 150, No. 1-3, 103-113 (1996; Zbl 0862.05053)]). Sections 4 through 7 consider the cases \(f=0\), and \((m,f)=(3,2), (4,3), (5,4)\). ``In Section 8 we give a list of examples for \((m,f)\)-free graphs. The constructions yield upper bounds for \(\sigma(m,f)\) in various ranges of…
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1334441
zbMATH Keywords: extremal problems
zbMATH Keywords: spectrum
zbMATH Keywords: induced subgraph
Wikidata QID: Q105697144
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Q3852212
cites work: An extension of the Erdős-Stone theorem
cites work: Q5672676
cites work: On the existence of triangulated spheres in 3-graphs, and related problems
cites work: On the Erdös-Stone Theorem
cites work: Q5543308
cites work: The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
cites work: Q5567712
cites work: Q4871156
cites work: On the structure of linear graphs
cites work: Graph spectra
cites work: Q3789593
cites work: On Moore Graphs with Diameters 2 and 3
cites work: On a problem of K. Zarankiewicz
cites work: Über ein Problem von K. Zarankiewicz
cites work: The sum of the squares of the parts of a partition, and some related questions
cites work: Q4175585
cites work: Q5781249
cites work: On the theory of graphs
full work available at URL: s0012-365x(98)00387-2
OpenAlex ID: W1967504232
Recommended article: Q4410007
Recommended article: Q3312262
Recommended article: Maximum number of colorings of (2k, k2)‐graphs
Recommended article: A weighted generalization of Tur�n's theorem
Recommended article: On the potentially \(P_k\)-graphic sequences
Recommended article: An Erdős-Stone Type Conjecture for Graphic Sequences
Recommended article: Q5543308
Recommended article: Q3421036
Recommended article: Q3108598
Recommended article: Paul turán, 1910–1976: His work in graph theory
description: scientific article; zbMATH DE number 1334441