2007/10/09 by Mireille Boutin, Gregor Kemper, Boutin, Mireille +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms #cs.CV #math.CO
paper · pdf · doi:10.48550/arxiv.0710.1870
19 pages
arxiv created 2007/10/09 · openalex publication_date 2007/10/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider complete graphs with edge weights and/or node weights taking values in some set. In the first part of this paper, we show that a large number of graphs are completely determined, up to isomorphism, by the distribution of their sub-triangles. In the second part, we propose graph representations in terms of one-dimensional distributions (e.g., distribution of the node weights, sum of adjacent weights, etc.). For the case when the weights of the graph are real-valued vectors, we show that all graphs, except for a set of measure zero, are uniquely determined, up to isomorphism, from these distributions. The motivating application for this paper is the problem of browsing through large sets of graphs.