Goto Chapter: Top 1 2 3 4 5 Bib Ind

### 4 Regular induced subgraphs

In this chapter we give methods to investigate regular induced subgraphs of regular graphs.

Let $$\Gamma$$ be a graph, and consider a subset $$U$$ of its vertices. The induced subgraph of $$\Gamma$$ on $$U$$, $$\Gamma[U]$$, is the graph with vertex set $$U$$, and vertices in $$\Gamma[U]$$ are adjacent if and only if they are adjacent in $$\Gamma$$.

#### 4.1 Spectral bounds

In this section, we introduce some bounds on regular induced subgraphs of regular graphs, which depend on the spectrum of the graph.

Let $$\Gamma$$ be a graph. A coclique, or independent set, of $$\Gamma$$ is a subset of vertices for which each pair of distinct vertices are non-adjacent. A clique of $$\Gamma$$ is a subset of vertices for which each pair of distinct vertices are adjacent.

##### 4.1-1 HoffmanCocliqueBound
 ‣ 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 $$\Gamma$$ be a non-null regular graph with parameters $$(v,k)$$ and least eigenvalue $$s$$. The Hoffman coclique bound, or ratio bound of $$\Gamma$$, is defined as

$\delta=\lfloor\left(\frac{v}{k-s}\right)\rfloor.$

It is known that any coclique in $$\Gamma$$ must contain at most $$\delta$$ 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



##### 4.1-2 HoffmanCliqueBound
 ‣ 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 $$\Gamma$$ be a non-null, non-complete regular graph. The Hoffman clique bound of $$\Gamma$$, 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 $$\Gamma$$ (see [BH11]). Note that in the case that $$\Gamma$$ 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



##### 4.1-3 HaemersRegularUpperBound
 ‣ 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 $$\Gamma$$ 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 $$\Gamma$$, is defined as

$\delta=\lfloor\left(\frac{v(d-s)}{k-s}\right)\rfloor.$

It is known that any $$d$$-regular induced subgraph in $$\Gamma$$ has order at most $$\delta$$ (see [Eva20]).


gap> HaemersRegularUpperBound(SimsGerwitzGraph(),3);
28
gap> HaemersRegularUpperBound([56,10,0,2],0);
16



##### 4.1-4 HaemersRegularLowerBound
 ‣ 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 $$\Gamma$$ 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 $$\Gamma$$, is defined as

$\delta=\lfloor\left(\frac{v(d-r)}{k-r}\right)\rfloor.$

It is known that any $$d$$-regular induced subgraph in $$\Gamma$$ has order at least $$\delta$$ (see [Eva20]).


gap> HaemersRegularLowerBound(HoffmanSingletonGraph(),4);
20
gap> HaemersRegularLowerBound([50,7,0,1],3);
10



#### 4.2 Block intersection polynomials and bounds

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 $$\Gamma$$ be an edge-regular graph with parameters $$(v,k,a)$$. The clique adjacency polynomial of $$\Gamma$$ 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
-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 $$\Gamma$$ 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 $$\Gamma$$ is defined as the smallest integer $$y\geq 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 $$\Gamma$$.


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 $$\Gamma$$ be a strongly regular graph with parameters $$(v,k,a,b)$$. The regular adjacency polynomial of $$\Gamma$$ is defined as

$R(x,y,d):=x(x+1)(v-y)-2xyk+(2x+a-b+1)yd+y(y-1)b-yd^{2}.$


-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 $$\Gamma$$ 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 $$\Gamma$$ is defined as the largest integer $$d+1\leq y\leq v$$ such that for all integers $$m$$, we have $$R(m,y,d) \geq 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 $$\Gamma$$.


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 $$\Gamma$$ 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 $$\Gamma$$ is defined as the smallest integer $$d+1\leq y\leq v$$ such that for all integers $$m$$, we have $$R(m,y,d) \geq 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 $$\Gamma$$.


5



#### 4.3 Regular sets

In this section we give functions to investigate regular sets, with a focus on regular sets in strongly regular graphs.

Let $$\Gamma$$ be a graph and $$U$$ be a subset of its vertices. Then $$U$$ is $$m$$-regular if every vertex in $$V(\Gamma)\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 $$\Gamma[U]$$ is a $$d$$-regular graph. Then we call $$(d,m)$$ the regular set parameters of $$U$$.

##### 4.3-1 Nexus
 ‣ 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



##### 4.3-2 RegularSetParameters
 ‣ 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 $$(\textit{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 ]



##### 4.3-3 IsRegularSet
 ‣ 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.

true

this function will return true if and only if U is a $$(d,m)$$-regular set for some $$d,m$$.

false

this 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



##### 4.3-4 RegularSetSRGParameters
 ‣ 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:

• $$(\textit{d,m})$$ are feasible regular set parameters for a strongly regular graph with parameters parms.

• s is the order of any $$(\textit{d,m})$$-regular set in a strongly regular graph with parameters parms.

Let $$\Gamma$$ 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 $$\Gamma$$ 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 $$\Gamma$$ must satisfy the above conditions (see [Eva20]).


gap> RegularSetSRGParameters([16,6,2,2],4);
[ [ 8, 2 ], [ 12, 6 ] ]



#### 4.4 Neumaier graphs

In this section, we give functions to investigate regular cliques in edge-regular graphs.

A clique $$S$$ in $$\Gamma$$ is $$m$$-regular, for some $$m>0$$, if $$S$$ is an $$m$$-regular set. A graph $$\Gamma$$ is a Neumaier graph with parameters $$(v,k,a;s,m)$$ if it is edge-regular with parameters $$(v,k,a)$$, and $$\Gamma$$ contains an $$m$$-regular clique of size $$s$$. For more information on Neumaier graphs, see [Eva20].

##### 4.4-1 NGParameters
 ‣ 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 ] ]



##### 4.4-2 IsNG
 ‣ 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



##### 4.4-3 IsFeasibleNGParameters
 ‣ 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 $$( \textit{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\leq s$$ and $$2\leq s\leq 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



##### 4.4-4 RegularCliqueERGParameters
 ‣ 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 $$(\textit{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 ] ]


Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML