Simple Graph (original) (raw)

Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology

Alphabetical Index New in MathWorld

SimpleGraph

A simple graph, also called a strict graph (Tutte 1998, p. 2), is an unweighted, undirected graph containing no graph loops or multiple edges (Gibbons 1985, p. 2; West 2000, p. 2; Bronshtein and Semendyayev 2004, p. 346). A simple graph may be either connected or disconnected.

Unless stated otherwise, the unqualified term "graph" usually refers to a simple graph. A simple graph with multiple edges is sometimes called a multigraph (Skiena 1990, p. 89).

SimpleGraphs

The number of nonisomorphic simple graphs on nodes can be given by NumberOfGraphs[_n_] in the Wolfram Language package Combinatorica` , and the values for n=1 , 2, ... are 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, ... (OEIS A000088; see above figure). King and Palmer (cited in Read 1981) have calculated S_n up to n=24 , for which

	(1)

There appears to be no standard term for a simple graph on edges, although the words "polynema" (Kyrmse) and "polyedge" (Muñiz 2011) have been proposed for -edge connected graphs.

All simple graphs on nodes can be enumerated using ListGraphs[_n_] in the Wolfram Language package Combinatorica` and a precomputed list on up to n=7 vertices is available via GraphData[_n_]. A much more efficient enumeration can be done using the program geng (part of nauty) by B. McKay. However, since the order in which graphs are returned by the geng program changes as a function of time as improvements are made, the canonical ordering given on McKay's website is used here and in GraphData.

A graph may be tested in the Wolfram Languageto see if it is a simple graph using SimpleGraphQ[_g_].

A polynomial

	(2)

that enumerates the number of distinct graphs with nodes (where g_(pq) is the number of graphs on nodes with edges) can be found using a rather complicated application of the Pólya enumeration theorem. This procedure gives the counting polynomial as

	(3)

where S_p^((2)) is the pair group that acts on the 2-subsets of {1,2,...,p} , which is given by

| $Z(S_p^((2)))=1/(p!)sum_((j))h_(j)product_(n=0)^(\|_(p-1)/2_|)a_(2n+1)^(nj_(2n+1)+(2n+1)(j_(2n+1); 2))product_(n=1)^(|_p/2_|)[(a_na_(2n))^(n-1)]^(j_(2n))a_(2n)^(2n(j_(2n); 2))product_(q=1)^pproduct_(r=q+1)^pa_(LCM(q,r))^(j_qj_rGCD(q,r))$ | (4) | | ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | --- |

(Harary 1994, p. 185). Here, |_x_| is the floor function, (n; m) is a binomial coefficient, LCM is the least common multiple, GCD is the greatest common divisor, thesum (j) is over all exponent vectors of the cycle index Z(S_p) of the symmetric group S_p , and h_(j) is the coefficient of the term with exponent vector j_p in Z(S_p) . The first few cyclic indices Z(S_p^((2))) are

These can be given by the command PairGroup[SymmetricGroup[_n_]], _x_] in the Wolfram Language package Combinatorica` . Normalizing by and letting a_i=1+x^i then gives g_p(x) , the first few of which are

These polynomials are implemented as GraphPolynomial[n, _x_] in the Wolfram Language package Combinatorica` .

Plugging in x=1 to any of these gives the total number of simple graphs on nodes. All simple graphs on nodes with edges can be enumerated using the command ListGraphs[n,_k_] in the Wolfram Language package Combinatorica` . The number of nonisomorphic simple graphs on nodes with edges can be given by NumberOfGraphs[_n_,_k_] in the Wolfram Language package Combinatorica` , The array for the number of graphs g_(nk) having nodes and edges is given below (OEIS A008406).

$n\k$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	1
2	1	1
3	1	1	1	1
4	1	1	2	3	2	1	1
5	1	1	2	4	6	6	6	4	2	1	1
6	1	1	2	5	9	15	21	24	24	21	15	9	5	2	1	1

The mean number of edges for graphs with vertices is given by n(n-1)/4 , giving the sequence for n=1 , 2, ... of 0, 1/2, 3/2, 3, 5, 15/2, 21/2, 14, 18, ... (OEISA064038 and A014695). This means that the total number of edges in the distinct graphs of orders n=1 , 2, ... are 0, 1, 6, 33, 170, 1170, 10962, 172844, 4944024, 270116280, ... (OEIS A086314).

SimpleGraphTypes

The figure above shows the first few members of various common classes of simple graphs: the antiprism graph, complete graph, cycle graph, empty graph, gear graph, prism graph, star graph, and wheel graph.

Explore with Wolfram|Alpha

References

Bronshtein, I. N. and Semendyayev, K. A. Handbook of Mathematics, 4th ed. New York: Springer-Verlag, 2004.Gibbons, A. Algorithmic Graph Theory. Cambridge, England: Cambridge University Press, 1985.Harary, F. "The Number of Linear, Directed, Rooted, and Connected Graphs." Trans. Amer. Math. Soc. 78, 445-463, 1955.Harary, F. "Enumeration of Graphs." In Graph Theory. Reading, MA: Addison-Wesley, pp. 185-187, 1994.ISGCI: Information System on Graph Class Inclusions v2.0. "List of Small Graphs."http://www.graphclasses.org/smallgraphs.html.Kyrmse, R. "Polynemas." http://www.oocities.org/kyrmse/POLIN-E.htm.McKay, B. "Simple Graphs." http://cs.anu.edu.au/~bdm/data/graphs.html.Muñiz, A. "Puzzle Zapper Blog: Pentaedges." http://puzzlezapper.com/blog/2011/04/pentaedges/. Apr. 10, 2011.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.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 89, 1990.Sloane, N. J. A. SequencesA000088/M1253, A008406,A014695, A064038, and A086314 in "The On-Line Encyclopedia of Integer Sequences."Steinbach, P. Field Guide to Simple Graphs. Albuquerque, NM: Design Lab, 1990.Tutte, W. T. Graph Theory as I Have Known It. Oxford, England: Oxford University Press, 1998.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Referenced on Wolfram|Alpha

Simple Graph

Cite this as:

Weisstein, Eric W. "Simple Graph." FromMathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SimpleGraph.html

Simple Graph (original) (raw)

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Subject classifications