Vertex-weighted graphs and their applications

Abstract

In our recent work in computational biology, our approach to modeling protein structures requires that each vertex be weighted by a vector of weights. This motivates the results we present here. We show that many graphical invariants can be generalized to vertex weights by replacing the maximum(minimum) cardinality of a vertex set with a sum over the vertex weights. We also generalize the Laplacian of a vertex-weighted graph to include vector-weighted vertices, including generalizing some spectral results.