ALGEBRAIC CONNECTIVITY AND EXACT LAPLACIAN SPECTRA OF GENERALIZED GRAPH PRODUCTS

Abstract

An anisotropically weighted Cartesian product is studied as a generalized graph product in which edges inherited from two factors receive independent positive weights α and β. The construction retains the Kronecker-sum form of the Laplacian and therefore admits an exact spectrum for arbitrary connected factors. In this paper, we are establishing explicit formulas for the algebraic connectivity, spectral radius, Laplacian energy, Kirchhoff index and weighted spanning-tree complexity from that spectral identity. With the resource constraint α+β=c, algebraic connectivity is a minimum of two affine functions. It derives its unique maximizing allocation in closed form by equalizing the weighted Fiedler values of the factors. From this representation whereby managers obtain cash through bonds, three other conclusions arise. The budget-averaged algebraic connectivity equals 1/2 of its optimal value, the width of the allocation interval that retains at least a fraction ρ of the optimum is c(1-ρ) and independent of spectra; the optimizer equalizes (but need not minimize) the two lowest directional modes yet does not necessarily minimize spectral condition number or Kirchhoff index. All formulas are supported by numerical calculations of five products: path-cycle, grid, complete-cube and Petersen-cycle combinations. In the cases tested, the optimized connectivity outperforms equal weighting by as much as 60%. All eigenvalues, resistance sums, tree complexities and the curves depicted here are derived from exact factor spectra rather than a stochastic simulation. The framework thus provides a straightforward mathematical design rule for products of weighted graphs that has an order of magnitude lower computational cost than diagonalizing the full product Laplacian.