On the rank of the distance matrix of graphs

Ezequiel Dratman, Luciano N. Grippo, Verónica Moyano and Adrián Pastine

Applied Mathematics and Computation, 2022, vol. 433, issue C

Abstract: Let G be a connected graph with V(G)={v1,…,vn}. The (i,j)-entry of the distance matrix D(G) of G is the distance between vi and vj. In this article, using the well-known Ramsey’s theorem, we prove that for each integer k≥2, there is a finite amount of graphs whose distance matrices have rank k. We exhibit the list of graphs with distance matrices of rank 2 and 3. Besides, we study the rank of the distance matrices of graphs belonging to a family of graphs with their diameters at most two, the trivially perfect graphs. We show that for each η≥1 there exists a trivially perfect graph with nullity η. We also show that for threshold graphs, which are a subfamily of the family of trivially perfect graphs, the nullity is bounded by one.

Keywords: Distance matrix; Distance rank; Threshold graph; Trivially perfect graph (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300322004684
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:433:y:2022:i:c:s0096300322004684

DOI: 10.1016/j.amc.2022.127394

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().