#14619: Test if a graph is distance-regular
---------------------------------+----------------------------------
Reporter: ncohen | Owner: jason, ncohen, rlm
Type: enhancement | Status: closed
Priority: major | Milestone: sage-5.12
Component: graph theory | Resolution: fixed
Keywords: distance | Merged in: sage-5.12.beta5
Authors: Nathann Cohen | Reviewers: Frédéric Chapoton
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+----------------------------------
Comment (by dimpase):
An example of a graph on 12 vertices which satisfies the wrong definition
here, but is not distance-regular, can be constructed using GRAPE (a
package of GAP included in Sage). It's vertex-transitive (and even edge-
transitive) bipartite graph of diameter 3, which is not distance-regular.
Some vertices (e.g. 1 and 6) at distance 2 from each other have 4 common
neighbours, and some (e.g. 1 and 2) only 2 common neighbours, whereas this
must be a constant across all distance 2 pairs.
Here is the adjacency list (say for a doctest) of this graph (vertices
from 1 to 12):
{{{
[ [ 8, 9, 10, 11 ],
[ 7, 9, 10, 12 ],
[ 7, 8, 11, 12 ],
[ 7, 8, 11, 12 ],
[ 7, 9, 10, 12 ],
[ 8, 9, 10, 11 ],
[ 2, 3, 4, 5 ],
[ 1, 3, 4, 6 ],
[ 1, 2, 5, 6 ],
[ 1, 2, 5, 6 ],
[ 1, 3, 4, 6 ],
[ 2, 3, 4, 5 ] ]
}}}
and this is the GAP computation
{{{
$ sage -gap
...
gap> LoadPackage("grape");
gap> gamma := JohnsonGraph(4,2);;
gap> B:=BipartiteDouble(gamma);;
gap> GlobalParameters(B);
[ [ 0, 0, 4 ], [ 1, 0, 3 ], [ -1, 0, -1 ], [ 4, 0, 0 ] ]
gap> a:=AutGroupGraph(B);;
gap> Orbits(a,[1..12]);
[ [ 1, 2, 7, 5, 3, 8, 12, 4, 6, 11, 9, 10 ] ]
gap> ha:=Stabilizer(a,1);;
gap> Orbits(ha,[1..12]);
[ [ 1 ], [ 2, 5, 3, 4 ], [ 6 ], [ 7, 12 ], [ 8, 9, 10, 11 ] ]
gap> List([1..12],x->Adjacency(B,x));
[ [ 8, 9, 10, 11 ], [ 7, 9, 10, 12 ], [ 7, 8, 11, 12 ], [ 7, 8, 11, 12 ],
[ 7, 9, 10, 12 ], [ 8, 9, 10, 11 ], [ 2, 3, 4, 5 ], [ 1, 3, 4, 6 ],
[ 1, 2, 5, 6 ], [ 1, 2, 5, 6 ], [ 1, 3, 4, 6 ], [ 2, 3, 4, 5 ] ]
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/14619#comment:27>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
