Frequency partition

From Wikipedia, the free encyclopedia

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 = 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.[1]

[edit] Frequency partition 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. 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 (181 ,161,142 ,123, 105, 84, 62, 41, 21) is an example.

[edit] Frequency partition of tournaments and hypegraphs

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

[edit] References

  1. ^ 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.
  2. ^ B. Alspach and K. B. Reid, Degree Frequencies in Digraphs and Tournaments, Journal of Graph Theory, Vol. 2 (1978) 241-249.
  3. ^ V. N. Bhat-Nayak and R. N. Naik, Frequency partitions of k-uniform hypergraphs, Utilitas Math. 28 (1985) 99-104.
  • T. M. Rao, Frequency sequences in Graphs, J. Comb. Theory, B 17 (1974), 19-21.
  • Vasanthi 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.
  • Vasanthi 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.