In this chapter we give methods for investigating the eigenvalues of a graph.
Let Γ be a graph of order v. The adjacency matrix of Γ, A(Γ), is the v× v matrix indexed by V(Γ) such that A(Γ)_xy=1 if xy∈ E(Γ), and A(Γ)_xy=0 otherwise.
The spectrum of Γ, Spec(Γ), is the multiset of eigenvalues of its adjacency matrix, and an eigenvalue of Γ is a member of Spec(Γ). The multiplicity of an eigenvalue α of Γ is the number of times α appears in Spec(Γ). For information on most of the objects and results discussed in this chapter, see [BH11].
In this section, we introduce methods for investigating eigenvalues of regular graphs. The input for these methods will be a specific graph or the parameters of a graph.
Let Γ be a regular graph with parameters (v,k). Then Γ has largest eigenvalue k (see [BH11]). Therefore we do not implement a "LargestEigenvalue" function for regular graphs.
Let Γ be a strongly regular graph with parameters (v,k,a,b). The eigenvalues of Γ and their corresponding multiplicities are uniquely determined by the parameters (v,k,a,b) (see [BH11]). Using this knowledge, we provide methods which take as input feasible strongly regular graph parameters (v,k,a,b). We also give methods which return an exact representation of the eigenvalues of a strongly regular graph with parameters (v,k,a,b), and their multiplicities.
‣ LeastEigenvalueInterval( gamma, eps ) | ( operation ) |
‣ LeastEigenvalueInterval( parms, eps ) | ( operation ) |
Returns: A list.
Given a graph gamma and rational number eps, this function returns an interval containing the least eigenvalue of gamma.
Given feasible strongly regular graph parameters parms and rational number eps, this function returns an interval containing the least eigenvalue of a strongly regular graph with parameters parms.
The interval returned is in the form of a list, [y,z] of rationals y≤ z with the property that z-y≤ eps. If the eigenvalue is rational this function will return a list [y,z], where y=z.
gap> gamma:=EdgeOrbitsGraph(Group((1,2,3,4,5)),[[1,2],[2,1]]);;
gap> LeastEigenvalueInterval(gamma,1/10);
[ -13/8, -25/16 ]
gap> parms:=SRGParameters(gamma);
[ 5, 2, 0, 1 ]
gap> LeastEigenvalueInterval(parms,1/10);
[ -13/8, -25/16 ]
gap> LeastEigenvalueInterval(JohnsonGraph(7,3),1/20);
[ -3, -3 ]
‣ SecondEigenvalueInterval( gamma, eps ) | ( operation ) |
‣ SecondEigenvalueInterval( parms, eps ) | ( operation ) |
Returns: A list.
Given a regular graph gamma and rational number eps, this function returns an interval containing the second largest eigenvalue of gamma.
Given feasible strongly regular graph parameters parms and rational number eps, this function returns an interval containing the second largest eigenvalue of a strongly regular graph with parameters parms.
The interval returned is in the form of a list, [y,z] of rationals y≤ z with the property that z-y≤ eps. If the eigenvalue is rational this function will return a list [y,z], where y=z.
gap> gamma:=EdgeOrbitsGraph(Group((1,2,3,4,5)),[[1,2],[2,1]]);;
gap> SecondEigenvalueInterval(gamma,1/10);
[ 9/16, 5/8 ]
gap> parms:=SRGParameters(gamma);
[ 5, 2, 0, 1 ]
gap> SecondEigenvalueInterval(parms,1/10);
[ 9/16, 5/8 ]
gap> SecondEigenvalueInterval(JohnsonGraph(7,3),1/20);
[ 5, 5 ]
‣ LeastEigenvalueFromSRGParameters( [v, k, a, b] ) | ( function ) |
Returns: An integer or an element of a cyclotomic field.
Given feasible strongly regular graph parameters [v, k, a, b] this function returns the least eigenvalue of a strongly regular graph with parameters (v,k,a,b). If the eigenvalue is integer, the object returned is an integer. If the eigenvalue is irrational, the object returned lies in a cyclotomic field.
gap> LeastEigenvalueFromSRGParameters([5,2,0,1]);
E(5)^2+E(5)^3
gap> LeastEigenvalueFromSRGParameters([10,3,0,1]);
-2
‣ SecondEigenvalueFromSRGParameters( [v, k, a, b] ) | ( function ) |
Returns: An integer or an element of a cyclotomic field.
Given feasible strongly regular graph parameters [v, k, a, b], this function returns the second largest eigenvalue of a strongly regular graph with parameters (v,k,a,b). If the eigenvalue is integer, the object returned is an integer. If the eigenvalue is irrational, the object returned lies in a cyclotomic field.
gap> SecondEigenvalueFromSRGParameters([5,2,0,1]);
E(5)+E(5)^4
gap> SecondEigenvalueFromSRGParameters([10,3,0,1]);
1
‣ LeastEigenvalueMultiplicity( [v, k, a, b] ) | ( operation ) |
Returns: An integer.
Given feasible strongly regular graph parameters [v, k, a, b] this function returns the multiplicity of the least eigenvalue of a strongly regular graph with parameters (v,k,a,b).
gap> LeastEigenvalueMultiplicity([16,9,4,6]);
6
gap> LeastEigenvalueMultiplicity([25,12,5,6]);
12
‣ SecondEigenvalueMultiplicity( [v, k, a, b] ) | ( operation ) |
Returns: An integer.
Given feasible strongly regular graph parameters [v, k, a, b] this function returns the multiplicity of the second eigenvalue of a strongly regular graph with parameters (v,k,a,b).
gap> SecondEigenvalueMultiplicity([16,9,4,6]);
9
gap> SecondEigenvalueMultiplicity([25,12,5,6]);
12
generated by GAPDoc2HTML