<p>In this chapter we give methods to investigate regular induced subgraphs of regular graphs.</p>
<p>Let <span class="SimpleMath">Γ</span> be a graph, and consider a subset <span class="SimpleMath">U</span> of its vertices. The <em>induced subgraph</em> of <span class="SimpleMath">Γ</span> on <span class="SimpleMath">U</span>, <span class="SimpleMath">Γ[U]</span>, is the graph with vertex set <span class="SimpleMath">U</span>, and vertices in <span class="SimpleMath">Γ[U]</span> are adjacent if and only if they are adjacent in <span class="SimpleMath">Γ</span>.</p>
<p>In this section, we introduce some bounds on regular induced subgraphs of regular graphs, which depend on the spectrum of the graph.</p>
<p>Let <span class="SimpleMath">Γ</span> be a graph. A <em>coclique</em>, or <em>independent set</em>, of <span class="SimpleMath">Γ</span> is a subset of vertices for which each pair of distinct vertices are non-adjacent. A <em>clique</em> of <span class="SimpleMath">Γ</span> is a subset of vertices for which each pair of distinct vertices are adjacent.</p>
<p>Given a non-null regular graph <var class="Arg">gamma</var>, this function returns the Hoffman coclique bound of <var class="Arg">gamma</var>.</p>
<p>Given feasible strongly regular graph parameters <var class="Arg">parms</var>, this function returns the Hoffman coclique bound of a strongly regular graph with parameters <var class="Arg">parms</var>.</p>
<p>Let <span class="SimpleMath">Γ</span> be a non-null regular graph with parameters <span class="SimpleMath">(v,k)</span> and least eigenvalue <span class="SimpleMath">s</span>. The <em>Hoffman coclique bound</em>, or <em>ratio bound</em> of <span class="SimpleMath">Γ</span>, is defined as</p>
<p>It is known that any coclique in <span class="SimpleMath">Γ</span> must contain at most <span class="SimpleMath">δ</span> vertices (see <a href="chapBib.html#biBBH_2011">[BH11]</a>).</p>
<p>Given a non-null, non-complete regular graph <var class="Arg">gamma</var>, this function returns the Hoffman clique bound of <var class="Arg">gamma</var>.</p>
<p>Given feasible strongly regular graph parameters <var class="Arg">parms</var>, this function returns the Hoffman clique bound of a strongly regular graph with parameters <var class="Arg">parms</var>.</p>
<p>Let <span class="SimpleMath">Γ</span> be a non-null, non-complete regular graph. The <em>Hoffman clique bound</em> of <span class="SimpleMath">Γ</span>, is defined as the Hoffman coclique bound of its complement (see <code class="func">HoffmanCocliqueBound</code> (<a href="chap4.html#X7FFE042C868779BD"><span class="RefLink">4.1-1</span></a>)). It is known that the Hoffman clique bound is an upper bound on the number of vertices in any clique of <span class="SimpleMath">Γ</span> (see <a href="chapBib.html#biBBH_2011">[BH11]</a>). Note that in the case that <span class="SimpleMath">Γ</span> is a strongly regular graph, this function returns the value of the well-known <em>Delsarte-Hoffman clique bound</em> (see <a href="chapBib.html#biBD_1975">[Del73]</a>).</p>
<p>Given a non-null regular graph <var class="Arg">gamma</var> and non-negative integer <var class="Arg">d</var>, this function returns the Haemers upper bound on <var class="Arg">d</var>-regular induced subgraphs of <var class="Arg">gamma</var>.</p>
<p>Given feasible strongly regular graph parameters <var class="Arg">parms</var> and non-negative integer <var class="Arg">d</var>, this function returns the Haemers upper bound on <var class="Arg">d</var>-regular induced subgraphs of a strongly regular graph with parameters <var class="Arg">parms</var>.</p>
<p>Let <span class="SimpleMath">Γ</span> be a non-null regular graph with parameters <span class="SimpleMath">(v,k)</span> and least eigenvalue <span class="SimpleMath">s</span> and let <span class="SimpleMath">d</span> be a non-negative integer. The <em>Haemers upper bound</em> on <span class="SimpleMath">d</span>-regular induced subgraphs of <span class="SimpleMath">Γ</span>, is defined as</p>
<p>It is known that any <span class="SimpleMath">d</span>-regular induced subgraph in <span class="SimpleMath">Γ</span> has order at most <span class="SimpleMath">δ</span> (see <a href="chapBib.html#biBE_2020">[Eva20]</a>).</p>
<p>Given a connected regular graph <var class="Arg">gamma</var> and non-negative integer <var class="Arg">d</var>, this function returns the Haemers lower bound on <var class="Arg">d</var>-regular induced subgraphs of <var class="Arg">gamma</var>.</p>
<p>Given the parameters of a connected strongly regular graph, <var class="Arg">parms</var>, and non-negative integer <var class="Arg">d</var>, this function returns the Haemers lower bound on <var class="Arg">d</var>-regular induced subgraphs of a strongly regular graph with parameters <varclass="Arg">parms</var>.</p>
<p>Let <span class="SimpleMath">Γ</span> be a connected regular graph with parameters <span class="SimpleMath">(v,k)</span> and second eigenvalue <span class="SimpleMath">r</span> and let <span class="SimpleMath">d</span> be a non-negative integer. The <em>Haemers lower bound</em> on <span class="SimpleMath">d</span>-regular induced subgraphs of <span class="SimpleMath">Γ</span>, is defined as</p>
<p>It is known that any <span class="SimpleMath">d</span>-regular induced subgraph in <span class="SimpleMath">Γ</span> has order at least <span class="SimpleMath">δ</span> (see <a href="chapBib.html#biBE_2020">[Eva20]</a>).</p>
<h4>4.2 <span class="Heading">Block intersection polynomials and bounds</span></h4>
<p>In this section, we introduce functions related to the block intersection polynomials, defined in <a href="chapBib.html#biBS_2010">[Soi10]</a>. If you would like to know more about the properties of these polynomials, see <a href="chapBib.html#biBS_2010">[Soi10]</a>, <a href="chapBib.html#biBS_2015">[Soi15]</a> and <a href="chapBib.html#biBGS_2016">[GS16]</a>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CliqueAdjacencyPolynomial</code>( <var class="Arg">parms</var>, <var class="Arg">x</var>, <var class="Arg">y</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A polynomial.</p>
<p>Given feasible edge-regular graph parameters <var class="Arg">parms</var> and indeterminates <var class="Arg">x,y</var>, this function returns the clique adjacency polynomial with respect to the parameters <var class="Arg">parms</var> and indeterminates <var class="Arg">x,y</var>, defined in <a href="chapBib.html#biBS_2015">[Soi15]</a>.</p>
<p>Let <span class="SimpleMath">Γ</span> be an edge-regular graph with parameters <span class="SimpleMath">(v,k,a)</span>. The <em>clique adjacency polynomial</em> of <span class="SimpleMath">Γ</span> is defined as</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CliqueAdjacencyBound</code>( <var class="Arg">parms</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An integer.</p>
<p>Given feasible edge-regular graph parameters <var class="Arg">parms</var>, this function returns the clique adjacency bound with respect to the parameters <var class="Arg">parms</var>, defined in <a href="chapBib.html#biBS_2010">[Soi10]</a>.</p>
<p>Let <span class="SimpleMath">Γ</span> be an edge-regular graph with parameters <span class="SimpleMath">(v,k,a)</span>, and let <span class="SimpleMath">C</span> be its corresponding clique adjacency poylnomial (see <code class="func">CliqueAdjacencyPolynomial</code> (<a href="chap4.html#X869E8B3B7F6D6AC6"><span class="RefLink">4.2-1</span></a>)). The <em>clique adjacency bound</em> of <span class="SimpleMath">Γ</span> is defined as the smallest integer <span class="SimpleMath">y≥ 2</span> such that there exists an integer <span class="SimpleMath">m</span> for which <span class="SimpleMath">C(m,y+1) < 0</span>. It is known that the clique adjacency bound is an upper bound on the number of vertices in any clique of <span class="SimpleMath">Γ</span>.</p>
<p>Given feasible strongly regular graph parameters <var class="Arg">parms</var> and indeterminates <var class="Arg">x,y,d</var>, this function returns the regular adjacency polynomial with respect to the parameters <var class="Arg">parms</var> and indeterminates <var class="Arg">x,y,d</var>, as defined in <a href="chapBib.html#biBE_2020">[Eva20]</a>.</p>
<p>Let <span class="SimpleMath">Γ</span> be a strongly regular graph with parameters <span class="SimpleMath">(v,k,a,b)</span>. The <em>regular adjacency polynomial</em> of <span class="SimpleMath">Γ</span> is defined as</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RegularAdjacencyUpperBound</code>( <var class="Arg">parms</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An integer.</p>
<p>Given strongly regular graph parameters <var class="Arg">parms</var> and non-negative integer <var class="Arg">d</var>, this function returns the regular adjacency upper bound with respect to the parameters <var class="Arg">parms</var> and integer <var class="Arg">d</var>, defined in <a href="chapBib.html#biBE_2020">[Eva20]</a>.</p>
<p>Let <span class="SimpleMath">Γ</span> be a strongly regular graph with parameters <span class="SimpleMath">(v,k,a,b)</span>, and let <span class="SimpleMath">R</span> be its corresponding regular adjacency poylnomial (see <code class="func">RegularAdjacencyPolynomial</code> (<a href="chap4.html#X854314CE811C1B65"><span class="RefLink">4.2-3</span></a>)). For fixed <span class="SimpleMath">d</span>, the <em>regular adjacency upper bound</em> of <span class="SimpleMath">Γ</span> is defined as the largest integer <span class="SimpleMath">d+1≤ y≤ v</span> such that for all integers <span class="SimpleMath">m</span>, we have <span class="SimpleMath">R(m,y,d) ≥ 0</span> if such a <span class="SimpleMath">y</span> exists, and 0 otherwise. It is known that the regular adjacency upper bound is an upper bound on the number of vertices in any <span class="SimpleMath">d</span>-regular induced subgraph of <span class="SimpleMath">Γ</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RegularAdjacencyLowerBound</code>( <var class="Arg">parms</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An integer.</p>
<p>Given the parameters of a connected strongly regular graph, <var class="Arg">parms</var>, and non-negative integer <var class="Arg">d</var>, this function returns the regular adjacency lower bound with respect to the parameters <var class="Arg">parms</var> and integer <var class="Arg">d</var>, defined in <a href="chapBib.html#biBE_2020">[Eva20]</a>.</p>
<p>Let <span class="SimpleMath">Γ</span> be a strongly regular graph with parameters <span class="SimpleMath">(v,k,a,b)</span>, and let <span class="SimpleMath">R</span> be its corresponding regular adjacency poylnomial (see <code class="func">RegularAdjacencyPolynomial</code> (<a href="chap4.html#X854314CE811C1B65"><span class="RefLink">4.2-3</span></a>)). For fixed <span class="SimpleMath">d</span>, the <em>regular adjacency lower bound</em> of <span class="SimpleMath">Γ</span> is defined as the smallest integer <span class="SimpleMath">d+1≤ y≤ v</span> such that for all integers <span class="SimpleMath">m</span>, we have <span class="SimpleMath">R(m,y,d) ≥ 0</span> if such a <span class="SimpleMath">y</span>, and <span class="SimpleMath">v+1</span> otherwise. It is known that the regular adjacency lower bound is a lower bound on the number of vertices in any <span class="SimpleMath">d</span>-regular induced subgraph of <span class="SimpleMath">Γ</span>.</p>
<p>In this section we give functions to investigate regular sets, with a focus on regular sets in strongly regular graphs.</p>
<p>Let <span class="SimpleMath">Γ</span> be a graph and <span class="SimpleMath">U</span> be a subset of its vertices. Then <span class="SimpleMath">U</span> is <span class="SimpleMath">m</span><em>-regular</em> if every vertex in <span class="SimpleMath">V(Γ)backslash U</span> is adjacent to the same number <span class="SimpleMath">m>0</span> of vertices in <span class="SimpleMath">U</span>. In this case we say that <span class="SimpleMath">U</span> has <em>nexus</em> <span class="SimpleMath">m</span>.</p>
<p>The set <span class="SimpleMath">U</span> is a <span class="SimpleMath">(d,m)</span><em>-regular set</em> if <span class="SimpleMath">U</span> is an <span class="SimpleMath">m</span>-regular set and <span class="SimpleMath">Γ[U]</span> is a <span class="SimpleMath">d</span>-regular graph. Then we call <span class="SimpleMath">(d,m)</span> the <em>regular set parameters</em> of <span class="SimpleMath">U</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Nexus</code>( <var class="Arg">gamma</var>, <var class="Arg">U</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An integer or <code class="keyw">fail</code>.</p>
<p>Given a graph <var class="Arg">gamma</var> and a subset <var class="Arg">U</var> of its vertices, this function returns the nexus of <var class="Arg">U</var>. If <var class="Arg">U</var> is not an <span class="SimpleMath">m</span>-regular set for some <span class="SimpleMath">m>0</span>, the function returns <code class="keyw">fail</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RegularSetParameters</code>( <var class="Arg">gamma</var>, <var class="Arg">U</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list or <code class="keyw">fail</code>.</p>
<p>Given a graph <var class="Arg">gamma</var> and a subset <var class="Arg">U</var> of its vertices, this function returns a list <var class="Arg">[d,m]</var> such that <var class="Arg">U</var> is a <span class="SimpleMath">(<var class="Arg">d,m</var>)</span>-regular set. If <var class="Arg">U</var> is not an <span class="SimpleMath">(d,m)</span>-regular set for some <span class="SimpleMath">d,m</span>, the function returns <code class="keyw">fail</code>.</p>
<p>Given a graph <var class="Arg">gamma</var> and a subset <var class="Arg">U</var> of its vertices, this function returns <code class="keyw">true</code> if <var class="Arg">U</var> is a regular set, and <code class="keyw">false</code> otherwise.</p>
<p>The input <var class="Arg">opt</var> should take a boolean value <code class="keyw">true</code> or <code class="keyw">false</code>. This option effects the output of the function in the following way.</p>
<dl>
<dt><strong class="Mark"><code class="keyw">true</code></strong></dt>
<dd><p>this function will return <code class="keyw">true</code> if and only if <var class="Arg">U</var> is a <span class="SimpleMath">(d,m)</span>-regular set for some <span class="SimpleMath">d,m</span>.</p>
</dd>
<dt><strong class="Mark"><code class="keyw">false</code></strong></dt>
<dd><p>this function will return <code class="keyw">true</code> if and only if <var class="Arg">U</var> is a <span class="SimpleMath">m</span>-regular set for some <span class="SimpleMath">m</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RegularSetSRGParameters</code>( <var class="Arg">parms</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list.</p>
<p>Given feasible strongly regular graph parameters <var class="Arg">parms</var> and non-negative integer <var class="Arg">d</var>, this function returns a list of pairs <var class="Arg">[s,m]</var> with the following properties:</p>
<ul>
<li><p><span class="SimpleMath">(<var class="Arg">d,m</var>)</span> are feasible regular set parameters for a strongly regular graph with parameters <var class="Arg">parms</var>.</p>
</li>
<li><p><var class="Arg">s</var> is the order of any <span class="SimpleMath">(<var class="Arg">d,m</var>)</span>-regular set in a strongly regular graph with parameters <var class="Arg">parms</var>.</p>
</li>
</ul>
<p>Let <span class="SimpleMath">Γ</span> be a strongly regular graph with parameters <span class="SimpleMath">(v,k,a,b)</span> and let <span class="SimpleMath">R</span> be its corresponding regular adjacency polynomial (see <code class="func">RegularAdjacencyPolynomial</code> (<a href="chap4.html#X854314CE811C1B65"><span class="RefLink">4.2-3</span></a>)). Then the tuple <span class="SimpleMath">(d,m)</span> is a <em>feasible regular set parameter tuple</em> for <span class="SimpleMath">Γ</span> if <span class="SimpleMath">d,m</span> are non-negative integers and there exists a positive integer <span class="SimpleMath">s</span> such that</p>
<p class="pcenter">R(m-1,s,d)=R(m,s,d)=0.</p>
<p>It is known that any <span class="SimpleMath">(d,m)</span>-regular set of size <span class="SimpleMath">s</span> in <span class="SimpleMath">Γ</span> must satisfy the above conditions (see <a href="chapBib.html#biBE_2020">[Eva20]</a>).</p>
<p>In this section, we give functions to investigate regular cliques in edge-regular graphs.</p>
<p>A clique <span class="SimpleMath">S</span> in <span class="SimpleMath">Γ</span> is <span class="SimpleMath">m</span><em>-regular</em>, for some <span class="SimpleMath">m>0</span>, if <span class="SimpleMath">S</span> is an <span class="SimpleMath">m</span>-regular set. A graph <span class="SimpleMath">Γ</span> is a <em>Neumaier graph</em> with <em>parameters</em> <span class="SimpleMath">(v,k,a;s,m)</span> if it is edge-regular with parameters <span class="SimpleMath">(v,k,a)</span>, and <span class="SimpleMath">Γ</span> contains an <span class="SimpleMath">m</span>-regular clique of size <span class="SimpleMath">s</span>. For more information on Neumaier graphs, see <a href="chapBib.html#biBE_2020">[Eva20]</a>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NGParameters</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list or <code class="keyw">fail</code>.</p>
<p>Given a graph <var class="Arg">gamma</var>, this function returns the Neumaier graph parameters of <var class="Arg">gamma</var>. If <var class="Arg">gamma</var> is not a Neumaier graph, the function returns <code class="keyw">fail</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsNG</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p>Given a graph <var class="Arg">gamma</var>, this function returns <code class="keyw">true</code> if <var class="Arg">gamma</var> is a Neumaier graph, and <code class="keyw">false</code> otherwise.</p>
<p>Given a list of integers of length 5, <var class="Arg">[v,k,a,s,m]</var>, this function returns <code class="keyw">true</code> if <span class="SimpleMath">( <var class="Arg">v,k,a;s,m</var> )</span> is a feasible parameter tuple for a Neumaier graph. Otherwise, the function returns <code class="keyw">false</code>.</p>
<p>The tuple <span class="SimpleMath">( v, k, a; s, m )</span> is a <em>feasible</em> parameter tuple for a Neumaier graph if it satisfies the following conditions:</p>
<ul>
<li><p><span class="SimpleMath">(v,k,a)</span> is a feasible edge-regular graph parameter tuple;</p>
</li>
<li><p><span class="SimpleMath">0<m≤ s</span> and <span class="SimpleMath">2≤ s≤ a+2</span>;</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RegularCliqueERGParameters</code>( <var class="Arg">parms</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list.</p>
<p>Given feasible edge-regular graph parameters <var class="Arg">parms</var><code class="code">=[v,k,a]</code>, this function returns a list of pairs <code class="code">[s,m]</code>, such that <span class="SimpleMath">(<var class="Arg">v,k,a;s,m</var>)</span> are feasible Neumaier graph parameters (as defined in <code class="func">IsFeasibleNGParameters</code> (<a href="chap4.html#X850602CB7B5977A1"><span class="RefLink">4.4-3</span></a>)).</p>
¤ Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.0.22Bemerkung:
(vorverarbeitet)
¤
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
