In this chapter we give methods to investigate regular induced subgraphs of regular graphs.
Let Γ be a graph, and consider a subset U of its vertices. The induced subgraph of Γ on U, Γ[U], is the graph with vertex set U, and vertices in Γ[U] are adjacent if and only if they are adjacent in Γ.
In this section, we introduce some bounds on regular induced subgraphs of regular graphs, which depend on the spectrum of the graph.
Let Γ be a graph. A coclique, or independent set, of Γ is a subset of vertices for which each pair of distinct vertices are non-adjacent. A clique of Γ is a subset of vertices for which each pair of distinct vertices are adjacent.
‣ HoffmanCocliqueBound( gamma ) | ( operation ) |
‣ HoffmanCocliqueBound( parms ) | ( operation ) |
Returns: An integer.
Given a non-null regular graph gamma, this function returns the Hoffman coclique bound of gamma.
Given feasible strongly regular graph parameters parms, this function returns the Hoffman coclique bound of a strongly regular graph with parameters parms.
Let Γ be a non-null regular graph with parameters (v,k) and least eigenvalue s. The Hoffman coclique bound, or ratio bound of Γ, is defined as
\delta=\lfloor\left(\frac{v}{k-s}\right)\rfloor.
It is known that any coclique in Γ must contain at most δ vertices (see [BH11]).
gap> HoffmanCocliqueBound(HammingGraph(3,5));
25
gap> HoffmanCocliqueBound(HammingGraph(2,5));
5
gap> parms:=SRGParameters(HammingGraph(2,5));
[ 25, 8, 3, 2 ]
gap> HoffmanCocliqueBound(parms);
5
‣ HoffmanCliqueBound( gamma ) | ( operation ) |
‣ HoffmanCliqueBound( parms ) | ( operation ) |
Returns: An integer.
Given a non-null, non-complete regular graph gamma, this function returns the Hoffman clique bound of gamma.
Given feasible strongly regular graph parameters parms, this function returns the Hoffman clique bound of a strongly regular graph with parameters parms.
Let Γ be a non-null, non-complete regular graph. The Hoffman clique bound of Γ, is defined as the Hoffman coclique bound of its complement (see HoffmanCocliqueBound (4.1-1)). It is known that the Hoffman clique bound is an upper bound on the number of vertices in any clique of Γ (see [BH11]). Note that in the case that Γ is a strongly regular graph, this function returns the value of the well-known Delsarte-Hoffman clique bound (see [Del73]).
gap> gamma:=EdgeOrbitsGraph(CyclicGroup(IsPermGroup,15),[[1,2],[2,1]]);;
gap> HoffmanCliqueBound(gamma);
2
gap> gamma:=JohnsonGraph(7,2);;
gap> HoffmanCliqueBound(gamma);
6
gap> parms:=SRGParameters(gamma);
[ 21, 10, 5, 4 ]
gap> HoffmanCliqueBound(parms);
6
‣ HaemersRegularUpperBound( gamma, d ) | ( operation ) |
‣ HaemersRegularUpperBound( parms, d ) | ( operation ) |
Returns: An integer.
Given a non-null regular graph gamma and non-negative integer d, this function returns the Haemers upper bound on d-regular induced subgraphs of gamma.
Given feasible strongly regular graph parameters parms and non-negative integer d, this function returns the Haemers upper bound on d-regular induced subgraphs of a strongly regular graph with parameters parms.
Let Γ be a non-null regular graph with parameters (v,k) and least eigenvalue s and let d be a non-negative integer. The Haemers upper bound on d-regular induced subgraphs of Γ, is defined as
\delta=\lfloor\left(\frac{v(d-s)}{k-s}\right)\rfloor.
It is known that any d-regular induced subgraph in Γ has order at most δ (see [Eva20]).
gap> HaemersRegularUpperBound(SimsGerwitzGraph(),3);
28
gap> HaemersRegularUpperBound([56,10,0,2],0);
16
‣ HaemersRegularLowerBound( gamma, d ) | ( operation ) |
‣ HaemersRegularLowerBound( parms, d ) | ( operation ) |
Returns: An integer.
Given a connected regular graph gamma and non-negative integer d, this function returns the Haemers lower bound on d-regular induced subgraphs of gamma.
Given the parameters of a connected strongly regular graph, parms, and non-negative integer d, this function returns the Haemers lower bound on d-regular induced subgraphs of a strongly regular graph with parameters parms.
Let Γ be a connected regular graph with parameters (v,k) and second eigenvalue r and let d be a non-negative integer. The Haemers lower bound on d-regular induced subgraphs of Γ, is defined as
\delta=\lfloor\left(\frac{v(d-r)}{k-r}\right)\rfloor.
It is known that any d-regular induced subgraph in Γ has order at least δ (see [Eva20]).
gap> HaemersRegularLowerBound(HoffmanSingletonGraph(),4);
20
gap> HaemersRegularLowerBound([50,7,0,1],3);
10
In this section, we introduce functions related to the block intersection polynomials, defined in [Soi10]. If you would like to know more about the properties of these polynomials, see [Soi10], [Soi15] and [GS16].
‣ CliqueAdjacencyPolynomial( parms, x, y ) | ( function ) |
Returns: A polynomial.
Given feasible edge-regular graph parameters parms and indeterminates x,y, this function returns the clique adjacency polynomial with respect to the parameters parms and indeterminates x,y, defined in [Soi15].
Let Γ be an edge-regular graph with parameters (v,k,a). The clique adjacency polynomial of Γ is defined as
C(x,y):=x(x+1)(v-y)-2xy(k-y+1)+y(y-1)(a-y+2).
gap> x:=Indeterminate(Rationals,"x");
x
gap> y:=Indeterminate(Rationals,"y");
y
gap> CliqueAdjacencyPolynomial([21,8,3],x,y);
-x^2*y-y^3+21*x^2-x*y+8*y^2+21*x-23*y
‣ CliqueAdjacencyBound( parms ) | ( function ) |
Returns: An integer.
Given feasible edge-regular graph parameters parms, this function returns the clique adjacency bound with respect to the parameters parms, defined in [Soi10].
Let Γ be an edge-regular graph with parameters (v,k,a), and let C be its corresponding clique adjacency poylnomial (see CliqueAdjacencyPolynomial (4.2-1)). The clique adjacency bound of Γ is defined as the smallest integer y≥ 2 such that there exists an integer m for which C(m,y+1) < 0. It is known that the clique adjacency bound is an upper bound on the number of vertices in any clique of Γ.
gap> CliqueAdjacencyBound([16,6,2]);
4
‣ RegularAdjacencyPolynomial( parms, x, y, d ) | ( function ) |
Returns: A polynomial.
Given feasible strongly regular graph parameters parms and indeterminates x,y,d, this function returns the regular adjacency polynomial with respect to the parameters parms and indeterminates x,y,d, as defined in [Eva20].
Let Γ be a strongly regular graph with parameters (v,k,a,b). The regular adjacency polynomial of Γ is defined as
R(x,y,d):=x(x+1)(v-y)-2xyk+(2x+a-b+1)yd+y(y-1)b-yd^{2}.
gap> RegularAdjacencyPolynomial([16,6,2,2],"x","y","d");
-x^2*y+2*x*y*d-y*d^2+16*x^2-x*y+2*y^2+y*d+4*x-2*y
‣ RegularAdjacencyUpperBound( parms, d ) | ( function ) |
Returns: An integer.
Given strongly regular graph parameters parms and non-negative integer d, this function returns the regular adjacency upper bound with respect to the parameters parms and integer d, defined in [Eva20].
Let Γ be a strongly regular graph with parameters (v,k,a,b), and let R be its corresponding regular adjacency poylnomial (see RegularAdjacencyPolynomial (4.2-3)). For fixed d, the regular adjacency upper bound of Γ is defined as the largest integer d+1≤ y≤ v such that for all integers m, we have R(m,y,d) ≥ 0 if such a y exists, and 0 otherwise. It is known that the regular adjacency upper bound is an upper bound on the number of vertices in any d-regular induced subgraph of Γ.
gap> RegularAdjacencyUpperBound([56,10,0,2],3);
28
‣ RegularAdjacencyLowerBound( parms, d ) | ( function ) |
Returns: An integer.
Given the parameters of a connected strongly regular graph, parms, and non-negative integer d, this function returns the regular adjacency lower bound with respect to the parameters parms and integer d, defined in [Eva20].
Let Γ be a strongly regular graph with parameters (v,k,a,b), and let R be its corresponding regular adjacency poylnomial (see RegularAdjacencyPolynomial (4.2-3)). For fixed d, the regular adjacency lower bound of Γ is defined as the smallest integer d+1≤ y≤ v such that for all integers m, we have R(m,y,d) ≥ 0 if such a y, and v+1 otherwise. It is known that the regular adjacency lower bound is a lower bound on the number of vertices in any d-regular induced subgraph of Γ.
gap> RegularAdjacencyLowerBound([50,7,0,1],2);
5
In this section we give functions to investigate regular sets, with a focus on regular sets in strongly regular graphs.
Let Γ be a graph and U be a subset of its vertices. Then U is m-regular if every vertex in V(Γ)backslash U is adjacent to the same number m>0 of vertices in U. In this case we say that U has nexus m.
The set U is a (d,m)-regular set if U is an m-regular set and Γ[U] is a d-regular graph. Then we call (d,m) the regular set parameters of U.
‣ Nexus( gamma, U ) | ( function ) |
Returns: An integer or fail.
Given a graph gamma and a subset U of its vertices, this function returns the nexus of U. If U is not an m-regular set for some m>0, the function returns fail.
gap> Nexus(SquareLatticeGraph(5),[1,2,3,4,6]);
fail
gap> Nexus(SquareLatticeGraph(5),[1,2,3,4,5]);
1
‣ RegularSetParameters( gamma, U ) | ( function ) |
Returns: A list or fail.
Given a graph gamma and a subset U of its vertices, this function returns a list [d,m] such that U is a (d,m)-regular set. If U is not an (d,m)-regular set for some d,m, the function returns fail.
gap> RegularSetParameters(SquareLatticeGraph(5),[6,11,16,21]);
fail
gap> RegularSetParameters(SquareLatticeGraph(5),[1,6,11,16,21]);
[ 4, 1 ]
‣ IsRegularSet( gamma, U, opt ) | ( function ) |
Returns: true or false.
Given a graph gamma and a subset U of its vertices, this function returns true if U is a regular set, and false otherwise.
The input opt should take a boolean value true or false. This option effects the output of the function in the following way.
truethis function will return true if and only if U is a (d,m)-regular set for some d,m.
falsethis function will return true if and only if U is a m-regular set for some m.
gap> IsRegularSet(HoffmanSingletonGraph(),[11..50],false);
true
gap> IsRegularSet(HoffmanSingletonGraph(),[11..50],true);
false
‣ RegularSetSRGParameters( parms, d ) | ( function ) |
Returns: A list.
Given feasible strongly regular graph parameters parms and non-negative integer d, this function returns a list of pairs [s,m] with the following properties:
(d,m) are feasible regular set parameters for a strongly regular graph with parameters parms.
s is the order of any (d,m)-regular set in a strongly regular graph with parameters parms.
Let Γ be a strongly regular graph with parameters (v,k,a,b) and let R be its corresponding regular adjacency polynomial (see RegularAdjacencyPolynomial (4.2-3)). Then the tuple (d,m) is a feasible regular set parameter tuple for Γ if d,m are non-negative integers and there exists a positive integer s such that
R(m-1,s,d)=R(m,s,d)=0.
It is known that any (d,m)-regular set of size s in Γ must satisfy the above conditions (see [Eva20]).
gap> RegularSetSRGParameters([16,6,2,2],4);
[ [ 8, 2 ], [ 12, 6 ] ]
In this section, we give functions to investigate regular cliques in edge-regular graphs.
A clique S in Γ is m-regular, for some m>0, if S is an m-regular set. A graph Γ is a Neumaier graph with parameters (v,k,a;s,m) if it is edge-regular with parameters (v,k,a), and Γ contains an m-regular clique of size s. For more information on Neumaier graphs, see [Eva20].
‣ NGParameters( gamma ) | ( function ) |
Returns: A list or fail.
Given a graph gamma, this function returns the Neumaier graph parameters of gamma. If gamma is not a Neumaier graph, the function returns fail.
gap> NGParameters(HigmanSimsGraph());
fail
gap> NGParameters(TriangularGraph(10));
[ [ 45, 16, 8, 9, 2 ] ]
‣ IsNG( gamma ) | ( function ) |
Returns: true or false.
Given a graph gamma, this function returns true if gamma is a Neumaier graph, and false otherwise.
gap> IsNG(HammingGraph(3,7));
false
gap> IsNG(HammingGraph(2,7));
true
‣ IsFeasibleNGParameters( [v, k, a, s, m] ) | ( function ) |
Returns: true or false.
Given a list of integers of length 5, [v,k,a,s,m], this function returns true if ( v,k,a;s,m ) is a feasible parameter tuple for a Neumaier graph. Otherwise, the function returns false.
The tuple ( v, k, a; s, m ) is a feasible parameter tuple for a Neumaier graph if it satisfies the following conditions:
(v,k,a) is a feasible edge-regular graph parameter tuple;
0<m≤ s and 2≤ s≤ a+2;
(v-s)m=(k-s+1)s;
(k-s+1)(m-1)=(a-s+2)(s-1).
Any Neumaier graph must have parameters which satisfy these conditions (see [Eva20]).
gap> IsFeasibleNGParameters([35,16,6,5,2]);
true
gap> IsFeasibleNGParameters([37,18,8,5,2]);
false
‣ RegularCliqueERGParameters( parms ) | ( function ) |
Returns: A list.
Given feasible edge-regular graph parameters parms=[v,k,a], this function returns a list of pairs [s,m], such that (v,k,a;s,m) are feasible Neumaier graph parameters (as defined in IsFeasibleNGParameters (4.4-3)).
gap> RegularCliqueERGParameters([8,7,6]);
[ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 4, 4 ], [ 5, 5 ], [ 6, 6 ], [ 7, 7 ] ]
gap> RegularCliqueERGParameters([8,6,4]);
[ [ 4, 3 ] ]
gap> RegularCliqueERGParameters([16,9,4]);
[ [ 4, 2 ] ]
generated by GAPDoc2HTML