Complete bipartite graph

Complete bipartite graph
Complete bipartite graph
Biclique K 3 5.svg
A complete bipartite graph with m = 5 and n = 3
Vertices n + m
Edges mn
Girth 4
Automorphisms 2m!n! if m=n, otherwise m!n!
Chromatic number 2
Chromatic index max{m, n}
Notation Km,n
v · 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.

Contents

Definition

A complete bipartite graph, G := (V1 + V2, E), is a bipartite graph such that for any two vertices, v1 ∈ V1 and v2 ∈ V2, v1v2 is an edge in G. The complete bipartite graph with partitions of size |V1|=m and |V2|=n, is denoted Km,n.

Examples

The star graphs S3, S4, S5 and S6.
The utility graph K3,3
  • For any k, K1,k is called a star. All complete bipartite graphs which are trees are stars.
  • The graph K1,3 is called a claw, and is used to define the claw-free graphs.
  • The graph K3,3 is called the utility graph. This usage comes from a standard mathematical puzzle in which three utilities must each be connected to three buildings; it is impossible to solve without crossings due to the nonplanarity of K3,3.

Properties

  • Given a bipartite graph, finding its complete bipartite subgraph Km,n with maximal number of edges mn is an NP-complete problem.
  • A planar graph cannot contain K3,3 as a minor; an outerplanar graph cannot contain K3,2 as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary).
  • A complete bipartite graph. Kn,n is a Moore graph and a (n,4)-cage.
  • A complete bipartite graph Kn,n or Kn,n+1 is a Turán graph.
  • A complete bipartite graph Km,n has a vertex covering number of min{m,n} and an edge covering number of max{m,n}.
  • A complete bipartite graph Km,n has a maximum independent set of size max{m,n}.
  • The adjacency matrix of a complete bipartite graph Km,n has eigenvalues √(nm), −√(nm) and 0; with multiplicity 1, 1 and n+m−2 respectively.
  • The laplacian matrix of a complete bipartite graph Km,n has eigenvalues n+m, n, m, and 0; with multiplicity 1, m−1, n−1 and 1 respectively.
  • A complete bipartite graph Km,n has mn−1 nm−1 spanning trees.
  • A complete bipartite graph Km,n has a maximum matching of size min{m,n}.
  • A complete bipartite graph Kn,n has a proper n-edge-coloring corresponding to a Latin square.
  • The last two results are corollaries of the Marriage Theorem as applied to a k-regular bipartite graph.

See also

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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 sets U and V such that every edge connects a vertex in U to one in V ; that is, U and V are independent sets.… …   Wikipedia

  • Complete graph — K7, a complete graph with 7 vertices Vertices n Edges …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Graph isomorphism — In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly… …   Wikipedia

  • Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia

  • Bipartite dimension — In the mathematical field of graph theory, the bipartite dimension of an graph G=(V,E) is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is …   Wikipedia

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… …   Universalium

  • Rook's graph — infobox graph name = Rook s graph image caption = 8x8 Rook s graph vertices = nm edges = nm ( n + m )/2 nm diameter = 2 chromatic number = max( n , m ) chromatic index = girth = 3 (if max( n , m ) ≥ 3) properties = regular, vertex transitive,… …   Wikipedia

Share the article and excerpts

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