A complete graph is a graph in which each pair of graph vertices is connected by an edge. The complete graph with 
graph vertices is denoted 
and has 
(the triangular numbers) undirected edges, where 
is a binomial coefficient. In older literature, complete graphs are sometimes called universal graphs.
graph vertices is denoted and has (the triangular numbers) undirected edges, where is a binomial coefficient. In older literature, complete graphs are sometimes called universal graphs.
is also the 
.
The complete graph on 
nodes is implemented in the Wolfram Language as CompleteGraph[n]. Precomputed properties are available using GraphData[
"Complete", n
]. A graph may be tested to see if it is complete in the Wolfram Language using the function CompleteGraphQ[g].
nodes is implemented in the Wolfram Language as CompleteGraph[n]. Precomputed properties are available using GraphData["Complete", n]. A graph may be tested to see if it is complete in the Wolfram Language using the function CompleteGraphQ[g].
The complete graph on 0 nodes is a trivial graph known as the null graph, while the complete graph on 1 node is a trivial graph known as the singleton graph.
In the 1890s, Walecki showed that complete graphs 
admit a Hamilton decomposition for odd 
, and decompositions into Hamiltonian cycles plus a perfect matching for even 
(Lucas 1892, Bryant 2007, Alspach 2008). Alspach et al. (1990) give a construction for Hamilton decompositions of all 
.
admit a Hamilton decomposition for odd , and decompositions into Hamiltonian cycles plus a perfect matching for even (Lucas 1892, Bryant 2007, Alspach 2008). Alspach et al. (1990) give a construction for Hamilton decompositions of all .
The graph complement of the complete graph 
is the empty graph on 
nodes. 
has graph genus ![[(n-3)(n-4)/12]](http://mathworld.wolfram.com/images/equations/CompleteGraph/Inline17.gif)
for 
(Ringel and Youngs 1968; Harary 1994, p. 118), where ![[x]](http://mathworld.wolfram.com/images/equations/CompleteGraph/Inline19.gif)
is the ceiling function.
is the empty graph on nodes. has graph genus for (Ringel and Youngs 1968; Harary 1994, p. 118), where is the ceiling function.
The adjacency matrix 
of the complete graph 
takes the particularly simple form of all 1s with 0s on the diagonal, i.e., the unit matrix minus the identity matrix,
of the complete graph takes the particularly simple form of all 1s with 0s on the diagonal, i.e., the unit matrix minus the identity matrix, |
(1)
|
is the cycle graph 
, as well as the odd graph 
(Skiena 1990, p. 162). 
is the tetrahedral graph, as well as the wheel graph 
, and is also a planar graph. 
is nonplanar, and is sometimes known as the pentatope graph or Kuratowski graph. Conway and Gordon (1983) proved that every embedding of 
is intrinsically linked with at least one pair of linked triangles, and 
is also a Cayley graph. Conway and Gordon (1983) also showed that any embedding of 
contains a knotted Hamiltonian cycle.
is the 
.
The chromatic polynomial 
of 
is given by the falling factorial 
. The independence polynomial is given by
of is given by the falling factorial . The independence polynomial is given by |
(2)
|
and the matching polynomial by
 |  |  |
(3)
|
 |  |  |
(4)
|
is a normalized version of the 
.
The chromatic number and clique number of 
are 
. The automorphism group of the complete graph 
is the symmetric group 
(Holton and Sheehan 1993, p. 27). The numbers of graph cycles in the complete graph 
for 
, 4, ... are 1, 7, 37, 197, 1172, 8018 ... (OEIS A002807). These numbers are given analytically by
are . The automorphism group of the complete graph is the symmetric group (Holton and Sheehan 1993, p. 27). The numbers of graph cycles in the complete graph for , 4, ... are 1, 7, 37, 197, 1172, 8018 ... (OEIS A002807). These numbers are given analytically by |  |  |
(5)
|
 |  | ![1/4n[2_3F_1(1,1,1-n;2;-1)-n-1],](http://mathworld.wolfram.com/images/equations/CompleteGraph/Inline55.gif) |
(6)
|
where 
is a binomial coefficient and 
is a generalized hypergeometric function (Char 1968, Holroyd and Wingate 1985).
is a binomial coefficient and is a generalized hypergeometric function (Char 1968, Holroyd and Wingate 1985).
It is not known in general if a set of trees with 1, 2, ..., 
graph edges can always be packed into 
. However, if the choice of trees is restricted to either the path or star from each family, then the packing can always be done (Zaks and Liu 1977, Honsberger 1985).
graph edges can always be packed into . However, if the choice of trees is restricted to either the path or star from each family, then the packing can always be done (Zaks and Liu 1977, Honsberger 1985).
is the 
.
댓글 없음:
댓글 쓰기