On homometric sets in graphs

Details On homometric sets in graphs On homometric sets in graphs

2012-03-06

arxiv.org/abs/1203.1158v1

Mathematics

Combinatorics

Scientific paper

For a vertex set $S\subseteq V(G)$ in a graph $G$, the {\em distance multiset}, $D(S)$, is the multiset of pairwise distances between vertices of $S$ in $G$. Two vertex sets are called {\em homometric} if their distance multisets are identical. For a graph $G$, the largest integer $h$, such that there are two disjoint homometric sets of order $h$ in $G$, is denoted by $h(G)$. We slightly improve the general bound on this parameter introduced by Albertson, Pach and Young (2010) and investigate it in more detail for trees and graphs of bounded diameter. In particular, we show that for any tree $T$ on $n$ vertices $h(T) \geq \sqrt[3]{n}$ and for any graph $G$ of fixed diameter $d$, $h(G) \geq cn^{1/ (2d-2)}$.

Affiliated with

Also associated with

No associations

Rating

On homometric sets in graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On homometric sets in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On homometric sets in graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-537115