Effective resistance matrices of weighted threshold graphs
Yingyue Ke (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Piet van Mieghem (TU Delft - Electrical Engineering, Mathematics and Computer Science)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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.
help_outline