Y.Y. Ke
Please Note
3 records found
1
A threshold graph is generated from a single node by repeatedly adding either a node i connected to all existing nodes with a common link weight wi > 0 or a node i connected to none. Let Gw be a weighted threshold graph encoded by the weight vector w = (w1, w2, …, wN ) with wi ≥ 0. A closed-form expression for the pseudoinverse of its Laplacian matrix Qw is derived via spectral decomposition, which yields an explicit formula for the effective resistance matrix Ωw. We present a detailed structural characterization of the matrix Ωw and determine a subset of the spectrum of the matrix Ωw in terms of the weights wi . As an application, we show that when the missing links of a threshold graph are sequentially added in nondecreasing order of effective resistance, the threshold property of the graph is preserved at each step until the complete graph of the same size is obtained.
Threshold graphs are generated from one node by repeatedly adding a node that links to all existing nodes or adding a node without links. In the weighted threshold graph, we add a new node in step i, which is linked to all existing nodes by a link of weight wi . In this work, we consider the set AN that contains all Laplacian matrices of weighted threshold graphs of order N. We show that AN forms a commutative algebra. Using this, we find a common basis of eigenvectors for the matrices in AN . It follows that the eigenvalues of each matrix in AN can be represented as a linear transformation of the link weights. In addition, we prove that, if there are just three or fewer different weights, two weighted threshold graphs with the same Laplacian spectrum must be isomorphic.