Disjoint induced subgraphs of the same order and size
For a graph G, let f(. G) be the largest integer k such that there are two vertex-disjoint subgraphs of G each on k vertices, both inducing the same number of edges. We prove that f(. G). ≥. n/2. -. o(. n) for every graph G on n vertices. This answers a question of Caro and Yuster.
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
Elsevier
2015
|