The generalized adjacency-distance matrix of connected graphs

Abstract

Let G be a connected graph with adjacency matrix $A(G)$ and distance matrix $\mathcal{D}(G)$. The adjacency-distance matrix of G is defined as $S(G)=\mathcal{D}(G)+A(G)$. In this paper, $S(G)$ is generalized by the convex linear combinations $S_{\alpha }(G)=\alpha \mathcal{D}(G)+(1-\alpha )A(G)$where $\alpha \in [0,1]$. Let $\rho (S_{\alpha }(G))$ be the spectral radius of $S_{\alpha }(G)$. This paper presents results on $S_{\alpha }(G)$ with emphasis on $\rho (S_{\alpha }(G))$ and some results on $S(G)$ are extended to all α in some subintervals of $[0,1]$. For $\alpha \in [1/2,1]$, the trees attaining the largest and the smallest $\rho (S_{\alpha }(G))$ among trees of fixed order are determined and it is proved that $\rho (S_{\alpha }(G))$ is a branching index. Moreover, for $\alpha \in (1/2,1]$, the graphs that uniquely minimize $\rho (S_{\alpha }(G))$:

1. among all connected graphs of fixed order and fixed connectivity, and

2. among all connected graphs of fixed order and fixed chromatic number

are characterized.

Keywords:

• Adjacency matrix
• distance matrix
• adjacency-distance matrix
• extremal graphs
• Turán graph

Acknowledgements

G. Pastén thanks the support of the Coloquio de Matemática CR-4486, Universidad de Antofagasta, Chile.

Disclosure statement

No potential conflict of interest was reported by the author(s).