Extremal subgraphs for two graphs (Q759768): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Q195254 / rank | |||
Property / author | |||
Property / author: J. H. Spencer / rank | |||
Revision as of 20:42, 9 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Extremal subgraphs for two graphs |
scientific article |
Statements
Extremal subgraphs for two graphs (English)
0 references
1985
0 references
In this paper we study several interrelated extremal graph problems: (i) Given integers \(n,e,m\), what is the largest integer f(n,e,m) such that every graph with \(n\) vertices and \(e\) edges must have an induced m-vertex subgraph with at least \(f(n,e,m)\) edges? (ii) Given integers \(n,e,e'\), what is the largest integer \(g(n,e,e')\) such that any two \(n\)-vertex graphs \(G\) and \(H\), with \(e\) and \(e'\) edges, respectively, must have a common subgraph with at least \(g(n,e,e')\) edges? Results obtained here can be used for solving several questionsrelated to the following graph decomposition problem, previously studied by two of the authors and others. (iii) Given integers \(n,r\), what is the least integer \(t=U(n,r)\) such that for any two \(n\)-vertex \(r\)-uniform hypergraphs \(G\) and \(H\) with the same number of edges the edge set \(E(G)\) of \(G\) can be partitioned into \(E_1,...,E_t\) and the edge set \(E(H)\) of \(H\) can be partitioned into \(E'_1,...,E'_t\) in such a way that for each \(i\), the graphs formed by \(E_i\) and \(E'_i\) are isomorphic.
0 references
extremal graph problem
0 references
graph decompositions
0 references
uniform hypergraphs
0 references
unavoidable graphs
0 references