For any given graph G, consider the graph Ĝ which is a cone over G. We study two important invariants of such a cone, namely, the complexity (the number of spanning trees) and the Jacobian of the graph. We prove that complexity of graph Ĝ coincides with the number of rooted spanning forests in G and the Jacobian of Ĝ is isomorphic to the cokernel of the operator I + L(G), where L(G) is the Laplacian of G and I is the identity matrix. As a consequence, one can calculate the complexity of Ĝ as det(I + L(G)). As an application, we establish general structural theorems for the Jacobian of Ĝ in the case when G is a circulant graph or cobordism of two circulant graphs.
Предметные области OECD FOS+WOS
- 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ
- 1.01 МАТЕМАТИКА
- 27.45 Комбинаторный анализ. Теория графов