Frequency partition

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.

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. [P. Z. Chinn, The frequency partition of a graph. Recent Trends in Graph Theory, Lecture Notes in Mathematics, Springer-Verlag, Berlin (1971) Vol. 186, 69-70.]

Frequency partition 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. 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. [B. Alspach and K. B. Reid, Degree Frequencies in Digraphs and Tournaments, Journal of Graph Theory, Vol. 2 (1978) 241-249.] [V. N. Bhat-Nayak and R. N. Naik, Frequency partitions of k-uniform hypergraphs, Utilitas Math. 28 (1985) 99-104.]

References

* T. M. Rao, Frequency sequences in Graphs, J. Comb. 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 Math. 20 (1977) 93-102.
* Vasanti N. Bhat-Nayak, Ranjan N. Naik and S. B. Rao, Characterization of Frequency Partitions of Eulerian Graphs – ISI Lecture Notes No. 4 (Edited A R Rao) Proc. Symposium on graph Theory, Published by The MacMillan comp. of India Ltd 1979.
* Berge , C., Hypergraphs, Combinatorics of Finite sets. Amsterdam: North-Holland 1989.