Adjacency-diametrical matrix of a graph S. P. Leka Amruthavarshini, R. Rajkumar Abstract The adjacency-diametrical matrix (AD matrix) of a connected graph G G with diameter d d , denoted by A ​ D ​ ( G ) AD(G) , is the matrix indexed by the vertices of G G in which the ( i , j ) (i,j) -entry of A ​ D ​ ( G ) AD(G) is 1 1 if d G ​ ( v i , v j ) = 1 d_{G}(v_{i},v_{j})=1 , is d d if d G ​ ( v i , v j ) = d d_{G}(v_{i},v_{j})=d , and 0 0 otherwise, where d G ​ ( v i , v j ) d_{G}(v_{i},v_{j}) denotes the distance between the vertices v i v_{i} and v j v_{j} in G G . We determine the spectrum of the AD matrix for paths, cycles, and double star graphs and obtain its determinant for a connected graph. We characterize a class of bipartite graphs using the coefficients of the characteristic polynomial and the eigenvalues of the AD matrix. We establish bounds relating the eigenvalues of the AD matrix to various graph invariants, and we determine the spectrum of the AD matrix for graphs formed by the join, lexicographic product, and Cartesian product operations under certain conditions on the constituent graphs. Keywords: Graphs, Adjacency-diametrical matrix, Spectrum, Graph products MSC: 05C12, 05C50, 05C69, 05C15, 05C76 1 Introduction We consider only undirected, simple and finite graphs. Let G be a graph with vertex set V(G)=\{v_{1},v_{2},\ldots,v_{n}\} and edge set E(G) . If v_{i} and v_{j} are adjacent in G , we write v_{i}\sim v_{j} . The adjacency matrix A(G) is the 0 – 1 matrix whose rows and columns correspond to the vertices of G . For i,j\in\{1,2,\ldots,n\} , the (i,j) -entry is 1 exactly when v_{i} and v_{j} are adjacent. This definition extends to a weighted graph with an edge–weight function w:E(G)\to\mathbb{R}^{+} by setting the (i,j) -entry of A(G) to be w(e) whenever e=\{v_{i},v_{j}\}\in E(G) . Suppose G is a connected graph with diameter d . For each integer k with 1\leq k\leq d , the k -th adjacency matrix A_{k}(G) is the 0-1 matrix whose (i,j) -entry entry is 1 if and only if d_{G}(v_{i},v_{j})=k , where d_{G}(v_{i},v_{j}) denotes the distance between the vertices v_{i} and v_{j} , i.e., the length of a shortest path between v_{i} and v_{j} . Note that A_{1}(G)=A(G) . The distance matrix D(G) of G is the matrix indexed by the vertices of G , where for i,j\in\{1,2,\ldots,n\} , the (i,j) -entry of D(G) is d_{G}(v_{i},v_{j}) . It is evident that D(G)=\sum_{k=1}^{d}kA_{k}(G) . A large literature is devoted to the study of adjacency matrix of a graphs and its spectrum. We refer the reader to [ 3 , 5 ] for more details. The distance matrix is another significant matrix, providing valuable insights into the metric and spectral characteristics of a graph. It has a wide range of applications, including in chemistry, molecular biology, psychology, and various other scientific fields. For more details of this matrix and its variants, we refer the reader to [ 1 , 2 , 8 , 13 ] . Recently, De Ville introduced the notion of a generalized distance matrix in [ 6 ] . The generalized distance matrix of a connected G with diameter d is defined as the matrix \mathcal{M}(f;G) , whose entries are given by \mathcal{M}(f;G)_{v_{i},v_{j}}=f(d_{G}(v_{i},v_{j})), where f is a real-valued function on \{0,1,\ldots,d\} . It is shown that several familiar matrices, including the adjacency matrix, Laplacian matrix, and distance matrix, appear as special instances of this construction. Moreover, the paper presents applications of the spectral properties of this matrix to competition models in ecology and to rapidly mixing Markov chains. Now, we define the adjacency-diametrical matrix (or AD matrix ) of a connected graph G with diameter d . It is denoted by AD(G) , and is given by AD(G)=A(G)+dA_{d}(G). Equivalently, for i,j=1,2,\ldots,n , the (i,j) -entry of AD(G) is 1 if d_{G}(v_{i},v_{j})=1 ; is d if d_{G}(v_{i},v_{j})=d , and 0 otherwise. Note that AD(G) is a special case of the generalized distance matrix obtained by taking the function f satisfying f(1)=1 , f(d)=d , and f(i)=0 for every i=2,3,\dots,d-1 . The AD matrix is introduced to explore how a graph’s diameter relates to its other invariants and to examine how the matrix’s eigenvalues, eigenvectors, and characteristic polynomial interact with the diameter and related structural properties of the graph. Note that d=1 if and only if AD(G)=A(G)=D(G) and G=K_{n} . If d=2 , then AD(G)=D(G) , and conversely AD(G)=D(G) if and only if d\in\{1,2\} . We associate to G a weighted graph \mathcal{G}_{G} defined as follows: its vertex set is the same as that of G , and two vertices v_{i} and v_{j} are joined by an edge e_{ij} of weight 1 or d precisely when d_{G}(v_{i},v_{j})=1 or d_{G}(v_{i},v_{j})=d respectively. Clearly, A(\mathcal{G}_{G})=AD(G) . We now recall some definitions and notations. In a graph G , the degree d(v) of its vertex v is the number of edges incident with it. If all vertex in G have the degree r , then G is called an r -regular graph. In a weighted graph G , the weighted degree of its vertex v is defined as the sum of the weights of the edges incident with v . The weighted graph G is said to be weighted regular of degree r or weighted r -regular, if every vertex of G has weighted degree r . As usual P_{n} , C_{n} , and K_{n} denote the path, cycle and complete graph each on n vertices, respectively. The star graph on n vertices is denoted by S_{n} . The double star graph S_{n_{1},n_{2}} constructed by taking two disjoint star graphs S_{n_{1}} and S_{n_{2}} and then joining their centers by a single edge. A graph is called bipartite if its vertex set V can be partitioned into two subsets V_{1} and V_{2} such that every edge of G connects a vertex from V_{1} to a vertex from V_{2} . A graph G is said to be planar if it can be drawn in a plane without intersecting edges. Two vertices in a connected graph G are said to be antipodal, if the distance between these vertices is equal to the diameter of G . The chromatic number \chi(G) of a graph G is the minimum number of colors needed for coloring the vertices of G such that no two adjacent vertices receives the same color. The clique number \omega(G) of a graph G is the number of vertices in the maximal complete subgraph in G . A distance-regular graph is a regular graph in which, for any vertices u and v , the number of vertices at distance j from u and distance k from v depends only on j , k , and the distance between u and v . Let M be an n\times n matrix. The trace of M is written as \mbox{tr}(M) , and its characteristic polynomial is denoted by \Phi_{M}(x) . The eigenvalues of M are denoted by \lambda_{i}(M) for i=1,2,\dots,n , and the multiset of these eigenvalues, called the spectrum of M , is written as \mbox{Spec}(M) . For two real n\times n matrices A_{1} and A_{2} , we say that \lambda_{1} and \lambda_{2} are co-eigenvalues of A_{1} and A_{2} if there exists a vector X\in\mathbb{R}^{n} such that A_{i}X=\lambda_{i}X for i=1,2 . We denote by I_{n} the n\times n identity matrix, by \mathbf{1} the n\times 1 all-ones vector, and by \mathbf{0} the zero matrix. The rest of the paper is structured as follows: In Section 2 , we compute the spectrum of the AD matrix of paths, cycles and double star graphs. In Section 3 , we obtain the determinant of the AD matrix of a connected graph. In addition, a special class of bipartite graphs, called diametrical bipartite graphs, and characterize this class using the coefficients of the characteristic polynomial and the eigenvalues of the AD matrix. In Section 4 , we establish bounds relating the eigenvalues of the AD matrix to various graph invariants. In Section 5 , we determine the spectrum of the AD matrix formed by the join, lexicographic product, and Cartesian product operations. 2 Spectrum of the AD matrix of some graphs We refer to the spectrum of the AD matrix of a graph G as the adjacency-diametrical spectrum (or AD-spectrum ) of G . We begin by computing the characteristic polynomial of the AD matrix of the path graph P_{n} . Theorem 2.1 . (i) The characteristic polynomial of AD(P_{2}) is x^{2}-1 . (ii) For n\geq 3 , the characteristic polynomial of AD(P_{n}) is \Phi_{n}(x)-(n-1)^{2}\Phi_{n-2}(x)+2(1-n), where \Phi_{n}(x)=\overset{n}{\underset{k=1}{\prod}}\left(x-2\cos\frac{\pi k}{n+1}\right) . Proof. (i). Since P_{2}=K_{2} , the result is straight forward. (ii). For n\geq 3 , the diameter of P_{n} is n-1 . By a suitable relabeling of the vertices of P_{n} , we get AD(P_{n})=\begin{bmatrix}0&n-1&1&\dots&0&0\\ n-1&0&0&\dots&0&1\\ 1&0&0&\dots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\dots&0&1\\ 0&1&0&\dots&1&0\end{bmatrix}, and the characteristic polynomial of AD(P_{n}) is given by \displaystyle\Phi_{AD(P_{n})}(x) \displaystyle=\det\left(xI_{n}-AD(P_{n})\right) \displaystyle=\det\left(\begin{bmatrix}B&C\\ C^{T}&xI_{n-2}-A(P_{n-2})\end{bmatrix}\right) \displaystyle=\det(xI_{n-2}-A(P_{n-2}))\times\det\left(B-C(xI_{n-2}-A(P_{n-2}))^{-1}C^{T}\right), (2.1) where B=\begin{bmatrix}x&1-n\\ 1-n&x\end{bmatrix} and C=\begin{bmatrix}-1&0&\cdots&0&0\\ 0&0&\cdots&0&-1\\ \end{bmatrix}. For convenience, we write \Phi_{n}(x):=\Phi_{A(P_{n})}(x) for all n and it is known (cf. [ 3 , Theorem 3.7] ) that \Phi_{n}(x)=\overset{n}{\underset{k=1}{\prod}}\left(x-2\cos\tfrac{\pi k}{n+1}\right). (2.2) Also we have \displaystyle\det \displaystyle\left(B-C(xI_{n-2}-A(P_{n-2}))^{-1}C^{T}\right) \displaystyle=\det\left(B-\left(C~\tfrac{1}{\Phi_{n-2}(x)}\adj(xI_{n-2}-A(P_{n-2}))C^{T}\right)\right) \displaystyle=\det\left(B-\tfrac{1}{\Phi_{n-2}(x)}\begin{bmatrix}\Phi_{n-3}(x)&1\\ 1&\Phi_{n-3}(x)\end{bmatrix}\right) \displaystyle=\det\left(\begin{bmatrix}x-\tfrac{\Phi_{n-3}(x)}{\Phi_{n-2}(x)}&(1-n)-\tfrac{1}{\Phi_{n-2}(x)}\\ (1-n)-\tfrac{1}{\Phi_{n-2}(x)}&x-\tfrac{\Phi_{n-3}(x)}{\Phi_{n-2}(x)}\end{bmatrix}\right) \displaystyle=\left(x^{2}-n^{2}+2n-1\right)-\tfrac{2x(\Phi_{n-3}(x))}{\Phi_{n-2}(x)}+\tfrac{(\Phi_{n-3}(x))^{2}-1}{(\Phi_{n-2}(x))^{2}}+\tfrac{2(1-n)}{\Phi_{n-2}(x)}. (2.3) Applying ( 2.2 ) and ( 2.3 ) in ( 2.1 ) we get \Phi_{AD(P_{n})}(x)=\left(x^{2}-n^{2}+2n-1\right)\Phi_{n-2}(x)-2x\Phi_{n-3}(x)+\tfrac{(\Phi_{n-3}(x))^{2}-1}{\Phi_{n-2}(x)}+2(1-n). (2.4) It is known that the characteristic polynomial of the adjacency matrix of the path P_{n} and the Chebyshev polynomial of the second kind are related by \Phi_{n}(x)=U_{n}(\tfrac{x}{2}) , see e.g., [ 5 ] . If t=\tfrac{x}{2} , then \Phi_{n-2}(x)=U_{n-2}(t) , \Phi_{n-3}(x)=U_{n-3}(t) . Since U_{n}(t) satisfies the identity U^{2}_{k}(t)-U_{k-1}(t)U_{k+1}(t)=1 [ 14 , Eqn. 3.21] , for k=n-3 we obtain \Phi^{2}_{n-3}(x)-\Phi_{n-4}(x)\Phi_{n-2}(x)=1 . This implies that the term \tfrac{(\Phi_{n-3}(x))^{2}-1}{(\Phi_{n-2}(x))^{2}} equals \Phi_{n-4}(x) . Then ( 2.4 ) becomes, \Phi_{AD(P_{n})}(x)=\left(x^{2}-n^{2}+2n-1\right)\Phi_{n-2}(x)-2x\Phi_{n-3}(x)+\Phi_{n-4}(x)+2(1-n) (2.5) Also U_{n}(t) satisfying the recurrence relation U_{k}(t)=2tU_{k-1}(t)-U_{k-2}(t) [ 9 , Eqns. 1.6a, 1.6b] , with U_{0}(t)=1,U_{1}(t)=2t . Then for k=n-2 , k=n-1 and k=n we get \Phi_{n-4}(x)=x\Phi_{n-3}(x)-\Phi_{n-2}(x) , \Phi_{n-3}(x)=x\Phi_{n-2}(x)-\Phi_{n-1}(x) and \Phi_{n}(x)=x\Phi_{n-1}(x)-\Phi_{n-2}(x) respectively. Substituting these in ( 2.5 ), we obtain \displaystyle\Phi_{AD(P_{n})}(x) \displaystyle=\left(x^{2}-n^{2}+2n-1\right)\Phi_{n-2}(x)-2x\Phi_{n-3}(x)+x\Phi_{n-3}(x)-\Phi_{n-2}(x)+2(1-n) \displaystyle=\left(x^{2}-n^{2}+2n-2\right)\Phi_{n-2}(x)-x\Phi_{n-3}(x)+2(1-n) \displaystyle=\left(x^{2}-n^{2}+2n-2\right)\Phi_{n-2}(x)-x^{2}\Phi_{n-2}(x)+x\Phi_{n-1}(x)+2(1-n) \displaystyle=-\Phi_{n-2}(x)-(n-1)^{2}\Phi_{n-2}(x)+x\Phi_{n-1}(x)+2(1-n) \displaystyle=\Phi_{n}(x)-(n-1)^{2}\Phi_{n-2}(x)+2(1-n). This completes the proof. ∎ The AD-spectrum of the cycle graph is determined in the following result. Theorem 2.2 . For n\geq 3 , we have \mbox{Spec}(AD(C_{n}))=\begin{cases}\left\{2\cos\frac{2\pi k}{n}+\frac{n}{2}\cos\pi k\,:\,k=1,2,\dots,n\right\},&\text{if }n\text{~is even};\\ \left\{2\cos\frac{2\pi k}{n}+(n-1)\cos\pi k\;\cos\frac{\pi k}{n}:\,k=1,2,\dots,n\right\},&\text{if }n\text{ is odd}.\end{cases} Proof. Note that the diameter of C_{n} is \frac{n}{2} when n is even and \frac{n-1}{2} when n is odd. Moreover, the matrix AD(C_{n}) is circulant: if n is odd, the nonzero entries in its first row are c_{1}=c_{n-1}=1 and c_{\tfrac{n}{2}}=\tfrac{n}{2} ; if n is even, the nonzero entries in its first row are c_{1}=c_{n-1}=1 and c_{\tfrac{n-1}{2}}=c_{\tfrac{n+1}{2}}=\tfrac{n-1}{2} . It is known that for an n\times n circulant matrix C with first row (c_{0},c_{1},\dots,c_{n-1}) , the eigenvalue \lambda_{k} of C is given by \lambda_{k}=\overset{n-1}{\underset{j=0}{\sum}}c_{j}\,\omega^{jk}_{n},\qquad j=0,1,\dots,n-1, where \omega_{n}=e^{\frac{2\pi i}{n}} is a primitive n -th root of unity. Suppose n is even. The eigenvalues \lambda_{k} of AD(C_{n}) for k=0,1\dots,n-1 are given by \lambda_{k}=\omega^{k}+(\omega^{k})^{n-1}+\tfrac{n}{2}(\omega^{k})^{\tfrac{n}{2}}\\ =e^{\frac{2\pi ik}{n}}+e^{-\frac{2\pi ik}{n}}+\tfrac{n}{2}(e^{\frac{2\pi ik}{n}})^{\frac{n}{2}}\\ =2\cos\tfrac{2\pi k}{n}+\tfrac{n}{2}\cos\pi k. Suppose n is odd. The eigenvalues \lambda_{k} of AD(C_{n}) for k=0,1\dots,n-1 are given by \displaystyle\lambda_{k} \displaystyle=\omega^{k}+(\omega^{k})^{n-1}+\left(\tfrac{n-1}{2}\right)((\omega^{k})^{\frac{n-1}{2}}+(\omega^{k})^{\frac{n+1}{2}}) \displaystyle=\omega^{k}+\omega^{-k}+\left(\tfrac{n-1}{2}\right)\left\{(\omega^{k})^{\tfrac{n}{2}}\left((\omega^{k})^{\frac{-1}{2}}+(\omega^{k})^{\frac{1}{2}}\right)\right\} \displaystyle=2\cos\tfrac{2\pi k}{n}+\left(\tfrac{n-1}{2}\right)\left\{e^{\pi ik}\left(e^{-\tfrac{\pi ik}{n}}+e^{\tfrac{\pi ik}{n}}\right)\right\} \displaystyle=2\cos\tfrac{2\pi k}{n}+(n-1)\left\{\cos\pi k\,\cos\tfrac{\pi k}{n}\right\} and the proof is complete. ∎ The characteristic polynomial of the AD matrix of the double star graph S_{n_{1},n_{2}} is described in the following result. Theorem 2.3 . The characteristic polynomial of AD(S_{n_{1},n_{2}}) is x^{n_{1}+n_{2}-4}\left(x^{4}-\left(9n_{1}n_{2}-8n_{1}-8n_{2}+8\right)x^{2}+4\left(n_{1}n_{2}-n_{1}-n_{2}+1\right)\right). Proof. By suitably arranging the vertices of S_{n_{1},n_{2}} , it can be seen that AD(S_{n_{1},n_{2}})=\begin{bmatrix}0&1&J_{1\times(n_{1}-1)}&\bm{0}_{1\times(n_{2}-1)}\\ 1&0&\bm{0}_{1\times(n_{1}-1)}&J_{1\times(n_{2}-1)}\\ J_{(n_{1}-1)\times 1}&\bm{0}_{(n_{1}-1)\times 1}&\bm{0}_{(n_{1}-1)\times(n_{1}-1)}&3J_{(n_{1}-1)\times(n_{2}-1)}\\ \bm{0}_{(n_{2}-1)\times 1}&J_{(n_{2}-1)\times 1}&3J_{(n_{2}-1)\times(n_{1}-1)}&\bm{0}_{(n_{2}-1)\times(n_{2}-1)}\end{bmatrix}. Since each row of \bm{0}_{(n_{1}-1)\times(n_{1}-1)} (resp. \bm{0}_{(n_{2}-1)\times(n_{2}-1)} ) has equal row sum 0 , the vector \bm{1}_{(n_{1}-1)\times 1} (resp. \bm{1}_{(n_{2}-1)\times 1} ) is an eigenvector corresponding to the eigenvalue 0 . Assume that the remaining eigenvectors X_{i} for i=2,3,\dots,n_{1}-1 (resp. Y_{j} for j=2,3,\dots,n_{2}-1 ) are chosen orthogonal to \bm{1}_{(n_{1}-1)\times 1} (resp. \bm{1}_{(n_{2}-1)\times 1} ). Then \left[0\quad 0\quad X^{T}_{i}\quad\bm{0}_{1\times(n_{2}-1)}\right]^{T} \big(\text{resp.}\left[0\quad 0\quad\bm{0}_{1\times(n_{1}-1)}\quad Y^{T}_{j}\right]^{T}\big) is an eigenvector of AD(S_{n_{1},n_{2}}) corresponding to the eigenvalue 0 . This implies that for i=2,3,\dots,n_{1}-1, and for j=2,3,\dots,n_{2}-1 , the vectors \left[0\quad 0\quad X_{i}\quad\bm{0}_{1\times(n_{2}-1)}\right]^{T} and \left[0\quad 0\quad\bm{0}_{1\times(n_{1}-1)}\quad Y_{j}\right]^{T} are eigenvectors of AD(S_{n_{1},n_{2}}) corresponding to the eigenvalues 0 with multiplicity n_{1}-2 and 0 with multiplicity n_{2}-2 respectively. Therefore 0 is an eigenvalue of AD(S_{n_{1},n_{2}}) with multiplicity n_{1}+n_{2}-4 . In this way we obtained n_{1}+n_{2}-4 eigenvalues. All these eigenvectors are orthogonal to \left[1\quad 0\quad\bm{0}_{1\times(n_{1}-1)}\quad\bm{0}_{1\times(n_{2}-1)}\right]^{T} , \left[0\quad 1\quad\bm{0}_{1\times(n_{1}-1)}\quad\bm{0}_{1\times(n_{2}-1)}\right]^{T} , \left[0\quad 0\quad J_{1\times(n_{1}-1)}\quad\bm{0}_{1\times(n_{2}-1)}\right]^{T} and \left[0\quad 0\quad\bm{0}_{1\times(n_{1}-1)}\quad J_{1\times(n_{2}-1)}\right]^{T} . Hence, the space spanned by these four vectors and the space spanned by the remaining four eigenvectors of AD(S_{n_{1},n_{2}}) are same. Therefore, the remaining eigenvectors of AD(S_{n_{1},n_{2}}) are of the form X=\left[\alpha_{1}\quad\alpha_{2}\quad\alpha_{3}J_{1\times(n_{1}-1)}\quad\alpha_{4}J_{1\times(n_{2}-1)}\right]^{T} for some (\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})\neq(0,0,0,0) . If \beta is an eigenvalue of AD(S_{n_{1},n_{2}}) corresponding to the eigenvector X , then AD(S_{n_{1},n_{2}})X=\beta X, which is equivalent to the system \begin{bmatrix}-\beta&1&n_{1}-1&0\\ 1&-\beta&0&n_{2}-1\\ 1&0&-\beta&3(n_{2}-1)\\ 0&1&3(n_{1}-1)&-\beta\end{bmatrix}\begin{bmatrix}\alpha_{1}\\ \alpha_{2}\\ \alpha_{3}\\ \alpha_{4}\end{bmatrix}=\begin{bmatrix}0\\ 0\\ 0\\ 0\end{bmatrix}. The above system admits a nontrivial solution if and only if the square matrix on the left-hand side is non-singular. Hence, the remaining four eigenvalues of AD(S_{n_{1},n_{2}}) are the eigenvalues of this matrix \begin{bmatrix}0&1&n_{1}-1&0\\ 1&0&0&n_{2}-1\\ 1&0&0&3(n_{2}-1)\\ 0&1&3(n_{1}-1)&0\end{bmatrix} whose characteristic polynomial is x^{4}-\left(9n_{1}n_{2}-8n_{1}-8n_{2}+8\right)x^{2}+4\left(n_{1}n_{2}-n_{1}-n_{2}+1\right) . This concludes the proof. ∎ 3 Determinant Definition 3.1 . Let G be a connected graph. A set P of vertices in G , with |P|\geq 3 is said to be an adjacency-diametrical cycle of G if the vertices in P admit a cyclic ordering in which each pair of consecutive vertices are either adjacent or antipodal. A partition \mathcal{S}=\left\{P_{1},P_{2},\dots,P_{k}\right\} of a subset of V(G) is said to be a adjacency-diametrical partition of G if its each part P_{i} satisfies one of the following: (i) P_{i} is of size \geq 3 and is an adjacency-diametrical cycle of G , (ii) P_{i} is of size 2 and its vertices are either adjacent or antipodal. In addition, if \mathcal{S} is a partition of V(G) , then it is said to be a spanning adjacency-diametrical partition of G . Let p(\mathcal{S}) and p_{1}(\mathcal{S}) denote the number of parts in an adjacency-diametrical partition \mathcal{S} of G which have size 2 and \geq 3 , respectively. Example 3.1 . For the graph G shown in Figure 1 , \{\{1,7\},\{2,3,5,6\}\} is an adjacency-diametrical partition of G , and \{\{1,3,5\},\{2,6\},\{7,4\}\} is a spanning adjacency-diametrical partition of G . Figure 1 : The graph G Lemma 3.1 . Let G be a connected graph with at least three vertices. There is a one-to-one correspondence between cycles of length k in the associated weighted graph \mathcal{G} and adjacency–diametrical cycles of length k in G . Proof. Let the diameter of G be d . Given a cycle C_{\mathcal{G}} in \mathcal{G} , traverse it in cyclic order. Every edge of C_{\mathcal{G}} is either a unit-weight edge that corresponds to an adjacency (an edge) of G , or a weight- d edge that corresponds to an antipodal pair of vertices in G . Replacing each weight- d edge of C_{\mathcal{G}} by the corresponding pair of antipodal vertices in G , and interpreting unit edges as usual adjacency edges gives a cycle in G that alternates between adjacencies and antipodal jumps, which is precisely an adjacency–diametrical cycle in G . Conversely, any adjacency–diametrical cycle of G contains adjacencies of G and antipodal relations; collapsing each antipodal relation to a single weight- d edge yields a unique cycle of \mathcal{G} . These two constructions are inverse to each other, establishing the bijection. With the bijection established, the parity of cycle lengths is preserved by this correspondence. ∎ By an elementary subgraph of \mathcal{G}_{G} we mean a subgraph of \mathcal{G}_{G} (whose edge weights are 1 or d ), and whose components are either a cycle or an edge. The following result is a direct consequence of the facts discussed so for in this section. Corollary 3.1 . Let G be a connected graph with diameter d . There is a one-to-one correspondence between an adjacency-diametrical partition \mathcal{S}=\{P_{1},P_{2},\dots,P_{k}\} of G and an elementary subgraph of \mathcal{G}_{G} with k components (each of whose edge weights are 1 or d ), and whose component is a cycle when |P_{i}|\geq 3 , and an edge when |P_{i}|=2 . Now we proceed to determine the determinant of the AD matrix of a connected graph. Theorem 3.1 . Let G be a connected graph with vertex set V(G)=\{1,2,\dots,n\} and having diameter d . Then \det(AD(G))=\sum(-1)^{n-p(\mathcal{S})-p_{1}(\mathcal{S})}2^{p_{1}(\mathcal{S})}d^{2a(\mathcal{S})+a_{1}(\mathcal{S})}, (3.1) where the summation is over all the spanning adjacency-diametrical partitions \mathcal{S} of G . Here a(\mathcal{S}) and a_{1}(\mathcal{S}) represents the number of pairs of antipodal vertices in all the parts P_{i} of size 2 and \geq 3 in \mathcal{S} , respectively. Proof. We consider the associated weighted graph \mathcal{G}_{G} of G . Let A(\mathcal{G}_{G})=(d_{ij}) . We have \det(A(\mathcal{G}_{G}))=\overset{}{\underset{\pi}{\sum}}sgn(\pi)d_{1\pi(1)}\dots d_{n\pi(n)}, (3.2) where the summation is overall the permutations \pi on \{1,2\dots,n\} . Consider a nonzero term d_{1\pi(1)}\dots d_{n\pi(n)} . Since \pi admits a cycle decomposition, such a term will correspond to some 2 cycle (ij) of \pi which designate either an edge joining i and j with weight 1 or d , as well as some cycles of higher order, which correspond to cycles of \mathcal{G}_{G} . (Note that \pi(i)\neq i for any i .) Thus, each nonzero term in the summation arises from an elementary weighted subgraph of \mathcal{G}_{G} . Suppose the term d_{1\pi(1)}\dots d_{n\pi(n)} corresponds to the elementary subgraph \mathcal{H} of \mathcal{G}_{G} . Then the sign of \pi is given by, sgn(\pi)=(-1)^{n-\text{number of cycles in }\pi} , which equals (-1)^{n-c(\mathcal{H})-c_{1}(\mathcal{H})} , where c(\mathcal{H}) and c_{1}(\mathcal{H}) denote the number of edge components and number of cycle components in \mathcal{H} , respectively. Each spanning elementary subgraph \mathcal{H} contributes 2^{c_{1}(\mathcal{H})} terms in the summation, since each cycle of \mathcal{G}_{G} can be associated to a cyclic permutation in two distinct ways. In \mathcal{H} , some edge component may have weight d , which contributes d^{2t(\mathcal{H})} to the summation in ( 3.2 ), where t(\mathcal{H}) denote the number of edge components of \mathcal{H} having weight d . Also, some cycle components of \mathcal{H} may contain edges with weight d , which contributes d^{t_{1}(\mathcal{H})} to the summation in ( 3.2 ), where t_{1}(\mathcal{H}) denote the number of edges having weight d in all the cycle components of \mathcal{H} . Hence, combining these observations, ( 3.2 ) becomes \det(A(\mathcal{G}_{G}))=\sum(-1)^{n-c(\mathcal{H})-c_{1}(\mathcal{H})}2^{c_{1}(\mathcal{H})}d^{2t(\mathcal{H})+t_{1}(\mathcal{H})}, (3.3) where the summation is over all the spanning elementary subgraphs \mathcal{H} of \mathcal{G}_{G} . In view of Corollary 3.1 , each spanning elementary subgraph \mathcal{H} of \mathcal{G}_{G} corresponds to a spanning adjacency-diametrical partitions \mathcal{S} of G . Moreover, it is evident that c(\mathcal{H})=p(\mathcal{S}) , c_{1}(\mathcal{H})=p_{1}(\mathcal{S}) , t(\mathcal{H})=a(\mathcal{S}) , and t_{1}(\mathcal{H})=a_{1}(\mathcal{S}) . Since AD(G)=A(\mathcal{G}_{G}) , applying these information in ( 3.3 ), we get the desired result. ∎ Example 3.2 . For the star graph S_{4} with central vertex 1 and pendent vertices 2, 3, 4, the spanning adjacency-diametrical partitions of are \mathcal{S}_{1}=\{\{1,2,3,4\}\} , \mathcal{S}_{2}=\{\{1,2,4,3\}\} , \mathcal{S}_{3}=\{\{1,3,2,4\}\} , \mathcal{S}_{4}=\{\{1,2\},\{3,4\}\} , \mathcal{S}_{5}=\{\{1,3\},\{2,4\}\} , and \mathcal{S}_{6}=\{\{1,4\},\{2,3\}\} . Note that p(\mathcal{S}_{i})=a(\mathcal{S}_{i})=p_{1}(\mathcal{S}_{j})=a_{1}(\mathcal{S}_{j})=0 for i=1,2,3 and j=4,5,6 ; p(\mathcal{S}_{i})=p_{1}(\mathcal{S}_{j})=a(\mathcal{S}_{j})=1 for i=1,2,3 and j=4,5,6 ; a_{1}(\mathcal{S}_{i})=2 for i=1,2,3 . Applying these values in ( 3.1 ), we get \det(AD(S_{4}))=3\,(-1)^{3}\,2^{1}\,2^{2}+3\,(-1)^{2}\,2^{0}\,2^{2(1)}=-12. This coincide with the direct computation of the determinant of AD(G) . Example 3.3 . Consider the path graph P_{n} on n (\geq 2) vertices. We show that \det(AD(P_{n}))=\begin{cases}2(n-1),&\text{if}~n\text{ is odd};\\ -1,&\text{if}~n=2;\\ (n-2)^{2},&\text{if}~n=4k\text{ for }k=1,2,\dots;\\ -n^{2},&\text{if}~n=4k+2\text{ for }k=1,2,\dots\end{cases} Clearly the diameter of P_{n} is n-1 . We assume that V(P_{n})=\{1,2,\ldots,n\} and E(P_{n})=\{\{i,i+1\}:i=1,2,\ldots,n-1\} . We proceed by considering three cases. Case 1. Suppose n is odd. In this case P_{n} has \mathcal{S}=\{\{1,2,\dots,n\}\} as the unique spanning adjacency-diametrical partition, and p(\mathcal{S})=a(\mathcal{S})=0 and p_{1}(\mathcal{S})=a_{1}(\mathcal{S})=1 , Applying these in ( 3.1 ), we get \det(AD(P_{n}))=(-1)^{n-1}\,2^{1}\,(n-1)^{1}=2(n-1) . Case 2. Suppose n is even. Let n=2 . The only spanning adjacency-diametrical partition of P_{2} is \mathcal{S}=\{\{1,2\}\} , and p(\mathcal{S})=a(\mathcal{S})=1 and p_{1}(\mathcal{S})=a_{1}(\mathcal{S})=0 . Then from ( 3.1 ), we get \det(AD(P_{2}))=(-1)^{2-1}\,2^{0}\,1^{2}=-1 . Let n=4k or n=4k+2 , where k=1,2,\dots . In either case, the spanning adjacency-diametrical partitions for P_{n} are the following: \mathcal{S}_{1}=\{\{1,2,\dots,n\}\} , \mathcal{S}_{2}=\{\{1,2\},\{3,4\},\dots,\{n-1,n\}\} and \mathcal{S}_{3}=\{\{1,n\},\{2,3\},\dots,\{n-2,n-1\}\} . Here p(\mathcal{S}_{1})=a(\mathcal{S}_{1})=p_{1}(\mathcal{S}_{2})=a(\mathcal{S}_{2})=a_{1}(\mathcal{S}_{2})=p_{1}(\mathcal{S}_{3})=a(\mathcal{S}_{3})=0 , p_{1}(\mathcal{S}_{1})=a_{1}(\mathcal{S}_{1})=a_{1}(\mathcal{S}_{3})=1 and p(\mathcal{S}_{2})=p(\mathcal{S}_{3})=\frac{n}{2} . When n=4k for k=1,2,\dots , applying these in ( 3.1 ), we obtain \det(AD(P_{n}))=(-1)^{n-1}\,2^{1}\,(n-1)^{1}+(-1)^{n-\frac{n}{2}}+(-1)^{n-\frac{n}{2}}\,(n-1)^{2}=(n-2)^{2} . Similarly, when n=4k+2 for k=1,2,\dots , from ( 3.1 ), we get \det(AD(P_{n}))=(-1)^{n-1}\,2^{1}\,(n-1)^{1}+(-1)^{n-\frac{n}{2}}+(-1)^{n-\frac{n}{2}}\,(n-1)^{2}=-n^{2} . Theorem 3.2 . Let G be a connected graph with n vertices and diameter d . Let \Phi_{AD(G)}(\lambda)=\det(\lambda I-AD(G))=\lambda^{n}+c_{1}\lambda^{n-1}+\dots+c_{n} be the characteristic polynomial of AD(G) . Then c_{k}=\sum(-1)^{p(\mathcal{S})+p_{1}(\mathcal{S})}2^{p_{1}(\mathcal{S})}d^{2a(\mathcal{S})+a_{1}(\mathcal{S})}, (3.4) where the summation is over all the adjacency-diametrical partitions \mathcal{S} of G with k vertices, for each k=1,2,\dots,n . Proof. Note that the number (-1)^{k}c_{k} is the sum of all k\times k principal minors of AD(G) , k=1,2,\dots,n . By Theorem 3.1 , c_{k}=(-1)^{k}\sum(-1)^{k-p(\mathcal{S})-p_{1}(\mathcal{S})}2^{p_{1}(\mathcal{S})}d^{2a(\mathcal{S})+a_{1}(\mathcal{S})}, where the summation is over all the adjacency-diametrical partitions \mathcal{S} of G with k vertices, for each k=1,2,\dots,n . Hence, c_{k}=\sum(-1)^{p(\mathcal{S})+p_{1}(\mathcal{S})}2^{p_{1}(\mathcal{S})}d^{2a(\mathcal{S})+a_{1}(\mathcal{S})} . Note that c_{1}=0 . ∎ Note 3.1 . We now obtain the explicit expressions of c_{2} and c_{3} by applying Theorem 3.2 . (i) Adjacency-diametrical partitions of G with two vertices is of the form either \mathcal{S}_{1}=\{\{v_{i},v_{j}\}\} , where v_{i}\sim v_{j} or \mathcal{S}_{2}=\{\{v_{i},v_{j}\}\} , where d_{G}(v_{i},v_{j})=d . For both types we have p(\mathcal{S}_{1})=p(\mathcal{S}_{2})=a(\mathcal{S}_{2})=1 , p_{1}(\mathcal{S}_{1})=p_{1}(\mathcal{S}_{2})=a(\mathcal{S}_{1})=a_{1}(\mathcal{S}_{1})=a_{1}(\mathcal{S}_{2})=0 . Substituting these values in ( 3.4 ), we get c_{2}={\sum}(-1)^{1}\,2^{0}\,d^{0}+{\sum}(-1)^{1}\,2^{0}\,d^{2(1)}, where the first and second sums range over all adjacency–diametrical partitions of the forms \mathcal{S}_{1} and \mathcal{S}_{2} , respectively. Hence, c_{2}=-(|E(G)|+kd^{2}), where k denotes the number of unordered antipodal pairs of vertices in G . (ii) Adjacency-diametrical partitions of G with three vertices fall into the following four types: \mathcal{S}_{1}=\{\{v_{i},v_{j},v_{k}\}\} , where v_{i}\sim v_{j} , v_{j}\sim v_{k} and v_{i}\sim v_{k} ; \mathcal{S}_{2}=\{\{v_{i},v_{j},v_{k}\}\} , where v_{i}\sim v_{j} , v_{j}\sim v_{k} and d_{G}(v_{i},v_{k})=d ; \mathcal{S}_{3}=\{\{v_{i},v_{j},v_{k}\}\} , where v_{i}\sim v_{j} , d_{G}(v_{j},v_{k})=d and d_{G}(v_{i},v_{k})=d ; \mathcal{S}_{4}=\{\{v_{i},v_{j},v_{k}\}\} , where d_{G}(v_{i},v_{j})=d , d_{G}(v_{j},v_{k})=d and d_{G}(v_{i},v_{k})=d . For i=1,2,3 , we have p(\mathcal{S}_{i})=a(\mathcal{S}_{i})=a_{1}(\mathcal{S}_{1})=0 , p_{1}(\mathcal{S}_{i})=a_{1}(\mathcal{S}_{2})=1 with a_{1}(\mathcal{S}_{3})=2 and a_{1}(\mathcal{S}_{4})=3 . Substituting these in ( 3.4 ), gives c_{3}=\sum(-1)^{1}\,2^{1}\,d^{0}+\sum(-1)^{1}\,2^{1}\,d^{1}+\sum(-1)^{1}\,2^{1}\,d^{2}+\sum(-1)^{1}\,2^{1}\,d^{3}\\ where the four sums correspond to adjacency-diametrical partitions of G of the form \mathcal{S}_{1} , \mathcal{S}_{2} , \mathcal{S}_{3} , and \mathcal{S}_{4} , respectively. Therefore, c_{3}=-2(k_{0}+k_{1}d+k_{2}d^{2}+k_{3}d^{3}), where for s\in\{0,1,2,3\} , k_{s} is the number of number of unordered triples \{v_{i},v_{j},v_{k}\} that have exactly s antipodal pairs and the other 3-s pairs at distance 1. Note that k_{0} is the number of triangles in G . Note that many results on the spectra of adjacency matrices of unweighted graphs in spectral graph theory extend directly to weighted graphs without any modification. In the forthcoming results, we will use these facts without explicitly stating this extension each time. We obtain the next result as a direct consequence of [ 3 , Corollary 3.11] , using the fact that AD(G)=A(\mathcal{G}_{G}) , and that adjacency-diametrical cycles of G can be viewed as cycles in \mathcal{G}_{G} (cf. Lemma 3.1 ). Corollary 3.2 . Let G be a connected graph on n vertices. Let \Phi_{AD(G)}(\lambda)=\det(\lambda I-AD(G))=\lambda^{n}+c_{1}\lambda^{n-1}+\dots+c_{n} be the characteristic polynomial of AD(G) . Suppose c_{3}=c_{5}=\dots=c_{2k-1}=0 . Then G has no odd adjacency-diametrical cycle of length i,3\leq i\leq 2k-1 . Furthermore, the number of adjacency-diametrical cycles of length 2k+1 in G is -\frac{1}{2}c_{2k+1} . 3.1 Diametrical bipartite graphs Now we introduce a special class of bipartite graphs. Definition 3.2 . A connected graph G is said to be diametrical bipartite if it is bipartite with bipartition (V_{1},V_{2}) and no two vertices in the same part are antipodal. Lemma 3.2 . A connected bipartite graph is diametrical bipartite if and only if its diameter d is odd. Proof. Let G be a connected bipartite graph with bipartition (V_{1},V_{2}) and diameter d . Since G is bipartite, every pair of vertices lying in the same part V_{i} has even distance, because any path in a bipartite graph alternates between the two parts. If d is odd, then no two vertices in the same part can be at distance d , and therefore G is diametrical bipartite. If d is even, then any pair of vertices x,y with d_{G}(x,y)=d must lie in the same bipartition class (as they are at even distance). Hence some two vertices in the same part are antipodal, so G is not diametrical bipartite. ∎ Theorem 3.3 . Let G be a connected graph with at least three vertices. Then the following are equivalent. (i) G is diametrical bipartite (ii) \mathcal{G}_{G} is bipartite (iii) All the adjacency-diametrical cycles in G are of even length Proof. Let the diameter of G be d . The weighted graph \mathcal{G}_{G} is obtained from G by taking a copy of G and assigning unit weight to their edges, and adding joining each pairs of antipodal vertices in G by a new edge having weight d . (i) \Leftrightarrow (ii): Suppose G is diametrical bipartite. By Lemma 3.2 , d is odd. Consequently, any pair of antipodal vertices cannot both occur in the same part of the bipartition of G . So end vertices of the newly added edge with weight d must lie in two different parts. Thus \mathcal{G}_{G} is bipartite. By retracing the above argument, we get the proof of converse part. (ii) \Leftrightarrow (iii): In view of Lemma 3.1 , \mathcal{G} is bipartite (every cycle in \mathcal{G} has even length) if and only if every adjacency–diametrical cycle in G has even length. ∎ Since AD(G)=A(\mathcal{G}_{G}) , the next result follows directly from Theorem 3.3 together with [ 3 , Theorem 3.14] . Theorem 3.4 . Let G be a connected graph on n vertices. Then the following conditions are equivalent. (i) G is diametrical bipartite; (ii) If \Phi_{AD(G)}(\lambda)=det(AD(G)-\lambda I)=\lambda^{n}+c_{1}\lambda^{n-1}+\dots+c_{n} is the characteristic polynomial of AD(G) , then c_{2k+1}=0,k=0,1,\dots ; (iii) The eigenvalues of AD(G) are symmetric with respect to the origin. 4 Some graph invariants and bounds Definition 4.1 . Let G be a connected graph with diameter d . The diametrical degree of a vertex u in G , denoted by \hat{d_{G}}(u) or simply by \hat{d}(u) , is the number of vertices v in G such that d_{G}(u,v)=d , i.e, \hat{d}(u)=|\{v\in V(G):d_{G}(u,v)=d\}|. We denote by \hat{\Delta}(G) and \hat{\delta}(G) , the maximum and the minimum of the diametrical degrees of the vertices of G , respectively. The diametrical degree sum of G , denoted by \hat{d}(G) , is the sum of all the diametrical degrees of the vertices of G , i.e., \hat{d}(G)=\overset{}{\underset{v\in V(G)}{\sum}}\hat{d}(v). Example 4.1 . The diametrical degrees of the vertices of the graph G shown in Figure 2 are \hat{d}(v_{1})=0,\hat{d}(v_{2})=0,\hat{d}(v_{3})=1,\hat{d}(v_{4})=0,\hat{d}(v_{5})=0, and \hat{d}(v_{6})=1 . And the diametrical degree of G is \hat{d}(G)=0+0+1+0+0+1=2 . Moreover, \hat{\delta}(G)=0 and \hat{\Delta}(G)=1 . Figure 2 : The graph G Lemma 4.1 . Let G be a connected graph with n vertices, m edges and diameter d . Let \lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} be the eigenvalues of AD(G) . Then (i) \overset{n}{\underset{i=1}{\sum}}\lambda_{i}=0 ; (ii) \overset{n}{\underset{i=1}{\sum}}\lambda^{2}_{i}=2m+d^{2}\hat{d}(G) . Proof. (i) Since the trace of AD(G) is 0 , statement (i) follows. (ii) Let AD(G)=(d_{ij}) . Then \overset{n}{\underset{i=1}{\sum}}\lambda^{2}_{i}=tr(AD(G))^{2}=\overset{n}{\underset{i=1}{\sum}}\overset{n}{\underset{j=1}{\sum}}d_{ij}d_{ji}=\overset{n}{\underset{i=1}{\sum}}\left(d(v_{i})+d^{2}\hat{d}(v_{i})\right)=2m+d^{2}\hat{d}(G) and the proof is complete. ∎ The largest eigenvalue of AD(G) is said to be the adjacency-diametrical spectral radius (or AD spectral radius ) of G . Theorem 4.1 . Let G be a connected graph with n vertices, m edges and diameter d . Let \lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} be the eigenvalues of AD(G) . Then \lambda_{1}\leq\sqrt{\left(\frac{n-1}{n}\right)(2m+d^{2}\hat{d}(G))}. Proof. From Lemma 4.1 (i),we have \overset{n}{\underset{i=1}{\sum}}\lambda_{i}=0 . Therefore, \lambda_{1}=-\overset{n}{\underset{i=2}{\sum}}\lambda_{i} and hence \lambda_{1}\leq\sum_{i=2}^{n}|\lambda_{i}|. (4.1) Using Cauchy-Schwarz inequality, we get \left(\overset{n}{\underset{i=2}{\sum}}|\lambda_{i}|\right)^{2}\leq(n-1)\overset{n}{\underset{i=2}{\sum}}\lambda^{2}_{i}. (4.2) By Lemma 4.1 (ii) and using ( 4.1 ), ( 4.2 ), we get 2m+d^{2}\hat{d}(G)-\lambda^{2}_{1}=\sum_{i=2}^{n}\lambda^{2}_{i}\geq\frac{1}{n-1}\left(\sum_{i=2}^{n}|\lambda_{i}|\right)^{2}\geq\frac{\lambda^{2}_{1}}{n-1}. Hence \displaystyle 2m+d^{2}\hat{d}(G)\geq\lambda^{2}_{1}\left(1+\frac{1}{n-1}\right)=\lambda^{2}_{1}\left(\frac{n}{n-1}\right), which leads to the required result. ∎ Theorem 4.2 . Let G be a adjacency-diametrical bipartite graph with n vertices, m edges and diameter d . Let \lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} be the eigenvalues of AD(G) . Then \lambda_{n}\leq\sqrt{m+\frac{1}{2}d^{2}\hat{d}(G)}. Proof. From Theorem 3.4 (iii), we know that \lambda_{1}=-\lambda_{n} and Lemma 4.1 gives \overset{n}{\underset{i=1}{\sum}}\lambda^{2}_{i}=2m+d^{2}\hat{d}(G) . Hence \lambda_{1}^{2}+\lambda_{n}^{2}\leq 2m+d^{2}\hat{d}(G) , which yields 2\lambda_{n}^{2}\leq 2m+d^{2}\hat{d}(G) . This completes the proof. ∎ An independent set S of G is said to be an adjacency-diametrical independent set (or AD independent set ) of G , if no two vertices of S are antipodal. The maximum cardinality of a adjacency-diametrical independent set in G , denoted by \alpha_{AD}(G) , is said to be the adjacency-diametrical independence number (or AD independence number ) of G [ 10 ] . Clearly \alpha_{AD}(G)\leq\alpha(G). For the graph G shown in Figure 3 , the subset \{v_{3},v_{4},v_{5}\} is a AD independent set of G and it is the AD independent set of G of maximum cardinality. So the AD independence number \alpha_{AD}(G)=3 . Figure 3 : The graph G Not every independent set is an AD independent set. For instance, in the graph shown in Figure 3 , the subset \{v_{1},v_{5}\} is an independent set, but not an AD independent set, since v_{1} and v_{5} are antipodal vertices. It is evident that the AD independence number of G equals the independence number of \mathcal{G}_{G} . Since AD(G)=A(\mathcal{G}_{G}) , applying [ 5 , Theorem 3.10.1] yields the following result. Theorem 4.3 . Let G be a connected graph on n vertices. Let n^{+} and n^{-} denote the number of positive and negative eigenvalues of AD(G) respectively. Then \alpha_{AD}(G)\leq\min\{n-n^{+},n-n^{-}\}. A proper coloring of a connected graph G is said to be an adjacency-diametrical coloring (or AD-coloring ) of G , if no two antipodal vertices have same color. The adjacency-diametrical chromatic number (or AD chromatic number ) of G , denoted by \chi_{AD}(G) , is the minimum number of colors needed for an adjacency-diametrical coloring of G . For each color, the set of all vertices which get that color is an AD independent and is called an adjacency-diametrical color class . Equivalently, \chi_{AD}(G) is the cardinality of minimum partition of V(G) into AD independent subsets [ 11 ] . Note that for any connected graph G , \chi(G)\leq\chi_{AD}(G) . For example, the path graph P_{5} has \chi(P_{5})=2 and \chi_{AD}(P_{5})=3 . It is clear that the AD chromatic number of G equals the chromatic number of \mathcal{G}_{G} . Since AD(G)=A(\mathcal{G}_{G}) , applying [ 3 , Theorem 3.23] directly implies the following result. Theorem 4.4 . Let G be a connected graph with n vertices and with at least one edge. Let \lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} be the eigenvalues of AD(G) . Then \chi_{AD}(G)\geq 1-\frac{\lambda_{1}}{\lambda_{n}}. Corollary 4.1 . Let G be a connected, planar graph on n vertices. Let \lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} be the eigenvalues of AD(G) . Suppose \chi(G)=\chi_{AD}(G) . Then \lambda_{1}\leq-3\lambda_{n} . Proof. It is known that every planar graph is 4- colorable [ 4 ] . It follows that \chi_{AD}(G)\leq 4 . Consequently, Theorem 4.4 yields \lambda_{1}\leq-3\lambda_{n} . ∎ There are several graphs for which the condition \chi(G)=\chi_{AD}(G) of Corollary 4.1 holds. Examples include the path P_{2n} , the cycle C_{n} for n=4k+2 with k=1,2,\dots , and double star. Definition 4.2 . Let G be a connected graph with diameter d . The adjacency-diametrical degree (or AD degree ) of a vertex v in G , denoted by \hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{d}}}_{G}(v) (or simply \hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{d}}}(v) ), is defined as \hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{d}}}_{G}(v)=d(v)+d\hat{d}(v). The maximum and the minimum of the AD degrees of vertices in G are denoted by \hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{\Delta}}}(G) and \hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{\delta}}}(G) , respectively. If every vertex of G has the same AD degree r , then G is called the adjacency-diametrical regular (or AD regular ) of degree r or simply r - AD regular . The mean adjacency-diametrical degree of G , denoted by \bar{d}_{AD}(G) , is defined as \bar{d}_{AD}(G)=\frac{1}{n}\overset{}{\underset{v\in V(G)}{\sum}}\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{d}}}_{G}(v). Observe that the AD degree of a vertex in G coincide with the weighted degree of the corresponding vertex in \mathcal{G}_{G} . Consequently, the maximum and minimum AD degrees of G agree with the maximum and minimum weighted degrees of \mathcal{G}_{G} respectively. Hence, G is AD regular if and only if \mathcal{G}_{G} is weighted regular. Moreover, the mean adjacency-diametrical degree of G is equal to the mean weighted degree of \mathcal{G}_{G} . Example 4.2 . Consider the cycle graph C_{6} . Each vertex in C_{6} has degree 2 and diametrical degree 1 , and the diameter of C_{6} is 3 . Hence the AD degree of every vertex in C_{6} is 5 . Thus C_{6} is 5 -AD regular. Remark 4.1 . Every distance-regular graph is AD-regular. However, not every AD regular graph is distance-regular. For instance, the hexagonal prism graph shown in Figure 4(a) is AD regular but not distance regular. Also, not every regular graph is AD-regular. For instance, the Frucht graph shown in Figure 4(b) is regular but not AD regular. Moreover, we have not discussed whether every AD regular graph must also be regular, nor have we provided an example showing that AD regular does not imply regular. (a) (b) Figure 4 : (a) The hexagonal prism graph, (b) The Frucht graph. Notice that the AD degree of each vertex in G equals the weighted degree of the corresponding vertex in \mathcal{G}_{G} . Then from [ 5 , Proposition 1.1.2] and [ 5 , Theorem 3.2.1] , we obtain the following two results. Proposition 4.1 . A connected graph G is r -AD regular if and only if all one vector is an eigenvector of G with corresponding eigenvalue r . Theorem 4.5 . Let G be a connected graph with n vertices and diameter d . Let \lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} be the eigenvalues of AD(G) . Then \hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{\delta}}}\leq\bar{d}_{AD}(G)\leq\lambda_{1}\leq\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{\Delta}}}. Equality holds if and only if G is AD regular. Notice that the mean adjacency-diametrical degree of G equals the mean weighted degree of \mathcal{G}_{G} . Since AD(G)=A(\mathcal{G}_{G}) , by [ 5 , Theorem 3.5.7] we obtain the following result. Theorem 4.6 . Let G be a AD regular graph and (r=)\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} be the eigenvalues of AD(G) . Let H be an induced subgraph of G with n_{1} vertices and mean adjacency-diametrical degree \bar{d}_{AD}(H) . Then \frac{n_{1}(r-\lambda_{n})}{n}+\lambda_{n}\leq\bar{d}_{AD}(H). (4.3) Clearly G is AD regular if and only if \mathcal{G}_{G} is regular. Since AD(G)=A(\mathcal{G}_{G}) , from [ 5 , Theorem 3.10.2] , the following result can be deduced. Theorem 4.7 . If G is a AD regular graph and (r=)\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} be the eigenvalues of AD(G) . Then \alpha_{AD}(G)\leq n\frac{-\lambda_{n}}{\lambda_{1}-\lambda_{n}}. Since AD(G)=A(\mathcal{G}_{G}) , applying [ 5 , Theorem 3.10.3] , we get the following result. Theorem 4.8 . Let G be a connected graph. Let \lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n} be the eigenvalues of AD(G) . Let t^{-},t^{0},t^{+} denote the number of eigenvalues \lambda_{i} less than, equal to, or greater than -1 respectively. Let m=\min\{t^{0}+t^{-}+1,t^{0}+t^{+},1+\lambda_{1}\} . Then \omega(G)\leq m . If m=t^{0}+t^{-}+1 and the eigenvalues greater than -1 is exceed t^{0}+t^{-} , then \omega(G)\leq m-1 . 5 Graph products and AD-spectra The join of two vertex-disjoint graphs G and H , denoted G\vee H , is the graph obtained from the union G\cup H by adding all possible edges between every vertex of G and every vertex of H . Since the diameter of G\vee H is 2 , so the AD-spectrum of G\vee H coincides the distance spectrum of G\vee H , which was described in [ 12 , Theorem 2] for the case when G and H are regular. The lexicographic product of two graphs G_{1}=(V_{1},E_{1}) and G_{2}=(V_{2},E_{2}) , denoted G_{1}[G_{2}] , is the graph with vertex set V_{1}\times V_{2} . Two vertices (u_{i},v_{j}) and (u_{k},v_{\ell}) are adjacent in G_{1}[G_{2}] if u_{i}u_{k}\in E_{1} or ( u_{i}=u_{k} and v_{j}v_{\ell}\in E_{2}) . We now compute the AD-spectrum of the lexicographic product of two graphs. Theorem 5.1 . Let G be a connected graph with n vertices and let H be an r -regular graph with m vertices. Let \lambda_{1},\lambda_{2},\dots,\lambda_{m} be the AD-spectrum of G and (r=)\mu_{1},\mu_{2},\dots,\mu_{n} be the spectrum of A(H) . (i) If the diameter of G[H] is 2 , then the AD-spectrum of G[H] contains the eigenvalue m\mu_{i}+2m-r-2 with multiplicity 1 and -(\lambda_{j}+2) with multiplicity n , for i=1,2,\dots,n ; j=2,3,\dots,m-1 . (ii) If the diameter of G[H] is greater than 2 , then the AD-spectrum of G[H] contains the eigenvalue m\mu_{i}+r with multiplicity 1 and \lambda_{j} with multiplicity n , for i=1,2,\dots,n ; j=2,3,\dots,m-1 . Proof. (i) Since the diameter of G[H] is 2, we have AD(G[H])=D(G[H]) . The distance spectrum of D(G[H]) is given in [ 7 , Theorem 3.3] , and therefore the claim follows. (ii) Suppose the diameter of G[H] is greater than 2 . Let AD(G)=[d_{ij}] . With a suitable labeling of the vertices of G[H] , the AD matrix of G[H] can be expressed as follows: \displaystyle AD(G[H]) \displaystyle=\begin{bmatrix}A(H)&d_{12}J_{m}&d_{13}J_{m}&\dots&d_{1n}J_{m}\\ d_{21}J_{m}&A(H)&d_{23}J_{m}&\dots&d_{2n}J_{m}\\ d_{31}J_{m}&d_{32}J_{m}&A(H)&\dots&d_{3n}J_{m}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ d_{(n-1)1}J_{m}&d_{(n-1)2}J_{m}&d_{(n-1)3}J_{m}&\dots&d_{(n-1)n}J_{m}\\ d_{n1}J_{m}&d_{n2}J_{m}&d_{n3}J_{m}&\dots&A(H)\end{bmatrix} \displaystyle=(AD(G)\otimes J_{m})+(I_{n}\otimes A(H)). Since H is r -regular, the all one vector \bm{1}_{m\times 1} is an eigenvector of A(H) corresponding to the eigenvalue r . The remaining eigenvalues \lambda_{j} of A(H) , with eigenvectors X_{j} , are orthogonal to \bm{1} . Let Y_{k} , k=1,2,\dots,n , denote the n linearly independent eigenvectors of I_{n} associated with the eigenvalue 1 . Then, \displaystyle AD(G[H])(Y_{k}\otimes X_{j}) \displaystyle=\left((AD(G)\otimes J_{m})+(I_{n}\otimes A(H))\right)(Y_{k}\otimes X_{j}) \displaystyle=(AD(G)Y_{k})\otimes(J_{m}X_{j})+(I_{n}Y_{k})\otimes(A(H)X_{j}) \displaystyle=0+(Y_{k}\otimes\lambda_{j}X_{j}) \displaystyle=\lambda_{j}(Y_{k}\otimes X_{j}). Thus, for each j=2,3,\dots,m , the vectors Y_{k}\otimes X_{j} (for k=1,2,\dots,n ) are eigenvectors of AD(G[H]) corresponding to the eigenvalue \lambda_{j} . Let Z_{i} be an eigenvector corresponding to the eigenvalue \mu_{i} of AD(G) for i=1,2\ldots,n . Then \displaystyle AD(G[H])(Z_{i}\otimes\bm{1}_{m}) \displaystyle=\left((AD(G)\otimes J_{m})+(I_{n}\otimes A(H))\right)(Z_{i}\otimes\bm{1}_{m}) \displaystyle=(AD(G)Z_{i})\otimes(J_{m}\bm{1}_{m})+(I_{n}Z_{i})\otimes(A(H)\bm{1}_{m}) \displaystyle=(\mu_{i}Z_{i}\otimes m\bm{1}_{m})+(Z_{i}\otimes r\bm{1}_{m}) \displaystyle=(m\mu_{i}+r)(Z_{i}\otimes\bm{1}_{m}). Therefore, m\mu_{i}+r is an eigenvalue of AD(G[H]) with eigenvector Z_{i}\otimes\bm{1}_{m} . Furthermore, the nm vectors of the form Z_{i}\otimes\bm{1}_{m} and Y_{k}\otimes X_{j} are linearly independent. Since eigenvectors associated with distinct eigenvalues are linearly independent, and AD(G[H]) has a basis consisting entirely of eigenvectors, the theorem is established. ∎ Let G_{1}=(V_{1},E_{1}) and G_{2}=(V_{2},E_{2}) be two graphs with vertex sets V_{1}=\{u_{1},u_{2},\dots,u_{n}\} and V_{2}=\{v_{1},v_{2},\dots,v_{n}\} , respectively. The Cartesian product of G_{1} and G_{2} , denoted by G_{1}\Box G_{2} , is the graph with vertex set V_{1}\times V_{2} , and two vertices (u_{i},v_{j}) and (u_{k},v_{\ell}) are adjacent if u_{i}=u_{k} and v_{j}v_{\ell}\in E_{2} , or u_{i}u_{k}\in E_{1} and v_{j}=v_{\ell} . Next, we determine the AD-spectrum of the Cartesian product of two graphs. Theorem 5.2 . Let G and H be two distance regular graphs with n and m vertices respectively and let the diameters of G and H be denoted by d_{G} and d_{H} respectively. Let the spectrum of A(G) and A(H) be \lambda_{1},\lambda_{2},\dots,\lambda_{n} and \mu_{1},\mu_{2},\dots,\mu_{m} , respectively. Let the spectrum of A_{d_{G}}(G) and A_{d_{H}}(H) be \gamma_{1},\gamma_{2},\dots,\gamma_{n} and \delta_{1},\delta_{2},\dots,\delta_{m} respectively, such that \lambda_{i} and \gamma_{i} (resp. \mu_{j} and \delta_{j} ) are the co-eigenvalues of A(G) and A_{d_{G}}(G) (resp. A(H) and A_{d_{H}}(H) ) for i=1,2,\dots,n (resp. j=1,2,\dots,m ). Then the AD-spectrum of G\Box H is given by \lambda_{i}+\mu_{j}+(d_{G}+d_{H})(\gamma_{l}\delta_{k}), for i,l=1,2,\dots,n and j,k=1,2,\dots,m . Proof. Let V(G)=\{u_{1},u_{2},\dots,u_{n}\} and V(H)=\{v_{1},v_{2},\dots,v_{m}\} . Let u=(u_{1},v_{1}) , v=(u_{2},v_{2}) \in V(G)\times V(H) . Then the (u,v) -th entry of AD(G\Box H) is given by AD(G\Box H)_{u,v}=\begin{cases}1,&\hskip-227.62204pt\text{if either }d_{G}(u_{1},u_{2})=1\text{ and }d_{H}(v_{1},v_{2})=0\\ \hskip 85.35826pt\text{or }d_{G}(u_{1},u_{2})=0,\text{ and }d_{H}(v_{1},v_{2})=1;\\ d_{G}+d_{H},&\hskip-227.62204pt\text{if }d_{G}(u_{1},u_{2})=d_{G}\text{ and }d_{H}(v_{1},v_{2})=d_{H};\\ 0,&\hskip-227.62204pt\text{otherwise}.\end{cases} By a suitable arrangement of the vertices of G\Box H , we obtain AD(G\Box H)=(A(G)\otimes I_{m})+(I_{n}\otimes A(H))+(d_{G}+d_{H})\,(A_{d_{G}}(G)\otimes A_{d_{H}}(H)). (5.1) Since G and H are distance regular, A_{d_{G}}(G) and A_{d_{H}}(H) can be written as A_{d_{G}}(G)=p_{d_{G}}(A(G)) and A_{d_{H}}(H)=q_{d_{H}}(A(H)) , where p_{d_{G}}(x) and q_{d_{H}}(x) are polynomials of degrees d_{G} and d_{H} , respectively. Therefore, ( 5.1 ) becomes \displaystyle AD(G\Box H) \displaystyle=A(G\Box H)+(d_{G}+d_{H})\,(p_{d_{G}}(A(G))\otimes q_{d_{H}}(A(H))). Let X_{i} and Y_{j} be the eigenvectors corresponding to the eigenvalues \lambda_{i} of A(G) and \mu_{j} of A(H) , respectively. Then \displaystyle AD(G\Box H)\,(X_{i}\otimes Y_{j}) \displaystyle=\Big(A(G\Box H)+(d_{G}+d_{H})\,(p_{d_{G}}(A(G))\otimes q_{d_{H}}(A(H)))\Big)(X_{i}\otimes Y_{j}) \displaystyle=A(G\Box H)(X_{i}\otimes Y_{j})+(d_{G}+d_{H})\,\Big(p_{d_{G}}(A(G))\otimes q_{d_{H}}(A(H))\Big)(X_{i}\otimes Y_{j}) \displaystyle=(\lambda_{i}+\mu_{j})(X_{i}\otimes Y_{j})+(d_{G}+d_{H})\,(p_{d_{G}}(\lambda_{i})q_{d_{H}}(\mu_{j}))(X_{i}\otimes Y_{j}) \displaystyle=(\lambda_{i}+\mu_{j}+(d_{G}+d_{H})(\gamma_{i}\delta_{j}))(X_{i}\otimes Y_{j}). Hence X_{i}\otimes Y_{j} is an eigenvector of AD(G\Box H) corresponding to the eigenvalue \lambda_{i}+\mu_{j}+(d_{G}+d_{H})(\gamma_{i}\delta_{j}) as desired. ∎