Find link

language:

Find link is a tool written by Edward Betts.

searching for Complete graph 71 found (413 total)

Seidel adjacency matrix (311 words) [view diff] exact match in snippet view article find links to article

coauthors. The Seidel matrix of G is also the adjacency matrix of a signed complete graph KG in which the edges of G are negative and the edges not in G are positive

Graph canonization (1,112 words) [view diff] exact match in snippet view article find links to article

forms are identical. The canonical form of a graph is an example of a complete graph invariant: every two isomorphic graphs have the same canonical form

Interval edge coloring (1,659 words) [view diff] exact match in snippet view article find links to article

coloring. A simple family of graphs that allows interval edge coloring is complete graph of even order and a counter example of family of graphs includes complete

Wheel graph (589 words) [view diff] exact match in snippet view article find links to article

conjecture of Paul Erdős on Ramsey theory: he had conjectured that the complete graph has the smallest Ramsey number among all graphs with the same chromatic

Erdős–Stone theorem (1,405 words) [view diff] exact match in snippet view article find links to article

Turán's theorem to bound the number of edges in an H-free graph for a non-complete graph H. It is named after Paul Erdős and Arthur Stone, who proved it in 1946

MaxDDBS (222 words) [view diff] exact match in snippet view article find links to article

diameter problem as a special case (namely, by taking a sufficiently large complete graph as a host graph). Despite being a natural generalization of the Degree-Diameter

Avoider-Enforcer game (618 words) [view diff] exact match in snippet view article find links to article

of such a game is Sim. There, the positions are all the edges of the complete graph on 6 vertices. Players take turns to shade a line in their color, and

Two-graph (1,591 words) [view diff] exact match in snippet view article find links to article

corresponding signed complete graph. The adjacency matrix of a two-graph is the adjacency matrix of the corresponding signed complete graph; thus it is symmetric

Incidence poset (423 words) [view diff] exact match in snippet view article find links to article

dimension 4 may be dense and may have unbounded chromatic number. Every complete graph on n vertices, and by extension every graph on n vertices, has an incidence

Dependent random choice (1,757 words) [view diff] exact match in snippet view article find links to article

n^{2}} edges, then G {\displaystyle G} contains a 1-subdivision of a complete graph with ϵ 3 / 2 n 1 / 2 {\displaystyle \epsilon ^{3/2}n^{1/2}} vertices

Multi-fragment algorithm (131 words) [view diff] exact match in snippet view article find links to article

maintains multiple tour fragments, each of which is a simple path in the complete graph of cities. At each stage, the algorithm selects the edge of minimal

Order dimension (1,205 words) [view diff] exact match in snippet view article find links to article

dimension of its incidence poset is at most three (Schnyder 1989). For a complete graph on n vertices, the order dimension of the incidence poset is Θ ( log

Hendecagon (971 words) [view diff] exact match in snippet view article find links to article

vertices with four regular hendecagrams: 10-simplex - can be seen as a complete graph in a regular hendecagonal orthogonal projection Haldeman, Cyrus B. (1922)

Graph flattenability (3,922 words) [view diff] exact match in snippet view article find links to article

and shows that the only forbidden minor for 1-flattenability is the complete graph K 3 {\displaystyle K_{3}} . Theorem. A graph is 1-flattenable if and

Tournament solution (572 words) [view diff] exact match in snippet view article find links to article

A tournament solution is a function that maps an oriented complete graph to a nonempty subset of its vertices. It can informally be thought of as a way

Copying mechanism (1,161 words) [view diff] exact match in snippet view article find links to article

are ancestors of the target and the copying mechanism would give a complete graph. Correspondingly, the total number of links L N {\displaystyle L_{N}}

EXPTIME (991 words) [view diff] exact match in snippet view article find links to article

and output whether there is an edge between them. For many natural P-complete graph problems, where the graph is expressed in a natural representation such

Graph product (610 words) [view diff] exact match in snippet view article find links to article

{\displaystyle a_{n}\sim b_{n}} . Let K 2 {\displaystyle K_{2}} be the complete graph on two vertices (i.e. a single edge). The product graphs K 2 ◻ K 2 {\displaystyle

Hedetniemi's conjecture (1,853 words) [view diff] exact match in snippet view article find links to article

a k-coloring is the same as a Kk-coloring (a homomorphism into the complete graph on k vertices). A graph K is called multiplicative if for any graphs

Reed's law (571 words) [view diff] exact match in snippet view article find links to article

much sparser than the set-of-subsets measured by Reed's law or the complete graph measured by Metcalfe's law. Andrew Odlyzko's "Content is Not King" Beckstrom's

Anthony Hill (artist) (679 words) [view diff] exact match in snippet view article

Harary, Frank and Hill, Anthony. On the number of crossings in a complete graph. Proceedings of the Edinburgh Math. Society (2), 13:333-338, 1962/1963

Modular decomposition (3,177 words) [view diff] exact match in snippet view article find links to article

quotients may not be unique. (For example, all subsets of the vertices of a complete graph are modules, which means that there are many different ways of decomposing

Combinatorial design (4,362 words) [view diff] exact match in snippet view article find links to article

is given by The columns of a BTD(n) provide a 1-factorization of the complete graph on 2n vertices, K2n. BTD(n)s can be used to schedule round-robin tournaments:

Harborth's conjecture (1,088 words) [view diff] exact match in snippet view article find links to article

to 1 Erdős–Diophantine graph, a complete graph with integer distances that cannot be extended to a larger complete graph with the same property Euler brick

György Hajós (575 words) [view diff] exact match in snippet view article find links to article

that every graph with chromatic number k contains a subdivision of a complete graph Kk. However, it is now known to be false: in 1979, Paul A. Catlin found

Extremal graph theory (1,360 words) [view diff] exact match in snippet view article find links to article

to G {\displaystyle G} . When G = K r {\displaystyle G=K_{r}} is a complete graph, Turán's theorem gives an exact value for ex ⁡ ( n , K r ) {\displaystyle

L. W. Beineke (193 words) [view diff] exact match in snippet view article find links to article

Beineke, Selected Topics in Graph Theory, 1978 "The thickness of the complete graph", LW Beineke, Frank Harary – Canadian Journal of Mathematics, 1965,

Sparsity matroid (3,454 words) [view diff] exact match in snippet view article find links to article

{\displaystyle (2,3)} -tight if and only if it can be constructed from the complete graph K 2 {\displaystyle K_{2}} via a sequence of 0 {\displaystyle 0} - and

Clustering coefficient (2,377 words) [view diff] exact match in snippet view article find links to article

a graph quantifies how close its neighbours are to being a clique (complete graph). Duncan J. Watts and Steven Strogatz introduced the measure in 1998

Markov random field (2,838 words) [view diff] exact match in snippet view article find links to article

one, more appropriately, allows the infinite energies to act on the complete graph on V {\displaystyle V} . MRF's factorize if at least one of the following

Triangle-free graph (2,524 words) [view diff] exact match in snippet view article find links to article

{\displaystyle \Theta ({\tfrac {t^{2}}{\log t}})} : if the edges of a complete graph on Ω ( t 2 log ⁡ t ) {\displaystyle \Omega ({\tfrac {t^{2}}{\log t}})}

Rooted product of graphs (476 words) [view diff] exact match in snippet view article find links to article

graceful numberings for a wide family of trees. If H is a two-vertex complete graph K2, then for any graph G, the rooted product of G and H has domination

Reconstruction conjecture (1,770 words) [view diff] exact match in snippet view article find links to article

decks. A particular type of regular graph which is interesting is the complete graph. Trees Disconnected graphs Unit interval graphs Separable graphs without

Graph bandwidth (1,519 words) [view diff] exact match in snippet view article find links to article

formula. The bandwidth of a path graph Pn on n vertices is 1, and for a complete graph Km we have φ ( K n ) = n − 1 {\displaystyle \varphi (K_{n})=n-1} . For

Richard K. Guy (3,160 words) [view diff] exact match in snippet view article find links to article

Tom; Schaer, Jonathan (1968). "The toroidal crossing number of the complete graph". J. Comb. Theory. 4 (4): 376–390. doi:10.1016/S0021-9800(68)80063-8

Slicing the Truth (768 words) [view diff] exact match in snippet view article find links to article

form of Ramsey's theorem: every edge coloring of a countably infinite complete graph or complete uniform hypergraph, using finitely many colors, contains

Clique-sum (1,178 words) [view diff] exact match in snippet view article find links to article

Wagner (1937), who proved that the graphs that do not have a five-vertex complete graph as a minor are the 3-clique-sums of planar graphs with the eight-vertex

Polygon-circle graph (606 words) [view diff] no match in snippet view article find links to article

"Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete", Graph-Theoretic Concepts in Computer Science: 33rd International Workshop

Arthur Hobbs (mathematician) (846 words) [view diff] exact match in snippet view article

vertices respectively, can be packed in an edge-disjoint manner into the complete graph on n vertices. This conjecture is still open. Hobbs also worked with

Paul Seymour (mathematician) (2,285 words) [view diff] exact match in snippet view article

proof that every graph that is not five-colourable has a six-vertex complete graph as a minor (the four-colour theorem is assumed to obtain this result

Serialization (4,974 words) [view diff] exact match in snippet view article find links to article

marked as transient must also be serialized; and if any object in the complete graph of non-transient object references is not serializable, then serialization

Homomorphism density (2,300 words) [view diff] exact match in snippet view article find links to article

density are asymptotically equivalent. For H {\displaystyle H} being a complete graph K m {\displaystyle K_{m}} , the homomorphism density and subgraph density

Topological graph (3,579 words) [view diff] exact match in snippet view article find links to article

results is Turán's theorem, where there is one forbidden subgraph: a complete graph with k vertices (k is fixed). Analogous questions can be raised for

Fano plane (3,097 words) [view diff] exact match in snippet view article find links to article

fingers out like the children's game Cat's Cradle. You will obtain a complete graph on seven vertices with seven colored triangles (projective lines). The

1000 (number) (24,090 words) [view diff] exact match in snippet view article

of 34 1451 = Sophie Germain prime 1452 = first Zagreb index of the complete graph K12 1453 = Sexy prime with 1459 1454 = 3 × 222 + 2 = number of points

Continuous-time quantum walk (1,022 words) [view diff] exact match in snippet view article find links to article

of adjacent vertices, unless it is a disjoint union of copies of the complete graph K 2 {\displaystyle K_{2}} . A strongly regular graph admits perfect

Clique percolation method (2,191 words) [view diff] exact match in snippet view article find links to article

interpreted with the help of a k-clique template (an object isomorphic to a complete graph of k nodes). Such a template can be placed onto any k-clique in the

Moser spindle (1,530 words) [view diff] exact match in snippet view article find links to article

graphs on four vertices. This construction removes an edge from each complete graph, merges two of the endpoints of the removed edges into a single vertex

Segmentation-based object categorization (1,901 words) [view diff] exact match in snippet view article find links to article

arbitrary feature space can be represented as a weighted undirected complete graph G = (V, E), where the nodes of the graph are the points in the feature

Combinatorics on words (2,588 words) [view diff] exact match in snippet view article find links to article

integer R ( k , m ) {\displaystyle R(k,m)} such that despite how a complete graph is colored with two colors, there will always exist a solid color subgraph

Gadget (computer science) (1,604 words) [view diff] exact match in snippet view article

; Johnson, David S.; Stockmeyer, Larry (1976), "Some simplified NP-complete graph problems", Theoretical Computer Science, 1 (3): 237–267, doi:10

Truncated projective plane (1,223 words) [view diff] exact match in snippet view article find links to article

ISSN 0209-9683. S2CID 13307018. Füredi, Zoltán (1989-05-01). "Covering the complete graph by partitions". Discrete Mathematics. 75 (1): 217–226. doi:10

Biased graph (1,541 words) [view diff] exact match in snippet view article find links to article

important in matroid structure theory. Just as a group expansion of a complete graph Kn encodes the group (see Dowling geometry), its combinatorial analog

Gap reduction (1,183 words) [view diff] exact match in snippet view article find links to article

a given graph G = (V, E) to this problem as follows: we construct a complete graph G' = (V, E'), for the traveling salesman problem. For each edge e ∈

Zero-knowledge proof (7,548 words) [view diff] exact match in snippet view article find links to article

encryption, one can create a zero-knowledge proof system for the NP-complete graph coloring problem with three colors. Since every problem in NP can be

Shift graph (591 words) [view diff] exact match in snippet view article find links to article

shift graph G n , 2 {\displaystyle G_{n,2}} is the line-graph of the complete graph K n {\displaystyle K_{n}} in the following way: Consider the numbers

Rainbow matching (2,561 words) [view diff] exact match in snippet view article find links to article

ISSN 0209-9683. S2CID 119173114. Füredi, Zoltán (1989-05-01). "Covering the complete graph by partitions". Discrete Mathematics. 75 (1–3): 217–226. doi:10

Matching polytope (1,552 words) [view diff] exact match in snippet view article find links to article

(a cycle of length 3), a square graph (a cycle of length 4), and the complete graph on 4 vertices. For every subset F of edges, the dot product 1E(v) ·

Howson property (1,531 words) [view diff] exact match in snippet view article find links to article

only if every connected component of Γ {\displaystyle \Gamma } is a complete graph. Limit groups have the Howson property. It is not known whether S L

Seidel's algorithm (797 words) [view diff] exact match in snippet view article find links to article

The base case tests whether the input adjacency matrix describes a complete graph, in which case all shortest paths have length 1 {\displaystyle 1} .

Talent scheduling (978 words) [view diff] exact match in snippet view article find links to article

Johnson, D. S.; Stockmeyer, L. (1 February 1976). "Some simplified NP-complete graph problems". Theoretical Computer Science. 1 (3): 237–267. doi:10

Graph structure theorem (2,783 words) [view diff] exact match in snippet view article find links to article

larger than the tree width of H (a notable exception is when H = K4, the complete graph on four vertices, for which k = 3). This is one reason that the graph

Grothendieck inequality (4,840 words) [view diff] exact match in snippet view article find links to article

For G = K n {\displaystyle G=K_{n}} , the n {\displaystyle n} -vertex complete graph, the Grothendieck inequality of G {\displaystyle G} becomes max x 1

Coxeter notation (6,423 words) [view diff] exact match in snippet view article find links to article

representing the rhombic symmetry of the Coxeter diagram. The paracompact complete graph diagram or , is represented as [3[3,3]] with the superscript [3,3] as

Graph removal lemma (5,077 words) [view diff] exact match in snippet view article find links to article

as follows: Given a red-blue coloring H ′ {\displaystyle H'} of the complete graph K h {\displaystyle K_{h}} (analogous to the graph H {\displaystyle H}

2-satisfiability (9,112 words) [view diff] exact match in snippet view article find links to article

Garey; D. S. Johnson; L. J. Stockmeyer (1976), "Some simplified NP-complete graph problems", Theoretical Computer Science, 1 (3): 237–267, doi:10

Generalized distributive law (6,400 words) [view diff] exact match in snippet view article find links to article

local domain graph G L D {\displaystyle G_{LD}} , which is a weighted complete graph with M {\displaystyle M} vertices v 1 , v 2 , v 3 , … , v M {\displaystyle

Incidence coloring (3,817 words) [view diff] exact match in snippet view article find links to article

colors. The bound is attained by trees and complete graphs: If G is a complete graph with at least two vertices then χ i ( G ) = Δ ( G ) + 1. {\displaystyle

Evolution of a random network (2,377 words) [view diff] exact match in snippet view article find links to article

N}{N}}\right)\rightarrow 0}} for large N. The network turns into a complete graph only at ⟨ k ⟩ = N − 1 {\displaystyle {\left\langle k\right\rangle =N-1}}

Cayley configuration space (4,161 words) [view diff] exact match in snippet view article find links to article

{\displaystyle d\geq 3} . The forbidden minors for 3-flattenability are the complete graph K 5 {\displaystyle K_{5}} and the 1-skeleton of the octahedron K 2

Italo Jose Dejter (5,660 words) [view diff] exact match in snippet view article find links to article

showed that for any positive integer n, all 2-covering graphs of the complete graph Kn on n vertices can be determined; in addition, he showed that among