Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Homometric sets in trees
 
conference paper

Homometric sets in trees

Fulek, Radoslav
•
Mitrovic, Slobodan  
2014
European Journal Of Combinatorics
6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb)', u'6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb)

Let G = (V, E) denote a simple graph with vertex set V and edge set E. The profile of a vertex set V' subset of V denotes the multiset of pairwise distances between the vertices of V'. Two disjoint subsets of V are homometric if their profiles are the same. If G is a tree on n vertices, we prove that its vertex set contains a pair of disjoint homometric subsets of size at least root n/2 - 1. Previously it was known that such a pair of size at least roughly n(1/3) exists. We get a better result in the case of haircomb trees, in which we are able to find a pair of disjoint homometric sets of size at least cn(2/3) for a constant c > 0. (C) 2013 Elsevier Ltd. All rights reserved.

  • Details
  • Metrics
Type
conference paper
DOI
10.1016/j.ejc.2013.06.008
Web of Science ID

WOS:000324786900021

Author(s)
Fulek, Radoslav
Mitrovic, Slobodan  
Date Issued

2014

Publisher

Academic Press Ltd- Elsevier Science Ltd

Publisher place

London

Published in
European Journal Of Combinatorics
Total of pages

8

Volume

35

Start page

256

End page

263

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL1  
Event name
6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb)', u'6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb)
Available on Infoscience
January 9, 2014
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/99172
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés