Characterization of Distance Matrices of Weighted Hypercube Graphs and Petersen Graphs
Elena Rubei and Dario Villanis Ziani
Given a positive-weighted simple connected graph with m vertices, labeled by the numbers 1, . . . , m, we can construct an m × m matrix whose entry (i, j ), for any i, j ∈ {1, . . . , m}, is the minimal weight of a path between i and j, where the weight of a path is the sum of the weights of its edges. Such a matrix is called the distance matrix of the weighted graph. There is wide literature about distance matrices of weighted graphs. In this paper, we characterize distance matrices of positive-weighted n-hypercube graphs. Moreover, we show that a connected bipartite n-regular graph with order 2n is not necessarily the n-hypercube graph. Finally, we give a characterization of distance matrices of positive-weighted Petersen graphs.
Keywords: Distance matrices, weighted hypercube graphs, weighted Petersen graphs