Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424134 | European Journal of Combinatorics | 2015 | 14 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Béla Bollobás, Teeradej Kittipassorn, Bhargav P. Narayanan, Alexander D. Scott,