2022/12/10 by Carlos A. Alfaro, Alfaro, Carlos A., Octavio Zapata +1 · 3 citations
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2212.05297
openalex publication_date 2022/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a connected graph with adjacency matrix A(G). The distance matrix D(G) of G has rows and columns indexed by V(G) with uv-entry equal to the distance dist(u,v) which is the number of edges in a shortest path between the vertices u and v. The transmission trs(u) of u is defined as ∑v∈ V(G)dist(u,v). Let trs(G) be the diagonal matrix with the transmissions of the vertices of G in the diagonal, and deg(G) the diagonal matrix with the degrees of the vertices in the diagonal. In this paper we investigate the Smith normal form (SNF) and the spectrum of the matrices Ddeg+(G):=deg(G)+D(G), Ddeg(G):=deg(G)-D(G), Atrs+(G):=trs(G)+A(G) and Atrs(G):=trs(G)-A(G). In particular, we explore how good the spectrum and the SNF of these matrices are for determining graphs up to isomorphism. We found that the SNF of Atrs has an interesting behaviour when compared with other classical matrices. We note that the SNF of Atrs can be used to compute the structure of the sandpile group of certain graphs. We compute the SNF of Ddeg+, Ddeg, Atrs+ and Atrs for several graph families. We prove that complete graphs are determined by the SNF of Ddeg+, Ddeg, Atrs+ and Atrs. Finally, we derive some results about the spectrum of Ddeg and Atrs.