# complete graph

Also found in: Wikipedia.

## complete graph

[kəm¦plēt ′graf]
(mathematics)
A graph with exactly one edge connecting each pair of distinct vertices and no loops.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.

## complete graph

A graph which has a link between every pair of nodes. A complete bipartite graph can be partitioned into two subsets of nodes such that each node is joined to every node in the other subset.
Mentioned in ?
References in periodicals archive ?
Let [K.sub.n] be the complete graph of order n; then [zeta]([K.sub.n]) = n, [[xi].sup.c]([K.sub.n]) = n(n - 1), [M.sup.*.sub.1] ([K.sub.n]) = n, and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
Thus the total number of edges of the elements of is Hence, Now the elements of form a complete graph of type So total edges of the vertices of are and each element of is adjacent to all elements of .
A complete graph with vertices n[epsilon]N, denoted by [K.sub.n] is a connected simple graph with every vertex is connected with every other vertex by an edge.
For any connected graph G with p vertices p [greater than or equal to] 2, [[gamma].sub.M](G) = p - [lambda](G), where [lambda](G) is a edge connectivity of G if and only if G is a complete graph of order p.
Up to now, the spectra are known for some particular graphs: path, cycle, complete graph, complete bipartite graph, complete tree, hypercube, k-dimensional lattice, star graph, etc.
We denote a complete graph of n vertices by [K.sub.n] and denote a star graph with k leaves by [S.sub.k], where the leaf refers to the vertex of degree one.
A variant of the traveling salesman problem called MaxLTSP, where the goal is to compute a Hamiltonian tour of maximum number of colors in an edge-colored complete graph, has been considered in [4, 10].
The complete graph [K.sub.n] on n vertices is referred to as an n-clique.
Let [K.sub.n], [C.sub.n], [Q.sub.m], [[product].sub.m], [A.sub.m] denote the complete graph with n vertices, the cycle on n vertices, m-dimensional hypercube, m-sided prism, and the m-sided antiprism, respectively.
As usual, [P.sub.n], [C.sub.n], and [K.sub.n] stand for the path, the cycle, and the complete graph with n vertices, respectively.
By proceeding in an iterative way according to claim 3.2, it is possible to effectively find an ordering of the pairs [V(G).sup.(2)] - E([PSI](G)) such that the tree T may be realized as a decomposition tree of the complete graph [K.sub.V(G)].
For a connected graph G, N(G) [congruent to] G if, and only if, G is either a complete graph or an odd cycle of order [greater than or equal to] 3.

Site: Follow: Share:
Open / Close