# On the Vector Degree Matrix of a Connected Graph

Authors: Nasr A. Zeyada; Anwar Saleh; Majed Albaity; Amr K. Amin
Journal: Journal of Mathematics
 (2022)

---

## Abstract

A matrix representation of the graph is one of the tools to study the algebraic structure and properties of a graph. In this paper, by defining the vector degree matrix of graphG, we provide a new matrix representation of the graph. For some standard graphs, VD-eigenvalues, VD-spectrum, and VD-energy values are defined and calculated. Moreover, we calculate the VD-matrix and calculate the VD-eigenvalues for graphs representing the chemical composition of paracetamol and tramadol.


---

## Body

## 1. Introduction

The relationship between structural and spectral properties of a network could be a key question within the field of Network Science. Spectral graph strategies have become an elementary tool in the analysis of huge advanced networks and connected disciplines, with a broad variety of applications in machine learning, data processing, Internet search and ranking, scientific computing, and PC vision. The central topic of pure mathematics graph theory is learning the relationship between a graph’s structure and its eigenvalues. Specifically, the eigenvalues of matrices representing the graph structure, like the contiguity or the Laplacian matrices, have an on-the-spot associated with the behavior of many networked slashing processes, like spreading processes, synchronization of oscillators, random walks, accord dynamics, and a large type of distributed algorithms. Details on spectra and the theory of graph energy can be found in [1, 2, 4–6, 10–15], whereas details on its chemical applications are found in the book [9] and the review [7, 8].Given a graph, we can associate several matrices that record information about vertices and how they are interconnected. In this paper, we introduced a new matrix based on the distances between the vertices and their degrees. By calculating the new eigenvalues for some standard graphs, we study some properties of this new matrix.Lemma 1 (see [4]).
For the standard graphsKn, Km,n, and Cn, we have(i)
SpecKn=n−1−11n−1.(ii)
SpecKm,n=mn−mn011m+n−2.(iii)
SpecCn=22cos2π/n⋯2cos2n−1π/n12⋯2,ifnis odd;22cos2π/n⋯2cos2n−2π/n−212⋯21,ifnis even..


## 2. The Vector Degree Spectrum of a Graph

Definition 1.
LetG=V,Ebe an undirected graph with vertex setV=v1,v2,…,vn. A vector degree function ofGdenoted byVDGis a functionVDG:VG⟶ℤ∪0d+1wheredis the diameter of the graphGsuch thatVDvj=vj⟶=Γ0vj,Γ1vj,…,Γdvj, whereΓivjis the number of vertices of distanceifrom the vertexvjinG. The vectorvj⟶is called the vector degree vector corresponding to the vertexvj.
The vector degree product of two-degree vectorsvi⟶ and vj⟶ in a graph G is denoted by VDvi⟶.vj⟶ and defined as(1)VDvi⟶.vj⟶=vi⟶.vj⟶,ifi≠j;0,otherwise,where vi⟶.vj⟶ is the dot product of the vectors vi⟶ and vj⟶ in the Euclidean space ℝd.
The vector degree matrix ofG is then VD=VDG=aij, where(2)aij=VDvi⟶.vj⟶.
The characteristic polynomialdetγI−VDG of VDG is called the VD-characteristic polynomial of G and is denoted by PVDG=∑i=0naiγn−i. The eigenvalues of the matrix VDG which are the zeros of γI−VDG are called the VD-eigenvalues of G and form its Spectrum denoted by SpecVDG. If the distinct VD-eigenvalues of G are γ1,γ2,…,γm with multiplicities t1,t2,…,tm, respectively, then SpecVDG is written as γ1γ2…γmt1t2…tm.By the above definition, the degree matrix is a real symmetricn×n matrix. Therefore, its eigenvalues γ1,γ2,…,γm are real numbers. Since the trace of VDG is zero, the sum of its eigenvalues is also equal to zero.Lemma 2.
LetGbe a connected graph withnvertices, and letγ1,γ2,…,γnbe its VD-eigenvalues. Then,(1)
∑i=1nγi=0.(2)
∑i=1nγi2=2∑1≤i<j≤nvi⟶.vj⟶2.Definition 2.
The Vector degree energy of the graphGis(3)EVD=EVDG=∑i=1nγi.Theorem 1.
For the complete graphKnof ordern≥2,(4)SpecVDKn=−n2+2n−2n−1n2−2n+2n−11,EVDKn=2n−1n2−2n+2.Proof.
LetG=Kn be a complete graph with vertices v1,v2,…,vn. Then, for every vertex vi,i=1,2,…,n, the vector of a degree corresponding to the vertex vi⟶=1,n−1. Thus, for any two vectors vi⟶andvj⟶,(5)vi⟶.vj⟶=n2−2n+2.
Hence,VDKn=n2−2n+2AKn, where AKn is the adjacency matrix of Kn. Therefore, Lemma 1 gives that(6)SpecVDKn=−n2+2n−2n−1n2−2n+2n−11,ELdKn=2n−1n2−2n+2.We now determine the VD-spectrum and VD-energy of any cycleCn.Theorem 2.
Letn≥4be an even integer. Then, for a cycleCn, we have(7)SpecVDCn=−2n−22n−12n−11.Further,EVDCn=2n−1EKn, where EKn is the energy of Kn.Proof.
By labeling the vertices of the cycleCn in the anticlockwise direction as v1,v2,…,vn, we observe that for any vertex vi⟶, we have(8)vi⟶=1,2,2,2,…,2,2︸n/2−1times,,1.
Then, clearly for any two verticesvi and vj,(9)vi⟶.vj⟶=11+22+22+⋯+22+11=2n−1.
Therefore,VDCn=2n−1AKn.
Hence, by Lemma1, we get(10)SpecVDCn=−2n−22n−12n−11,and it is easy to see that(11)EVDCn=2n−1EKn,where EKn is the energy of Kn.Theorem 3.
Letn≥3 be an odd integer. Then, for a cycle Cn, we have(12)SpecVDCn=−2n−12n−1n−1n−11.
FurtherEVDCn=2n−1EKn, where EKn is the energy of EKn.Proof.
By labeling the vertices of the cycleCn in the anticlockwise direction as v1,v2,…,vn, we observe that for any vertex vi⟶, we have(13)vi⟶=1,2,2,2,…,2,2︸n−1/2times.
Then, clearly for every two verticesvi and vj with i≠j,(14)vi⟶.vj⟶=11+22+22+⋯+22+22=2n−1.
Therefore,VDCn=2n−1AKn.
Hence, by Lemma1, we get,(15)SpecVDCn=−2n−12n−1n−1n−11.
Further,EVDCn=2n−1EKn.Theorem 4.
LetGbe a complete bipartite graphKn,m, where1≤n≤m. Then,(16)SpecVDKn,m=−α−γr1r2n−1m−111,where α=1+m2+n−12, β=1+nm+n−1m−1, γ=1+n2+m−12, and r1 and r2 are the zeros of the polynomial.(17)n−1α−xx−m−1γ+nmβ2.
Furthermore,(18)EVDKn,m=n−1α+m−1γ+n−1α+m−1γ2−4n−1αm−1γ−nmβ2.Proof.
LetV=v1,v2,…,vn and U=u1,u2,…,un be the bipartite sets of the graph. Then, vi is adjacent to uj for all i,0≤i≤n, and every j,0≤j≤m. Now, if 0≤i≤n, vi⟶=1,m,n−1; similarly, if 0≤j≤m, uj⟶=1,n,m−1. It follows that(19)vi⟶⋅vk⟶=1+m2+n−12,0≤i≠k≤n,vi⟶⋅uj⟶=1+nm+n−1m−1,0≤i≤n,0≤j≤m,ul⟶⋅uj⟶=1+n2+m−12,0≤l≠j≤m.
Putα=1+m2+n−12, β=1+nm+n−1m−1, and γ=1+n2+m−12. Therefore,(20)VDKn,m=ABBTC,where A=αAKn, B is an n×m matrix with all entries β, and C=γAKm. Theorem 1 gives(21)SpecA=−αn−1αn−11,and the corresponding basis of the eigen space E−α is(22)x1=−110...0,x2=−1010...0,…,xn−1=−10...01.
Thus,−α is an eigen value of VDKn,m, and the corresponding basis of the eigen space E−α≤ℝn+m is(23)x10...0,x20...0,…,xn−10...0.
Similarly,−γ is an eigen value of VDKn,m with multiplicity m−1. Consequently, the characteristic polynomial can be written as x+αn−1x+γm−1px where px is a polynomial of degree 2 and by a routine calculations, px=n−1α−xx−m−1γ+nmβ2. Hence,(24)SpecVDKn,m=−α−γr1r2n−1m−111,where r1 and r2 are the zeros of the polynomial.(25)n−1α−xx−m−1γ+nmβ2.
Furthermore,(26)EVDKn,m=n−1α+m−1γ+n−1α+m−1γ2−4n−1αm−1γ−nmβ2.
The following results are obtained from Theorem4.Corollary 1.
LetGbe a complete bipartite graph, wheren≥1. Then,(27)SpecVDKn,n=−n2−2n+2n−1n2−2n+22n−11,EDKn,n=3n−2n2−2n+2.Corollary 2.
LetG be any star graph K1,n. Then,(28)SpecVDK1,n=−n2−2n+3r1r2n−111,where r1 and r2 are the zeros of the polynomial: x2−n−1n2−2n+3−n1+n2. Furthermore,(29)EDK1,n=n−1n2−2n+3+n−12n2−2n+32+4n1+n2.


## 3. Vector Degree Spectrum and Energy of Regular and Strongly Regular Graphs

One of the most important families of regular graphs is strongly regular graphs (abbreviated SRG), which has so many beautiful properties. There are many SRGs which arise from combinatorial concepts such as orthogonal arrays, Latin squares, conference matrices, designs, and geometric graphs.A strongly regular graph (SRG) with parametersn,k,λ,μ is a graph on n vertices which is regular with valency k and has the following properties:(i)
Any two adjacent vertices have exactlyλ common neighbors(ii)
Any two nonadjacent vertices have exactlyμ common neighbors [3]Theorem 5 (see [5]).
LetG be a strongly regular graph with parameters n,k,λ,μ. Then, the eigenvalues of G satisfy the following properties:(1)
G has exactly three distinct eigenvalues which are k,θ, and τ where(30)θ=12λ−μ+λ−μ2+4k−μ,(31)τ=12λ−μ−λ−μ2+4k−μ.(2)
The multiplicity of the eigenvaluek is 1, and the multiplicities of θ and τ are f and g, respectively, where(32)f=n−1+n−1μ−λ−2kλ−μ2+4k−μ,g=n−1−n−1μ−λ−2kλ−μ2+4k−μ.(3)
Ifn−1μ−λ−2k≠0, then the eigenvalues θ and τ are integers. On the other hand, if n−1μ−λ−2k=0, then f=g and θ and τ need not be integers. The strongly regular graph is called a conference graph in this case.Theorem 6.
LetG be a strongly regular graph with parameters n,k,λ,μ. Then,(33)SpecVDG=−δn−1δn−11,and further EVDG=δEKn, where δ=1+k2+n−k−12 and EKn is the energy of Kn.Proof.
LetG be a strongly regular graph with the parameters n,k,λ,μ. For any vertex v clearly v⟶=1,k,n−k−1, then the degree product of any two-degree vectors is equal to 1+k2+n−k−12. Hence,(34)VDG=1+k2+n−k−12AKn.
If we putδ=1+k2+n−k−12, then(35)SpecVDG=−δn−1δn−11,and EVDG=δEKn
We can generalize Theorem6 as the follows.Theorem 7.
LetG=V,Ebe ak-regular graph of diameter two. Then,(36)SpecVDG=−δn−1δn−11,and EVDG=δEKn. Further, EVDG=δEKn, where δ=1+k2+n−k−12 and EKn is the energy of Kn.In the following, we calculate VD-matrix and calculate VD-eigenvalues for graphs representing the chemical composition of paracetamol and tramadol. Also, we note that the closeness of eigen values between paracetamol and tramadol might indicate pharmacological and chemical characteristics convergence.Scheme 1
The graph of Paracetamol.Example 1.
Paracetamol(37)V1=1,1,3,2,2,2,4,3,1,1,V2=1,1,3,2,2,2,4,3,1,1,V3=1,4,2,2,2,4,3,1,1,0,V4=1,1,3,2,2,2,4,3,1,1,V5=1,3,5,2,4,3,1,1,0,0,V6=1,1,2,5,2,4,3,1,1,0,V7=1,3,4,7,3,1,1,0,0,0,V8=1,1,2,4,7,3,1,1,0,0,V9=1,3,6,5,4,1,0,0,0,0,V10=1,3,4,5,4,3,0,0,0,0,V11=1,1,2,4,5,4,3,0,0,0,V12=1,3,4,4,3,2,3,0,0,0,V13=1,1,2,4,4,3,2,3,0,0,V14=1,3,5,3,1,2,2,3,0,0,V15=1,2,2,4,3,1,2,2,3,0,V16=1,1,1,2,4,3,1,2,2,3,V17=1,1,2,4,4,3,2,3,0,0,V18=1,3,4,4,3,2,3,0,0,0,V19=1,3,4,5,4,3,0,0,0,0,V20=1,1,2,4,5,4,3,0,0,0.
(38)eigC=1.011219.2−9.0−87.6−35.7−38.6−42.0−79.3−48.9−51.8−75.8−60.9−65.0−63.7−50.0−50.0−76.0−72.0−64.0−60.0.Example 2.
Tramadol(39)V1=1,1,1,2,2,2,3,3,2,2,V2=1,2,2,2,2,3,3,2,2,0,V3=1,3,3,2,3,3,2,2,0,0,V4=1,2,3,5,4,2,2,0,0,0,V5=1,2,3,2,1,3,3,2,2,0,V6=1,2,2,3,4,3,2,2,0,0,V7=1,2,3,4,4,3,2,0,0,0,V8=1,3,5,5,3,2,0,0,0,0,V9=1,4,5,4,4,1,0,0,0,0,V10=1,1,3,5,4,4,1,0,0,0,V11=1,3,5,5,2,2,1,0,0,0,V12=1,2,4,4,3,2,2,1,0,0,V13=1,3,1,2,4,3,2,2,1,0,V14=1,1,2,1,2,4,3,2,2,1,V15=1,1,2,1,2,4,3,2,2,1,V16=1,2,3,4,4,2,2,1,0,0,V17=1,2,2,2,3,4,2,2,1,0,V18=1,2,2,3,3,3,4,1,0,0,V19=1,2,4,4,3,4,1,0,0,0.
(40)eigA=−72.8695−68.7152−65.8056−61.3030−60.3018−57.6119−54.6774−54.2252−50.0643−47.6270−45.4837−42.8595−39.9573−34.9652−32.940339.4311840.9000.


## 4. Conclusions

One of the main tools for studying the algebraic structure and properties of a graph is a matrix representation of the graph. We have introduced a new matrix representation, called the vector degree matrix of graph G. For analogues to this new matrix, we have defined and calculated VD-eigenvalues, VD-eigenvectors, VD-spectrum, and VD-energy for various standard graphs. Furthermore, for graphs illustrating the chemical composition of paracetamol and tramadol, we have constructed and calculated the VD-matrix and VD-eigenvalues.Scheme 2
The graph of Tramadol.



---

*Source: 8307871-2022-04-04.xml*