Extensions of the Graham-Hoffman-Hosoya Type Theorems for the Exponential Distance Matrices and $q$-Distance Matrices

Abstract:

      Let $G$ be a strongly connected directed weighted graph with vertex set $\{v_1,v_2,\dots,v_n\}$, in which each edge $e$ is assigned with an arbitrary nonzero weight $w(e)$. For any two vertices $v_i$, $v_j$ of $G$, the distance $d_{ij}$ from $v_i$ to $v_j$ is defined as $$d_{ij}=\min_{P \in \mathcal{P}(v_i,v_j)}\sum_{e \in P}w(e),$$ where $\mathcal{P}(v_i,v_j)$ denotes the set consisting of all the directed paths from $v_i$ to $v_j$ in $G$. Given a nonzero indeterminant $q$, following the definitions from Yan and Yeh (Adv. Appl. Math., 2007), and Bapat et al. (Linear Algebra Appl., 2006), one can define the exponential distance matrix of $G$ as $\mathcal{F}^q_G=(q^{d_{ij}})_{n\times n}$, and define the $q$-distance matrix of $G$ as $\mathcal{D}^q_G=(d^q_{ij})_{n\times n}$ with \begin{center}$d^q_{ij} = \left\{\begin{array}{ll}\frac{1 - q^{d_{ij}}}{1 - q},&\text{if $q \ne 1$}\\ d_{ij},&\text{if $q = 1$}\end{array}\right.,$\end{center} extending the original definitions only for the undirected unweighted connected graphs. One of the remarkable results about the distance matrices of graphs is due to the Graham-Hoffman-Hosoya theorem (J. Graph Theory, 1977). In this paper, we present some Graham-Hoffman-Hosoya type theorems for the exponential distance matrix $\mathcal{F}^q_G$ and $q$-distance matrix $\mathcal{D}^q_G$, extending all the known Graham-Hoffman-Hosoya type theorems.