Article ID Journal Published Year Pages File Type
6424134 European Journal of Combinatorics 2015 14 Pages PDF
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
, , , ,