Saturday, May 18, 2013

Weakly ordering vertex targets

Given a strongly connected directed graph G we can produce a weak order of the vertices of G based upon their proximity to a vertex G:
(= (targets-list G 0)
   [#{0} #{1 2} #{3}])
We can represent the shape of a targets list by enumerating the sizes of each target set which provides a useful graph invariant. By examining the cubic graphs of size 8 we see that not all regular graphs are eccentricity regular and not all graphs that are both regular graphs and eccentricity regular are distance regular. We further see that not all distance regular graphs are isomorphic.

No comments:

Post a Comment