Graph (Graph Theory)

A mathematical object composed of points known as Vertices or Nodes and lines connecting some (possibly empty) Subset of them, known as Edges. The study of graphs is known as Graph Theory. Graphs are 1-D Complexes, and there are always an Even number of Odd Nodes in a graph. The number of nonisomorphic graphs with $v$ Nodes is given by the Pólya Enumeration Theorem. The first few values for $v=1$, 2, ..., are 1, 2, 4, 11, 34, 156, 1044, ... (Sloane's A000088; see above figure).

Graph sums, differences, powers, and products can be defined, as can graph eigenvalues.

Before applying Pólya Enumeration Theorem, define the quantity

$$h_{\bf j} = {p!\over\prod_{i=1}^p i^{j_i}j_i!},$$ (1)

where $p!$ is the Factorial of $p$, and the related polynomial

$$Z_p(S)=\sum_{i} h_{{\bf j}_i} \prod_{k=1}^p {f_k}^{({\bf j}_i)_k},$$ (2)

where the ${\bf j}_i=(j_1, \ldots, j_p)_i$ are all of the $p$-Vectors satisfying

$$j_1+2j_2+3j_3+\ldots+p j_p=p.$$ (3)

For example, for $p=3$, the three possible values of ${\bf j}$ are

${\bf j}_1=(3,0,0), {\rm\ since\ } (1\cdot 3)+(2\cdot 0)+(3\cdot 0)=3,$
${\rm\ giving\ } h_{{\bf j}_1}={3!\over (1^3 3!)(2^0 0!)(3^0 0!)}=1\quad$	(4)
${\bf j}_2=(1,1,0), {\rm\ since\ } (1\cdot 1)+(2\cdot 1)+(3\cdot 0)=3,$
${\rm\ giving\ } h_{{\bf j}_2}={3!\over (1^1 1!)(2^1 1!)(3^0 0!)}=3,\quad$	(5)
${\bf j}_3=(0,0,1), {\rm\ since\ } (1\cdot 0)+(2\cdot 0)+(3\cdot 1)=3$
${\rm\ giving\ } h_{{\bf j}_3}={3!\over (1^0 0!)(2^0 0!)(3^1 1!)}=2.\quad$	(6)

Therefore,

$$Z_3(S) = {f_1}^3+3 {f_1} {f_2}+2 {f_3}.$$ (7)

For small $p$, the first few values of $Z_p(S)$ are given by

$$Z_2(S) = {f_1}^2+{f_2}$$ (8)

$$Z_3(S) = {f_1}^3+3 {f_1} {f_2}+2 {f_3}$$ (9)

$$Z_4(S) = {f_1}^4+6 {f_1}^2 {f_2}+3 {f_2}^2+8 {f_1} {f_3}+6 {f_4}$$ (10)

$$Z_5(S) = {f_1}^5+10 {f_1}^3 {f_2}+15 {f_1} {f_2}^2+20 {f_1}^2 {f_3}$$

$$\phantom{=} +20 {f_2} {f_3}+30 {f_1} {f_4}+24 {f_5}$$ (11)

$$Z_6(S) = {f_1}^6+15 {f_1}^4 {f_2}+45 {f_1}^2 {f_2}^2+15 {f_2}^3$$

$$\phantom{=} +40 {f_1}^3 {f_3}+120 {f_1} {f_2} {f_3}+40 {f_3}^2$$

$$\phantom{=} +90 {f_1}^2 {f_4}+90 {f_2} {f_4}+144 {f_1} {f_5}+120 {f_6}$$ (12)

$$Z_7(S) = {f_1}^7+21 {f_1}^5 {f_2}+105 {f_1}^3 {f_2}^2+105 {f_1} {f_2}^3$$

$$\phantom{=} +70 {f_1}^4 {f_3}+420 {f_1}^2 {f_2} {f_3}+210 {f_2}^2 {f_3}$$

$$\phantom{=} +280 {f_1} {f_3}^2+210 {f_1}^3 {f_4}+630 {f_1} {f_2} {f_4}$$

$$\phantom{=} +420 {f_3} {f_4}+504 {f_1}^2 {f_5}+504 {f_2} {f_5}$$

$$\phantom{=} +840 {f_1} {f_6}+ 720 {f_7}.$$ (13)

Application of the Pólya Enumeration Theorem then gives the formula

$Z(R)={1\over p!}\sum_{(j)} h_{\bf j}\prod_{n=0}^{\left\lfloor{(p-1)/2}\right\rfloor } {g_{2n+1}}^{n j_{2n+1}+(2n+1){j_{2n+1}\choose 2}}$
$\times\prod_{n=1}^{\left\lfloor{p/2}\right\rfloor } [(g_n g_{2n})^{n-1}]^{j_{2n}} {g_{2n}}^{2n {j_{2n}\choose 2}}$
$\times\prod_{q=1}^p \prod_{r=q+1}^p {g_{{\rm LCM}(q,r)}}^{j_q j_r {\rm GCD}(q,r)},\quad$	(14)

where $\left\lfloor{x}\right\rfloor$ is the Floor Function, ${n\choose m}$ is a Binomial Coefficient, LCM is the Least Common Multiple, GCD is the Greatest Common Divisor, and the Sum $(j)$ is over all ${\bf j}_i$ satisfying the sum identity described above. The first few generating functions $Z_p(R)$ are

$$Z_2(R) = 2 {g_1}$$ (15)

$$Z_3(R) = {g_1}^3+3 {g_1} {g_2}+2 {g_3}$$ (16)

$$Z_4(R) = {g_1}^6+9 {g_1}^2 {g_2}^2+8 {g_3}^2+6 {g_2} {g_4}$$ (17)

$$Z_5(R) = {g_1}^{10}+10 {g_1}^4 {g_2}^3+15 {g_1}^2 {g_2}^4+20 {g_1} {g_3}^3$$

$$\phantom{=} +30 {g_2} {g_4}^2+24 {g_5}^2+20 {g_1} {g_3} {g_6}$$ (18)

$$Z_6(R) = {g_1}^{15}+15 {g_1}^7 {g_2}^4+60 {g_1}^3 {g_2}^6+40 {g_1}^3 {g_3}^4$$

$$\phantom{=} +40 {g_3}^5+180 {g_1} {g_2} {g_4}^3+144 {g_5}^3$$

$$\phantom{=} +120 {g_1} {g_2} {g_3}^2 {g_6}+120 {g_3} {g_6}^2$$

$$Z_7(R) = {g_1}^{21}+21 {g_1}^{11} {g_2}^5+105 {g_1}^5 {g_2}^8$$ (19)

$$\phantom{=} +105 {g_1}^3 {g_2}^9+70 {g_1}^6 {g_3}^5+280 {g_3}^7$$

$$\phantom{=} +210 {g_1}^3 {g_2} {g_4}^4+630 {g_1} {g_2}^2 {g_4}^4$$

$$\phantom{=} +504 {g_1} {g_5}^4+420 {g_1}^2 {g_2}^2 {g_3}^3 {g_6}$$

$$\phantom{=} +210 {g_1}^2 {g_2}^2 g_3 {g_6}^2+840 g_3 {g_6}^3+720 {g_7}^3$$

$$\phantom{=} +504 g_1 {g_5}^2 g_{10}+ 420 g_2 g_3 g_4 g_{12}.$$ (20)

Letting $g_i=1+x^i$ then gives a Polynomial $S_i(x)$, which is a Generating Function for (i.e., the terms of $x^i$ give) the number of graphs with $i$ Edges. The total number of graphs having $i$ edges is $S_i(1)$. The first few $S_i(x)$ are

$$S_2 = 1+x$$ (21)

$$S_3 = 1+x+x^2+x^3$$ (22)

$$S_4 = 1+x+2 x^2+3 x^3+2 x^4+x^5+x^6$$ (23)

$$S_5 = 1+x+2 x^2+4 x^3+6 x^4+6 x^5+6 x^6$$

$$\phantom{=} +4 x^7+2 x^8+x^9+x^{10}$$ (24)

$$S_6 = 1+x+2 x^2+5 x^3+9 x^4+15 x^5$$

$$\phantom{=} +21 x^6 +24 x^7+24 x^8+21 x^9$$

$$\phantom{=} +15 x^{10}+ 9 x^{11}+ 5 x^{12}$$

$$\phantom{=} + 2 x^{13}+ x^{14}+ x^{15}$$ (25)

$$S_7 = 1+ x +2 x^2 +5 x^3 +10 x^4 +21 x^5$$

$$\phantom{=} +21 x^6+24 x^7+41 x^6+65 x^7+97 x^8$$

$$\phantom{=} + 131 x^9+148 x^{10}+148 x^{11}$$

$$\phantom{=} +131 x^{12}+97 x^{13}+65 x^{14}+41 x^{15}$$

$$\phantom{=} + 21 x^{16}+10 x^{17}+5 x^{18}+2 x^{19}+x^{20}+x^{21},$$ (26)

giving the number of graphs with $n$ nodes as 1, 2, 4, 11, 34, 156, 1044, ... (Sloane's A000088). King and Palmer (cited in Read 1981) have calculated $S_n$ up to $n=24$, for which

$S_{24}=195,704,906,302,078,447,922,174,862,416,\cdots$
$\cdots 726,256,004,122,075,267,063,365,754,368.\quad$	(27)

See also Bipartite Graph, Caterpillar Graph, Cayley Graph, Circulant Graph, Cocktail Party Graph, Comparability Graph, Complement Graph, Complete Graph, Cone Graph, Connected Graph, Coxeter Graph, Cubical Graph, de Bruijn Graph, Digraph, Directed Graph, Dodecahedral Graph, Euler Graph, Extremal Graph, Gear Graph, Graceful Graph, Graph Theory, Hanoi Graph, Harary Graph, Harmonious Graph, Hoffman-Singleton Graph, Icosahedral Graph, Interval Graph, Isomorphic Graphs, Labeled Graph, Ladder Graph, Lattice Graph, Matchstick Graph, Minor Graph, Moore Graph, Null Graph, Octahedral Graph, Path Graph, Petersen Graphs, Planar Graph, Random Graph, Regular Graph, Sequential Graph, Simple Graph, Star Graph, Subgraph, Supergraph, Superregular Graph, Sylvester Graph, Tetrahedral Graph, Thomassen Graph, Tournament, Triangular Graph, Turan Graph, Tutte's Graph, Universal Graph, Utility Graph, Web Graph, Wheel Graph

References

Bogomolny, A. ``Graph Puzzles.'' http://www.cut-the-knot.com/do_you_know/graphs2.html.

Fujii, J. N. Puzzles and Graphs. Washington, DC: National Council of Teachers, 1966.

Harary, F. ``The Number of Linear, Directed, Rooted, and Connected Graphs.'' Trans. Amer. Math. Soc. 78, 445-463, 1955.

Pappas, T. ``Networks.'' The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 126-127, 1989.

Read, R. ``The Graph Theorists Who Count--and What They Count.'' In The Mathematical Gardner (Ed. D. Klarner). Boston, MA: Prindle, Weber, and Schmidt, pp. 326-345, 1981.

Sloane, N. J. A. Sequence A000088/M1253 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and extended entry in Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.