### Abstract

Let E_{m} denote the set of edges of the complete graph on m vertices K_{m}, and let f : E_{m} → E_{m} be a function. A subgraph G = (V (G), E (G)) of K_{m} 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 language | English (US) |
---|---|

Pages (from-to) | 93-104 |

Number of pages | 12 |

Journal | European Journal of Combinatorics |

Volume | 7 |

Issue number | 2 |

DOIs | |

State | Published - Jan 1 1986 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics