Complete bipartite graph

Ask a question about 'Complete bipartite graph' Start a new discussion about 'Complete bipartite graph' Answer questions from other users Full Discussion Forum

Definition

Examples

• For any k, is called a star
  Star (graph theory)
  
  In graph theory, a star Sk is the complete bipartite graph K1,k.A star with 3 edges is called a claw; these are notable in the definition of claw-free graphs, graphs that do not have any claw as an induced subgraph....
  .
• The graph is called a claw
  Claw (graph theory)
  
  In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.A claw is another name for the complete bipartite graph K1,3 that is, a star graph with three edges, three leaves, and one central vertex....
  .

Properties

• Given a bipartite graph, finding its complete bipartite subgraph with maximal number of edges is an NP-complete
  NP-complete
  
  In computational complexity theory, the complexity class NP-complete is a class of problems having two properties:* Any given solution to the problem can be verified quickly ; the set of problems with this property is called NP ....
   problem.
• A planar graph
  Planar graph
  
  In graph theory, a planar graph is a graph which can be graph embedding in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints....
   cannot contain as a minor
  Minor (graph theory)
  
  In graph theory, a graph H is called a minor of the graph G if H is Graph isomorphism to a graph that can be obtained by zero or more edge contractions on a subgraph of G....
  ; an outerplanar graph cannot contain as a minor (These are not sufficient conditions for planarity and outerplanarity, but necessary).
• A complete bipartite graph. is a Moore graph
  Moore graph
  
  In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper boundAn equivalent definition of a Moore graph is that it is a graph of diameter k with girth 2k + 1....
   and a -cage
  Cage (graph theory)
  
  In the mathematics area of graph theory, a cage is a regular graph that has as few vertex as possible for its girth .Formally, an -graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle graph has length exactly g....
  
• A complete bipartite graph or is a Turán graph
  Turán graph
  
  The Tur?n graph T is a graph formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and connecting two vertices by an edge whenever they belong to different subsets....
  
• A complete bipartite graph has a vertex covering number of and an edge covering number of
• A complete bipartite graph has a maximum independent set of size
• A complete bipartite graph has m^n-1 n^m-1 spanning tree
  Spanning tree
  
  Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
  s.
• A complete bipartite graph has a maximum matching of size
• A complete bipartite graph has a proper n-edge-coloring
  Edge coloring
  
  In graph theory, edge coloring is one type of the graph coloring problem. A coloring of a graph's edges assigns a "color" to each edge of the graph....
  
• The last two results are corollaries
  Corollary
  
  A corollary is a statement which follows readily from a previously proven statement. In mathematics a corollary typically follows a theorem. The use of the term corollary, rather than proposition or theorem, is intrinsically subjective....
   of the Marriage Theorem
  Marriage theorem
  
  Hall's theorem , also known as the marriage theorem is usually credited to mathematician Philip Hall. The theorem is a combinatorics result that gives the condition allowing the selection of a distinct element from each of a collection of subsets....
   as applied to a k-regular
  Regular graph
  
  In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same Degree or valency....
   bipartite graph

See also

• Cycle graph
  Cycle graph
  
  In graph theory, a cycle graph is a graph that consists of a single path , or in other words, some number of vertices connected in a closed chain....
  
• Path graph
  Path graph
  
  In the Mathematics field of graph theory, a path graph is a particularly simple example of a tree , namely one which is not branched at all, that is, contains only nodes of degree two and one....
  
• Crown graph
  Crown graph
  
  File:Crown graphs.svgIn graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices u'i and v'i and with an edge from u'i to v'j whenever i ? j....
  
• Complete graph
  Complete graph
  
  In graph theory, a complete graph is a simple graph in which every pair of distinct vertex is connected by an edge . The complete graph on n vertices has n vertices and n/2 edges, and is denoted by ....
  
• Null graph
  Null graph
  
  The null graph or the empty graph is either the graph with no vertices and no edges, or any graph with no edges.The null graph is the initial object in the category of graphs, according to some definitions of a category of graphs....
  
• water, gas, and electricity
• Adjacency matrix
  Adjacency matrix
  
  In mathematics and computer science, the adjacency matrix of a finite set directed or undirected graph G on n vertices is the n × n matrix where the nondiagonal entry is the number of edges from vertex i to vertex j, and the diagonal entry is either twice the number of loops at vertex i or just the number o...