- Source: 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.
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 identified; 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
(
p
−
1
)
/
2
{\displaystyle (p-1)/2}
is a frequency partition of a Eulerian graph and conversely.
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:
Line graphs
Bipartite graphs
References
External section
Berge, C. (1989), Hypergraphs, Combinatorics of Finite sets, Amsterdam: North-Holland, ISBN 0-444-87489-5