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 = 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 and f_i ≥ f_j for i < j. 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. The graphic degree sequences of the partitions are:

• For :$4m\equiv 0{\pmod {4}}\,$ , ...(2m + 2)^f₃,(2m)^f₁,(2m - 2)^f₂, ... , example, for 12 = 5 + 4 + 3, the Eulerian degree sequence is 8³,6⁵,4⁴.

• For :$4m\equiv 1{\pmod {4}}\,$, ...(2m + 2)^f₂,(2m)^f₁,(2m - 2)^f₃, ... , example, for 13 = 6 + 4 + 3, the Eulerian degree sequence is 8⁴,6⁶,4³.

• For :$4m\equiv 2{\pmod {4}}\,$, ...(2m + 2)^f₂,(2m)^f₁,(2m - 2)^f₃, ... , example, for 14 = 6 + 5 + 3, the Eulerian degree sequence is 8⁵,6⁶,4³.

• For :$4m\equiv 3{\pmod {4}}\,$, ...(2m + 4)^f₃,(2m + 2)^f₁,(2m)^f₂, ... , example, for 15 = 6 + 5 + 4, the Eulerian degree sequence is 10⁴,8⁶,6⁵.

Frequency partition of trees, tournaments and hypegraphs

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

References

External section

• 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.