Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/agt/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 31.11.2022 mit Größe 37 kB image not shown  

Quelle  chap4_mj.html   Sprache: HTML

 
 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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">‣ 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>

100%


¤ Dauer der Verarbeitung: 0.19 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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.