GraphTypes

A note on graph types

The connectivity of graphs is specified by a single number which is the decimal representation of a binary encoding of the connectivity matrix of the graph. For example, a fully-connected three-vertex graph would have a connectivity matrix:

   i j k
i    1 1
j  1   1
k  1 1 1

We leave the diagonal blank, as it is irrelevant for our purposes. This connectivity matrix is symmetric, so we need only look at the upper-right triangle:

   i j k
i    1 1
j      1
k      

Reading this off row by row, we get 111 in binary which is 7 in decimal. The star graph, with connections i-j and i-k has matrix

   i j k
i    1 1
j      0
k      

and binary representation 110 which is 6 in decimal. The following lists have been compiled by AA.

Three Vertex Graphs

3-vertex terms (ijk)

   Three possible links are
    (i-j)  (i-k)
           (j-k)

ID = (abc) = <math>a. 2^2 + b. 2^1 + c. 2^1</math>

• a=1 if (i-j) link exists. Otherwise 0.
• b=1 if (i-k) link exists
• c=1 if (j-k) link exists

2=(010)    ( i-k , j disconnected)
3=(011)    ( i-k-j        [chain]
4=(100)    (i-j, k disconnected)
5=(101)    (i-j-k)        [chain]
6=(110)    (i-j,i-k)      [Star-graphs]
7=(111)    (i-j,i-k,j-k)  [fully-connected]

Four Vertex Graphs

4-vertex terms (ijkl)

  6 possible links = (4 choose 2)
  (i-j) (i-k) (i-l)
        (j-k) (j-l)
              (k-l)

   (abcdef)

ID= <math>a. 2^5 + b. 2^4 +c. 2^3 +d. 2^2 + e. 2^1 + f. 2^0</math>

• a=1 implies (i-j) link exists
• b=1 (i-k) link
• c=1 (i-l)
• d=1 (j-k)
• e=1 (j-l)
• f=1 (k-l)

8 = (001000)
32= (100000)
33= (100001)
34= (100010)
35= (100011)
36= (100100)
37= (100101) (i-j,j-k,k-l)  [tree]
38= (100110) (i-j,j-k,j-l)  [tree]
39= (100111) (i-j,j-k,j-l,k-l)  [jkl cycle]
40= (101000) (i-j,i-l)  [k-not connected]
41= (101001) i-j,i-l,k-l            [tree]
42= (101010) (i-j,i-l,j-l)    [k not connected]
43= (101011) (i-j,i-l,j-l,k-l)  [ijl cycle]
44= (101100) (l-i-j-k)   [tree]
45= (101101) (i-j,i-l,j-k,k-l)  [4-cycle i-j-k-l-i]
46= (101110) (i-j,i-l,j-k,j-l)   [ijl cycle]
47= (101111) (i-j,i-l,j-k,j-l,k-l)  [ijl cycle and jkl cycle]
48= (110000) (i-j,i-k)   [l not connected]
49= (110001) (i-j,i-k,k-l)  [tree]
50= (110010) (i-j,i-k,j-l)  [tree]
51= (110011) (i-j,i-k,j-l,k-l)  [ijlk 4-cycle]
52= (110100) (i-j,i-k,j-k)   [3-vertex], l-not connected
53= (110101) (i-j,i-k,j-k,k-l)  [i-j-k-i 3 cycle and k-l 2-cycle]
54= (110110) (i-j,i-k,j-k,j-l)
55= (110111) (i-j,i-k,j-k,j-l,k-l)
56= (111000) [i-j,i-k,i-l] (star about i)
57= (111001) [i-j,i-k,i-l,k-l]  [star around i with 3 cycle i-k-l-i]
58= (111010) (i-j,i-k,i-l,j-l)
59= (111011) (i-j,i-k,i-l,j-l,k-l)
60= (111100) (i-j,i-k,i-l,j-k)  [Star around i with 3-cycle i-j-k-i]
61= (111101) (i-j,i-k,i-l,j-k,k-l] [star around i, and 2 3-cycles i-k-l-i and i -j-k-i ]
62= (111110) (i-j,i-k,i-l,j-k,j-l)
63= (111111) [fully connected]

The four-vertex trees are: 37,38,41,44,49,50,56

Five Vertex Graphs

5-vertex terms (ijklm) (5 choose 3)=10 possible links

  (i-j) (i-k) (i-l) (i-m)
        (j-k) (j-l) (j-m)
              (k-l) (k-m)
                    (l-m)

612=  1001100100  (i-j-k-l-i,i-m), 4-cycle about i, and i-m 2-cycle
613=  1001100101=2^9+2^6+2^5+2^2+1  (i-j-k-l-m-i)
836=  1101000100=(i-j,i-k,i-m,k-l)  [a 3-spoke star with 1 spoke as a chain]
837=  1101000101=(i-j,i-k,i-m,k-l,l-m)  [a 4-cycle and 2-cycle in a star, similar to 612]
897=  1110000001=(i-j,i-k,i-l,l-m)
960=  1111000000 (star about i)