# Integral Eigen-Pair Balanced Classes of Graphs with Their Ratio, Asymptote, Area, and Involution-Complementary Aspects

Authors: Paul August Winter; Carol Lynne Jessop
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

The association of integers, conjugate pairs, and robustness with the eigenvalues of graphs provides the motivation for the following definitions. A class of graphs, with the property that, for each graph (member) of the class, there exists a paira,b of nonzero, distinct eigenvalues, whosesumandproductare integral, is said to beeigen-bibalanced. If theratio(a+b)/(a·b) is a function f(n), of the order n of the graphs in this class, then we investigate itsasymptoticproperties. Attaching the average degree to the Riemann integral of this ratio allowed for the evaluation of eigen-balancedareasof classes of graphs. Complete graphs on n vertices are eigen-bibalanced with the eigen-balanced ratio (n-2)/(1-n)=f(n) which isasymptotic to the constant value of −1. Its eigen-balanced area is (n-1)(n-ln⁡⁡(n-1))—we show that this is themaximumarea for most known classes of eigen-bibalanced graphs. We also investigate the class of eigen-bibalanced graphs, whose class of complements gives rise to an eigen-balanced asymptote that is aninvolutionand the effect of the asymptotic ratio on theenergyof the graph theoretical representation of molecules.


---

## Body

## 1. Introduction: Integers, Conjugate Pairs, and Eigenvalues of a Graph

The graphs in this paper are simple and connected and all graph properties mentioned will be according to definitions in Harris et al. [1]. There has been much work done in the analysis of eigenvalues of matrices which are adjacency matrices of associated graphs. The following are some examples of these findings, with the references as specified.(i)
There has been interest in classes of graphs whosepairsof eigenvalues satisfy certain conditions. In Sarkar and Mukherjee [2], graphs are considered with reciprocalpairsof eigenvalues (λ, 1/λ) whoseproductis the integer 1.(ii)
Pairsof eigenvalues (1, −1), summing to 0, and whose product is −1, are considered in Dias [3].(iii)
Summing the eigenvalues of the adjacency matrix of a graph is connected to theenergyof physical structures; see Aimei et al. [4].(iv)
In the paper by van Dam [5], on regular graphs with 4 eigenvalues, he considers the eigenvalue pair of real conjugates (a±b)/2 and shows that if a matrix has an eigenvalue (a+b)/2, then it has an eigenvalue (a-b)/2 of the same multiplicity, and vice versa. Adding the pair of conjugates (a+b)/2 and (a-b)/2, we obtain the integer a. Their product is (a2-b)/4 which is integral, provided the numerator is a multiple of 4. The paper shows that there are graphs whose matrices have conjugate pairs of eigenvalues whose sum does not necessarily sum to thesameinteger a.The following references show other areas of research which, together with the results on eigenvalues, provide motivation for the new definitions which are contained in this paper.(i)
There has been interest in the importance of pairs of numbers, whose sum and product produce the same integral constant, and this exists outside the linear algebra of matrices; see, for example, Dias [3].(ii)
In Brouwer and Haemers [6], integral trees (where the eigenvalues of trees are integral) are investigated.(iii)
In the cryptography article, Hamada [7] considers the conjugate codepair consisting of linear codes [n,k′] and [n,k′′] satisfying the constant (integral) sum term k′+k′′=n+k, where n is the dimension of the vector space involved and k is the k-digit secret information sent.(iv)
In the paper by Kadin [8] he investigates the Cooperpairof opposite wave vectors k and -k whichbalance by summing to 0 and whose product is -k2.(v)
Hinch and Leal [9] consider the notion of an isolated particle in the absence of rotary Brownian motion, under the condition that the hydrodynamic and external fieldcouples exactlybalance one another.(vi)
Armstrong [10] investigates the importance of the quadratic part of a characteristic equation which has the form x2-τx+δ. This quadratic gives rise to the two eigenvalues a,b=(τ±τ2-4δ)/2. Thesumandproduct (τ,δ, resp.) are often referred to as the eigen-pair, but we will focus on thepair of eigenvalues(a,b) as the eigen-pair.Generally, there often exist two eigenvalues (associated with the adjacency matrix of a graph) whose sum or product is integral It is therefore possible to get thesame integer when adding or multiplying two distinct, nonzero eigenvalues. This integer is either a fixed constant or a function of an inherent property of the graph, for all graphs belonging to a certain class of graphs. For example, complete graphs Kn on n vertices have a pair of eigenvalues with sum of f(n)=n-2 and product of g(n)=1-n for each n≥2, and the complete bipartite graphs Kn/2,n/2 on n vertices have eigen-pair sum (of nonzero eigenvalues) of 0 and product of -n2/4.Definition 1 (functionf(p) of a member of a class of graphs).
We define afunction of a memberbelonging to a class of graphs as a real function f(p) of an inherent property p of the member in the class, such as the number of vertices or the clique number of a graph, and so forth.
In this paper, we combine the ideas of a pair of eigenvalues and their balanced integral sum and product with respect to a class of graphs, to introduce a definition which is a form ofintegral-eigenvalue balance associated with classes of graphs. We investigateclasses of graphson n vertices with pairs (a,b) of distinct nonzero eigenvalues such that a+b=s or ab=t, where s,t are thesame integer(resp.) for each graph in the classor the samefunction for each graph in the class.


## 2. Integral Sum Eigen-Pair Balanced Classes of Graphs

Definition 2 (sum*(s)eigen*-pair (integral) balanced).
The classI of connected graphs on n elements is said to be sum*(s)eigen*-pair (integral) balancedif there exists a pair (a,b) ofdistinct nonzero eigenvalues of the matrices associated with each class of the structures such that a+b=s is thesame integer as a fixed constant for each member in the class or s is thesame integer as afunction of each member in the class. The sum balance isexactif s is the same integer as a fixed constant for each member in the class, or otherwise it isnonexact.The following are some examples of such classes of graphs, noting that sum(a,b)=a+b in the examples below.


### 2.1. Complete Graphs

The distinct eigenvalues of the complete graphKn are -1 and (n-1) (as per Brouwer and Haemers [6]), with the sum of the eigenvalues being (n-2). Therefore the class of complete graphs Kn is nonexact sum(*n-2)*eigen-pair balanced, for n≥3.


### 2.2. Complete Bipartite Graphs

The class of complete bipartite graphsKp,p on n=2p vertices has as its associated eigenvalues p, -p, and 0 (as per Brouwer and Haemers [6]), so it is exact sum(*0)*eigen-pair balanced.The class of complete bipartite graphsKp,k on p+k vertices, p≠k, has eigenvalues -pk, pk, 0 (as per Brouwer and Haemers [6]), so it is exact sum(*0)*eigen-pair balanced (this includes the star graphs with radius 1).


### 2.3. Cycle Graphs

From Brouwer and Haemers [6], the cycle Cn on n vertices and n edges has eigenvalues
(1)2cos⁡⁡(2πjn),0≤j≤n-1.The 3-cycle (complete graph on 3 vertices) has distinct eigenvalues −1 and 2.The 4-cycle has distinct eigenvalues 2, 0, and −2.The 5-cycle has distinct eigenvalues2, (-1+5)/2, and  (-1-5)/2.The 6-cycle has distinct eigenvalues2, 1, -1, and -2.The 7-cycle has distinct eigenvalues 2, 1.247, −0.445, and 1.802.For the 3-, 5-, and 6-cycle, there exist two distinct nonzero eigenvalues whose sum is 1. However, for the 7-cycle, there are no two distinct eigenvalues whose sum is 1. Therefore the class of cycles is not sum(1)eigen-pair balanced as it does not satisfy Definition2.However, even cycles are sum(*0)*eigen-pair balanced, since if n=2k,
(2)2cos⁡⁡(2πjn)=2cos⁡⁡(πjk),0≤j≤2k-1.
Then j=0 and j=k yield eigenvalues of 2 and −2, respectively.


### 2.4. Path Graphs

From Brouwer and Haemers [6], the path Pn on n≥2 vertices and (n-1) edges has eigenvalues
(3)2cos⁡⁡(πjn+1),1≤j≤n.
Note that
(4)cos⁡⁡(nπn+1)=cos⁡⁡(π-πn+1)=cos⁡⁡πcos⁡⁡(πn+1)+sin⁡πsin⁡(πn+1)=-cos⁡⁡(πn+1)
so that the nonzero pair, with j=n and j=1,
(5)(a,b)=(2cos⁡(nπn+1),2cos⁡(πn+1))
has the sum
(6)sum(a,b)=2cos⁡⁡(nπn+1)+2cos⁡⁡(πn+1)=-2cos⁡⁡(πn+1)+2cos⁡⁡(πn+1)=0,
so the class of path graphs is exact sum(*0)*eigen-pair balanced.


### 2.5. Graph Which Is the Join of Two Graphs Whose Adjacency Matrices Are Both Circulant Matrices

From Lee and Yeh [11], the conjugate eigenvalues of the join of two circulant matrices of graphs are
(7)(a,b)=n[-(dA-dB)±(dA-dB)2+4nm2n]+dA.
So the sum of the eigenvalues is
(8)Sum(a,b)=n[-(dA-dB)+(dA-dB)2+4nm2n]+dA+n[-(dA-dB)-(dA-dB)2+4nm2n]+dA=n[-2(dA-dB)2n]+2dA=-(dA-dB)+2dA=dA+dB,
so the class of graphs, which are the join of two graphs whose adjacency matrices are circulant, is sum*(dA+dB)*eigen-pair balanced.


### 2.6. Wheel Graphs

As per Lee and Yeh [11], the wheel graph Wn on n vertices, with (n-1) spokes (join of cycle with a single vertex), has conjugate eigenvalues
(9)(a,b)=2±4+4(n-1)2.
The sum of the conjugate eigenvalues is therefore
(10)sum(a,b)=2+4+4(n-1)2+2-4+4(n-1)2=2
so the class of cycle wheel graphs is exact sum(*2)*eigen-pair balanced.


### 2.7. Strongly Regular Graphs

If a connected regular graphG of degree k with parameters (k,λ,μ) is strongly regular (i.e., srg(v,k,λ,μ)), then A(G) has at least 3 different eigenvalues. The eigenvalues are
(11)k,(λ-μ)+(λ-μ)2-4(k-μ)2,(λ-μ)-(λ-μ)2-4(k-μ)2.
See Spielman [12].The complement of ansrg(v,k,λ,μ) is also strongly regular. It is an srg(v,v-k-1,v-2-2k+μ, v-2k+λ).Note that if we ignore the largest eigenvaluek of strongly regular graphs, adding the remaining two eigenvalues yields the integer (λ-μ) so the class of strongly regular graphs with parameters (v,k,λ,μ) is nonexact sum(*λ-μ)*eigen-pair balanced; see Godsil and Royle [13] for more information on strongly regular graphs.


### 2.8. Divisible Design Graphs

Definition 3 (divisible design graph).
Ak-regular graph is adivisible design graph if the vertex set can be partitioned into m classes of size n, such that two distinct vertices from the same class have exactly λ1 common neighbours, and two vertices from different classes have exactly λ2 common neighbours.
The eigenvalues of divisible design graphs are provided in Haemers [14]; there are 5 distinct eigenvalues. Two of the eigenvalues are
(12)(a,b)=±k-λ1,
so the sum of the eigen-pair is
(13)sum(a,b)=(k-λ1)+(-k-λ1)=0.
Therefore, the class of divisible design graphs is exact sum(*0)*eigen-pair balanced.


### 2.9. Hypercube Graphs

As per Brouwer and Haemears [6], the p-regular hypercube on 2p vertices and p2p-1edges has eigenvalues
(14)(p-2k)(pk);k=0,1,2,…,p.
Using the eigenvalues p and p-2k, for p≠2k and k≠0, this class of graphs will be sum(*2p-2k)*eigen-pair balanced.


### 2.10. Eigenvalue Pair of Real Conjugates

The following results are due to van Dam and Haemers [15].ByZ[x] and Q[x] we denote the rings of polynomials over the integer and rational numbers, respectively.Lemma 4.
If a monic polynomialp(x)∈Z[x] has a monic divisor q(x)∈Q[x], then also q(x)∈Z[x].Lemma 5.
If(a+b), with a,b∈Q, is an irrational root of a polynomial p(x)∈Q[x], then so is (a-b), with the same multiplicity.The characteristic polynomialPA(G)(λ) of the adjacency matrix of a graph is monic and has integral coefficients. Using Lemmas 4 and 5 we now obtain the following results.Corollary 6.
Every rational eigenvalue of a graph is integral.Corollary 7.
If(a+b)/2 is an irrational eigenvalue of a graph, for some a,b∈Q, then so is (a-b)/2, with the same multiplicity, and a,b∈Z.Adding the pair of real conjugates(a+b)/2, (a-b)/2 we obtain the integer a.Therefore, if the real conjugate pairs are eigenvalues associated with the adjacency matrix of all graphs belonging to a class of graphs, then the class of graphs issum*(a)*eigen-pair balanced.


## 2.1. Complete Graphs

The distinct eigenvalues of the complete graphKn are -1 and (n-1) (as per Brouwer and Haemers [6]), with the sum of the eigenvalues being (n-2). Therefore the class of complete graphs Kn is nonexact sum(*n-2)*eigen-pair balanced, for n≥3.


## 2.2. Complete Bipartite Graphs

The class of complete bipartite graphsKp,p on n=2p vertices has as its associated eigenvalues p, -p, and 0 (as per Brouwer and Haemers [6]), so it is exact sum(*0)*eigen-pair balanced.The class of complete bipartite graphsKp,k on p+k vertices, p≠k, has eigenvalues -pk, pk, 0 (as per Brouwer and Haemers [6]), so it is exact sum(*0)*eigen-pair balanced (this includes the star graphs with radius 1).


## 2.3. Cycle Graphs

From Brouwer and Haemers [6], the cycle Cn on n vertices and n edges has eigenvalues
(1)2cos⁡⁡(2πjn),0≤j≤n-1.The 3-cycle (complete graph on 3 vertices) has distinct eigenvalues −1 and 2.The 4-cycle has distinct eigenvalues 2, 0, and −2.The 5-cycle has distinct eigenvalues2, (-1+5)/2, and  (-1-5)/2.The 6-cycle has distinct eigenvalues2, 1, -1, and -2.The 7-cycle has distinct eigenvalues 2, 1.247, −0.445, and 1.802.For the 3-, 5-, and 6-cycle, there exist two distinct nonzero eigenvalues whose sum is 1. However, for the 7-cycle, there are no two distinct eigenvalues whose sum is 1. Therefore the class of cycles is not sum(1)eigen-pair balanced as it does not satisfy Definition2.However, even cycles are sum(*0)*eigen-pair balanced, since if n=2k,
(2)2cos⁡⁡(2πjn)=2cos⁡⁡(πjk),0≤j≤2k-1.
Then j=0 and j=k yield eigenvalues of 2 and −2, respectively.


## 2.4. Path Graphs

From Brouwer and Haemers [6], the path Pn on n≥2 vertices and (n-1) edges has eigenvalues
(3)2cos⁡⁡(πjn+1),1≤j≤n.
Note that
(4)cos⁡⁡(nπn+1)=cos⁡⁡(π-πn+1)=cos⁡⁡πcos⁡⁡(πn+1)+sin⁡πsin⁡(πn+1)=-cos⁡⁡(πn+1)
so that the nonzero pair, with j=n and j=1,
(5)(a,b)=(2cos⁡(nπn+1),2cos⁡(πn+1))
has the sum
(6)sum(a,b)=2cos⁡⁡(nπn+1)+2cos⁡⁡(πn+1)=-2cos⁡⁡(πn+1)+2cos⁡⁡(πn+1)=0,
so the class of path graphs is exact sum(*0)*eigen-pair balanced.


## 2.5. Graph Which Is the Join of Two Graphs Whose Adjacency Matrices Are Both Circulant Matrices

From Lee and Yeh [11], the conjugate eigenvalues of the join of two circulant matrices of graphs are
(7)(a,b)=n[-(dA-dB)±(dA-dB)2+4nm2n]+dA.
So the sum of the eigenvalues is
(8)Sum(a,b)=n[-(dA-dB)+(dA-dB)2+4nm2n]+dA+n[-(dA-dB)-(dA-dB)2+4nm2n]+dA=n[-2(dA-dB)2n]+2dA=-(dA-dB)+2dA=dA+dB,
so the class of graphs, which are the join of two graphs whose adjacency matrices are circulant, is sum*(dA+dB)*eigen-pair balanced.


## 2.6. Wheel Graphs

As per Lee and Yeh [11], the wheel graph Wn on n vertices, with (n-1) spokes (join of cycle with a single vertex), has conjugate eigenvalues
(9)(a,b)=2±4+4(n-1)2.
The sum of the conjugate eigenvalues is therefore
(10)sum(a,b)=2+4+4(n-1)2+2-4+4(n-1)2=2
so the class of cycle wheel graphs is exact sum(*2)*eigen-pair balanced.


## 2.7. Strongly Regular Graphs

If a connected regular graphG of degree k with parameters (k,λ,μ) is strongly regular (i.e., srg(v,k,λ,μ)), then A(G) has at least 3 different eigenvalues. The eigenvalues are
(11)k,(λ-μ)+(λ-μ)2-4(k-μ)2,(λ-μ)-(λ-μ)2-4(k-μ)2.
See Spielman [12].The complement of ansrg(v,k,λ,μ) is also strongly regular. It is an srg(v,v-k-1,v-2-2k+μ, v-2k+λ).Note that if we ignore the largest eigenvaluek of strongly regular graphs, adding the remaining two eigenvalues yields the integer (λ-μ) so the class of strongly regular graphs with parameters (v,k,λ,μ) is nonexact sum(*λ-μ)*eigen-pair balanced; see Godsil and Royle [13] for more information on strongly regular graphs.


## 2.8. Divisible Design Graphs

Definition 3 (divisible design graph).
Ak-regular graph is adivisible design graph if the vertex set can be partitioned into m classes of size n, such that two distinct vertices from the same class have exactly λ1 common neighbours, and two vertices from different classes have exactly λ2 common neighbours.
The eigenvalues of divisible design graphs are provided in Haemers [14]; there are 5 distinct eigenvalues. Two of the eigenvalues are
(12)(a,b)=±k-λ1,
so the sum of the eigen-pair is
(13)sum(a,b)=(k-λ1)+(-k-λ1)=0.
Therefore, the class of divisible design graphs is exact sum(*0)*eigen-pair balanced.


## 2.9. Hypercube Graphs

As per Brouwer and Haemears [6], the p-regular hypercube on 2p vertices and p2p-1edges has eigenvalues
(14)(p-2k)(pk);k=0,1,2,…,p.
Using the eigenvalues p and p-2k, for p≠2k and k≠0, this class of graphs will be sum(*2p-2k)*eigen-pair balanced.


## 2.10. Eigenvalue Pair of Real Conjugates

The following results are due to van Dam and Haemers [15].ByZ[x] and Q[x] we denote the rings of polynomials over the integer and rational numbers, respectively.Lemma 4.
If a monic polynomialp(x)∈Z[x] has a monic divisor q(x)∈Q[x], then also q(x)∈Z[x].Lemma 5.
If(a+b), with a,b∈Q, is an irrational root of a polynomial p(x)∈Q[x], then so is (a-b), with the same multiplicity.The characteristic polynomialPA(G)(λ) of the adjacency matrix of a graph is monic and has integral coefficients. Using Lemmas 4 and 5 we now obtain the following results.Corollary 6.
Every rational eigenvalue of a graph is integral.Corollary 7.
If(a+b)/2 is an irrational eigenvalue of a graph, for some a,b∈Q, then so is (a-b)/2, with the same multiplicity, and a,b∈Z.Adding the pair of real conjugates(a+b)/2, (a-b)/2 we obtain the integer a.Therefore, if the real conjugate pairs are eigenvalues associated with the adjacency matrix of all graphs belonging to a class of graphs, then the class of graphs issum*(a)*eigen-pair balanced.


## 3. Integral Product Eigen-Pair Balanced Classes of Graphs

Definition 8 (product*(t)eigen*-pair (integral) balanced).
A classI of connected graphs on n elements is said to be product*(t)eigen*-pair (integral) balancedif there exists a pair of (a,b) ofdistinct nonzero eigenvalues (counting eigenvalues only once, i.e., ignoring multiplicities) of the matrices associated with each class of the structures such that (ab=t) is the same integer as a fixed constant foreach member in the class or t is the same integer as a function of each member in the class. The product balance isexactif t is the same integer as a fixed constant for each member in the class; otherwise it isnonexact.The following are some examples of such classes of product balanced classes of graphs, discussed above, noting that the product of the pair(a,b)=ab in the examples below.


### 3.1. Complete Graphs

The class of complete graphsKn is nonexact product(*1-n)*eigen-pair balanced for n≥3, since the eigenvalues of the associated adjacency matrices, are, as per Section 2.1, -1 and (n-1).


### 3.2. Complete Bipartite Graphs

The class of complete bipartite graphsKp,p on n=2p vertices has as its associated eigenvalues p, -p, and 0 (as per Section 2.2), so that they are nonexact product(*-p2)*eigen-pair balanced.The class of complete bipartite graphsKp,k on (p+k) vertices, p≠k, has distinct eigenvalues -pk, pk, and 0 (as per Section 2.2), so that it is nonexact product(*-pk)*eigen-pair balanced (this includes the star graphs with radius 1).


### 3.3. Cycle Graphs

Cycles graphs onn vertices have associated eigenvalues
(15)2cos⁡⁡(2πjn),0≤j≤n-1.C
3 on 3 vertices has eigenvalues 2 and −1 so that the eigen-pair product is −2.C
4 on 4 vertices has eigenvalues 2, 0, and −2 so that the eigen-pair product is −4.C
5 on 5 vertices has eigenvalues 2, (-1+5)/2, and (-1-5)/2 with conjugate eigen-pair product −1.C
6 on 6 vertices has eigenvalues 2, 1, −1, and −2. Possible eigen-pair products are −1, −2, 2, and −4.The 7-cycle has eigenvalues 2, 1.247, −0.445, and −1.802. No product of two eigenvalues yields an integer!Therefore, the class of cycles is not eigen(*k)*product balanced for any integer k.However, the class of even cycles is product(*-4)*eigen-pair balanced, since if n=2k then
(16)2cos⁡⁡(2πjn)=2cos⁡⁡(2πj2k);0≤j≤2k-1,
so that for j=0 we get eigenvalue 2 and for j=k we get eigenvalue −2, with eigen-pair product −4.


### 3.4. Path Graphs

Paths graphs onn vertices have eigenvalues:
(17)2cos⁡(πjn+1),1≤j≤n.
From Section 2.4,
(18)2cos⁡(πnn+1)=-2cos⁡⁡(πn+1)
so that with j=1 and (j=n) the product is
(19)-2(1+cos⁡⁡(2πn+1))
which is a function of n but is not integral in general.


### 3.5. Graph Which Is the Join of Two Graphs Whose Adjacency Matrices Are Both Circulant Matrices

The conjugate eigenvalues are(20)(a,b)=n[-(dA-dB)±(dA-dB)2+4nm2n]+dA.
So the product of the eigenvalues is
(21)product(a,b)={n[-(dA-dB)+(dA-dB)2+4nm2n]+dA}×{n[-(dA-dB)-(dA-dB)2+4nm2n]+dA}=n2[(dA-dB)2-[(dA-dB)2+4nm]4n2]-2dA(dA-dB)+dA2=[-(4nm)4]-2dA(dA-dB)+dA2=-mn-2dA(dA-dB)+dA2,
so the class of graphs whose adjacency matrix is the join of two graphs whose adjacency matrices are circulant matrices is product(*-mn-2dA(dA-dB)+dA2)*eigen-pair balanced.


### 3.6. Wheel Graphs

The wheel graphWn on n vertices, with (n-1) spokes, has conjugate eigenvalues
(22)(a,b)=2±4+4(n-1)2.
The product of the conjugate eigenvalues is
(23)product(a,b)=[2+4+4(n-1)2][2-4+4(n-1)2]=4-[4+4(n-1)]4=-(n-1),
so the class of cycle wheel graphs is nonexact product(*1-n)*eigen-pair balanced.


### 3.7. Strongly Regular Graphs

The conjugate eigen-pair of strongly regular graphs is(24)(a,b)=(λ-μ)±(λ-μ)2-4(k-μ)2.
If we multiply the two conjugate pairs of strongly regular graphs we obtain the integer (μ-k), so that the class of strongly regular graphs is nonexact product(*μ-k)*eigen-pair balanced.


### 3.8. Divisible Design Graphs

Two of the eigenvalues of a divisible design graph are(25)(a,b)=±k-λ1.
This class of graphs has eigen-pair product
(26)product(a,b)=(k-λ1)(-k-λ1)=-(k-λ1)=λ1-k.
Therefore, the class of divisible design graphs is nonexact product(*λ1-k)*balanced.


### 3.9. Bipartite Graphs with Four Distinct Eigenvalues

The eigenvalues of a bipartite graph with four distinct eigenvalues are(27)(a,b)=±k-λ,(c,d)=±k.
Then product (a,b)=-(k-λ) and product (c,d)=-k2.Therefore, incidence graphs of symmetric 2-(v,k,l) designs are product*t*eigen-pair balanced for t=(λ-k) and t=-k2 of the nonexact kind.


### 3.10. Hypercube Graphs

The class ofp-regular hypercubes on 2p vertices and p2p-1edges has eigenvalues:
(28)(p-2k)(pk),0≤k≤p.
Using the eigenvalues p and p-2k, for p≠2k, k≠0, this class of graphs is product(*p2-2pk)*eigen-pair balanced.


### 3.11. Eigenvalue Pair of Real Conjugates

The product of the real conjugate pair of eigenvalues(a+b)/2 and (a-b)/2 is (a2-b)/4. This is integral, provided the numerator is a multiple of 4.Therefore, if the real conjugate pairs are eigenvalues associated with the adjacency matrix of all graphs belonging to a class of graphs, then the class of graphs is product(*(a2-b)/4)*eigen-pair balanced.


## 3.1. Complete Graphs

The class of complete graphsKn is nonexact product(*1-n)*eigen-pair balanced for n≥3, since the eigenvalues of the associated adjacency matrices, are, as per Section 2.1, -1 and (n-1).


## 3.2. Complete Bipartite Graphs

The class of complete bipartite graphsKp,p on n=2p vertices has as its associated eigenvalues p, -p, and 0 (as per Section 2.2), so that they are nonexact product(*-p2)*eigen-pair balanced.The class of complete bipartite graphsKp,k on (p+k) vertices, p≠k, has distinct eigenvalues -pk, pk, and 0 (as per Section 2.2), so that it is nonexact product(*-pk)*eigen-pair balanced (this includes the star graphs with radius 1).


## 3.3. Cycle Graphs

Cycles graphs onn vertices have associated eigenvalues
(15)2cos⁡⁡(2πjn),0≤j≤n-1.C
3 on 3 vertices has eigenvalues 2 and −1 so that the eigen-pair product is −2.C
4 on 4 vertices has eigenvalues 2, 0, and −2 so that the eigen-pair product is −4.C
5 on 5 vertices has eigenvalues 2, (-1+5)/2, and (-1-5)/2 with conjugate eigen-pair product −1.C
6 on 6 vertices has eigenvalues 2, 1, −1, and −2. Possible eigen-pair products are −1, −2, 2, and −4.The 7-cycle has eigenvalues 2, 1.247, −0.445, and −1.802. No product of two eigenvalues yields an integer!Therefore, the class of cycles is not eigen(*k)*product balanced for any integer k.However, the class of even cycles is product(*-4)*eigen-pair balanced, since if n=2k then
(16)2cos⁡⁡(2πjn)=2cos⁡⁡(2πj2k);0≤j≤2k-1,
so that for j=0 we get eigenvalue 2 and for j=k we get eigenvalue −2, with eigen-pair product −4.


## 3.4. Path Graphs

Paths graphs onn vertices have eigenvalues:
(17)2cos⁡(πjn+1),1≤j≤n.
From Section 2.4,
(18)2cos⁡(πnn+1)=-2cos⁡⁡(πn+1)
so that with j=1 and (j=n) the product is
(19)-2(1+cos⁡⁡(2πn+1))
which is a function of n but is not integral in general.


## 3.5. Graph Which Is the Join of Two Graphs Whose Adjacency Matrices Are Both Circulant Matrices

The conjugate eigenvalues are(20)(a,b)=n[-(dA-dB)±(dA-dB)2+4nm2n]+dA.
So the product of the eigenvalues is
(21)product(a,b)={n[-(dA-dB)+(dA-dB)2+4nm2n]+dA}×{n[-(dA-dB)-(dA-dB)2+4nm2n]+dA}=n2[(dA-dB)2-[(dA-dB)2+4nm]4n2]-2dA(dA-dB)+dA2=[-(4nm)4]-2dA(dA-dB)+dA2=-mn-2dA(dA-dB)+dA2,
so the class of graphs whose adjacency matrix is the join of two graphs whose adjacency matrices are circulant matrices is product(*-mn-2dA(dA-dB)+dA2)*eigen-pair balanced.


## 3.6. Wheel Graphs

The wheel graphWn on n vertices, with (n-1) spokes, has conjugate eigenvalues
(22)(a,b)=2±4+4(n-1)2.
The product of the conjugate eigenvalues is
(23)product(a,b)=[2+4+4(n-1)2][2-4+4(n-1)2]=4-[4+4(n-1)]4=-(n-1),
so the class of cycle wheel graphs is nonexact product(*1-n)*eigen-pair balanced.


## 3.7. Strongly Regular Graphs

The conjugate eigen-pair of strongly regular graphs is(24)(a,b)=(λ-μ)±(λ-μ)2-4(k-μ)2.
If we multiply the two conjugate pairs of strongly regular graphs we obtain the integer (μ-k), so that the class of strongly regular graphs is nonexact product(*μ-k)*eigen-pair balanced.


## 3.8. Divisible Design Graphs

Two of the eigenvalues of a divisible design graph are(25)(a,b)=±k-λ1.
This class of graphs has eigen-pair product
(26)product(a,b)=(k-λ1)(-k-λ1)=-(k-λ1)=λ1-k.
Therefore, the class of divisible design graphs is nonexact product(*λ1-k)*balanced.


## 3.9. Bipartite Graphs with Four Distinct Eigenvalues

The eigenvalues of a bipartite graph with four distinct eigenvalues are(27)(a,b)=±k-λ,(c,d)=±k.
Then product (a,b)=-(k-λ) and product (c,d)=-k2.Therefore, incidence graphs of symmetric 2-(v,k,l) designs are product*t*eigen-pair balanced for t=(λ-k) and t=-k2 of the nonexact kind.


## 3.10. Hypercube Graphs

The class ofp-regular hypercubes on 2p vertices and p2p-1edges has eigenvalues:
(28)(p-2k)(pk),0≤k≤p.
Using the eigenvalues p and p-2k, for p≠2k, k≠0, this class of graphs is product(*p2-2pk)*eigen-pair balanced.


## 3.11. Eigenvalue Pair of Real Conjugates

The product of the real conjugate pair of eigenvalues(a+b)/2 and (a-b)/2 is (a2-b)/4. This is integral, provided the numerator is a multiple of 4.Therefore, if the real conjugate pairs are eigenvalues associated with the adjacency matrix of all graphs belonging to a class of graphs, then the class of graphs is product(*(a2-b)/4)*eigen-pair balanced.


## 4. Eigen-Bibalanced Classes of Graphs

Definition 9 (eigen-bibalanced classes of graphs).
Classes of connected graphs, which are both sum and product eigen-pair balanced, are said to beeigen-bibalancedwith respect to the eigen-pair (a,b). If this pair is unique to the class, then it isuniquely eigen-bibalanced. For example, the class of complete graphs is uniquely eigen-bibalanced with respect to the eigen-pair (n-1,-1).The largest eigenvalue occurs in the eigen-pair associated with some classes of graphs discussed above. We observe the following.(i)
The only regular eigen-pair balanced graphs on 2 and 3 vertices areK2 and K3.(ii)
The 4-cycle is the same as the complete bipartite graphK2,2, which is sum and product eigen-pair balanced.(iii)
The only other regular graph on 4 vertices isK4.(iv)
The 5-cycle has eigenvalues(2)1, ((-1+5)/2)2, and ((-1-5)/2)2 which are not sum or product eigen-pair balanced when the largest eigenvalue is included in the eigen-pair.(v)
The only other regular graph on 5 vertices isK5.Thus we have the following theorem.Theorem 10.
The only regular graphs onn vertices, where 2≤n≤5, belonging to eigen-pair balanced classes of graphs, where the eigen-pair contains the largest eigenvalue, are K2, K3, K4, K5, and K2,2.


## 5. Eigen-Bibalanced Classes of Graphs: Criticality, Ratios, Asymptotes, and Area

If a class of connected graphsI arebothsum and product eigen-pair balanced with respect to the eigen-pair (a,b), they have been defined above aseigen-bibalanced with respect to (a,b). The class of complete graphs G is eigen-bibalanced with the property that the removal of any vertex v from G results in a complete graph, which belongs to the same class of complete graphs, which is eigen-bibalanced. The same holds for complete bipartite graphs except for star graphs. Such graphs are said to bestableeigen-bibalanced.Definition 11 (critically eigen-bibalanced classes of graphs).
IfG belongs to a class I of eigen-bibalanced graphs, and there exists a vertex v of G, such that G-v belongs to a class I′ of graphs which isnoteigen-bibalanced, we say that I iscriticallyeigen-bibalanced with respect to v.
Wheels onp spokes are eigen-bibalanced and the removal of the central vertex results in p-cycles, which are not eigen-bibalanced. Therefore, the class of wheel graphs is critically eigen-bibalanced with respect to its central vertex. This suggests that the central vertex is essential to the eigen-bibalanced characteristic of wheels.
The reciprocals of eigenvalues are connected to the idea ofrobustness ortightnessof graphs, Brouwer and Haemers [7]. Since a and b are nonzero, the sum of their reciprocals is defined. Therefore we have the following definition.Definition 12 (eigen-bibalanced ratio of classes of graphs).
The importance of ratios in graphs is well researched (see Winter and Adewusi [16]). Theeigen-bibalanced ratioof the class of graphs (with respect to the eigen-pairs (a,b)) is
(29)r(aIb)=1b+1a=a+bab.
As a and b are nonzero, the product ab is never zero, and so this ratio will always be defined.Definition 13 (eigen-bibalanced ratio asymptote of classes of graphs).
If this ratio is a functionf(n) of the order n of the graph and has a horizontal asymptote (see Winter and Adewusi [16]), we call this asymptote theeigen-bibalanced ratio asymptote with respect to the eigen-pair (a,b) and is denoted by
(30)r(aIb)∞orasymp(r(aIb)).
This asymptote can be seen as describing the behavior of the ratio as the order of the graph becomes increasingly large.
The “area” termn2 can be found in the following relation involving spanning trees. Let D be the matrix composed of the degrees of G in the main diagonal form D′ by adding 1 to each entry of D. We then form theshadow number of a graph defined by shad(G)=det⁡(D′-A), where A is the adjacency matrix of G. We then have the combinatorial result
(31)n2=shad(G)t(G)=det⁡(D′-A)t(G),
where t(G) is the number of spanning trees of a connected graph G.
Also, the number of spanning trees of a connected graphG is associated with the Laplacian eigenvalues, θn≥θn-1≥⋯>θ1=0, of the graph by the following:
(32)∏j=2nθj=nt(G).
This excludes the first Laplacian eigenvalue. Thus, as in the case of the complete graph, the eigenvalue n-1 of the adjacency matrix associated with G will not be taken into account when considering spanning trees.
Eigenvalues have been associated with theexpansion of graphs (see Hamada [7]), which motivates the idea ofareasassociated with a class of graphs.
If the eigen-bibalanced ratio of a class of graphs is a function ofn, then we are able to integrate it with respect to n, which leads to the following definition.Definition 14 (eigen-bibalanced ratio area of classes of graphs).
We define theeigen-bibalanced ratio area of the class of graphs with respect to the eigen-pair (a,b) as (see Winter and Adewusi [16])
(33)Ar(I)a,b={2mn|∫a+babdn|,a+baba+babifa+b≠0,a+bab2mn|∫abdn|=2mn|2b|,ifa+b=0,
where m is the number of edges and n is the number of vertices, and Ar(I)a,b=0 when n=0, 1, or 2.
Now we define length denoted byB, as
B
=
2
m
/
n, that is, the average degree of the vertices in G, and defineheight,denoted by H, as
(34)H={|∫a+babdn|,a+baba+babifa+b≠0,|∫abdn|=2mn|2b|,ifa+b=0,
so Ar(I)a,b=B·H.
If there is more than one pair giving rise to such area, then the area of the class ismax⁡⁡Ar(I)ai,bi for all pairs (ai,bi). If there is only one eigen-pair associated with the class of graphs that gives rise to the area, then the area isunique.
The height involves binding the sum of the reciprocals of the eigen-pair by its integration and the multiplication of this height by the average degree. This involves one of the most basic, yet important, combinatorial aspects of the graph and results in the termn2 appearing in the eigen-bibalanced ratio area of some classes of graphs.


## 6. Examples of Eigen-Bibalanced Classes of Graphs

When we refer to a graphG having eigen-pair balanced properties such as sum, product, bibalanced, ratio, and asymptote, we imply that G belongs to a class of graphs having such eigen-pair properties. We will now look at various examples of eigen-bibalanced classes of graphs.


### 6.1. Complete Graphs

The complete graph onn vertices has the unique eigen-bibalanced ratio of
(35)r((n-1)Kn(-1))=(n-1)+(-1)(n-1)(-1)=n-21-n.
This depends on the order of the graph and has the unique eigen-bibalanced ratio asymptote
(36)r((n-1)Kn(-1))∞=-1
and eigen-bibalanced ratio area
(37)Ar(Kn)-1,n-1=2mn|∫n-21-ndn|=2(n(n-1)/2)n|∫[2n-1-nn-1]dn|=(n-1)|∫[2n-1-nn-1]dn|=(n-1)B,
where
(38)B=|∫2n-1-n-1n-1-1n-1|dn=n-ln⁡|n-1|+c.
When n=0 we have A=0 so c=0 so that its area is
(39)Ar(Kn)-1,n-1=(n-1)(n-ln⁡(n-1))=(n-1)H.
Note that the length of the longest path for the complete graph is n-1, so that H in the above expression can be regarded as theheight of the graph. Also, the term ln⁡⁡(n-1) occurs as part of the upper bound of thediameterof a graph involving the second largest eigenvalue; see Brouwer and Haemers [6].Is this area the maximum for all classes of eigen-bibalanced graphs?


### 6.2. Complete Bipartite Graphs

The complete bipartite graphKs,t on s+t vertices has the eigen-bibalanced ratio of
(40)r(stKs,t(-st))=st-st-st=0
which is independent of the size of the graph.Its area is(41)Ar(Ks,t)-st,st=2st(s+t)|2st|=4(st)3/2s+t.
This attains its maximum when s=t=n/2, and then the graph (thecomplete split bipartitegraph on n vertices) is s-regular and the area is
(42)Ar(Kn/2,n/2)-n/2,n/2=n2|∫-n/2n/2dn|=n22.


### 6.3. Wheel Graphs

Wheels onn vertices, containing (n-1) spokes and 2(n-1) edges, have eigen-bibalanced ratio
(43)r(2+4+4(n-1)2Wn2-4+4(n-1)2)=-2(n-1).
This depends on the size of the graph, so they have an eigen-bibalanced ratio asymptote of 0 and eigen-bibalanced ratio area of
(44)Ar(Wn)(2+4+4(n-1))/2,(2-4+4(n-1))/2=2mn|∫a+babdn|=2mn|∫21-ndn|=4(n-1)n(ln⁡|n-1|+c)=4(n-1)n(ln⁡|n-1|+c).
Now Ar(Wn)(2+4+4(n-1))/2,(2-4+4(n-1))/2=0 when n=2 so that c=0.So(45)Ar(Wn)(2+4+4(n-1))/2,(2-4+4(n-1))/2=4(n-1)n(ln⁡|n-1|).


### 6.4. Star Graphs

As per Brouwer and Haemers [6], star graphs with m rays of length 2 have eigenvalues 0, -1, 1, and ±m+1.Using the pair(a,b)=(-1,1) we obtain the ratio
(46)r(-1S1,mP31)=0-1=0
and using the pair (a,b)=(m+1,-m+1) we get
(47)r(m+1S1,mP3-m+1)=0-(m+1)=0.
Using the class of graphs, where (m+1)=t2 and eigen-pair (a,b)=(m+1,1), we have the ratio
(48)r(m+1S1,mP31)=m+1+1m+1=t+1t.
Therefore the class of star graphs with m rays of length 2 does not have a unique eigen-bibalanced ratio.The area with respect to the pair(a,b)=(-1,1) is
(49)Ar(S1,mP3)-1,1=2mn|2b|=2.2m2m+1|2|=8m2m+1
and with respect to the pair (a,b)=(m+1,-m+1) is
(50)Ar(S1,mP3)m+1,-m+1=2mn|2b|=4m2m+12m+1.
Since m=(n-1)/2, the areas are, respectively,
(51)Ar(S1,mP3)-1,1=8m2m+1=4(n-1)n-1+1=4(n-1)n,Ar(S1,mP3)-m+1,m+1=4m2m+12m+1=2(n-1)n2n+12=22(n-1)nn+1.
The greater of the two gives the area of the class of graphs; that is,
(52)Ar(S1,mP3)-m+1,m+1=22(n-1)nn+1.


### 6.5. Hypercube Graphs

Thep-regular hypercube has eigenvalues λ=(p-2k)(pk), k=0,1,2,…,p, and eigen-bibalanced ratio (k fixed, n varying, p≠2k, and k≠0)
(53)2p-2kp2-2pk=2ln⁡⁡n/ln⁡⁡2-kln2n/ln22-2k(ln⁡⁡n/ln⁡⁡2)=2ln⁡⁡2ln⁡⁡n-kln⁡⁡2ln2n-2kln⁡⁡2ln⁡⁡n,
where, since n=2p, we have p=ln⁡⁡n/ln⁡⁡2.Then(54)asymp(2p-2kp2-2pk)=0.
For k=1 and using the eigenvalue pair p and p-2, the eigen-bibalanced ratio area is
(55)Ar(I)p,p-2=∫2p-2p2-2pd(2p)=2ln⁡⁡2∫‍ln⁡⁡n-ln⁡⁡2ln2n-2ln⁡⁡2ln⁡⁡ndn.
Setting u=ln2n-2ln⁡⁡2ln⁡⁡n and rearranging, we get
(56)ln2n-2ln⁡⁡2ln⁡⁡n-u=0.
So
(57)ln⁡⁡n=2ln⁡⁡2±(2ln⁡⁡2)2+4u2=ln⁡⁡2+ln22+u⟹n=eln⁡⁡2+ln22+u=2eln22+u⟹eln22+u=n2.
Also, for u=ln2n-2ln⁡⁡2ln⁡⁡n, we have
(58)dudn=[2ln⁡⁡nn-2ln⁡⁡2n]=2n(ln⁡⁡n-ln⁡⁡2)⟹du=2n(ln⁡⁡n-ln⁡⁡2)dn.
Now substituting the above results into (55), we get
(59)Ar(I)p,p-2=2ln⁡⁡2∫‍ln⁡⁡n-ln⁡⁡2ln2n-2ln⁡⁡2ln⁡⁡ndn=2ln⁡⁡2∫n2udu=ln⁡⁡2∫nudu=ln⁡⁡2∫eln⁡⁡2+ln22+uudu,u=ln2n-2ln⁡⁡2ln⁡⁡n.Nowu>1⇒1/u<1 and eln⁡⁡2+ln22+u<eu so that
(60)ln⁡⁡2∫eln⁡⁡2+ln22+uudu<ln⁡⁡2∫euudu<ln⁡⁡2∫eudu=ln⁡⁡2eu=ln⁡⁡2eln2n-2ln⁡⁡2ln⁡⁡n.
Although this is not a good approximation for the area of a hypercube class of graphs, it may suggest that the area of such a class of graphs is greater than that of complete graphs.


### 6.6. Join of Two Graphs

Taking the join of the complement of the complete graph on 2 vertices and the complete graph onn vertices, we get that the resulting adjacency matrix of the graph has the conjugate pair of eigenvalues
(61)λ=(n-1)±(n-1)2+8n2
so that their eigen-bibalanced ratio is
(62)r=(((n-1)+(n-1)2+8n2)+((n-1)-(n-1)2+8n2))×(((n-1)+(n-1)2+8n2)×((n-1)-(n-1)2+8n2))-1=2(n-1)/2((n-1)2-(n-1)2-8n)/4=n-1-2nwhichtendsto-12.


### 6.7. Cycle Graphs

Conjecture 15.
The only class of regular graphs which are neither sum nor product eigen-pair balanced is cycles.


## 6.1. Complete Graphs

The complete graph onn vertices has the unique eigen-bibalanced ratio of
(35)r((n-1)Kn(-1))=(n-1)+(-1)(n-1)(-1)=n-21-n.
This depends on the order of the graph and has the unique eigen-bibalanced ratio asymptote
(36)r((n-1)Kn(-1))∞=-1
and eigen-bibalanced ratio area
(37)Ar(Kn)-1,n-1=2mn|∫n-21-ndn|=2(n(n-1)/2)n|∫[2n-1-nn-1]dn|=(n-1)|∫[2n-1-nn-1]dn|=(n-1)B,
where
(38)B=|∫2n-1-n-1n-1-1n-1|dn=n-ln⁡|n-1|+c.
When n=0 we have A=0 so c=0 so that its area is
(39)Ar(Kn)-1,n-1=(n-1)(n-ln⁡(n-1))=(n-1)H.
Note that the length of the longest path for the complete graph is n-1, so that H in the above expression can be regarded as theheight of the graph. Also, the term ln⁡⁡(n-1) occurs as part of the upper bound of thediameterof a graph involving the second largest eigenvalue; see Brouwer and Haemers [6].Is this area the maximum for all classes of eigen-bibalanced graphs?


## 6.2. Complete Bipartite Graphs

The complete bipartite graphKs,t on s+t vertices has the eigen-bibalanced ratio of
(40)r(stKs,t(-st))=st-st-st=0
which is independent of the size of the graph.Its area is(41)Ar(Ks,t)-st,st=2st(s+t)|2st|=4(st)3/2s+t.
This attains its maximum when s=t=n/2, and then the graph (thecomplete split bipartitegraph on n vertices) is s-regular and the area is
(42)Ar(Kn/2,n/2)-n/2,n/2=n2|∫-n/2n/2dn|=n22.


## 6.3. Wheel Graphs

Wheels onn vertices, containing (n-1) spokes and 2(n-1) edges, have eigen-bibalanced ratio
(43)r(2+4+4(n-1)2Wn2-4+4(n-1)2)=-2(n-1).
This depends on the size of the graph, so they have an eigen-bibalanced ratio asymptote of 0 and eigen-bibalanced ratio area of
(44)Ar(Wn)(2+4+4(n-1))/2,(2-4+4(n-1))/2=2mn|∫a+babdn|=2mn|∫21-ndn|=4(n-1)n(ln⁡|n-1|+c)=4(n-1)n(ln⁡|n-1|+c).
Now Ar(Wn)(2+4+4(n-1))/2,(2-4+4(n-1))/2=0 when n=2 so that c=0.So(45)Ar(Wn)(2+4+4(n-1))/2,(2-4+4(n-1))/2=4(n-1)n(ln⁡|n-1|).


## 6.4. Star Graphs

As per Brouwer and Haemers [6], star graphs with m rays of length 2 have eigenvalues 0, -1, 1, and ±m+1.Using the pair(a,b)=(-1,1) we obtain the ratio
(46)r(-1S1,mP31)=0-1=0
and using the pair (a,b)=(m+1,-m+1) we get
(47)r(m+1S1,mP3-m+1)=0-(m+1)=0.
Using the class of graphs, where (m+1)=t2 and eigen-pair (a,b)=(m+1,1), we have the ratio
(48)r(m+1S1,mP31)=m+1+1m+1=t+1t.
Therefore the class of star graphs with m rays of length 2 does not have a unique eigen-bibalanced ratio.The area with respect to the pair(a,b)=(-1,1) is
(49)Ar(S1,mP3)-1,1=2mn|2b|=2.2m2m+1|2|=8m2m+1
and with respect to the pair (a,b)=(m+1,-m+1) is
(50)Ar(S1,mP3)m+1,-m+1=2mn|2b|=4m2m+12m+1.
Since m=(n-1)/2, the areas are, respectively,
(51)Ar(S1,mP3)-1,1=8m2m+1=4(n-1)n-1+1=4(n-1)n,Ar(S1,mP3)-m+1,m+1=4m2m+12m+1=2(n-1)n2n+12=22(n-1)nn+1.
The greater of the two gives the area of the class of graphs; that is,
(52)Ar(S1,mP3)-m+1,m+1=22(n-1)nn+1.


## 6.5. Hypercube Graphs

Thep-regular hypercube has eigenvalues λ=(p-2k)(pk), k=0,1,2,…,p, and eigen-bibalanced ratio (k fixed, n varying, p≠2k, and k≠0)
(53)2p-2kp2-2pk=2ln⁡⁡n/ln⁡⁡2-kln2n/ln22-2k(ln⁡⁡n/ln⁡⁡2)=2ln⁡⁡2ln⁡⁡n-kln⁡⁡2ln2n-2kln⁡⁡2ln⁡⁡n,
where, since n=2p, we have p=ln⁡⁡n/ln⁡⁡2.Then(54)asymp(2p-2kp2-2pk)=0.
For k=1 and using the eigenvalue pair p and p-2, the eigen-bibalanced ratio area is
(55)Ar(I)p,p-2=∫2p-2p2-2pd(2p)=2ln⁡⁡2∫‍ln⁡⁡n-ln⁡⁡2ln2n-2ln⁡⁡2ln⁡⁡ndn.
Setting u=ln2n-2ln⁡⁡2ln⁡⁡n and rearranging, we get
(56)ln2n-2ln⁡⁡2ln⁡⁡n-u=0.
So
(57)ln⁡⁡n=2ln⁡⁡2±(2ln⁡⁡2)2+4u2=ln⁡⁡2+ln22+u⟹n=eln⁡⁡2+ln22+u=2eln22+u⟹eln22+u=n2.
Also, for u=ln2n-2ln⁡⁡2ln⁡⁡n, we have
(58)dudn=[2ln⁡⁡nn-2ln⁡⁡2n]=2n(ln⁡⁡n-ln⁡⁡2)⟹du=2n(ln⁡⁡n-ln⁡⁡2)dn.
Now substituting the above results into (55), we get
(59)Ar(I)p,p-2=2ln⁡⁡2∫‍ln⁡⁡n-ln⁡⁡2ln2n-2ln⁡⁡2ln⁡⁡ndn=2ln⁡⁡2∫n2udu=ln⁡⁡2∫nudu=ln⁡⁡2∫eln⁡⁡2+ln22+uudu,u=ln2n-2ln⁡⁡2ln⁡⁡n.Nowu>1⇒1/u<1 and eln⁡⁡2+ln22+u<eu so that
(60)ln⁡⁡2∫eln⁡⁡2+ln22+uudu<ln⁡⁡2∫euudu<ln⁡⁡2∫eudu=ln⁡⁡2eu=ln⁡⁡2eln2n-2ln⁡⁡2ln⁡⁡n.
Although this is not a good approximation for the area of a hypercube class of graphs, it may suggest that the area of such a class of graphs is greater than that of complete graphs.


## 6.6. Join of Two Graphs

Taking the join of the complement of the complete graph on 2 vertices and the complete graph onn vertices, we get that the resulting adjacency matrix of the graph has the conjugate pair of eigenvalues
(61)λ=(n-1)±(n-1)2+8n2
so that their eigen-bibalanced ratio is
(62)r=(((n-1)+(n-1)2+8n2)+((n-1)-(n-1)2+8n2))×(((n-1)+(n-1)2+8n2)×((n-1)-(n-1)2+8n2))-1=2(n-1)/2((n-1)2-(n-1)2-8n)/4=n-1-2nwhichtendsto-12.


## 6.7. Cycle Graphs

Conjecture 15.
The only class of regular graphs which are neither sum nor product eigen-pair balanced is cycles.


## 7. Eigen-Bibalanced Properties of the Class of Complements of Graphs

Theorem 16.
LetI be a class of eigen-bibalanced, k-regular graphs with eigen-pair a,b; a,b≠k or -1. Let I¯ be the class of graphs consisting of the complement, G¯, of graphs G∈I, where G¯ is connected. Then, for all G¯∈I¯, G¯ is (n-1-k)-regular, eigen-bibalanced with eigen-pair c,d=-1-a,-1-b, and the eigen-bibalanced ratio of I¯ is r(cI¯d)=(c+d)/cd=(-2-(a+b))/(1+(a+b)+ab). Therefore, the class I¯ of graphs is eigen-bibalanced.Proof.
As per Brouwer and Haemers [6], if a,b are eigenvalues of G and a,b≠k or −1, then c=(-1-a) and d=(-1-b) are eigenvalues of G¯.
Therefore,(63)Sumoftheeigen-pair(c,d)ofG¯=c+d=(-1-a)+(-1-b)=-2-(a+b),Productoftheeigen-pair(c,d)ofG¯=cd=(-1-a)×(-1-b)=1+(a+b)+ab.
Since G∈I is eigen-bibalanced, then (a+b) and (ab) are constant integers. Therefore, G¯∈I¯ is eigen-bibalanced.
Therefore,(64)r(cI¯d)=c+dcd=-2-(a+b)1+(a+b)+ab=ratioofintegers.
Therefore the class I¯ of graphs is eigen-bibalanced.Corollary 17.
LetI be a class of eigen-bibalanced, k-regular graphs with eigen-pair a,b; a,b≠k or −1. Let I¯ be the class of graphs consisting of the complement, G¯, of graphs G∈I, where G¯ is connected. If the asymptote of the ratio (a+b)/ab=t, a,b≠k or -1 and lim⁡n→∞ab=∞, then
(65)r(cI¯d)∞=asymp(r(cI¯d))=-tt+1.Proof.
Consider the following:(66)r(cI¯d)=c+dcd=-2-(a+b)1+(a+b)+ab=-2/ab-(a+b)/ab1/ab+(a+b)/ab+1.
Now lim⁡n→∞ab=∞(67)⟹r(cI¯d)∞=asymp(r(cI¯d))=lim⁡n→∞(-2/ab-t1/ab+t+1)=-tt+1.Corollary 18.
LetI be a class of eigen-bibalanced k-regular graphs with eigen-bibalanced ratio asymptote f(t)=t with respect to pair a,b where a,b≠k or −1. Let I¯ be the class of graphs consisting of the complement, G¯, of graphs G∈I, where G¯ is connected. Then the eigen-bibalanced ratio asymptote of I¯ with respect to eigen-pair (c,d) is g(t)=-t/(t+1) which is an involution.Proof.
As per Corollary17, let g(t)=asymp(r(cI¯d))=-t/(t+1).
Then,(68)g(-tt+1)=-(-t/(t+1))(-t/(t+1))+1=t/(t+1)1/(t+1)=t
so that g[g(t)]=t which implies that g(t)=g-1(t).
Functions, which are equal to their own inverse, are called involutions, so thatg(t) is an involution. Classes of uniquely eigen-bibalanced graphs whose complements form a class of eigen-bibalanced graphs with an involution property are said to beinvolution-complementary.Corollary 19.
The involutiong(t)=-t/(t+1) is a solution of the differential equation
(69)dg(t)dt=1t(t+1);g(-12)=1.Proof.
Since(70)g′(t)=-1(t+1)+t(t+1)2=-1(t+1)2,
then
(71)g′(g(t))=-1(-t/(t+1)+1)2=-(t+1)2.
Also, g(t)=-t/(t+1),
(72)⟹t+(t+1)g(t)=0⟹f(t)+(t+1)g(t)=0.
Differentiating both sides, we get
(73)f′(t)+g′(t)(t+1)+g(t)=0.
Since g(t) is an involution, g(g(t))=t, then differentiating both sides and recalling f(t)=t we get
(74)g′(g(t))g′(t)=f′(t)=1.
Substituting (71) and (74) into (73), we get(75)f′(t)+g′(t)(t+1)+g(t)=0⟹g′(g(t))g′(t)+g′(t)(t+1)+g(t)=0⟹-(t+1)2g′(t)+g′(t)(t+1)+g(t)=0⟹g′(t)[-(t+1)2+(t+1)]+g(t)=0⟹g′(t)[-t(t+1)]+g(t)=0⟹dg(t)dt=g(t)t(t+1)⟹dyy=dtt(t+1),
where y=g(t).
Solving this variable separable equation we get(76)ln⁡|y|=∫(1t-1t+1)dt=ln⁡⁡|t|-ln⁡⁡|t+1|+c=ln⁡|t||t+1|+c
and y=k(|t|/|t+1|) is a general solution of (69).
Ift≤0 and t+1>0, then the solution is
(77)y=-ktt+1;
if y(-1/2)=1, then k=1, so
(78)y=-tt+1.In Section6.6 we showed that -1/2 is the eigen-bibalanced ratio asymptote of the class of graphs comprising the join of the complement of the complete graph on 2 vertices and the complete graph on n vertices.Note. There are other possible solutions of the general differential equation dg(t)/dt=1/t(t+1), g(p)=q.For example, whent≥0⇒t+1≥0, y=t/(t+1) is a solution of the differential equation
(79)dg(t)dt=1t(t+1);g(1)=12.


## 8. Properties of Eigen-Bibalanced Classes of Graphs

Theorem 20.
If a class of noncomplete graphsI is eigen-bibalanced with respect to the eigen-pair (a,b), (a,b) are conjugate eigen-pairs arising from the quadratic λ2+sλ+t′, with at least one of a,b positive and of the form n+c (with n being an integer and c being negative), and the ratio (aIb)=(a+b)/ab is a function of n, then t′ is negative and the eigen-pair balanced ratio asymptote lies on the interval [-1,0].Proof.
Let the conjugate eigen-pair(a,b) arise from the roots of the quadratic λ2+sλ+t′; that is,
(80)a,b=-s±s2-4t′2.
Assume t′>0, then s≥2t′:⇒t′≥0 and s≥0,⇒a<0 and b<0, which is a contradiction of the assumption that at least one of a,b is positive.
Therefore, we have shown thatt′≤0.
Ift′=0, then
(81)a,b=-s±s22
and either a=0 or b=0, which is not allowed.
Therefore, we have shown thatt′<0.
So lett′=-t, where t>0.
We havea≤n-1 and b≤n-1 (as these are conjugate eigenvalues of the class of noncomplete graphs I); a+b=-s; and ab=-t and
(82)r(aIb)=a+bab=st.
If a=-b then the ratio r=(a+b)/ab=0. However, we are given that r(aIb)=(a+b)/ab is a function of n, so we must have a≠-b.
Ifa and b are both fixed constants, then the ratio is not a function of n, so we cannot have a and b being both fixed constants.
From (82) above, r=s/t. If t=f(n), f(n) is of order n, and s is a fixed constant c, then
(83)asymp(r(aIb))=asymp(st)=asymp(cf(n))=0.
If s=a+b is a function of n, so t=-(ab) will be a function of n.
If botha and b are functions of n, then a+b is O(np) and ab has O(nq) where q≥p.
Therefore,asymp(r(aIb))=0.
Now let us assume thata=n+c>0 and b=k,  k negative (as per conditions in Theorem 20).
Then ifs=n+c′, t=kn+c′′, (k<0), and c′ and c′′are constants, then(84)⟹asymp(r(aIb))=1k<0.
Since a is an integer, b=k must be an integer too (as they are conjugate pairs), so k≤-1. Therefore,
(85)asymp(r(aIb))=1k≥-1.
So we have proved that -1≤asymp(r(aIb))<0.
We have therefore shown separately thatasymp(r(aIb))=0 and -1≤asymp(r(aIb))<0 under different conditions.
Thereforeasymp(r(aIb))∈[-1,0].For the complete graphKn, the quadratic for the complete graph, with eigenvalues (-1,n-1), sum=n-2, and product -(n-1), is
(86)λ2-(n-2)λ-(n-1)⟹λ=(n-2)±(n-2)2+4(n-1)2.
So, asymp(r(-1Knn-1))=(n-2)/-(n-1)=-1.So the eigen-bibalanced ratio asymptote of the complete graphs is −1, which is the same as one of the eigen-pairs. If a class of graphs is eigen-bibalanced with respect to the pair(a,b) and its asymptote is the same as one of the eigen-pairs, then it is said to beasymptotically closed with respect to the pair (a,b). Therefore, the class of complete graphs is asymptotically closed with respect to the pair (-1,n-1).Theorem 21.
The eigen-bibalanced ratio areas of complete bipartite graphs, wheel graphs, and star graphs with rays of length 2 are each bounded above by the area of the complete graph.Proof.
As discussed above, the eigen-bibalanced ratio area of the complete graph is(87)Ar(Kn)-1,n-1=(n-1)(n-ln⁡(n-1)).
As per Section 6.2, the eigen-bibalanced ratio area of the split complete bipartite graph is
(88)Ar(Kn/2,n/2)n/2,n/2=n22.
As per Section 6.3, the eigen-bibalanced ratio area of the wheel graph is
(89)Ar(Wn)(2+4+4(n-1))/2,(2-4+4(n-1))/2=4(n-1)n(ln⁡|n-1|).
As per Section 6.4, the eigen-bibalanced ratio area of the star graph with rays of length 2 is
(90)Ar(S1,mP3)m+1,-m+1=22(n-1)nn+1,
where m=(n-1)/2 and n≥3.
(1) Considering the eigen-bibalanced ratio area of the complete graph and the complete split bipartite graph, we get Table1.
Now, for large values ofn, Ar(Kn)-1,n-1=(n-1)(n-ln⁡(n-1)) behaves like n2 and is an increasing function of n, and
(91)Ar(Kn/2,n/2)n/2,n/2=n22.
So we can conclude that
(92)Ar(Kn)-1,n-1>Ar(Kn/2,n/2)n/2,n/2forlargen;
that is, the area of the complete graphs is greater than or equal to the area of the split complete bipartite graph.
(2) Considering the eigen-bibalanced ratio area of the complete graph and the wheel graph forn≥3, we get Table 2.
Now, for large values ofn, Ar(Kn)-1,n-1=(n-1)(n-ln⁡⁡(n-1)) behaves like n2 and is an increasing function of n, and
(93)Ar(Wn)(2+4+4(n-1))/2,(2-4+4(n-1))/2=4(n-1)n(ln⁡⁡|n-1|)<n.
So we can conclude that
(94)Ar(Kn)-1,n-1>Ar(Wn)(2+4+4(n-1))/2,(2-4+4(n-1))/2forlargen;
that is, the eigen-bibalanced ratio area of the complete graphs is greater than the area of the wheel graph for n≥3. Considering the eigen-bibalanced ratio area of the complete graph and the star graph with rays of length 2, for n≥3, we get Table 3.
Now, for large values ofn, Ar(Kn)-1,n-1=(n-1)(n-ln⁡⁡(n-1)) behaves like n2 and is an increasing function of n, and Ar(S1,mP3)-m+1,m+1=(22(n-1)/n)n+1, where m=(n-1)/2 behaves like 22n and is an increasing function of n.
So we can conclude that(95)Ar(Kn)-1,n-1>Ar(S1,mP3)-m+1,m+1,
where m=(n-1)/2; that is, the eigen-bibalanced ratio area of the complete graph is greater than the area of the star graph with rays of length 2, for n≥3.
So we can conclude that the eigen-bibalanced areas of complete bipartite graphs, wheel graphs, and star graphs with rays of length 2 are each bounded above by the area of the complete graph.Table 1
Eigen-bi-balanced area of complete and complete split bipartite graphs for values onn.
N
Complete graph
Complete split bipartite graph
2
2
2
3
4.61
4.5
4
8.7
8
5
14.45
12.5
100
9445.08
5 000
1000
992 100.15
500 000
10 000
99  897 906.81
50 000 000Table 2
Eigen-bi-balanced area of complete and wheel graphs for values onn.
N
Complete graph
Wheel graph
3
4.61
1.85
4
8.7
3.3
5
14.45
4.4
100
9445.08
18.2
1000
992 100.15
27.6
10 000
99 897 906.81
36.84Table 3
Eigen-bi-balanced area of complete and star graphs of rays of length 2 for values onn.
N
Complete graph
Star graph with rays of length 2
3
4.61
3.77
5
14.45
5.54
7
31.25
6.86
101
9 639.48
28.28
1001
99 4092.24
89.44
10001
999 17896.60
282.84Theorem 22.
If a class of graphs has eigen-bibalanced ratio(96)r=r(aIb)=a+bab,
then ar≠1 and br≠1.
Also, ifr is nonzero, the elements of the eigen-pair (a,b) cannot both be 1/r.Proof.
Let(97)a+bab=r(aIb)=r⟹a+b=rab.
If we let ab=y, we get a+b=rab=ry, so
(98)a+ya=ry,⟹a2+y=ray,⟹y=-a21-ar=ab,⟹b=aar-1,forar≠1.
Swopping the roles of a and b we get the desired result.The following theorem can be derived from Lee and Yeh [11].Theorem 23.
Define the class of graphs(99)I=Kk¯⊕Kn,
where k is fixed and n varies and is greater than 1.
Then this class has eigen-pair(100)a,b=(n-1)±(n-1)2+4nk2
with eigen-bibalanced ratio
(101)r(aIb)=n-1-nk
with eigen-bibalanced ratio asymptote
(102)asymp(r(aIb))=-1k
and area
(103)Ar(I)a,b=(n(n-1)+2knn+k)(nk-1kln⁡⁡(n+1)).Proof.
From Lee and Yeh [11], the eigenvalue conjugate pair associated with this join is
(104)(a,b)=(n-1)±(n-1)2+4nk2.Then (105)sum(a,b)=2(n-1)2=(n-1),product(a,b)=-4nk4=-kn,r(aIb)=n-1-nk,asymp(r(aIb))=-1k,
as n becomes increasingly large.
The eigen-bibalanced ratio area is (with average degreeB)
(106)Ar(I)a,b=B|∫1-nknd(n+k)|=n(n-1)+2kn(n+k)|∫[1kn-1kd(n)]|=n(n-1+2k)(n+k)(nk-1kln⁡⁡n+c).
With k=1, the area must be that of the complete graph on (n+1) vertices, which is, as per Section 6.1,
(107)Ar(Kn+1)-1,n=(n+1-1)(n+1-ln⁡(n+1-1))=(n)(n+1-ln⁡⁡(n)).
Hence, from (106) with k=1,
(108)Ar(I)a,b=n(n-1+2)n+1(n1-11ln⁡⁡n+c)=Ar(Kn+1)-1,n=(n)(n+1-ln⁡⁡(n))⟹n(n+1)n+1(n-ln⁡⁡n+c)=(n)(n+1-ln⁡(n))⟹n(n+1)n+1(n-ln⁡⁡n+c)=(n)(n-ln⁡(n)+1)⟹c=1.
So,
(109)Ar(I)a,b=(n(n-1)+2knn+k)(nk-1k(ln⁡⁡n)+1).Note that the complementG¯ of any G∈I above is not connected and therefore cannot be eigen-bibalanced as per the definition. Hence the class of graphs G¯∈I¯ is not eigen-bibalanced. This result applies for the class of complete graphs, complete bipartite graphs, and wheels and star graphs.Alternatively, we could have formed the join (withn vertices) I=Kk¯⊕Kn-k, which, by substituting n with (n-k) into (61), has conjugate pairs
(110)(a,b)=n-k-1±(n-k-1)2+4k(n-k)2
with ratio
(111)r(aIb)=k+1-nk(n-k)=-(n-k)+1k(n-k)
which has asymptote asymp(r(aIb))=-1/k.The area is(112)Ar(I)a,b=B|∫[-1kdn+1k(n-k)]dn|=B(nk-1kln⁡⁡(n-k)+c)=((n-k)(n-k-1)+2k(n-k)n)×(nk-1kln⁡⁡(n-k)+c).
When k=1, we must get the area the of the complete graph on n vertices, so that
(113)Ar(Kn)-1,n-1=(n-1)(n-ln⁡⁡(n-1))=((n-1)(n-1-1)+2(n-1)n)×(n1-11ln⁡⁡(n-1)+c)=((n-1)(n-2)+2(n-1)n)×(n-ln⁡⁡(n-1)+c)=(n-1)(n-ln⁡⁡(n-1)+c)whichgivesc=0.
Hence
(114)Ar(I)a,b=((n-k)(n-k-1)+2k(n-k)n)×(nk-1k(ln⁡⁡(n-k))),
where I=Kk¯⊕Kn-k.Conjecture 24.
The maximum eigen-bibalanced ratio area of classes of graphs on at least 6 vertices is that of the complete graph and is equal to(n-1)(n-ln⁡⁡(n-1)).Remark 25.
The heightH=n of the complete split bipartite graphis greater than the height H=n-ln⁡⁡(n-1) of complete graphs. However multiplying by the average degree results in the complete graph having the greater area; that is,
(115)Ar(Kn)-1,n-1=(n-1)(n-ln⁡⁡(n-1))>n22=Ar(Kn/2,n/2)-n/2,n/2.
A trivial association with spanning trees and areas is given below.From Section6.2, the complete split-bipartite graph has area
(116)Ar(G)=n22=shad(G)2t(G).
From Section 6.1, for the complete graph the area, in respect of the eigenvalues −1 and n-1, is
(117)Ar(Kn)-1,n-1=(n-1)(n-ln⁡⁡(n-1))=n2-nln⁡⁡(n-1)-n+ln⁡⁡(n-1)<n2+ln⁡⁡(n-1).
Now ln⁡⁡(n-1)<ln⁡⁡(n)<n<2n+1, so
(118)Ar(Kn)-1,n-1<n2+2n+1=(n+1)2=shad(Kn+1)t(Kn+1).
Note that, for wheels with n spokes, the conjugate eigen-pair, as per Section 2.6, is
(119)(a,b)=2±4+4n2
so that
(120)|a+b|+|ab|=|2+4+4n2+2-4+4n2|+|2+4+4n2·2-4+4n2|=2+n.
For the join of two cycles of length n, there exist a pair of eigenvalues (a,b)=2±n so that
(121)|a+b|+|ab|=|2+n+2-n|+|(2+n)(2-n)|=4+|4-n2|=n2.
See Lee and Yeh [11].Note that, forc(d), respectively, being the maximum (minimum) degrees of the vertices in the respective graphs, the wheel graph above has |a+b|+|ab|=(2+n)≤3(n-1)=cd and the join of two cycles of length n has |a+b|+|ab|=n2≤(n+2)2=cd. This suggests part (i) of the following conjecture.For star graphs withm rays of length 2, we have eigen-pair (a,b)=(m+1,-m+1), and |a+b|=|m+1-m+1|=0 and |ab|=|(m+1)(-m+1)|=(m+1). Also c=m and d=1, so |ab|/d=(m+1)/1=c+1. So, the star graph with m rays of length 2 suggests part (ii) of the conjecture below.Conjecture 26.
If a class of noncomplete graphs is eigen-bibalanced with associated eigen-pair(a,b) of a member of the class, the member having maximum (minimum) degree c(d), respectively, then(i)
ifa+b≠0, then |a+b|+|ab|≤cd;(ii)
ifa+b=0, then |ab|/d≤c+1.


## 9. Eigen-Bibalanced Classes of Graphs: Density

Definition 27 (eigen-bibalanced density).
The interval[-1,0] is more convenient if it is a positive interval: we define theeigen-bibalanced density of a class of eigen-bibalanced graphs with asymptote asymp(r(aIb)) as
(122)Ωr(I)=|asymp(r(aIb))|
so that the complete graph has eigen-bibalanced density 1, which we propose as thelargestdensity of all possible eigen-bibalanced graphs (the maximum density of a class of graphs will be the largest of its densities over all its possible ratios).Conjecture 28.
The asymptotic eigen-bibalanced ratio of uniquely eigen-bibalanced classes of graphs lies in the interval[-1,0] and the complete graph is the only graph which is asymptotically closed with respect to its unique eigen-pair. The density lies on the interval [0,1] with the largest density being that of complete graphs, which equals 1.


## 10. Eigen-Bibalanced Classes of Graphs: Energy and Asymptotes

There is much research on the energy of a graph - it is related to the totalπ-electron energy in a molecule represented by a (molecular) graph (see Adiga et al. [17]).Definition 29 (energy of a graph).
Theenergy of a graph with adjacency matrix A with eigenvalues λ1≥λ2≥⋯≥λn is
(123)EA=∑i=1n|λi|.
See Stevanoviç [18].
If we have a class of eigen-bibalanced graphs, is there a way of determining if the asymptotic ratio has an effect on the energy of a graph? It may be possible by assigning this asymptotic value to the vertices of the graph as, for example, a weight of a loop on a vertex; see Adiga et al. [17]. This suggests the following definition.Definition 30 (r-asymptotic eigen-bibalanced matrix).
Ther-asymptotic eigen-bibalanced matrixCr∞=(cij), associated with the adjacency matrix A=(aij) of G on n vertices with an eigen-bibalanced ratio asymptote r(aIb)∞, is defined as
(124)cij={aij;i≠jdeg⁡⁡(aj)+r(aIb)∞;i=j.
If G is k-regular and A has eigenvalues k=λ1≥λ2≥⋯≥λn, then the eigenvalues of Cr∞ are
(125)2k+r(aIb)=λ1≥λ2+k+r(aIb)≥⋯≥λn+k+r(aIb).
In particular, if r=0 the C0∞ is the signless Laplacian matrix.Definition 31 (r-asymptotic eigen-bibalanced energy).
Theenergyof ther-asymptotic eigen-bibalanced matrixCr∞=C, associated with the graph G on n vertices and m edges, with eigenvalues of Cr∞=C being λ1≥λ2≥⋯≥λn, is
(126)ECr∞=∑i=1n|λi-2mn|.
See Stevanoviç [18].Ifr=0, then we get the energy of the signless Laplacian matrix.Ifr≠0, such as for the complete graph Kn on n vertices and n(n-1)/2 edges, then its (−1)-asymptotic eigen-bibalanced energy is found as follows.
As per Section2.1, the eigenvalues of Kn are (n-1)1, (-1)n-1so that the eigenvalues of C-1∞ are
(127)λ1=2(n-1)-1=2n-3once,λ2=-1+(n-1)-1=n-3(n-1)times
so that the r-asymptotic eigen-bibalanced energy of G (with eigen-pair (a,b)) is
(128)EC-1∞=∑i=1n|λi-2mn|=|(2n-3)-2n(n-1)2n|+(n-1)|(n-3)-2n(n-1)2n|=|(2n-3)-(n-1)|+(n-1)|(n-3)-(n-1)|=|(n-2)|+(n-1)|(-2)|=n-2+2n-2=3n-4.
This energy is greater than the normal energy EA=2n-2 of a complete graph on a large number of vertices. This asymptotic energy can be regarded as the eigen-pair balanced energy associated with the graph G as the order of G becomes increasingly large.


## 11. Eigen-Bibalanced Classes of Graphs: Matrix Ratio

Definition 32 (matrix eigen-bibalanced ratio equation).
LetA be the adjacency matrix of a graph G∈I, where I is a eigen-bibalanced class of graphs. If the eigenvectors v1_, v2_, associated with the eigen-pair (a,b), haveunit length,then one has thematrix eigen-bibalanced ratio equation:(129)v1_tAv1_+v2_tAv2_v1_tAv1_v2_tAv2_=a+bab.
For example, if I is the class of complete graphs, Kn, then A(Kn) has eigenvalues n-1 and -1, with eigenvectors of unit length v1_=1/n(1,1,…,1) and v2_ (which is the unit eigenvector associated with the second eigenvalue of −1); then
(130)v1_tAv1_+v2_tAv2_v1_tAv1_v2_tAv2_=n-1+(-1)(n-1)(-1)=n-21-n.
This is an original definition, and is interesting along with other ratios of matrices which have been defined and investigated over time, for example, the Rayleigh ratio: R(H,x_)=x_THx_/x_Tx_, for any (hxh) matrix H and any (hx1) vector x_.


## 12. Conclusion

In this paper we used the ideas of integral eigenvalues and conjugate eigen-pairs to introduce the new idea of eigen-sum and eigen-product balanced properties of graphs, involving a pair of nonzero distinct eigenvaluesa and b. The fact that these attributes were nonzero, together with the idea of robustness, provided the motivation for the definition of the eigen-bibalanced ratio of classes of graphs, which allowed for the definitions of area and asymptotic ratio of classes of graphs. We found areas and asymptotes of known classes of graphs and it appears that complete graphs have the largest area and the asymptotes of all uniquely eigen-bibalanced classes of graphs may belong to the interval [-1,0]. Future investigation may also include classes of eigen-bibalanced graphs whose complement class is also eigen-bibalanced.



---

*Source: 148690-2014-09-23.xml*