New exact values of the maximum size of graphs free of topological complete subgraphs
type: Item
instance of: scholarly article
title: New exact values of the maximum size of graphs free of topological complete subgraphs
zbMATH Open document ID: 1122.05044
author: A. Diánez
author: C. Balbuena
author: Martín Cera
author: P. García-Vázquez
published in: Discrete Mathematics
publication date: 2007-03-15T00:00:00Z
review text: A generalization of the famous extremal problem of Turán asks for determining the number ex\((n,p)\), the maximum number of edges of a graph of order \(n\) not containing a graph homeomorphic to the complete graph on \(p\) vertices. In this paper the exact values of ex\((n,p)\) are given for \((7n+7)/12\leq p<(12n+1)/3\), provided that \(n-p\geq 15.\) The corresponding extremal graphs are described as well.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 5134172
zbMATH Keywords: topological compete graph
zbMATH Keywords: extremal graphs
reviewed by: Peter Horák
MaRDI profile type: Publication
full work available at URL: j.disc.2006.07.031
OpenAlex ID: W2035328755
cites work: Q3852212
cites work: Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
cites work: The Size of a Graph Without Topological Complete Subgraphs
cites work: Extremal Graphs without Topological Complete Subgraphs
cites work: Q4947393
cites work: In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
cites work: Homomorphism theorems for graphs
cites work: On Representatives of Subsets
cites work: Topological Cliques in Graphs
cites work: Topological cliques in graphs II
cites work: Homomorphieeigenschaften und mittlere Kantendichte von Graphen
cites work: Hinreichende Bedingungen für die Existenz von Teilgraphen, die zu einem vollständigen Graphen homöomorph sind
cites work: \(3n-5\) edges do force a subdivision of \(K_5\)
cites work: Graphs with \(3n-6\) edges not containing a subdivision of \(K_5\)
DOI: 10.1016/J.DISC.2006.07.031
Recommended article: The Size of a Graph Without Topological Complete Subgraphs
Recommended article: Extremal digraph results for topological complete subgraphs
Recommended article: Q5575346
Recommended article: On the extremal sizes of maximal graphs without \(( k + 1 )\)-connected subgraphs
Recommended article: Q5331113
Recommended article: Some bounds on the size of maximum G-free sets in graphs
Recommended article: On the maximal number of certain subgraphs in \(K_ r\)-free graphs
Recommended article: The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
Recommended article: Bounds on the number of complete subgraphs
Recommended article: Maximum \(\mathcal{H}\)-free subgraphs
description: scientific article; zbMATH DE number 5134172