Abstract
This paper is devoted for presenting new neutrosophic similarity measures between neutrosophic graphs. We propose two ways to determine the neutrosophic distance between neutrosophic vertex graphs. The two neutrosophic distances are based on the Haussdorff distance, and a robust modified variant of the Haussdorff distance, moreover we show that they both satisfy the metric distance measure axioms. Furthermore, a similarity measure between neutrosophic edge graphs, that is based on a probabilistic variant of Haussdorff distance, is introduced. The aim is to use those measures for the purpose of matching neutrosophic graphs whose structure can be described in the neutrosophic domain.