At this page we introduce some terminology.


  1. First we explain the definition of a 'triangle free strongly regular graph':
    1. Triangle free means that there is no cycle of length 3 in the graph.

    2. The degree of a vertex is the number of graph edges which touch the vertex.

    3. A regular graph is a graph in which every vertex has the same degree.

    4. A regular graph G is strongly regular if there exist integers &lambda, &mu so that every pair of adjacent vertices have exactly &lambda common neighbors, and every pair of nonadjacent vertices have exactly &mu common neighbors.

      To eliminate degeneracies, we shall further assume that &mu &ge 1 . If G is k-regular and the number of vertices |V(G)| = n , then we say that G is a (n,k,&lambda,&mu) strongly regular graph.

      A useful remark is that triangle free means nothing more than &lambda = 0



  2. Some other definitions:
    1. The diameter of a graph is the length of the "longest shortest path" between any two graph vertices of a graph.

    2. The girth is the length of the shortest cycle in a graph (if no cycle exist, the girth is not defined). Remark: triangle free is equivalent with the restriction 'girth > 3'.

    3. A clique in an (undirected) graph is a subset of its vertices such that every two vertices in the subset are connected by an edge (source: Wikipedia).



  3. Also a few definitions about Moore graphs:
    1. A Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound 1+d\sum_{i=0}^{k-1}(d-1)^i .

      An equivalent definition of a Moore graph is that it is a graph of diameter k with girth 2k + 1.

    2. A Moore graph of type (v,g) is a regular graph of vertex degree v>2 and girth g that contains the maximum possible number of nodes, namely:
    (g-4)/2
    1 +  (v-1) (g/2-1) + v &sum (v-1)r   for g even,
    r=0
    n(v,g) =  
    (g-3)/2
    1 + v &sum (v-1)r for g odd.
    r=0



  4. About distance-regular and strongly regular graph:
    1. A connected graph G is distance-regular if for any vertices x and y of G and any integers i, j=0, 1, ... d (where d is the graph diameter), the number of vertices at distance i from x and distance j from y depends only on i, j, and the graph distance between x and y, independently of the choice of x and y.

    2. In particular, a distance-regular graph is a graph for which there exist integers bi, ci, i=0,...,d such that for any two vertices x,y in G and distance i=d(x,y), there are exactly ci neighbors of y in G(i-1)(x) and bi neighbors of y in G(i+1)(x), where Gi(x) is the set of vertices y of G with d(x,y)=i (Brouwer et al. 1989, p. 434). The array of integers characterizing a distance-regular graph is known as its intersection array.

    3. A regular graph G is strongly regular if there exist integers &lambda, &mu so that every pair of adjacent vertices have exactly &lambda common neighbors, and every pair of nonadjacent vertices have exactly &mu common neighbors.

      To eliminate degeneracies, we shall further assume that &mu &ge 1. If G is k-regular and the number of vertices |V(G)| = n, then we say that

      G is a (n,k,&lambda,&mu) strongly regular graph.

Note:

Nested Menu

Favourite Links