Complete bipartite graph

Last updated
Complete bipartite graph
Biclique K 3 5.svg
A complete bipartite graph with m = 5 and n = 3
Vertices n + m
Edges mn
Radius
Diameter
Girth
Automorphisms
Chromatic number 2
Chromatic index max{m, n}
Spectrum
NotationK{m,n}
Table of graphs and parameters

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set. [1] [2]

Contents

Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher. [3] [4] Llull himself had made similar drawings of complete graphs three centuries earlier. [3]

Definition

A complete bipartite graph is a graph whose vertices can be partitioned into two subsets V1 and V2 such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph (V1, V2, E) such that for every two vertices v1 ∈ V1 and v2 ∈ V2, v1v2 is an edge in E. A complete bipartite graph with partitions of size |V1| = m and |V2| = n, is denoted Km,n; [1] [2] every two graphs with the same notation are isomorphic.

Examples

The star graphs K1,3, K1,4, K1,5, and K1,6. Star graphs.svg
The star graphs K1,3, K1,4, K1,5, and K1,6.
A complete bipartite graph of K4,7 showing that Turan's brick factory problem with 4 storage sites (yellow spots) and 7 kilns (blue spots) requires 18 crossings (red dots) Zarankiewicz K4 7.svg
A complete bipartite graph of K4,7 showing that Turán's brick factory problem with 4 storage sites (yellow spots) and 7 kilns (blue spots) requires 18 crossings (red dots)

Properties

Example Kp,p complete bipartite graphs [7]
K3,3 K4,4K5,5
Complex polygon 2-4-3-bipartite graph.png Complex polygon 2-4-4 bipartite graph.png Complex polygon 2-4-5-bipartite graph.png
Complex polygon 2-4-3.png
3 edge-colorings		 Complex polygon 2-4-4.png
4 edge-colorings		 Complex polygon 2-4-5.png
5 edge-colorings
Regular complex polygons of the form 2{4}p have complete bipartite graphs with 2p vertices (red and blue) and p2 2-edges. They also can also be drawn as p edge-colorings.

See also

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Tree (graph theory) Undirected, connected and acyclic graph

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by at most one path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees.

Bipartite graph Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Outerplanar graph

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

Extremal graph theory

Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure. Results in extremal graph theory deal with quantitative connections between various graph properties, both global and local, and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy? A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory.

In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is an automorphism of G that maps e1 to e2.

Degree (graph theory) Number of edges touching a vertex in a graph

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex is denoted or . The maximum degree of a graph , denoted by , and the minimum degree of a graph, denoted by , are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0.

Hadwiger conjecture (graph theory)

In graph theory, the Hadwiger conjecture states that if G is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges, or in other words if every pair of vertices is connected by one edge. The opposite, a graph with only a few edges, is a sparse graph. The distinction between sparse and dense graphs is rather vague, and depends on the context.

Graph factorization

In graph theory, a factor of a graph G is a spanning subgraph, i.e., a subgraph that has the same vertex set as G. A k-factor of a graph is a spanning k-regular subgraph, and a k-factorization partitions the edges of the graph into disjoint k-factors. A graph G is said to be k-factorable if it admits a k-factorization. In particular, a 1-factor is a perfect matching, and a 1-factorization of a k-regular graph is an edge coloring with k colors. A 2-factor is a collection of cycles that spans all vertices of the graph.

The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size. It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951.

Neighbourhood (graph theory)

In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the subgraph of G induced by all vertices adjacent to v, i.e., the graph composed of the vertices adjacent to v and all edges connecting vertices adjacent to v.

Rooks graph Graph of chess rook moves

In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge represents a legal move from one square to another. The same graphs can be defined mathematically as the Cartesian products of two complete graphs, as the two-dimensional Hamming graphs, or as the line graphs of complete bipartite graphs.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

Pancyclic graph

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

In graph theory, interval edge coloring is a type of edge coloring in which edges are labeled by the integers in some interval, every integer in the interval is used by at least one edge, and at each vertex the labels that appear on incident edges form a consecutive set of distinct numbers.

In graph theory, a branch of mathematics, a t-biclique-free graph is a graph that has no 2t-vertex complete bipartite graph Kt,t as a subgraph. A family of graphs is biclique-free if there exists a number t such that the graphs in the family are all t-biclique-free. The biclique-free graph families form one of the most general types of sparse graph family. They arise in incidence problems in discrete geometry, and have also been used in parameterized complexity.

References

  1. 1 2 Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p.  5, ISBN   0-444-19451-7 .
  2. 1 2 3 Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN   3-540-26182-6 . Electronic edition, page 17.
  3. 1 2 Knuth, Donald E. (2013), "Two thousand years of combinatorics", in Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, pp. 7–37, ISBN   0191630624 .
  4. ↑ Read, Ronald C.; Wilson, Robin J. (1998), An Atlas of Graphs, Clarendon Press, p. ii, ISBN   9780198532897 .
  5. ↑ Lovász, László; Plummer, Michael D. (2009), Matching theory, Providence, RI: AMS Chelsea, p. 109, ISBN   978-0-8218-4759-6, MR   2536865 . Corrected reprint of the 1986 original.
  6. ↑ Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer, p. 437, ISBN   9780387941158 .
  7. ↑ Coxeter, Regular Complex Polytopes, second edition, p.114
  8. ↑ Garey, Michael R.; Johnson, David S. (1979), "[GT24] Balanced complete bipartite subgraph", Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, p.  196, ISBN   0-7167-1045-5 .
  9. ↑ Diestel 2005 , p. 105
  10. ↑ Biggs, Norman (1993), Algebraic Graph Theory, Cambridge University Press, p. 181, ISBN   9780521458979 .
  11. ↑ Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer, p. 104, ISBN   9780387984889 .
  12. ↑ Bollobás (1998), p. 266.
  13. ↑ Jungnickel, Dieter (2012), Graphs, Networks and Algorithms, Algorithms and Computation in Mathematic, vol. 5, Springer, p. 557, ISBN   9783642322785 .
  14. ↑ Jensen, Tommy R.; Toft, Bjarne (2011), Graph Coloring Problems, Wiley Series in Discrete Mathematics and Optimization, vol. 39, Wiley, p. 16, ISBN   9781118030745 .
  15. ↑ Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Absolute retracts of bipartite graphs", Discrete Applied Mathematics , 16 (3): 191–215, doi: 10.1016/0166-218X(87)90058-8 , MR   0878021 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.