TOPICS
Search

Labeled Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
LabeledGraphTypes

A labeled graph is a graph whose graph vertices carry distinct labels. For a finite undirected simple graph G=(V,E), V is a set of graph vertices and E is a set of 2-subsets of V representing its graph edges. Given a graph vertex set V_n={1,2,...,n}, the number of vertex-labeled graphs is given by 2^(n(n-1)/2). Two graphs G and H with graph vertices V_n={1,2,...,n} are said to be isomorphic if there is a permutation p of V_n such that {u,v} is in the set of graph edges E(G) iff {p(u),p(v)} is in the set of graph edges E(H).

LabeledGraphs

The counts below are for finite undirected simple graphs on a specified graph vertex set. The total number of (not necessarily connected) labeled n-node graphs for n=1, 2, ... is given by 1, 2, 8, 64, 1024, 32768, ... (OEIS A006125; illustrated above), and the numbers of connected labeled graphs on n-nodes are given by the logarithmic transform of the preceding sequence, 1, 1, 4, 38, 728, 26704, ... (OEIS A001187; Sloane and Plouffe 1995, p. 19).

The numbers of graph vertices in all labeled graphs of orders n=1, 2, ... are 1, 4, 24, 256, 5120, 196608, ... (OEIS A095340), while the numbers of graph edges are 0, 1, 12, 192, 5120, 245760, ... (OEIS A095351), the latter of which has closed-form

e(n)=n(n-1)2^(n(n-1)/2-2).

See also

15 Puzzle, Connected Graph, Cordial Graph, Edge-Graceful Graph, Edge-Ordered Graph, Elegant Graph, Graceful Graph, Graph, Harmonious Graph, Labeled Digraph, Labeled Tree, Local Antimagic Labeling, Magic Graph, Oriented Graph, Taylor's Condition, Unlabeled Graph, Weighted Tree

Explore with Wolfram|Alpha

References

Cahit, I. "Homepage for the Graph Labelling Problems and New Results." http://www.emu.edu.tr/~cahit/CORDIAL.htm.Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin., Dynamic Survey DS6, Oct. 30, 2025. https://doi.org/10.37236/27.Gilbert, E. N. "Enumeration of Labeled Graphs." Canad. J. Math. 8, 405-411, 1956.Harary, F. "Labeled Graphs." Graph Theory. Reading, MA: Addison-Wesley, pp. 10 and 178-180, 1994.Harary, F. and Palmer, E. M. "Labeled Enumeration." Ch. 1 in Graphical Enumeration. New York: Academic Press, pp. 1-31, 1973.Sloane, N. J. A. Sequences A001187/M3671, A006125/M1897, A095340 and A095351 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.

Referenced on Wolfram|Alpha

Labeled Graph

Cite this as:

Weisstein, Eric W. "Labeled Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LabeledGraph.html

Subject classifications