A complete bipartite graph is a bipartite graph (i.e., a set of graph vertices
decomposed into two disjoint sets such that no two graph
vertices within the same set are adjacent) such that every pair of graph vertices in the two sets are adjacent. If there are  and  graph vertices in the two sets, the complete bipartite graph
(sometimes also called a complete bigraph) is denoted  . The above
figures show  and  .  is also
known as the utility graph (and
the circulant graph  ), and
is the unique 4-cage graph.
A complete bipartite graph  is a circulant graph (Skiena 1990, p. 99),
specifically  , where  is the floor function.
 is a Cayley graph.
The numbers of (directed) Hamiltonian circuits for the graph  with  , 2, ... are 0, 2, 12, 144, 2880, 86400,
3628800, 203212800, ... (Sloane's A143248), where the  th term for  is given by  with  a factorial.
The independence polynomial of  is given by
which has recurrence equation
The complete bipartite graph  illustrated
above plays an important role in the novel Foucault's Pendulum by Umberto Eco (1989, p. 473;
Skiena 1990, p. 143).
Eco, U. Foucault's Pendulum. San Diego: Harcourt Brace Jovanovich,
p. 473, 1989.
Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York:
Dover, p. 12, 1986.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory
with Mathematica. Reading, MA: Addison-Wesley, 1990.
Sloane, N. J. A. Sequence A143248 in "The On-Line Encyclopedia of Integer Sequences."
|
Contact the MathWorld Team
