 | ||
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.
Contents
- Frequency partitions of Eulerian graphs
- Frequency partition of trees Hamiltonian graphs tournaments and hypegraphs
- Unsolved problems in frequency partitions
- References
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.
Frequency partitions of Eulerian graphs
For a frequency partition p = f1 + f2 + ... + fk of an integer p > 1, its graphic degree sequence is denoted as ((d1)f1,(d2)f2, (d3)f3, ..., (dk) fk) where degrees di's are different and fi ≥ fj for i < j. Bhat-Nayak et al. (1979) showed that a partition of p with k parts, k ≤ integral part of
Frequency partition of trees, Hamiltonian graphs, tournaments and hypegraphs
The frequency partitions of families of graphs such as trees, Hamiltonian graphs directed graphs and tournaments and to k-uniform hypergraphs. have been characterized.
Unsolved problems in frequency partitions
The frequency partitions of the following families of graphs have not yet been characterized: