<?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>
<title>GAP (AGT) - Chapter 2: Regular graphs</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="chap2"  onload="jscontent()">


<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap1.html">[Previous Chapter]</a>    <a href="chap3.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap2_mj.html">[MathJax on]</a></p>
<p><a id="X7DE253B0786AF3CD" name="X7DE253B0786AF3CD"></a></p>
<div class="ChapSects"><a href="chap2.html#X7DE253B0786AF3CD">2 <span class="Heading">Regular graphs</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X7DE253B0786AF3CD">2.1 <span class="Heading">Regular graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X805E414884F74B4E">2.1-1 RGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X8506FD9C84FD1D88">2.1-2 IsRG</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X859728CC8117B2C1">2.1-3 IsFeasibleRGParameters</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X852488AC7C59D75F">2.2 <span class="Heading">Edge-regular graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7CF02EC580D221E8">2.2-1 ERGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X811393AE7E816FFA">2.2-2 IsERG</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X8578C5A7817E2754">2.2-3 IsFeasibleERGParameters</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap2.html#X87124C8C7EBA8FA4">2.3 <span class="Heading">Strongly regular graphs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X7DBE09557F9F6ABD">2.3-1 SRGParameters</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X80992E527F0BD206">2.3-2 IsSRG</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap2.html#X8436E237851A17BC">2.3-3 IsFeasibleSRGParameters</a></span>
</div></div>
</div>

<h3>2 <span class="Heading">Regular graphs</span></h3>

<p>In this chapter we give functions used to identify graphs with various regularity properties and determine their parameters.</p>

<p><a id="X7DE253B0786AF3CD" name="X7DE253B0786AF3CD"></a></p>

<h4>2.1 <span class="Heading">Regular graphs</span></h4>

<p>A graph <span class="SimpleMath">Γ</span> is <em>regular</em> with <em>parameters</em> <span class="SimpleMath">(v,k)</span> if <span class="SimpleMath">Γ</span> is simple and undirected, it has order <span class="SimpleMath">v</span>, and every vertex of <span class="SimpleMath">Γ</span> has degree <span class="SimpleMath">k</span>.</p>

<p><a id="X805E414884F74B4E" name="X805E414884F74B4E"></a></p>

<h5>2.1-1 RGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; RGParameters</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 regular graph parameters of <var class="Arg">gamma</var>. If <var class="Arg">gamma</var> is not a regular graph, the function returns <code class="keyw">fail</code>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=EdgeOrbitsGraph(Group((2,3,4,5)),[[1,2],[2,1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RGParameters(gamma);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=HammingGraph(3,4);;                              </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">RGParameters(gamma);</span>
[ 64, 9 ]
    
  </pre></div>

<p><a id="X8506FD9C84FD1D88" name="X8506FD9C84FD1D88"></a></p>

<h5>2.1-2 IsRG</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsRG</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 regular graph, and <code class="keyw">false</code> otherwise.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=NullGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRG(gamma);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=EdgeOrbitsGraph(Group((2,3,4,5)),[[1,2],[2,1]]);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRG(gamma);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=TriangularGraph(6);;                             </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsRG(gamma);</span>
true
    
  </pre></div>

<p><a id="X859728CC8117B2C1" name="X859728CC8117B2C1"></a></p>

<h5>2.1-3 IsFeasibleRGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsFeasibleRGParameters</code>( [<var class="Arg">v</var>, <var class="Arg">k</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 2, <var class="Arg">[v,k]</var>, this function returns <code class="keyw">true</code> if <span class="SimpleMath">( <var class="Arg">v</var>, <var class="Arg">k</var> )</span> is a feasible parameter tuple for a regular graph. Otherwise, the function returns <code class="keyw">false</code>.</p>

<p>The tuple <span class="SimpleMath">(v, k)</span> is a <em>feasible</em> parameter tuple for a regular graph if it satisfies the following well-known conditions:</p>


<ul>
<li><p><span class="SimpleMath">v>k≥ 0</span>;</p>

</li>
<li><p><span class="SimpleMath">2</span> divides <span class="SimpleMath">vk</span>.</p>

</li>
</ul>
<p>Any regular graph must have parameters that satisfy these conditions (see <a href="chapBib.html#biBBCN_1989">[BCN89]</a>).</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleRGParameters([15,9]);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleRGParameters([16,9]);</span>
true
    
  </pre></div>

<p><a id="X852488AC7C59D75F" name="X852488AC7C59D75F"></a></p>

<h4>2.2 <span class="Heading">Edge-regular graphs</span></h4>

<p>A graph <span class="SimpleMath">Γ</span> is <em>edge-regular</em> with <em>parameters</em> <span class="SimpleMath">(v,k,a)</span> if it is regular with parameters <span class="SimpleMath">(v,k)</span>, it has at least one edge, and every pair of adjacent vertices have exactly <span class="SimpleMath">a</span> common neighbours.</p>

<p><a id="X7CF02EC580D221E8" name="X7CF02EC580D221E8"></a></p>

<h5>2.2-1 ERGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; ERGParameters</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 edge-regular graph parameters of <var class="Arg">gamma</var>. If <var class="Arg">gamma</var> is not an edge-regular graph, the function returns <code class="keyw">fail</code>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=NullGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ERGParameters(gamma);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=JohnsonGraph(7,3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">ERGParameters(gamma);</span>
[ 35, 12, 5 ]
    
  </pre></div>

<p><a id="X811393AE7E816FFA" name="X811393AE7E816FFA"></a></p>

<h5>2.2-2 IsERG</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsERG</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 an edge-regular graph, and <code class="keyw">false</code> otherwise.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=NullGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsERG(gamma);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=JohnsonGraph(7,3);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsERG(gamma);</span>
true
    
  </pre></div>

<p><a id="X8578C5A7817E2754" name="X8578C5A7817E2754"></a></p>

<h5>2.2-3 IsFeasibleERGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsFeasibleERGParameters</code>( [<var class="Arg">v</var>, <var class="Arg">k</var>, <var class="Arg">a</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 3, <var class="Arg">[v,k,a]</var>, this function returns <code class="keyw">true</code> if <span class="SimpleMath">( <var class="Arg">v, k, a</var> )</span> is a feasible parameter tuple for an edge-regular graph. Otherwise, the function returns <code class="keyw">false</code>.</p>

<p>The tuple <span class="SimpleMath">( v, k, a )</span> is a <em>feasible</em> parameter tuple for an edge-regular graph if it satisfies the following well-known conditions:</p>


<ul>
<li><p><span class="SimpleMath">(v,k)</span> is a feasible regular graph parameter tuple;</p>

</li>
<li><p><span class="SimpleMath">k>a≥ 0</span>;</p>

</li>
<li><p><span class="SimpleMath">2</span> divides <span class="SimpleMath">ka</span> and <span class="SimpleMath">6</span> divides <span class="SimpleMath">vka</span>;</p>

</li>
<li><p><span class="SimpleMath">v-2k+a ≥ 0</span>.</p>

</li>
</ul>
<p>Any edge-regular graph must have parameters which satisfy these conditions (see <a href="chapBib.html#biBBCN_1989">[BCN89]</a>).</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleERGParameters([15,9,6]);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleERGParameters([16,9,4]);</span>
true
    
  </pre></div>

<p><a id="X87124C8C7EBA8FA4" name="X87124C8C7EBA8FA4"></a></p>

<h4>2.3 <span class="Heading">Strongly regular graphs</span></h4>

<p>A graph <span class="SimpleMath">Γ</span> is <em>strongly regular</em> with <em>parameters</em> <span class="SimpleMath">(v,k,a,b)</span> if it is edge-regular with parameters <span class="SimpleMath">(v,k,a)</span>, it has at least one pair of distinct non-adjacent vertices, and every pair of distinct non-adjacent vertices have exactly <span class="SimpleMath">b</span> common neighbours.</p>

<p><a id="X7DBE09557F9F6ABD" name="X7DBE09557F9F6ABD"></a></p>

<h5>2.3-1 SRGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; SRGParameters</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 strongly regular graph parameters of <var class="Arg">gamma</var>. If <var class="Arg">gamma</var> is not a strongly regular graph, the function returns <code class="keyw">fail</code>.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=CompleteGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SRGParameters(gamma);</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=JohnsonGraph(5,3);;            </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">SRGParameters(gamma);</span>
[ 10, 6, 3, 4 ]
    
  </pre></div>

<p><a id="X80992E527F0BD206" name="X80992E527F0BD206"></a></p>

<h5>2.3-2 IsSRG</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsSRG</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 strongly regular graph, and <code class="keyw">false</code> otherwise.</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=CompleteGraph(Group(()),5);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSRG(gamma);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">gamma:=JohnsonGraph(5,3);;         </span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsSRG(gamma);</span>
true
    
  </pre></div>

<p><a id="X8436E237851A17BC" name="X8436E237851A17BC"></a></p>

<h5>2.3-3 IsFeasibleSRGParameters</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; IsFeasibleSRGParameters</code>( [<var class="Arg">v</var>, <var class="Arg">k</var>, <var class="Arg">a</var>, <var class="Arg">b</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 4, <var class="Arg">[v,k,a,b]</var>, this function returns <code class="keyw">true</code> if <span class="SimpleMath">( <var class="Arg">v, k, a, b</var> )</span> is a feasible parameter tuple for a strongly regular graph. Otherwise, this function returns <code class="keyw">false</code>.</p>

<p>The tuple <span class="SimpleMath">(v,k,a,b)</span> is a <em>feasible</em> parameter tuple for a strongly regular graph if it satisfies the following well-known 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">k≥ b</span>;</p>

</li>
<li><p><span class="SimpleMath">(v-k-1)b = k(k-a-1)</span>;</p>

</li>
<li><p><span class="SimpleMath">v-2-2k+b ≥ 0</span>;</p>

</li>
<li><p>the formulae for the multiplicities of the eigenvalues of a strongly regular graph with these parameters evaluate to positive integers (see <a href="chapBib.html#biBBH_2011">[BH11]</a>).</p>

</li>
</ul>
<p>Any strongly regular graph must have parameters which satisfy these conditions (see <a href="chapBib.html#biBBCN_1989">[BCN89]</a>).</p>


<div class="example"><pre>
    
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleSRGParameters([15,9,4,7]);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFeasibleSRGParameters([10,3,0,1]);</span>
true
    
  </pre></div>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap1.html">[Previous Chapter]</a>    <a href="chap3.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.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>