Extremal Problems Concerning Transformations of the Set of Edges of the Complete Graph

N. Alon, Y. Caro

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

Let Em denote the set of edges of the complete graph on m vertices Km, and let f : Em → Em be a function. A subgraph G = (V (G), E (G)) of Km is called f-fixed if f(e) = e for all e ∈ E (G) and f-free if f(e) ∉ E(G) for all e ∈ E(G). For two finite graphs G, H we define m(G,H)=max{m:∃f:Em→EmsuchthatnocopyofGinKmisf-fixedandnocopyofHinKmisf-free} If m > 2 we define l(m,H)=max{l:∃f:Em→Em,f(e)≠eforledgese∈EmandnocopyofHinKmisf-free} In this paper we investigate the functions m(G, H) and l(m, H). We determine m(G, H) precisely for some families of graphs and estimate the asymptotic behaviour of l(m, H) for fixed H as m tends to infinity. Some of the results are generalised to functions defined on the set of edges of a hypergraph.

Original languageEnglish (US)
Pages (from-to)93-104
Number of pages12
JournalEuropean Journal of Combinatorics
Volume7
Issue number2
DOIs
StatePublished - Jan 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Extremal Problems Concerning Transformations of the Set of Edges of the Complete Graph'. Together they form a unique fingerprint.

  • Cite this