Find link

Complete graph not in Multi-fragment algorithm

language:

Find link is a tool written by Edward Betts.

searching for Complete graph 66 found (414 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,115 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

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,760 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

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 (575 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

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)

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}}

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

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

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

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

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,

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

Sparsity matroid (3,459 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,817 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,820 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,517 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

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

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

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

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

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

1000 (number) (24,122 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

Fano plane (3,102 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

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

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

Gap reduction (1,171 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 ∈

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

Zero-knowledge proof (7,955 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

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

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} .

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,422 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

Jim Pitman (941 words) [view diff] exact match in snippet view article find links to article

proof of Cayley's formula computing the number of spanning trees in a complete graph. This proof involving a double counting argument is noted for its elegance

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

Cayley configuration space (4,169 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