Frequency partition

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"1 + "f"2 + ... + "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"1 + "f"2 + ... + "f""k" 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.

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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Frequency distribution — In statistics, a frequency distribution is an arrangement of the values that one or more variables take in a sample. Each entry in the table contains the frequency or count of the occurrences of values within a particular group or interval, and… …   Wikipedia

  • Frequency (statistics) — In statistics the frequency of an event i is the number ni of times the event occurred in the experiment or the study. These frequencies are often graphically represented in histograms. We speak of absolute frequencies, when the counts ni… …   Wikipedia

  • Frequency probability — Statistical probability redirects here. For the episode of Star Trek: Deep Space Nine, see Statistical Probabilities. John Venn Frequency probability is the interpretation of probability that defines an event s probability as the limit of its… …   Wikipedia

  • List of partition topics — This is a list of partition topics, in the mathematical sense. Partition (disambiguation) lists meanings in other fields. In mathematics, a partition may be a partition of a set or an ordered partition of a set, or a partition of a graph, or a… …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Bhat-Nayak Vasanti N. — Vasanti N. Bhat Nayak (1938 ndash;) is an Indian born mathematician and a professor. She has written many papers in reputed journals of mathematics. Her Erdos number is 2.ee also* Bivariegated graph * Frequency partitionelected works* (With V. D …   Wikipedia

  • VOptimal Histograms — Histograms are most commonly used as visual representations of data. However, database systems use histograms to summarize data internally and provide size estimates for queries. These histograms are not presented to users or displayed visually,… …   Wikipedia

  • Cochlea — Cross section of the cochlea …   Wikipedia

  • Wave–particle duality — Quantum mechanics Uncertainty principle …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”