graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a discipline within mathematics, the frequency partition of a graph (

simple graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

) 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 mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

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. Image:6n-graf.svg, A graph with frequency partition 6 = 3 + 2 + 1. Image:Simple-bipartite-graph.svg, A bipartite graph with frequency partition 9 = 5 + 3 + 1. Image:Nonplanar no subgraph K 3 3.svg, 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 A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...

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 various graph families are completely identified; frequency partitions of many families of graphs are not identified.

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 a Eulerian graph and conversely.

Frequency partition of trees, Hamiltonian graphs, tournaments and hypegraphs

The frequency partitions of families of graphs such as

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...

Hamiltonian graph In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...

s and tournaments and to k-uniform

hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) ...

s. have been characterized.

Unsolved problems in frequency partitions

The frequency partitions of the following families of graphs have not yet been characterized: *

Line graph In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...

s *

Bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

S. B. Rao Siddani Bhaskara Rao is a graph theorist, Professor Emeritus, and director of the Indian Statistical Institute (ISI) in Calcutta. Rao is the first director of the CR Rao Advanced Institute of Mathematics, Statistics and Computer Science. S. B. ...

, A survey of the theory of potentially p-graphic and forcibly p-graphic sequences, in: S. B. Rao edited., Combinatorics and Graph Theory Lecture Notes in Math., Vol. 885 (Springer, Berlin, 1981), 417-440

References

External section

*{{citation , last=Berge , first=C. , author-link=Claude Berge , title=Hypergraphs, Combinatorics of Finite sets , year=1989 , publisher=North-Holland , location=Amsterdam , isbn=0-444-87489-5 Graph theory