Journal article icon

Journal article

Disjoint induced subgraphs of the same order and size

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.
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1016/j.ejc.2015.03.005

Authors


Bollobas, B More by this author
Kittipassorn, T More by this author
Narayanan, BP More by this author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
Publisher:
Elsevier Ltd. Publisher's website
Journal:
European Journal of Combinatorics Journal website
Volume:
49
Pages:
153-166
Publication date:
2015-04-11
Acceptance date:
2015-03-16
DOI:
ISSN:
0195-6698
URN:
uuid:5521671b-5e96-463d-8b49-5e615548358d
Source identifiers:
521483
Local pid:
pubs:521483
Keywords:

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP