| products/Sources/formale Sprachen/GAP/pkg/agt/doc/chap4_mj.html |
 |
<?xml version= "1.0" encoding= "UTF-8"?>
<! DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
< html xmlns= "http://www.w3.org/1999/xhtml" xml:lang= "en">
< head>
< script type= "text/javascript"
src= "https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</ script>
< title>GAP (AGT) - Chapter 4: Regular induced subgraphs</ title>
< meta http-equiv= "content-type" content= "text/html; charset=UTF-8" />
< meta name= "generator" content= "GAPDoc2HTML" />
< link rel= "stylesheet" type= "text/css" href= "manual.css" />
< script src= "manual.js" type= "text/javascript"></ script>
< script type= "text/javascript">overwriteStyle();</ script>
</ head>
< body class= "chap4" onload= "jscontent()">
< div class= "chlinktop">< span class= "chlink1">Goto Chapter: </ span>< a href= "chap0_mj.html">Top< /a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap3_mj.html">[Previous Chapter]</a> <a href="chap5_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap4.html">[MathJax off]</a></p>
<p><a id="X86A779307874D0E1" name="X86A779307874D0E1"></a></p>
<div class="ChapSects"><a href="chap4_mj.html#X86A779307874D0E1">4 <span class="Heading">Regular induced subgraphs</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X7B76CADC80E1DD61">4.1 <span class="Heading">Spectral bounds</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X7FFE042C868779BD">4.1-1 HoffmanCocliqueBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X78B8D3BC8298F747">4.1-2 HoffmanCliqueBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X8445E33B83D28DBC">4.1-3 HaemersRegularUpperBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X7E6591D284767760">4.1-4 HaemersRegularLowerBound</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X7F08702D7DA7B1CA">4.2 <span class="Heading">Block intersection polynomials and bounds</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X869E8B3B7F6D6AC6">4.2-1 CliqueAdjacencyPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X799A64687F196C08">4.2-2 CliqueAdjacencyBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X854314CE811C1B65">4.2-3 RegularAdjacencyPolynomial</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X7F0F9D8E7ED699D7">4.2-4 RegularAdjacencyUpperBound</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X852FEF678096CF3E">4.2-5 RegularAdjacencyLowerBound</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X7A9F9FFF818BF0D9">4.3 <span class="Heading">Regular sets</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X7970E9C2876A3E60">4.3-1 Nexus</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X79ED00CD7B158DA5">4.3-2 RegularSetParameters</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X8006908D7DFDC04B">4.3-3 IsRegularSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X7EB5DA8E7910EF87">4.3-4 RegularSetSRGParameters</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4_mj.html#X829DEC4F81279CA7">4.4 <span class="Heading">Neumaier graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X80CF6B4F85B75E8A">4.4-1 NGParameters</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X7B61884985AED829">4.4-2 IsNG</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X850602CB7B5977A1">4.4-3 IsFeasibleNGParameters</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4_mj.html#X7990FD6785E2FADF">4.4-4 RegularCliqueERGParameters</a></span>
</div></div>
</div>
<h3>4 <span class="Heading">Regular induced subgraphs</span></h3>
<p>In this chapter we give methods to investigate regular induced subgraphs of regular graphs.</p>
<p>Let <span class="SimpleMath">\(\Gamma\)</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">\(\Gamma\)</span> on <span class="SimpleMath">\(U\)</span>, <span class="SimpleMath">\(\Gamma[U]\)</span>, is the graph with vertex set <span class="SimpleMath">\(U\)</span>, and vertices in <span class="SimpleMath">\(\Gamma[U]\)</span> are adjacent if and only if they are adjacent in <span class="SimpleMath">\(\Gamma\)</span>.</p>
<p><a id="X7B76CADC80E1DD61" name="X7B76CADC80E1DD61"></a></p>
<h4>4.1 <span class="Heading">Spectral bounds</span></h4>
<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">\(\Gamma\)</span> be a graph. A <em>coclique</em>, or <em>independent set</em>, of <span class="SimpleMath">\(\Gamma\)</span> is a subset of vertices for which each pair of distinct vertices are non-adjacent. A <em>clique</em> of <span class="SimpleMath">\(\Gamma\)</span> is a subset of vertices for which each pair of distinct vertices are adjacent.</p>
<p><a id="X7FFE042C868779BD" name="X7FFE042C868779BD"></a></p>
<h5>4.1-1 HoffmanCocliqueBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; HoffmanCocliqueBound</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; HoffmanCocliqueBound</code>( <var class="Arg">parms</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An integer.</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">\(\Gamma\)</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">\(\Gamma\)</span>, is defined as</p>
<p class="center">\[\delta=\lfloor\left(\frac{v}{k-s}\right)\rfloor.\]</p>
<p>It is known that any coclique in <span class="SimpleMath">\(\Gamma\)</span> must contain at most <span class="SimpleMath">\(\delta\)</span> vertices (see <a href="chapBib_mj.html#biBBH_2011">[BH11]</a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">HoffmanCocliqueBound(HammingGraph(3,5));</span>
25
<span class="GAPprompt">gap></span> <span class="GAPinput">HoffmanCocliqueBound(HammingGraph(2,5)); </span>
5
<span class="GAPprompt">gap></span> <span class="GAPinput">parms:=SRGParameters(HammingGraph(2,5));</span>
[ 25, 8, 3, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">HoffmanCocliqueBound(parms);</span>
5
</pre></div>
<p><a id="X78B8D3BC8298F747" name="X78B8D3BC8298F747"></a></p>
<h5>4.1-2 HoffmanCliqueBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; HoffmanCliqueBound</code>( <var class="Arg">gamma</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; HoffmanCliqueBound</code>( <var class="Arg">parms</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An integer.</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">\(\Gamma\)</span> be a non-null, non-complete regular graph. The <em>Hoffman clique bound</em> of <span class="SimpleMath">\(\Gamma\)</span>, is defined as the Hoffman coclique bound of its complement (see <code class="func">HoffmanCocliqueBound</code> (<a href="chap4_mj.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">\(\Gamma\)</span> (see <a href="chapBib_mj.html#biBBH_2011">[BH11]</a>). Note that in the case that <span class="SimpleMath">\(\Gamma\)</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_mj.html#biBD_1975">[Del73]</a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=EdgeOrbitsGraph(CyclicGroup(IsPermGroup,15),[[1,2],[2,1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">HoffmanCliqueBound(gamma);</span>
2
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=JohnsonGraph(7,2);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">HoffmanCliqueBound(gamma);</span>
6
<span class="GAPprompt">gap></span> <span class="GAPinput">parms:=SRGParameters(gamma);</span>
[ 21, 10, 5, 4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">HoffmanCliqueBound(parms);</span>
6
</pre></div>
<p><a id="X8445E33B83D28DBC" name="X8445E33B83D28DBC"></a></p>
<h5>4.1-3 HaemersRegularUpperBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; HaemersRegularUpperBound</code>( <var class="Arg">gamma</var>, <var class="Arg">d</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; HaemersRegularUpperBound</code>( <var class="Arg">parms</var>, <var class="Arg">d</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An integer.</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">\(\Gamma\)</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">\(\Gamma\)</span>, is defined as</p>
<p class="center">\[\delta=\lfloor\left(\frac{v(d-s)}{k-s}\right)\rfloor.\]</p>
<p>It is known that any <span class="SimpleMath">\(d\)</span>-regular induced subgraph in <span class="SimpleMath">\(\Gamma\)</span> has order at most <span class="SimpleMath">\(\delta\)</span> (see <a href="chapBib_mj.html#biBE_2020">[Eva20]</a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">HaemersRegularUpperBound(SimsGerwitzGraph(),3);</span>
28
<span class="GAPprompt">gap></span> <span class="GAPinput">HaemersRegularUpperBound([56,10,0,2],0); </span>
16
</pre></div>
<p><a id="X7E6591D284767760" name="X7E6591D284767760"></a></p>
<h5>4.1-4 HaemersRegularLowerBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; HaemersRegularLowerBound</code>( <var class="Arg">gamma</var>, <var class="Arg">d</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; HaemersRegularLowerBound</code>( <var class="Arg">parms</var>, <var class="Arg">d</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: An integer.</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 <var class="Arg">parms</var>.</p>
<p>Let <span class="SimpleMath">\(\Gamma\)</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">\(\Gamma\)</span>, is defined as</p>
<p class="center">\[\delta=\lfloor\left(\frac{v(d-r)}{k-r}\right)\rfloor.\]</p>
<p>It is known that any <span class="SimpleMath">\(d\)</span>-regular induced subgraph in <span class="SimpleMath">\(\Gamma\)</span> has order at least <span class="SimpleMath">\(\delta\)</span> (see <a href="chapBib_mj.html#biBE_2020">[Eva20]</a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">HaemersRegularLowerBound(HoffmanSingletonGraph(),4);</span>
20
<span class="GAPprompt">gap></span> <span class="GAPinput">HaemersRegularLowerBound([50,7,0,1],3); </span>
10
</pre></div>
<p><a id="X7F08702D7DA7B1CA" name="X7F08702D7DA7B1CA"></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_mj.html#biBS_2010">[Soi10]</a>. If you would like to know more about the properties of these polynomials, see <a href="chapBib_mj.html#biBS_2010">[Soi10]</a>, <a href="chapBib_mj.html#biBS_2015">[Soi15]</a> and <a href="chapBib_mj.html#biBGS_2016">[GS16]</a>.</p>
<p><a id="X869E8B3B7F6D6AC6" name="X869E8B3B7F6D6AC6"></a></p>
<h5>4.2-1 CliqueAdjacencyPolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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_mj.html#biBS_2015">[Soi15]</a>.</p>
<p>Let <span class="SimpleMath">\(\Gamma\)</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">\(\Gamma\)</span> is defined as</p>
<p class="center">\[C(x,y):=x(x+1)(v-y)-2xy(k-y+1)+y(y-1)(a-y+2).\]</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=Indeterminate(Rationals,"x");</span>
x
<span class="GAPprompt">gap></span> <span class="GAPinput">y:=Indeterminate(Rationals,"y");</span>
y
<span class="GAPprompt">gap></span> <span class="GAPinput">CliqueAdjacencyPolynomial([21,8,3],x,y);</span>
-x^2*y-y^3+21*x^2-x*y+8*y^2+21*x-23*y
</pre></div>
<p><a id="X799A64687F196C08" name="X799A64687F196C08"></a></p>
<h5>4.2-2 CliqueAdjacencyBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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_mj.html#biBS_2010">[Soi10]</a>.</p>
<p>Let <span class="SimpleMath">\(\Gamma\)</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_mj.html#X869E8B3B7F6D6AC6"><span class="RefLink">4.2-1</span></a>)). The <em>clique adjacency bound</em> of <span class="SimpleMath">\(\Gamma\)</span> is defined as the smallest integer <span class="SimpleMath">\(y\geq 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">\(\Gamma\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">CliqueAdjacencyBound([16,6,2]);</span>
4
</pre></div>
<p><a id="X854314CE811C1B65" name="X854314CE811C1B65"></a></p>
<h5>4.2-3 RegularAdjacencyPolynomial</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; RegularAdjacencyPolynomial</code>( <var class="Arg">parms</var>, <var class="Arg">x</var>, <var class="Arg">y</var>, <var class="Arg">d</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A polynomial.</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_mj.html#biBE_2020">[Eva20]</a>.</p>
<p>Let <span class="SimpleMath">\(\Gamma\)</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">\(\Gamma\)</span> is defined as</p>
<p class="center">\[R(x,y,d):=x(x+1)(v-y)-2xyk+(2x+a-b+1)yd+y(y-1)b-yd^{2}.\]</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RegularAdjacencyPolynomial([16,6,2,2],"x","y","d");</span>
-x^2*y+2*x*y*d-y*d^2+16*x^2-x*y+2*y^2+y*d+4*x-2*y
</pre></div>
<p><a id="X7F0F9D8E7ED699D7" name="X7F0F9D8E7ED699D7"></a></p>
<h5>4.2-4 RegularAdjacencyUpperBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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_mj.html#biBE_2020">[Eva20]</a>.</p>
<p>Let <span class="SimpleMath">\(\Gamma\)</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_mj.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">\(\Gamma\)</span> is defined as the largest integer <span class="SimpleMath">\(d+1\leq y\leq v\)</span> such that for all integers <span class="SimpleMath">\(m\)</span>, we have <span class="SimpleMath">\(R(m,y,d) \geq 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">\(\Gamma\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RegularAdjacencyUpperBound([56,10,0,2],3);</span>
28
</pre></div>
<p><a id="X852FEF678096CF3E" name="X852FEF678096CF3E"></a></p>
<h5>4.2-5 RegularAdjacencyLowerBound</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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_mj.html#biBE_2020">[Eva20]</a>.</p>
<p>Let <span class="SimpleMath">\(\Gamma\)</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_mj.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">\(\Gamma\)</span> is defined as the smallest integer <span class="SimpleMath">\(d+1\leq y\leq v\)</span> such that for all integers <span class="SimpleMath">\(m\)</span>, we have <span class="SimpleMath">\(R(m,y,d) \geq 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">\(\Gamma\)</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RegularAdjacencyLowerBound([50,7,0,1],2);</span>
5
</pre></div>
<p><a id="X7A9F9FFF818BF0D9" name="X7A9F9FFF818BF0D9"></a></p>
<h4>4.3 <span class="Heading">Regular sets</span></h4>
<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">\(\Gamma\)</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(\Gamma)\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">\(\Gamma[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>
<p><a id="X7970E9C2876A3E60" name="X7970E9C2876A3E60"></a></p>
<h5>4.3-1 Nexus</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Nexus(SquareLatticeGraph(5),[1,2,3,4,6]);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">Nexus(SquareLatticeGraph(5),[1,2,3,4,5]);</span>
1
</pre></div>
<p><a id="X79ED00CD7B158DA5" name="X79ED00CD7B158DA5"></a></p>
<h5>4.3-2 RegularSetParameters</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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">\((\textit{d,m})\)</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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RegularSetParameters(SquareLatticeGraph(5),[6,11,16,21]); </span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">RegularSetParameters(SquareLatticeGraph(5),[1,6,11,16,21]);</span>
[ 4, 1 ]
</pre></div>
<p><a id="X8006908D7DFDC04B" name="X8006908D7DFDC04B"></a></p>
<h5>4.3-3 IsRegularSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsRegularSet</code>( <var class="Arg">gamma</var>, <var class="Arg">U</var>, <var class="Arg">opt</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> 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>
</dd>
</dl>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRegularSet(HoffmanSingletonGraph(),[11..50],false);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRegularSet(HoffmanSingletonGraph(),[11..50],true); </span>
false
</pre></div>
<p><a id="X7EB5DA8E7910EF87" name="X7EB5DA8E7910EF87"></a></p>
<h5>4.3-4 RegularSetSRGParameters</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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">\((\textit{d,m})\)</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">\((\textit{d,m})\)</span>-regular set in a strongly regular graph with parameters <var class="Arg">parms</var>.</p>
</li>
</ul>
<p>Let <span class="SimpleMath">\(\Gamma\)</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_mj.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">\(\Gamma\)</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="center">\[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">\(\Gamma\)</span> must satisfy the above conditions (see <a href="chapBib_mj.html#biBE_2020">[Eva20]</a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RegularSetSRGParameters([16,6,2,2],4);</span>
[ [ 8, 2 ], [ 12, 6 ] ]
</pre></div>
<p><a id="X829DEC4F81279CA7" name="X829DEC4F81279CA7"></a></p>
<h4>4.4 <span class="Heading">Neumaier graphs</span></h4>
<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">\(\Gamma\)</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">\(\Gamma\)</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">\(\Gamma\)</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_mj.html#biBE_2020">[Eva20]</a>.</p>
<p><a id="X80CF6B4F85B75E8A" name="X80CF6B4F85B75E8A"></a></p>
<h5>4.4-1 NGParameters</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">NGParameters(HigmanSimsGraph()); </span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">NGParameters(TriangularGraph(10));</span>
[ [ 45, 16, 8, 9, 2 ] ]
</pre></div>
<p><a id="X7B61884985AED829" name="X7B61884985AED829"></a></p>
<h5>4.4-2 IsNG</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNG(HammingGraph(3,7));</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsNG(HammingGraph(2,7));</span>
true
</pre></div>
<p><a id="X850602CB7B5977A1" name="X850602CB7B5977A1"></a></p>
<h5>4.4-3 IsFeasibleNGParameters</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; IsFeasibleNGParameters</code>( [<var class="Arg">v</var>, <var class="Arg">k</var>, <var class="Arg">a</var>, <var class="Arg">s</var>, <var class="Arg">m</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 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">\(( \textit{v,k,a;s,m} )\)</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\leq s\)</span> and <span class="SimpleMath">\(2\leq s\leq a+2\)</span>;</p>
</li>
<li><p><span class="SimpleMath">\((v-s)m=(k-s+1)s\)</span>;</p>
</li>
<li><p><span class="SimpleMath">\((k-s+1)(m-1)=(a-s+2)(s-1)\)</span>.</p>
</li>
</ul>
<p>Any Neumaier graph must have parameters which satisfy these conditions (see <a href="chapBib_mj.html#biBE_2020">[Eva20]</a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleNGParameters([35,16,6,5,2]);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleNGParameters([37,18,8,5,2]);</span>
false
</pre></div>
<p><a id="X7990FD6785E2FADF" name="X7990FD6785E2FADF"></a></p>
<h5>4.4-4 RegularCliqueERGParameters</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">an style='color: green'>8227; 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">\((\textit{v,k,a;s,m})\)</span> are feasible Neumaier graph parameters (as defined in <code class="func">IsFeasibleNGParameters</code> (<a href="chap4_mj.html#X850602CB7B5977A1"><span class="RefLink">4.4-3</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">RegularCliqueERGParameters([8,7,6]);</span>
[ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 4, 4 ], [ 5, 5 ], [ 6, 6 ], [ 7, 7 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RegularCliqueERGParameters([8,6,4]);</span>
[ [ 4, 3 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">RegularCliqueERGParameters([16,9,4]);</span>
[ [ 4, 2 ] ]
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap3_mj.html">[Previous Chapter]</a> <a href="chap5_mj.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
¤ Dauer der Verarbeitung: 0.21 Sekunden
¤
*© Formatika GbR, Deutschland
|
|