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. Note that the frequency partition is an unordered list which does not specify the degree of any of the graph's vertices.

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 = f₁ + f₂ + ... + f_k 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 Eulerian graphs

For a frequency partition p = f₁ + f₂ + ... + f_k of an integer p > 1, its graphic degree sequence is denoted as ((d₁)^f₁,(d₂)^f₂, (d₃)^f₃, ..., (d_k) ^f_k) where degrees d_i's are different. Bhat-Nayak et al. (1979) showed that a partition of p with k parts, k ≤ integral part of $(p-1)/2$ is a frequency partition of an Eulerian graph and conversley. For p = 5 + 4 + 3 + 2 + 2 + 1 + 1 + 1 + 1, the Eulerian degree sequence (18¹ ,16¹,14² ,12³, 10⁵, 8⁴, 6², 4¹, 2¹) is an example.

Frequency partition of tournaments and hypegraphs

The concept of frequency partitions can be extended to directed graphs and tournaments and to k-uniform hypergraphs.

References

• T. M. Rao, Frequency sequences in Graphs, Journal of Combinatorial Theory B 17 (1974), 19-21.
• Vasanti N. Bhat-Nayak, Ranjan N. Naik and S. B. Rao, Frequency partitions: forcibly pancyclic and forcibly nonhamiltonian degree sequences, Discrete Mathematics 20 (1977) 93-102.
• Berge , C., Hypergraphs, Combinatorics of Finite sets. Amsterdam: North-Holland 1989.