Frequency Partition of A Graph

Frequency Partition Of A Graph

In graph theory, a discipline within mathematics, the frequency partition of a graph (simple graph) is a partition of its vertices grouped by their degree.For example, the degree sequence of the left-hand graph below is (3, 3, 3, 2, 2, 1) and its frequency partition is 6 = 3 + 2 + 1. This indicates that it has 3 vertices with some degree, 2 vertices with some other degree, and 1 vertex with a third degree. The degree sequence of the bipartite graph in the middle below is (3, 2, 2, 2, 2, 2, 1, 1, 1) and its frequency partition is 9 = 5 + 3 + 1. The degree sequence of the right-hand graph below is (3, 3, 3, 3, 3, 3, 2) and its frequency partition is 7 = 6 + 1.

  • A graph with frequency partition 6 = 3 + 2 + 1.

  • A bipartite graph with frequency partition 9 = 5 + 3 + 1.

  • A graph with frequency partition 7 = 6 + 1.

In general, there are many non-isomorphic graphs with a given frequency partition. A graph and its complement have the same frequency partition. For any partition p = f1 + f2 + ... + fk of an integer p > 1, other than p = 1 + 1 + 1 + ... + 1, there is at least one (connected) simple graph having this partition as its frequency partition.

Frequency partitions of various graph families are completely identifieds; frequency partitions of many families of graphs are not identified.

Read more about Frequency Partition Of A Graph:  Frequency Partitions of Eulerian Graphs, Frequency Partition of Trees, Hamiltonian Graphs, Tournaments and Hypegraphs, Unsolved Problems in Frequency Partitions

Famous quotes containing the words frequency and/or graph:

    “One is apt to be discouraged by the frequency with which Mr. Hardy has persuaded himself that a macabre subject is a poem in itself; that, if there be enough of death and the tomb in one’s theme, it needs no translation into art, the bold statement of it being sufficient.”
    —Rebecca West (1892–1983)

    “When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
    —Marshall McLuhan (1911–1980)