8982:
5529:, the vertices of a graph are said to be labeled if they are all distinguishable from each other. For instance, this can be made to be true by fixing a one-to-one correspondence between the vertices and the integers from 1 to the order of the graph. When vertices are labeled, graphs that are isomorphic to each other (but with different vertex orderings) are counted as separate objects. In contrast, when the vertices are unlabeled, graphs that are isomorphic to each other are not counted separately.
3310:. That is, it is the maximum of the distances between pairs of vertices in the graph. If the graph has weights on its edges, then its weighted diameter measures path length by the sum of the edge weights along a path, while the unweighted diameter measures path length by the number of edges. For disconnected graphs, definitions vary: the diameter may be defined as infinite, or as the largest diameter of a connected component, or it may be undefined.
7471:, spanning trees of a graph whose distances approximate the graph distances, and graph spanners, sparse subgraphs of a dense graph whose distances approximate the original graph's distances. A greedy spanner is a graph spanner constructed by a greedy algorithm, generally one that considers all edges from shortest to longest and keeps the ones that are needed to preserve the distance approximation.
3793:
an ear decomposition in which each ear after the first is open; a graph has an open ear decomposition if and only if it is biconnected. An ear is odd if it has an odd number of edges, and an odd ear decomposition is an ear decomposition in which each ear is odd; a graph has an odd ear decomposition if and only if it is factor-critical.
7259:
is a form of logic in which variables may represent vertices, edges, sets of vertices, and (sometimes) sets of edges. This logic includes predicates for testing whether a vertex and edge are incident, as well as whether a vertex or edge belongs to a set. To be distinguished from first order logic, in
3792:
is a partition of the edges of a graph into a sequence of ears, each of whose endpoints (after the first one) belong to a previous ear and each of whose interior points do not belong to any previous ear. An open ear is a simple path (an ear without repeated vertices), and an open ear decomposition is
1341:
is a collection of mutually touching connected subgraphs, where two subgraphs touch if they share a vertex or each includes one endpoint of an edge. The order of a bramble is the smallest size of a set of vertices that has a nonempty intersection with all of the subgraphs. The treewidth of a graph is
1310:
is an embedding of a graph onto a topological book, a space formed by joining a collection of half-planes along a shared line. Usually, the vertices of the embedding are required to be on the line, which is called the spine of the embedding, and the edges of the embedding are required to lie within a
2851:
is a partition of the vertices of a graph into two subsets, or the set (also known as a cut-set) of edges that span such a partition, if that set is non-empty. An edge is said to span the partition if it has endpoints in both subsets. Thus, the removal of a cut-set from a connected graph disconnects
6837:
or proper circular arc graph is an intersection graph of a collection of intervals or circular arcs (respectively) such that no interval or arc contains another interval or arc. Proper interval graphs are also called unit interval graphs (because they can always be represented by unit intervals) or
4005:
is a walk that uses every edge of a graph exactly once. An
Eulerian circuit (also called an Eulerian cycle or an Euler tour) is a closed walk that uses every edge exactly once. An Eulerian graph is a graph that has an Eulerian circuit. For an undirected graph, this means that the graph is connected
2595:
is an elementary operation that removes an edge from a graph while merging the two vertices that it previously joined. Vertex contraction (sometimes called vertex identification) is similar, but the two vertices are not necessarily connected by an edge. Path contraction occurs upon the set of edges
4824:
is a mapping from the vertex set of one graph to the vertex set of another graph that maps adjacent vertices to adjacent vertices. This type of mapping between graphs is the one that is most commonly used in category-theoretic approaches to graph theory. A proper graph coloring can equivalently be
4239:
A graph is finite if it has a finite number of vertices and a finite number of edges. Many sources assume that all graphs are finite without explicitly saying so. A graph is locally finite if each vertex has a finite number of incident edges. An infinite graph is a graph that is not finite: it has
3809:
An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two (or in hypergraphs, more) vertices to which it is attached, called its endpoints. Edges may be directed or undirected; undirected edges are also called lines and directed edges are
3714:
is a set of vertices that includes or is adjacent to every vertex in the graph; not to be confused with a vertex cover, a vertex set that is incident to all edges in the graph. Important special types of dominating sets include independent dominating sets (dominating sets that are also independent
561:
In a graph with a matching, an alternating path is a path whose edges alternate between matched and unmatched edges. An alternating cycle is, similarly, a cycle whose edges alternate between matched and unmatched edges. An augmenting path is an alternating path that starts and ends at unsaturated
6850:
is something that can be true of some graphs and false of others, and that depends only on the graph structure and not on incidental information such as labels. Graph properties may equivalently be described in terms of classes of graphs (the graphs that have a given property). More generally, a
1967:
of graphs or family of graphs is a (usually infinite) collection of graphs, often defined as the graphs having some specific property. The word "class" is used rather than "set" because, unless special restrictions are made (such as restricting the vertices to be drawn from a particular set, and
1083:
is a graph whose vertices can be divided into two disjoint sets such that the vertices in one set are not connected to each other, but may be connected to vertices in the other set. Put another way, a bipartite graph is a graph with no odd cycles; equivalently, it is a graph that may be properly
2142:
4. A graph property is closed under some operation on graphs if, whenever the argument or arguments to the operation have the property, then so does the result. For instance, hereditary properties are closed under induced subgraphs; monotone properties are closed under subgraphs; and
4791:
A hole is an induced cycle of length four or more. An odd hole is a hole of odd length. An anti-hole is an induced subgraph of order four whose complement is a cycle; equivalently, it is a hole in the complement graph. This terminology is mainly used in the context of perfect graphs, which are
5138:
is a graph whose vertices correspond to sets or geometric objects, with an edge between two vertices exactly when the corresponding two sets or objects have a nonempty intersection. Several classes of graphs may be defined as the intersection graphs of certain types of objects, for instance
3992:
is the problem of counting the graphs in a given class of graphs, as a function of their order. More generally, enumeration problems can refer either to problems of counting a certain class of combinatorial objects (such as cliques, independent sets, colorings, or spanning trees), or of
4006:
and every vertex has even degree. For a directed graph, this means that the graph is strongly connected and every vertex has in-degree equal to the out-degree. In some cases, the connectivity requirement is loosened, and a graph meeting only the degree requirements is called
Eulerian.
7330:
is a graph without loops and without multiple adjacencies. That is, each edge connects two distinct endpoints and no two edges have the same endpoints. A simple edge is an edge that is not part of a multiple adjacency. In many cases, graphs are assumed to be simple unless specified
7765:. The vertex subset must include all endpoints of the edge subset, but may also include additional vertices. A spanning subgraph is one that includes all vertices of the graph; an induced subgraph is one that includes all the edges whose endpoints belong to the vertex subset.
3289:
The depth of a node in a rooted tree is the number of edges in the path from the root to the node. For instance, the depth of the root is 0 and the depth of any one of its adjacent nodes is 1. It is the level of a node minus one. Note, however, that some authors instead use
1978:, on edge coloring simple graphs, a graph is said to be of class one if its chromatic index equals its maximum degree, and class two if its chromatic index equals one plus the degree. According to Vizing's theorem, all simple graphs are either of class one or class two.
1579:
of a graph is an invariant such that two graphs have equal invariants if and only if they are isomorphic. Canonical forms may also be called canonical invariants or complete invariants, and are sometimes defined only for the graphs within a particular family of graphs.
3917:
is a topological representation of a graph as a subset of a topological space with each vertex represented as a point, each edge represented as a curve having the endpoints of the edge as endpoints of the curve, and no other intersections between vertices or edges. A
2205:
2. Some authors use "coloring", without qualification, to mean a proper coloring, one that assigns different colors to the endpoints of each edge. In graph coloring, the goal is to find a proper coloring that uses as few colors as possible; for instance,
2280:
and two vertices are adjacent when they are comparable in the partial order. Equivalently, a comparability graph is a graph that has a transitive orientation. Many other classes of graphs can be defined as the comparability graphs of special types of partial
2920:) or more usually a closed walk without repeated vertices and consequently edges (also called a simple cycle). In the latter case it is usually regarded as a graph, i.e., the choices of first vertex and direction are usually considered unimportant; that is,
2015:
is a set of mutually adjacent vertices (or the complete subgraph induced by that set). Sometimes a clique is defined as a maximal set of mutually adjacent vertices (or maximal complete subgraph), one that is not part of any larger such set (or subgraph). A
5771:
2. A simple graph with a given property is maximal for that property if it is not possible to add any more edges to it (keeping the vertex set unchanged) while preserving both the simplicity of the graph and the property. Thus, for instance, a
7561:(sometimes called vertex cleaving) is an elementary graph operation that splits a vertex into two, where these two new vertices are adjacent to the vertices that the original vertex was adjacent to. The inverse of vertex splitting is vertex contraction.
4165:, a connected component of the subset of the plane or surface of the embedding that is disjoint from the graph. For an embedding in the plane, all but one face will be bounded; the one exceptional face that extends to infinity is called the outer face.
4252:
is a form of logic in which variables represent vertices of a graph, and there exists a binary predicate to test whether two vertices are adjacent. To be distinguished from second order logic, in which variables can also represent sets of vertices or
3715:
sets) and connected dominating sets (dominating sets that induced connected subgraphs). A single-vertex dominating set may also be called a universal vertex. The domination number of a graph is the number of vertices in the smallest dominating set.
1550:, cactus tree, cactus, or Husimi tree is a connected graph in which each edge belongs to at most one cycle. Its blocks are cycles or single edges. If, in addition, each vertex belongs to at most two blocks, then it is called a Christmas cactus.
7386:
is a graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other node by a small number of hops or steps. Specifically, a small-world network is defined to be a graph where the typical distance
6851:
graph property may also be a function of graphs that is again independent of incidental information, such as the size, order, or degree sequence of a graph; this more general definition of a property is also called an invariant of the graph.
5720:
or complete matching is a matching that matches every vertex; it may also be called a 1-factor, and can only exist when the order is even. A near-perfect matching, in a graph with odd order, is one that saturates all but one vertex. A
2098:
by operations that create a labeled vertex, form the disjoint union of two labeled graphs, add an edge connecting all pairs of vertices with given labels, or relabel all vertices with a given label. The graphs of clique-width at most
2453:
is a proper coloring in which each pairs of colors is used for the endpoints of at least one edge. Every coloring with a minimum number of colors is complete, but there may exist complete colorings with larger numbers of colors. The
4680:
or
Hamiltonian cycle is a simple spanning path or simple spanning cycle: it covers all of the vertices in the graph exactly once. A graph is Hamiltonian if it contains a Hamiltonian cycle, and traceable if it contains a Hamiltonian
2547:
is one in which each pair of vertices forms the endpoints of a path. Higher forms of connectivity include strong connectivity in directed graphs (for each two vertices there are paths from one to the other in both directions),
1141:
is a maximal subgraph which is either an isolated vertex, a bridge edge, or a 2-connected subgraph. If a block is 2-connected, every pair of vertices in it belong to a common cycle. Every edge of a graph belongs in exactly one
7549:
of an arbitrary graph is a partition of its vertices into two nonempty subsets, such that the edges spanning this cut form a complete bipartite subgraph. The splits of a graph can be represented by a tree structure called its
7095:, a graph property is recognizable if its truth can be determined from the deck of the graph. Many graph properties are known to be recognizable. If the reconstruction conjecture is true, all graph properties are recognizable.
6820:
1. A proper subgraph is a subgraph that removes at least one vertex or edge relative to the whole graph; for finite graphs, proper subgraphs are never isomorphic to the whole graph, but for infinite graphs they can
2715:, in which each cograph vertex is a leaf of the tree, each internal node of the tree is labeled with 0 or 1, and two cograph vertices are adjacent if and only if their lowest common ancestor in the tree is labeled 1.
7886:
of a collection of points in the
Euclidean plane is constructed by constructing a system of cones surrounding each point and adding one edge per cone, to the point whose projection onto a central ray of the cone is
6549:
is a tree decomposition whose underlying tree is a path. Its width is defined in the same way as for tree decompositions, as one less than the size of the largest bag. The minimum width of any path decomposition of
7554:. A split is called a strong split when it is not crossed by any other split. A split is called nontrivial when both of its sides have more than one vertex. A graph is called prime when it has no nontrivial splits.
5556:
In an unweighted graph, the length of a cycle, path, or walk is the number of edges it uses. In a weighted graph, it may instead be the sum of the weights of the edges that it uses. Length is used to define the
8014:
is an orientation of a complete graph; that is, it is a directed graph such that every two vertices are connected by exactly one directed edge (going in only one of the two directions between the two vertices).
6627:
is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with this ordering optimally colors every induced subgraph. The perfectly orderable graphs are a subclass of the perfect
2201:
is a labeling of the vertices of a graph by elements from a given set of colors, or equivalently a partition of the vertices into subsets, called "color classes", each of which is associated with one of the
5768:
is a complete subgraph that cannot be expanded to a larger complete subgraph. The word "maximal" should be distinguished from "maximum": a maximum subgraph is always maximal, but not necessarily vice versa.
6050:
A multiple adjacency or multiple edge is a set of more than one edge that all have the same endpoints (in the same direction, in the case of directed graphs). A graph with multiple edges is often called a
4902:
This prefix, in combination with a graph property, indicates a graph that does not have the property but such that every subgraph formed by deleting a single vertex does have the property. For instance, a
3214:
is the collection of degrees of all vertices, in sorted order from largest to smallest. In a directed graph, one may distinguish the in-degree (number of incoming edges) and out-degree (number of outgoing
7773:
A subtree is a connected subgraph of a tree. Sometimes, for rooted trees, subtrees are defined to be a special type of connected subgraph, formed by all vertices and edges reachable from a chosen vertex.
8589:(plural vertices) is (together with edges) one of the two basic units out of which graphs are constructed. Vertices of graphs are often considered to be atomic objects, with no internal structure.
5159:(intersection graphs of the maximal cliques of a graph). Every graph is an intersection graph for some family of sets, and this family is called an intersection representation of the graph. The
7542:
is a graph whose vertices can be partitioned into a clique and an independent set. A related class of graphs, the double split graphs, are used in the proof of the strong perfect graph theorem.
6423:
is an oriented tree; it differs from a directed tree (an arborescence) in that there is no requirement of consistency in the directions of its edges. Other special types of orientation include
4451:, a giant component is a connected component that contains a constant fraction of the vertices of the graph. In standard models of random graphs, there is typically at most one giant component.
5303:
is a one-to-one incidence preserving correspondence of the vertices and edges of one graph to the vertices and edges of another graph. Two graphs related in this way are said to be isomorphic.
1003:, of the length of the longest edge (the number of steps in the ordering between its two endpoints). It is also one less than the size of the maximum clique in a proper interval completion of
7968:
is the algorithmic problem of arranging a directed acyclic graph into a topological order, a vertex sequence such that each edge goes from an earlier vertex to a later vertex in the sequence.
3100:-degenerate. A degeneracy ordering is an ordering of the vertices such that each vertex has minimum degree in the induced subgraph of it and all later vertices; in a degeneracy ordering of a
4721:
of a node in a rooted tree is the number of edges in a longest path, going away from the root (i.e. its nodes have strictly increasing depth), that starts at that node and ends at a leaf.
6620:
are two theorems about perfect graphs, the former proving that their complements are also perfect and the latter proving that they are exactly the graphs with no odd holes or anti-holes.
3905:
or totally disconnected graph on a given set of vertices is the graph that has no edges. It is sometimes called the empty graph, but this term can also refer to a graph with no vertices.
6419:
of an undirected graph is an assignment of directions to its edges, making it into a directed graph. An oriented graph is one that has been assigned an orientation. So, for instance, a
1458:
3. A bridge of a cycle can also mean a path that connects two vertices of a cycle but is shorter than either of the paths in the cycle connecting the same two vertices. A
8092:
is an undirected graph that is both connected and acyclic, or a directed graph in which there exists a unique walk from one vertex (the root of the tree) to all remaining vertices.
8056:
of a given directed graph is a graph on the same vertex set that has an edge from one vertex to another whenever the original graph has a path connecting the same two vertices. A
2743:
A critical graph for a given property is a graph that has the property but such that every subgraph formed by deleting a single vertex does not have the property. For instance, a
5585:. A node's level in a rooted tree is the number of nodes in the path from the root to the node. For instance, the root has level 1 and any one of its adjacent nodes has level 2.
2391:, graphs in which the vertices are divided into more than two subsets and every pair of vertices in different subsets are adjacent; if the numbers of vertices in the subsets are
920:, although that term more properly refers to 2-ary trees in which the children of each node are distinguished as being left or right children (with at most one of each type). A
3814:, an edge may be represented as the set of its vertices, and in a directed simple graph it may be represented as an ordered pair of its vertices. An edge that connects vertices
7721:
is a regular graph in which every two adjacent vertices have the same number of shared neighbours and every two non-adjacent vertices have the same number of shared neighbours.
2473:
of a graph is a maximal connected subgraph. The term is also used for maximal subgraphs or subsets of a graph's vertices that have some higher order of connectivity, including
2160:
2. A closure of a directed graph is a set of vertices that have no outgoing edges to vertices outside the closure. For instance, a sink is a one-vertex closure. The
389:
7894:
or Lovász theta function of a graph is a graph invariant related to the clique number and chromatic number that can be computed in polynomial time by semidefinite programming.
8950:
3. The width of a tree decomposition or path decomposition is one less than the maximum size of one of its bags, and may be used to define treewidth and pathwidth.
7667:
is the minimum ratio of the number of edges removed from the graph to components created, over all possible removals; it is analogous to toughness, based on vertex removals.
6998:
8969:
is the union of a collection of cliques, all of the same order as each other, with one shared vertex belonging to all the cliques and all other vertices and edges distinct.
4173:
A factor of a graph is a spanning subgraph: a subgraph that includes all of the vertices of the graph. The term is primarily used in the context of regular subgraphs: a
2319:
8824:
A numerical value, assigned as a label to a vertex or edge of a graph. The weight of a subgraph is the sum of the weights of the vertices or edges within that subgraph.
6886:
A quasi-line graph or locally co-bipartite graph is a graph in which the open neighborhood of every vertex can be partitioned into two cliques. These graphs are always
3973:
One of the two vertices joined by a given edge, or one of the first or last vertex of a walk, trail or path. The first endpoint of a given directed edge is called the
8538:
7940:
6525:
may either be a walk or a walk without repeated vertices and consequently edges (also called a simple path), depending on the source. Important special cases include
606:
3965:
of an infinite graph is an equivalence class of rays, where two rays are equivalent if there is a third ray that includes infinitely many vertices from both of them.
1649:
6824:
2. A proper coloring is an assignment of colors to the vertices of a graph (a coloring) that assigns different colors to the endpoints of each edge; see
1226:
1199:
6246:
of a non-bipartite graph is the length of its shortest odd cycle. An odd hole is a special case of an odd cycle: one that is induced and has four or more vertices.
5075:
or full subgraph of a graph is a subgraph formed from a subset of vertices and from all of the edges that have both endpoints in the subset. Special cases include
2747:
is one that has a perfect matching (a 1-factor) for every vertex deletion, but (because it has an odd number of vertices) has no perfect matching itself. Compare
1804:
is not chordal (unless it is a forest); it is a bipartite graph in which every cycle of six or more vertices has a chord, so the only induced cycles are 4-cycles.
1420:, isthmus, or cut edge is an edge whose removal would disconnect the graph. A bridgeless graph is one that has no bridges; equivalently, a 2-edge-connected graph.
5834:
A subgraph of given graph is minimal for a particular property if it has that property but no proper subgraph of it also has the same property. That is, it is a
429:
409:
357:
337:
5119:
A vertex of a path or tree is internal if it is not a leaf; that is, if its degree is greater than one. Two paths are internally disjoint (some people call it
1610:
Carving width is a notion of graph width analogous to branchwidth, but using hierarchical clusterings of vertices instead of hierarchical clusterings of edges.
7503:
is one that has few edges relative to its number of vertices. In some definitions the same property should also be true for all subgraphs of the given graph.
6026:
is a regular graph for which the Moore bound is met exactly. The Moore bound is an inequality relating the degree, diameter, and order of a graph, proved by
8080:
of a given directed graph is a graph on the same vertices, with each edge reversed in direction. It may also be called the converse or reverse of the graph.
5354:
by adding an edge from each vertex of one graph to each vertex of the other. Equivalently, it is the complement of the disjoint union of the complements.
1249:
is a block graph; so in particular the block graph of any graph is a block graph, and every block graph may be constructed as the block graph of a graph.
1153:, with an edge connecting two vertices when the corresponding blocks share an articulation point; that is, it is the intersection graph of the blocks of
6059:
The multiplicity of an edge is the number of edges in a multiple adjacency. The multiplicity of a graph is the maximum multiplicity of any of its edges.
6863:
is an undirected graph in which each connected component has at most one cycle, or a directed graph in which each vertex has at most one outgoing edge.
5800:
1. A median of a triple of vertices, a vertex that belongs to shortest paths between all pairs of vertices, especially in median graphs and
5548:
of a tree is a graph whose vertices are the leaves of the tree and whose edges connect leaves whose distance in the tree is at most a given threshold.
8428:
is a graph that contains as subgraphs all graphs in a given family of graphs, or all graphs of a given size or order within a given family of graphs.
6256:
3. An odd ear is a simple path or simple cycle with an odd number of edges, used in odd ear decompositions of factor-critical graphs; see
5131:
1. The intersection of two graphs is their largest common subgraph, the graph formed by the vertices and edges that belong to both graphs.
4295:
is a characterization of a family of graphs as being the graphs that do not have certain other graphs as subgraphs, induced subgraphs, or minors. If
2461:
5. A complete invariant of a graph is a synonym for a canonical form, an invariant that has different values for non-isomorphic graphs.
7463:
A spanner is a (usually sparse) graph whose shortest path distances approximate those in a dense graph or other metric space. Variations include
5716:
is a set of edges in which no two share any vertex. A vertex is matched or saturated if it is one of the endpoints of an edge in the matching. A
5506:
1. Information associated with a vertex or edge of a graph. A labeled graph is a graph whose vertices or edges have labels. The terms
4958:
of a graph is a matrix whose rows are indexed by vertices of the graph, and whose columns are indexed by edges, with a one in the cell for row
4661:
of a graph is the order of the largest complete minor of the graph. It is also called the contraction clique number or the homomorphism degree.
1243:(also called a clique tree if connected, and sometimes erroneously called a Husimi tree) is a graph all of whose blocks are complete graphs. A
5788:
is maximum for a particular property if it is the largest subgraph (by order or size) among all subgraphs with that property. For instance, a
2184:
is a coloring in which each vertex induces either an independent set (as in proper coloring) or a clique (as in a coloring of the complement).
6265:
4. An odd chord is an edge connecting two vertices that are an odd distance apart in an even cycle. Odd chords are used to define
4345:
is an undirected graph without cycles (a disjoint union of unrooted trees), or a directed graph formed as a disjoint union of rooted trees.
7731:
5. A strongly perfect graph is a graph in which every induced subgraph has an independent set meeting all maximal cliques. The
5974:, a graph in which each triple of vertices has at least one median vertex that belongs to shortest paths between all pairs of the triple.
9475:
Graph theory and applications (Proc. Conf., Western
Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs)
8816:
graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.
2596:
in a path that contract to form a single edge between the endpoints of the path. The inverse of edge contraction is vertex splitting.
7603:
is a planar graph that can be drawn so that all bounded faces are 4-cycles and all vertices of degree ≤ 3 belong to the outer face.
4499:
of a graph is a coloring produced by considering the vertices in some sequence and assigning each vertex the first available color.
2264:. It is so called because applying a greedy coloring algorithm to a degeneracy ordering of the graph uses at most this many colors.
7879:
1. A theta graph is the union of three internally disjoint (simple) paths that have the same two distinct end vertices.
7334:
2. A simple path or a simple cycle is a path or cycle that has no repeated vertices and consequently no repeated edges.
4732:
of a tree is the number of edges in a longest possible path, going away from the root, that starts at the root and ends at a leaf.
5860:
has minimum total weight, possibly restricted to cuts that separate a designated pair of vertices; they are characterized by the
1955:
of a graph is the length of its longest simple cycle. The graph is
Hamiltonian if and only if its circumference equals its order.
8060:
of a graph is a minimal graph having the same transitive closure; directed acyclic graphs have a unique transitive reduction. A
7954:
is a representation of the vertices and edges of a graph by points and curves in the plane (not necessarily avoiding crossings).
4907:
is one that does not have a
Hamiltonian cycle, but for which every one-vertex deletion produces a Hamiltonian subgraph. Compare
4396:
is a directed graph where every vertex has out-degree one. Equivalently, a functional graph is a maximal directed pseudoforest.
2364:
is one in which every two vertices on opposite sides of the partition of vertices are adjacent. A complete bipartite graph with
1493:
2. The butterfly network is a graph used as a network architecture in distributed computing, closely related to the
7996:
that starts and ends at the same vertex and has no repeated edges. Euler tours are tours that use all of the graph edges; see
7391:
between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes
6379:
3. An order or ordering of a graph is an arrangement of its vertices into a sequence, especially in the context of
3780:
An ear of a graph is a path whose endpoints may coincide but in which otherwise there are no repetitions of vertices or edges.
3025:. An edge-deck is formed in the same way by deleting a single edge in all possible ways. The graphs in a deck are also called
983:
A bipartite or multipartite graph is balanced if each two subsets of its vertex partition have sizes within one of each other.
9532:
9490:
9408:
9351:
9319:
9173:
1783:
1. A chord of a cycle is an edge that does not belong to the cycle, for which both endpoints belong to the cycle.
2693:
8435:(also called an apex or dominating vertex) is a vertex that is adjacent to every other vertex in the graph. For instance,
6383:(an order of a directed acyclic graph in which every edge goes from an earlier vertex to a later vertex in the order) and
3112:-core number, width, and linkage, and one plus the degeneracy is also called the coloring number or Szekeres–Wilf number.
8158:. The width of a tree decomposition is one less than the maximum number of vertices in any of its bags; the treewidth of
6490:
is a graph that can be embedded in the plane (without crossings) so that all vertices are on the outer face of the graph.
4709:. Havens can be used to characterize the treewidth of finite graphs and the ends and Hadwiger numbers of infinite graphs.
4471:
The fundamental object of study in graph theory, a system of vertices connected in pairs by edges. Often subdivided into
17:
8263:
4894:
is a generalization of a graph in which each edge (called a hyperedge in this context) may have more than two endpoints.
478:
of a graph is a matrix whose rows and columns are both indexed by vertices of the graph, with a one in the cell for row
9581:
5981:, a decomposition of a graph into subgraphs within which all vertices connect to the rest of the graph in the same way.
4665:
2470:
1111:
are the subsets of vertices of each color. However, unless the graph is connected, it may not have a unique 2-coloring.
5756:
is maximal for a particular property if it has that property but no other supergraph of it that is also a subgraph of
4217:-factorization is an edge coloring with the additional property that each vertex is incident to an edge of each color.
6711:
onto the
Euclidean plane. A plane graph is a planar graph for which a particular embedding has already been fixed. A
4705:
vertices to one of its flaps, often satisfying additional consistency conditions. The order of a haven is the number
3647:
1. Two subgraphs are edge disjoint if they share no edges, and vertex disjoint if they share no vertices.
3425:, a directed edge is again one that has a distinguished direction; directed edges may also be called arcs or arrows.
9010:
4292:
1968:
defining edges to be sets of two vertices) classes of graphs are usually not sets when formalized using set theory.
6648:
is a partition of the edges of a graph into perfect matchings so that each two matchings form a
Hamiltonian cycle.
3273:
nodes, the density is the ratio of the number of edges of the graph to the number of edges in a complete graph on
6770:
is a closely related concept, derived from a power of a tree by taking the subgraph induced by the tree's leaves.
4866:, having any number of endpoints, in contrast to the requirement that edges of graphs have exactly two endpoints.
4035:
1474:
or isthmus-free graph is a graph that has no bridge edges (i.e., isthmi); that is, each connected component is a
7735:
are also called "very strongly perfect graphs" because in them, every vertex belongs to such an independent set.
6042:
is a graph that allows multiple adjacencies (and, often, self-loops); a graph that is not required to be simple.
3690:
between any two vertices in a graph is the length of the shortest path having the two vertices as its endpoints.
1071:
The smallest possible ratio of the number of neighbors of a proper subset of vertices to the size of the subset.
5009:
2345:
is one in which every two vertices are adjacent: all edges that could exist are present. A complete graph with
2249:(every 2-colored subgraph is acyclic), co-coloring (every color class induces an independent set or a clique),
1790:
is a graph in which every cycle of four or more vertices has a chord, so the only induced cycles are triangles.
5012:
is a set of vertices that induces an edgeless subgraph. It may also be called a stable set or a coclique. The
2731:
is a set of edges incident to every vertex in a graph. A set of subgraphs of a graph covers that graph if its
9160:, Graduate Texts in Mathematics, vol. 173 (5th ed.), Berlin, New York: Springer-Verlag, p. 3,
9115:
5941:
5667:
of the vertices in the graph. For instance, a graph is locally finite if all of its neighborhoods are finite.
8856:
s. A vertex-weighted graph has weights on its vertices and an edge-weighted graph has weights on its edges.
6792:
are a phenomenon in which the number of vertices of a given degree is proportional to a power of the degree.
5518:
refers to several different problems of assigning labels to graphs subject to certain constraints. See also
2429:
2. A completion of a given graph is a supergraph that has some desired property. For instance, a
9519:, Graduate Texts in Mathematics, vol. 173, Berlin, Heidelberg: Springer Berlin Heidelberg, p. 2,
8775:
7705:
7676:
6777:
is a method for analyzing complex networks by identifying cliques, bicliques, and stars within the network.
6617:
6116:
5664:
4793:
2482:
1971:
2. A color class of a colored graph is the set of vertices or edges having one particular color.
1952:
45:
9217:
van der Holst, Hein (March 2009), "A polynomial-time algorithm to find a linkless embedding of a graph",
8995:
5277:
An isolated vertex of a graph is a vertex whose degree is zero, that is, a vertex with no incident edges.
2990:
generated by the simple cycles in a graph, often over the field of 2 elements but also over other fields.
2544:
2494:
2388:
451:
1. A graph is acyclic if it has no cycles. An undirected acyclic graph is the same thing as a
8259:
states that Turán graphs have the maximum number of edges among all clique-free graphs of a given order.
7479:
A subgraph is spanning when it includes all of the vertices of the given graph. Important cases include
6731:
is an oriented tree; equivalently, a directed acyclic graph whose underlying undirected graph is a tree.
6387:(an order in which each vertex has minimum degree in the induced subgraph of it and all later vertices).
566:
of the matching and the augmenting path; a matching is maximum if and only if it has no augmenting path.
282:
is the matching number of the graph, which equals the independence number of its line graph. Similarly,
9093:
6911:
6416:
6213:
A non-edge or anti-edge is a pair of vertices that are not adjacent; the edges of the complement graph.
5925:
5371:
For the notation for complete graphs, complete bipartite graphs, and complete multipartite graphs, see
5037:
of a graph, a subset of edges is independent if the corresponding subgraph is a tree or forest. In the
1378:
of this binary tree, of the number of shared vertices between the subgraphs determined by the edges of
1268:: a set of edges whose removal disconnects the graph, for which no proper subset has the same property.
1129:
graph in which there are only two different vertex degrees, one for each set of the vertex bipartition.
362:
9243:
Sudakov, Benny; Volec, Jan (2017), "Properly colored and rainbow copies of graphs with few cherries",
5537:
1. A leaf vertex or pendant vertex (especially in a tree) is a vertex whose degree is
8011:
7104:
7092:
6624:
6424:
6384:
5347:
3650:
2. The disjoint union of two or more graphs is a graph whose vertex and edge sets are the
3089:
3022:
2732:
2261:
1593:
1299:
2. Another type of graph, also called a book, or a quadrilateral book, is a collection of
9423:
Watts, Duncan J.; Strogatz, Steven H. (June 1998), "Collective dynamics of 'small-world' networks",
6970:
3084:-degenerate graph is an undirected graph in which every induced subgraph has minimum degree at most
2505:, and an edge connecting pairs of components that contain the two endpoints of at least one edge in
1455:
is a cycle with at most one bridge; it must be a face boundary in any planar embedding of its graph.
8505:
8376:
is a graph in which the two endpoints of each edge are not distinguished from each other. See also
7958:
7907:
7558:
6612:
is a graph in which, in every induced subgraph, the chromatic number equals the clique number. The
5988:
of a graph clustering, the difference of the number of cross-cluster edges from its expected value.
5861:
4557:
A variable often used to denote a graph, especially when another graph has already been denoted by
4026:
is a graph whose edge expansion, vertex expansion, or spectral expansion is bounded away from zero.
2549:
2361:
1034:
1016:
4796:
as being the graphs with no odd holes or odd anti-holes. The hole-free graphs are the same as the
4521:
3363:
undirected graphs as they require repeating the same edge twice, which violates the definition of
1990:
is a tree with one internal vertex and three leaves, or equivalently the complete bipartite graph
9000:
6089:
is often used (especially in computer science) to denote the number of vertices in a given graph.
5713:
5027:
3687:
1801:
31:
9311:
9305:
7119:
in all possible ways. In this context, reconstruction is the formation of a graph from its deck.
5679:
or self-loop is an edge both of whose endpoints are the same vertex. It forms a cycle of length
2295:
8954:
8689:
8388:, an undirected edge is again one in which the endpoints are not distinguished from each other.
8203:
8061:
7725:
7718:
7424:
6440:
6266:
6183:. When the openness or closedness of a neighborhood is not specified, it is assumed to be open.
5188:
4740:
3006:
2560:
2478:
1794:
1475:
1338:
575:
456:
7832:. Some sources require in addition that a superconcentrator be a directed acyclic graph, with
9576:
8787:
8586:
8510:
7912:
7521:
6834:
6692:
6613:
6586:. It is also known as interval thickness, vertex separation number, or node searching number.
5985:
5978:
4904:
4186:
4061:
2. The vertex expansion, vertex isoperimetric number, or magnification of a graph
3675:
3129:
2831:
2744:
2474:
2277:
2012:
1494:
1417:
1054:
633:
585:
466:
of an undirected graph is a proper coloring in which every two color classes induce a forest.
49:
9301:
8256:
6296:-element set, and an edge connecting two subsets when their corresponding sets are disjoint.
3359:
is a simple cycle of length two in a directed graph or a multigraph. Digons cannot occur in
2751:, used for graphs which do not have a property but for which every one-vertex deletion does.
9500:
9432:
9361:
9081:
8451:
8195:
8057:
7546:
7436:
7404:
6967:-regular graph, such that the second-largest eigenvalue of its adjacency matrix is at most
6923:
6774:
6380:
6243:
5773:
5562:
5541:. A leaf edge or pendant edge is the edge connecting a leaf vertex to its single neighbour.
4694:
4460:
4439:. When used as an adjective, it means related to shortest paths or shortest path distances.
3421:
is one in which the edges have a distinguished direction, from one vertex to another. In a
2937:
2924:
and reversals of the walk produce the same cycle. Important special types of cycle include
2905:
2893:
1592:
A graph formed from a given graph by deleting one vertex, especially in the context of the
1435:
and in which each two vertices and edges belong to a path that is internally disjoint from
1359:
1204:
1177:
563:
455:. An acyclic directed graph, which is a digraph without directed cycles, is often called a
9336:
The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968)
7596:
of a bipartite graph is the subgraph of its square induced by one side of the bipartition.
4421:
The genus of a graph is the minimum genus of a surface onto which it can be embedded; see
2133:
3. A graph is transitively closed if it equals its own transitive closure; see
8:
8783:
8751:
8682:
8219:
8089:
8065:
8049:
7965:
7664:
7633:
7610:
defined from points in the plane with integer coordinates connected by unit-length edges.
7488:
7383:
6785:
6522:
6432:
5676:
5398:
5160:
5013:
4991:
4913:, used for graphs which have a property but for which every one-vertex deletion does not.
4752:
4624:
4367:
4342:
4299:
is one of the graphs that does not occur as a subgraph, induced subgraph, or minor, then
4202:
3927:
3576:
2662:
2643:
2273:
1987:
1975:
1559:
1277:
502:
1. The relation between two vertices that are both endpoints of the same edge.
452:
304:
is the chromatic index of the graph, which equals the chromatic number of its line graph.
9436:
8230:
A trivial graph is a graph with 0 or 1 vertices. A graph with 0 vertices is also called
7451:
is a subspace of the edge space that has the cut-sets of the graph as its elements. The
7435:
may be associated with a graph. Each has sets of edges or vertices for its vectors, and
7163:
A regular tournament is a tournament where in-degree equals out-degree for all vertices.
5776:
is a planar graph such that adding any more edges to it would create a non-planar graph.
4508:
3698:
A domatic partition of a graph is a partition of the vertices into dominating sets. The
2692:
4. In the theory of graph matchings, the core of a graph is an aspect of its
9456:
9252:
8987:
8881:
8187:
8127:
8053:
7801:
A superconcentrator is a graph with two designated and equal-sized subsets of vertices
7692:
7415:
A source, in a directed graph, is a vertex with no incoming edges (in-degree equals 0).
7009:
7008:
A ray, in an infinite graph, is an infinite simple path with exactly one endpoint. The
6903:
6789:
6542:
6428:
5450:
5184:
5135:
5054:
5038:
4821:
4809:
3962:
2921:
2848:
2651:
2430:
2211:
2051:
1964:
1924:
1812:
1678:
1581:
951:
867:
414:
394:
342:
322:
9547:
9110:
7342:
A sink, in a directed graph, is a vertex with no outgoing edges (out-degree equals 0).
9528:
9514:
9486:
9448:
9404:
9347:
9315:
9203:
9169:
9047:
8981:
7951:
7524:
is the branch of graph theory that uses spectra to analyze graphs. See also spectral
7464:
6487:
6250:
5913:
5655:
is a variation of graph coloring in which each vertex has a list of available colors.
5526:
5300:
4943:
4329:
4127:
3989:
3789:
3207:
3136:(or its maximum degree) is the maximum of the degrees of its vertices, often denoted
2925:
2786:
2779:
2501:
is a directed acyclic graph with one vertex for each strongly connected component of
2455:
2450:
2250:
1444:
440:
8266:
asks for the minimum number of crossings in a drawing of a complete bipartite graph.
8064:
is an orientation of a graph that is its own transitive closure; it exists only for
7728:
is a chordal graph in which every even cycle of length six or more has an odd chord.
6578:. It may also be defined in terms of the clique number of an interval completion of
6191:
A graph in which attributes (e.g. names) are associated with the nodes and/or edges.
4514:
9520:
9478:
9460:
9440:
9339:
9262:
9226:
9198:
9161:
9124:
9077:
9042:
9005:
8897:
8432:
8373:
7636:
is a tree with one internal vertex; equivalently, it is a complete bipartite graph
7484:
6657:
6632:
5826:
is a graph in which every odd cycle of length five or more has at least two chords.
5741:
5722:
5717:
5072:
4955:
4677:
4668:
is the conjecture that the
Hadwiger number is never less than the chromatic number.
4492:
4476:
4393:
3950:
3021:
by deleting a single vertex in all possible ways, especially in the context of the
2933:
2592:
2518:
2437:
2290:
2246:
2245:(proper coloring with each vertex restricted to a subset of the available colors),
2173:
1834:
1808:
1619:
1490:
has five vertices and six edges; it is formed by two triangles that share a vertex.
1471:
1452:
686:
475:
463:
8312:
are neighbors), and they are false twins if they have the same open neighborhood:
7891:
7487:, spanning subgraphs that are matchings. A spanning subgraph may also be called a
4619:-free graphs are the family of all graphs (or, often, all finite graphs) that are
3801:
The eccentricity of a vertex is the farthest distance from it to any other vertex.
1323:, a boundary walk is the subgraph containing all incident edges and vertices to a
9496:
9398:
9357:
8869:
8676:
8447:
8440:
8425:
8077:
8023:
7256:
7185:
1. A designated vertex in a graph, particularly in directed trees and
6960:
6927:
6887:
6708:
6678:
6645:
6361:
6027:
5940:
as a minor. A family of graphs is minor-closed if it is closed under minors; the
5835:
5761:
5034:
4946:
in a graph is a vertex-edge pair such that the vertex is an endpoint of the edge.
4875:
4658:
4537:
4524:
that triangle-free planar graphs can always be colored with at most three colors.
4496:
4283:
of a cycle, which is either a flap of the cycle vertices or a chord of the cycle.
4249:
4162:
3914:
3211:
2772:
2689:, and is a core in the sense that all of its self-homomorphisms are isomorphisms.
2207:
2161:
2115:
1. A closed neighborhood is one that includes its central vertex; see
2000:
1863:
1487:
1370:, represented by an unrooted binary tree with its leaves labeled by the edges of
1350:
A path of degree-two vertices, ending at vertices whose degree is unequal to two.
1320:
1120:
1080:
992:
9189:
Woodall, D. R. (1973), "The Binding Number of a Graph and its Anderson Number",
8364:
In a rooted tree, a unary vertex is a vertex which has exactly one child vertex.
4517:, the smallest triangle-free graph requiring four colors in any proper coloring.
2124:
2. A closed walk is one that starts and ends at the same vertex; see
256:
is often used to modify notation for graph invariants so that it applies to the
9378:
9282:
9267:
9230:
9089:
8966:
8726:
8243:
7407:
is a simple, connected, bridgeless cubic graph with chromatic index equal to 4.
7204:
is another graph on the same vertex set such that two vertices are adjacent in
6847:
6685:
6447:
5996:
A monotone property of graphs is a property that is closed under subgraphs: if
5789:
5765:
5645:
5519:
5515:
5194:
2. The interval in a graph is the union of all shortest paths from
5180:
5148:
4628:
4472:
4023:
3943:
3923:
3902:
3711:
3699:
3651:
3418:
3376:
2342:
2254:
2198:
1797:
is a chordal graph in which every cycle of length six or more has an odd chord.
1576:
1307:
505:
2. The relation between two distinct edges that share an end vertex.
253:
9524:
9165:
8249:
6963:
is a graph whose spectral expansion is as large as possible. That is, it is a
5167:
is the minimum total number of elements in any intersection representation of
4014:
Divisible by two; for instance, an even cycle is a cycle whose length is even.
3132:
of a vertex in a graph is its number of incident edges. The degree of a graph
3063:
1404:
1303:-cycles joined at a shared edge; the Cartesian product of a star with an edge.
9570:
8865:
8501:
7903:
7732:
7607:
7480:
7428:
7144:
6907:
6609:
6530:
6436:
5971:
5897:
5823:
5801:
5652:
5558:
5140:
5080:
4797:
4652:
4533:
4436:
4354:
4312:
4002:
3319:
3307:
2929:
2705:
2685:
is unique up to isomorphism. It can be represented as an induced subgraph of
2242:
2238:
2025:
1896:
1871:
1787:
1682:
1459:
8622:
7284:
3057:
3051:
2862:
2782:, formed from a hypercube by adding a matching connecting opposite vertices.
2625:
is the induced subgraph formed by removing all vertices of degree less than
2241:(coloring edges so that no two edges with the same endpoint share a color),
971:
823:
9338:, Lecture Notes in Mathematics, vol. 110, Springer, pp. 223–230,
8744:
8738:
7500:
7468:
7444:
7327:
7186:
7016:
6860:
6704:
6526:
6277:
5808:
5566:
5156:
5144:
5123:) if they do not have any vertex in common, except the first and last ones.
5076:
5042:
4448:
4360:
4158:
4134:-shallow minors have a ratio of edges to vertices bounded by a function of
4116:
3919:
3811:
3364:
3360:
2987:
2883:
2797:
2724:
2215:
2087:
2043:
1940:
1920:
1816:
1631:
1547:
1170:
is a bipartite graph where one partite set consists of the cut-vertices of
726:
41:
9452:
6906:
is a sequence of graphs that shares several properties with a sequence of
4269:-flap is a connected component of the induced subgraph formed by deleting
3702:
of the graph is the maximum number of dominating sets in such a partition.
2834:, a cubic graph formed by replacing each vertex of a hypercube by a cycle.
1660:, no other vertex has subtree size greater than half the size of the tree.
891:
the graph. More generally, a vertex whose removal increases the number of
805:
9477:, Lecture Notes in Mathematics, vol. 303, Springer, pp. 43–54,
9304:; Le, Van Bang; Spinrad, Jeremy (1999), "Chapter 7: Forbidden Subgraph",
8893:
8722:
8436:
8385:
7883:
7600:
7593:
7574:
7539:
7452:
7193:
6740:
6023:
5959:
5877:
5842:
5663:
A local property of a graph is a property that is determined only by the
5454:
4812:
if there exist two homomorphisms, one from each graph to the other graph.
4480:
4277:, functions that map small sets of vertices to their flaps. See also the
3422:
3278:
2983:
2961:
2820:
2808:
2790:
1936:
1529:
1240:
917:
881:
8488:
7978:
6127:. The closed neighbourhood is defined in the same way but also includes
5445:
5057:
is another name for a proper interval graph or unit interval graph; see
1427:
is a maximal connected subgraph separated from the rest of the graph by
847:
743:
9482:
9343:
9129:
9085:
9030:
8231:
7848:
A graph formed by adding vertices, edges, or both to a given graph. If
7789:
7517:
7440:
6891:
6808:
6767:
6306:
6078:
6039:
5725:
is a matching that uses as many edges as possible; the matching number
5597:
5545:
5485:
5285:
Two graphs are isomorphic if there is an isomorphism between them; see
5152:
4996:
4891:
3724:
3607:
3389:
2765:
2728:
2237:
3. Many variations of coloring have been studied, including
2181:
2117:
906:
665:
257:
9033:; Miller, D. J. (1986), "Concerning the achromatic number of graphs",
8931:
8610:
8280:
7044:
6947:
6752:
is another graph on the same vertex set; two vertices are adjacent in
6665:
6446:
2. Oriented graph, used by some authors as a synonym for a
6372:
6076:
1. For the notation for open and closed neighborhoods, see
5041:, a subset of edges is independent if the corresponding subgraph is a
4828:
2. The homomorphism degree of a graph is a synonym for its
4088:
is the minimum ratio, over subsets of at most half of the vertices of
3922:
is a graph that has such an embedding onto the Euclidean plane, and a
3842:
3621:
3343:
3218:
2. The homomorphism degree of a graph is a synonym for its
1636:
1462:
is a graph in which every cycle of four or more vertices has a bridge.
924:-ary tree is said to be complete if every internal vertex has exactly
59:
9310:, SIAM Monographs on Discrete Mathematics and Applications, pp.
8925:
8685:
that the chromatic index is at most one more than the maximum degree.
8175:
7697:
7620:
7448:
6781:
6567:
6366:
6273:
6223:
5287:
4879:
4370:
that every finite group is the group of symmetries of a finite graph.
4363:, one of the two smallest cubic graphs with no nontrivial symmetries.
4189:
is a graph for which deleting any one vertex produces a graph with a
3521:
3206:. The total degree is the sum of the degrees of all vertices; by the
2875:
2074:
938:
916:
children. A 1-ary tree is just a path. A 2-ary tree is also called a
629:
532:
8910:
8628:
6249:
2. An odd vertex is a vertex whose degree is odd. By the
6006:
5632:
5093:
4862:
3240:(using the Greek letter delta) is the maximum degree of a vertex in
2635:
2153:
2135:
887:
9257:
8943:
8937:
8919:
8884:
is a graph all of whose maximal independent sets are the same size.
8779:
7824:
there exists a family of disjoint paths connecting every vertex in
7761:
is another graph formed from a subset of the vertices and edges of
7687:
7681:
7526:
7298:
7243:
7173:
6728:
6420:
5946:
5900:
if it can be formed as a minor in such a way that the subgraphs of
5700:
5648:
is a computer representation of graphs for use in graph algorithms.
5581:
of a node plus 1, although some define it instead to be synonym of
5431:
5313:
5241:
5207:
4842:
4755:
of graphs is a property that is closed under induced subgraphs: if
4423:
3931:
3635:
3557:
3539:
3492:
3337:
2606:
2580:
2531:
1744:
1695:
1622:
or caterpillar is a tree in which the internal nodes induce a path.
1125:
1059:
1049:
893:
783:
9444:
8812:
7998:
7229:
7127:
A simple cycle consisting of exactly four edges and four vertices.
6637:
6513:
along the incoming edge, the one that is directed toward the root.
5373:
5221:
4909:
4765:
4759:
has a hereditary property, then so must every induced subgraph of
3866:
3768:
3581:
3031:
2827:-regular graph, one in which each vertex has three incident edges.
2458:
of a graph is the maximum number of colors in a complete coloring.
2442:
2180:
is a graph produced by operations that include complementation; a
2151:
1. For the transitive closure of a directed graph, see
2060:
1750:
1562:
is a regular graph with the smallest possible order for its girth.
1021:
954:
is a symmetry of a graph, an isomorphism from the graph to itself.
549:
443:
of a graph is the maximum number of colors in a complete coloring.
9473:
Bondy, J. A. (1972), "The "graph theory" of the Greek alphabet",
8222:
is an undirected graph that does not have any triangle subgraphs.
7710:
6715:-planar graph is one that can be drawn in the plane with at most
6398:
6253:
every finite undirected graph has an even number of odd vertices.
5856:
4777:
4380:
3860:
2888:
2712:
2210:
are the graphs that have colorings with only two colors, and the
2177:
2164:
is the problem of finding a closure of minimum or maximum weight.
2104:
2003:
is a graph that does not have an induced subgraph that is a claw.
1374:. The width of a branch-decomposition is the maximum, over edges
1264:
1259:
1166:
3. The block-cut (or block-cutpoint) graph of a graph
912:
is a rooted tree in which every internal vertex has no more than
678:-apex graph is a graph that can be made planar by the removal of
232:
8852:
8840:
8604:
8572:
8482:
8470:
7783:
7745:
7655:. The special case of a star with three leaves is called a claw.
7050:
7024:
6802:
6688:, a 10-vertex 15-edge graph frequently used as a counterexample.
6460:
6201:
5425:
5423:
A kernel of a directed graph is a set of vertices which is both
5407:
5327:
5107:
5059:
4930:
4783:
A simple cycle consisting of exactly six edges and six vertices.
4279:
3854:
3605:
2. The asymmetric relation between two vertices in a
3586:
3498:
3331:
3257:
1903:
available colors. The choosability of the graph is the smallest
1770:
along an outgoing edge, one that is directed away from the root.
1431:. That is, it is a maximal subgraph that is edge-disjoint from
1280:, book graph, or triangular book is a complete tripartite graph
1245:
1159:
875:
731:
670:
8834:
8616:
8464:
8454:
in a formula may be called a universal vertex for that formula.
8096:
7030:
6826:
6392:
6242:
1. An odd cycle is a cycle whose length is odd. The
5962:
is a graph that may include both directed and undirected edges.
5588:
2. A set of all node having the same level or depth.
5235:
4227:
3848:
3598:
3592:
3463:
3449:
3435:
3041:(graphs that do not have a property that is held by all cards).
3037:
3035:(graphs that have a property that is not held by any card) and
2619:
2218:
can be colored with at most four colors. A graph is said to be
1847:
is the minimum number of colors needed in a proper coloring of
1829:
1534:
530:(using the Greek letter alpha) is its independence number (see
8846:
8476:
8036:
7992:
7270:
7067:
6871:
A pseudograph is a graph or multigraph that allows self-loops.
6596:
6474:
6353:
6315:
5944:
characterizes minor-closed families as having a finite set of
5811:
is a graph in which every three vertices have a unique median.
5494:
5331:, in the sense of an edge whose removal disconnects the graph.
4856:
3930:
of a graph is the minimum possible genus of a two-dimensional
3836:
3484:
3477:
2916:
2914:. As a walk it may be either be a closed walk (also called a
2910:
2387:. The same terminology and notation has also been extended to
2329:, with an edge for each two vertices that are not adjacent in
2126:
1833:. Chromatic graph theory is the theory of graph coloring. The
1670:
1598:
1443:
may be a set of vertices. A chord is a one-edge bridge. In
1325:
772:
761:
737:
713:
699:
27:
List of definitions of terms and concepts used in graph theory
8917:
2. For other graph invariants known as width, see
7432:
6258:
6123:
is the subgraph induced by all vertices that are adjacent to
5850:
5618:
and an edge for each pair of edges that share an endpoint in
5514:
may be used to specify which objects of a graph have labels.
4878:
is a graph formed from the vertices and edges of a geometric
3356:
3306:
The diameter of a connected graph is the maximum length of a
2964:
is a graph that is itself a simple cycle; a cycle graph with
2953:
2879:
2768:, the eight-vertex graph of the vertices and edges of a cube.
2604:
The converse graph is a synonym for the transpose graph; see
2260:
4. The coloring number of a graph is one plus the
2094:
is the minimum number of distinct labels needed to construct
656:
A three-vertex independent set, the complement of a triangle.
8186:. It can also be defined in terms of the clique number of a
6894:. They are used in the structure theory of claw-free graphs.
4607:-free if it does not have an induced subgraph isomorphic to
1084:
colored with two colors. Bipartite graphs are often written
9384:
9288:
9098:(2 ed.), MIT Press and McGraw-Hill, pp. 1080–1084
8134:
is a tree whose nodes are labeled with sets of vertices of
6660:
or non-separating cycle is a cycle with at most one bridge.
4479:
according to whether the edges have an orientation or not.
4034:
1. The edge expansion, isoperimetric number, or
3409:
The head of a directed edge whose tail is the given vertex.
3401:
The tail of a directed edge whose head is the given vertex.
2727:
is a set of vertices incident to every edge in a graph. An
1935:
A circuit may refer to a closed trail or an element of the
1811:
is a line segment connecting two points on the circle; the
9143:
9076:
7115:, a multiset of graphs formed by removing one vertex from
6582:. It is always between the bandwidth and the treewidth of
4273:. The flap terminology is commonly used in the context of
4123:
of its adjacency matrix and the second-largest eigenvalue.
2735:– taken vertex-wise and edge-wise – is equal to the graph.
582:
of vertices that are pairwise incomparable, i.e., for any
8692:
on the domination number of Cartesian products of graphs.
7467:, graphs whose vertices are points in a geometric space;
6695:
that every bridgeless cubic graph has a perfect matching.
4728:
of a rooted tree is the height of its root. That is, the
4536:
of a graph is the maximum number of colors produced by a
4240:
infinitely many vertices, infinitely many edges, or both.
4205:
is a partition of the edges of the graph into factors; a
3322:
is an undirected graph with four vertices and five edges.
2711:
2. A rooted tree structure used to describe a
668:
is a graph in which one vertex can be removed, leaving a
6000:
has a monotone property, then so must every subgraph of
5744:
is a matching to which no additional edges can be added.
3926:
is a graph that has such an embedding onto a torus. The
2775:, a higher-dimensional generalization of the cube graph.
1727:(using the Greek letter chi) is the chromatic number of
8754:
characterizing planar graphs by their forbidden minors.
6390:
4. For the order of a haven or bramble, see
4743:
is the maximum length of a directed path in this graph.
4084:
3. The unique neighbor expansion of a graph
4982:
The relation between an edge and one of its endpoints.
4928:
The number of incoming edges in a directed graph; see
4639:-minor-free if it does not have a minor isomorphic to
8513:
8146:
must induce a subtree of the tree, and for each edge
7915:
6973:
2436:
3. A complete matching is a synonym for a
2298:
1207:
1180:
588:
417:
397:
365:
345:
325:
9028:
8977:
7455:
has the Eulerian spanning subgraphs as its elements.
6663:
2. A peripheral vertex is a vertex whose
5764:
of the subgraphs with the property. For instance, a
4073:, of the number of vertices outside but adjacent to
3148:
is the minimum of its vertex degrees, often denoted
1390:
is the minimum width of any branch-decomposition of
9334:Mitchem, John (1969), "Hypo-properties in graphs",
9300:
5888:can be obtained by deleting edges or vertices from
5819:
1. Henri Meyniel, French graph theorist.
5155:(intersection graphs of the edges of a graph), and
4185:-factor is the same thing as a perfect matching. A
2172:This prefix has various meanings usually involving
674:subgraph. The removed vertex is called the apex. A
8757:4. Wagner's theorem characterizing the
8532:
8162:is the minimum width of any tree decomposition of
7934:
7695:is an orientation that is strongly connected; see
6992:
5205:3. Interval thickness is a synonym for
3108:later neighbours. Degeneracy is also known as the
3017:The multiset of graphs formed from a single graph
2629:, and all vertices whose degree becomes less than
2313:
1870:, the minimum number of colors needed in a proper
1220:
1193:
1149:is another graph whose vertices are the blocks of
999:is the minimum, over all orderings of vertices of
600:
423:
403:
383:
351:
331:
8798:if its first and last vertices are distinct, and
7314:is a vertex which has the same parent vertex as
5105:An infinite graph is one that is not finite; see
1236:is connected, its block-cutpoint graph is a tree.
9568:
8412:. For instance, ordinary graphs are the same as
8182:is the minimum width of a tree decomposition of
6574:is the minimum width of a path decomposition of
5740:is the number of edges in a maximum matching. A
5522:, in which the labels are interpreted as colors.
5397:(using the Greek letter kappa) can refer to the
4990:An incomparability graph is the complement of a
4825:described as a homomorphism to a complete graph.
4328:
2800:, a distance-preserving subgraph of a hypercube.
2222:-colored if it has been (properly) colored with
2143:minor-closed properties are closed under minors.
1311:single half-plane, one of the pages of the book.
562:vertices. A larger matching can be found as the
7491:, especially (but not only) when it is regular.
6635:is a matching that saturates every vertex; see
5792:is any of the largest cliques in a given graph.
4463:of a graph is the length of its shortest cycle.
4327:is sufficient to test whether that sequence is
3009:, a directed graph without any directed cycles.
2696:, formed as the union of all maximum matchings.
1943:of a graph is the dimension of its cycle space.
9113:(1973), "Acyclic colorings of planar graphs",
8138:; these sets are called bags. For each vertex
7809:, such that for every two equal-sized subsets
7139:-regular when all of its vertices have degree
6896:
5151:(intersection graphs of intervals of a line),
4138:, and polynomial expansion if the function of
3731:is a graph that has a vertex for each face of
359:is a set of vertices such that for any vertex
9422:
9373:
9371:
9216:
7516:The spectrum of a graph is the collection of
6166:, and the closed neighborhood may be denoted
5760:also has the same property. That is, it is a
5147:(intersection graphs of chords of a circle),
5143:(intersection graphs of subtrees of a tree),
5083:, induced subgraphs that are paths or cycles.
4319:such that evaluating the subgraph density of
3810:also called arcs or arrows. In an undirected
2253:(every two color classes share an edge), and
1685:, namely a set of vertices or a set of edges.
1634:of a graph is the set of vertices of minimum
1584:is the process of computing a canonical form.
1366:is a hierarchical clustering of the edges of
9242:
8700:The sum of the degrees of a set of vertices.
8278:are true twins if they have the same closed
8114:-cliques. A tree in the ordinary sense is a
8026:is a graph that contains a Hamiltonian path.
7260:which variables can only represent vertices.
6443:, orientations that are transitively closed.
6431:, orientations that are strongly connected;
6102:A vertex that is adjacent to a given vertex.
3104:-degenerate graph, every vertex has at most
2936:, and the shortest cycle, which defines the
2372:vertices on the other side is often denoted
697:Synonym for a rooted and directed tree; see
8957:is the maximum cardinality of an antichain.
7443:is the space of all sets of edges, and the
7012:of a graph are equivalence classes of rays.
6669:is maximum. In a tree, this must be a leaf.
2908:may be either a kind of graph or a kind of
2559:vertices cannot disconnect the graph), and
2325:is another graph on the same vertex set as
9368:
8252:is a balanced complete multipartite graph.
8150:there must exist a bag that contains both
7675:1. For strong connectivity and
7447:is the space of all sets of vertices. The
7370:is often used for this quantity. See also
7296:Vertex separation number is a synonym for
7208:if and only if they have distance at most
6930:. The edges of a quiver are called arrows.
6351:is often used for this quantity. See also
5614:is a graph with a vertex for each edge of
4802:
4107:4. The spectral expansion of a
2368:vertices on one side of the partition and
689:, a vertex adjacent to all other vertices.
260:instead of the given graph. For instance,
9266:
9256:
9245:Journal of Combinatorial Theory, Series B
9219:Journal of Combinatorial Theory, Series B
9202:
9128:
9046:
9035:Journal of Combinatorial Theory, Series B
7483:, spanning subgraphs that are trees, and
7439:of sets as its vector sum operation. The
7192:2. The inverse operation to a
5904:that were contracted to form vertices of
5683:. These are not allowed in simple graphs.
4435:As a noun, a geodesic is a synonym for a
3993:algorithmically listing all such objects.
3116:-degenerate graphs have also been called
3062:
2896:of sets as its vector addition operation.
2673:such that there exist homomorphisms from
1677:2. When applying methods from
1403:
1342:the maximum order of any of its brambles.
1145:2. The block graph of a graph
9403:, New York: Springer-Verlag, p. 5,
9156:Diestel, Reinhard (2017), "1.1 Graphs",
9109:
7310:In a rooted tree, a sibling of a vertex
5752:1. A subgraph of given graph
4832:, the order of the largest clique minor.
4584:is also a graph) is a homomorphism from
4413:A variable often used to denote a graph.
3953:, a graph with no vertices and no edges.
3222:, the order of the largest clique minor.
2433:is a supergraph that is a chordal graph.
2042:is the order of its largest clique. The
936:A special type of alternating path; see
9512:
9333:
9188:
9155:
8621:
7970:
7606:3. A square grid graph is a
7283:
7241:Node searching number is a synonym for
6890:and they include as a special case the
6505:In a rooted tree, a parent of a vertex
4635:-free is always hereditary. A graph is
3056:
3050:
2861:
1602:, the multiset of all cards of a graph.
1352:
970:
822:
271:is the independence number of a graph;
14:
9569:
9396:
9149:
9072:
9070:
9068:
9066:
9064:
9062:
9060:
9058:
8218:A cycle of length three in a graph. A
7376:
7059:is said to be reachable from a vertex
6439:, orientations that are Eulerian; and
5596:A synonym for an undirected edge. The
4540:, with a badly-chosen vertex ordering.
3977:and the second endpoint is called the
3656:
2572:
2276:if its vertices are the elements of a
2257:(both edges and vertices are colored).
1815:of a collection of chords is called a
1762:In a rooted tree, a child of a vertex
9472:
8640:The set of vertices of a given graph
8120:
7157:
6945:The radius of a graph is the minimum
6926:is a directed multigraph, as used in
6535:
6044:
5245:compared to another arrow. The arrow
4631:as a subgraph. The property of being
4615:is a forbidden induced subgraph. The
4126:5. A family of graphs has
3395:
1939:(an Eulerian spanning subgraph). The
1707:A cherry is a path on three vertices.
1423:2. A bridge of a subgraph
1157:. The block graph of any graph is a
1007:, chosen to minimize the clique size.
865:
804:
7795:
7569:1. The square of a graph
7290:
7276:
6010:(closed under induced subgraphs) or
4092:, of the number of vertices outside
3782:
1019:or complete bipartite subgraph; see
880:
293:is the chromatic number of a graph;
9055:
8804:
8729:. The notation is not standardized.
8487:
8456:
8118:-tree according to this definition.
7977:
7235:
6880:
6681:(1839–1910), Danish graph theorist.
6427:, orientations of complete graphs;
6331:1. The order of a graph
5838:of the subgraphs with the property.
5444:
5350:of two graphs is formed from their
5257:is the inverted arrow of the arrow
4974:are incident, and a zero otherwise.
4948:
4386:
4209:-factorization is a partition into
4096:but adjacent to a unique vertex in
4069:of at most half of the vertices of
4065:is the minimum ratio, over subsets
4046:of at most half of the vertices of
4042:is the minimum ratio, over subsets
3403:
2892:s of the graph as its elements and
2570:edges cannot disconnect the graph).
1899:whenever each vertex has a list of
1687:
846:
742:
494:are adjacent, and a zero otherwise.
468:
24:
8790:. Walks are also sometimes called
8404:endpoints, and uniform when it is
7788:
7107:states that each undirected graph
6807:
6806:coming before a given vertex in a
6758:when they are at distance at most
6305:
6077:
4995:
4984:
4697:is a function that maps every set
4627:are the graphs that do not have a
4323:in the graphs of a graph sequence
3878:The set of edges of a given graph
3606:
3388:
2803:6. The cube of a graph
2704:1. The complement of a
2116:
1296:triangles joined at a shared edge.
1047:though it is not 2-connected. See
648:, a pair of non-adjacent vertices.
25:
9593:
8930:
8826:
8609:
8596:
8400:-uniform when all its edges have
8279:
7961:is the study of graph embeddings.
7787:coming after a given vertex in a
7618:A stable set is a synonym for an
7097:
7043:
6946:
6664:
6435:, orientations that are acyclic;
6371:
6131:itself. The open neighborhood of
5227:
4050:, of the number of edges leaving
3895:
3841:
3620:
3342:
1635:
1382:in the two subtrees separated by
1137:1. A block of a graph
1065:
969:One of the sets of vertices in a
612:, there is no directed path from
459:, especially in computer science.
384:{\displaystyle v\in G\setminus A}
375:
219:
9011:Glossary of areas of mathematics
8980:
8924:
8747:, an eight-vertex Möbius ladder.
8620:. A one-vertex cut is called an
8494:
7896:
7696:
7619:
6365:
6222:
6109:
5936:-minor-free if it does not have
5692:
5569:between two vertices in a graph.
5525:2. In the context of
5305:
5286:
4769:(closed under all subgraphs) or
4526:
4305:
4293:forbidden graph characterization
4195:
3662:A subset of vertices in a graph
3520:
3496:. If a directed path leads from
3469:
3455:
3441:
3043:
2694:Dulmage–Mendelsohn decomposition
2266:
2073:
2064:, a complete bipartite subgraph.
1974:3. In the context of
1945:
1827:Having to do with coloring; see
1604:
937:
650:
531:
9540:
9506:
9466:
9416:
9390:
9327:
9294:
8909:
8874:
8858:
8627:
8443:always have a universal vertex.
8358:
7249:
7085:
7014:
6853:
6335:is the number of its vertices,
6104:
6053:
6005:
5631:
5125:
5092:
5047:
4861:
4846:having a source and target set.
4814:
4119:between the largest eigenvalue
3795:
3627:
3427:
2634:
2487:
2234:-chromatic if this is possible.
2152:
2134:
2080:
1885:
1569:
944:
886:
691:
204:
62:
52:connected in pairs by lines or
9400:Combinatorics and Graph Theory
9275:
9236:
9210:
9182:
9137:
9103:
9022:
8942:
8936:
8918:
8896:is a graph formed by adding a
8872:use the same number of colors.
7944:
7686:
7680:
7525:
7297:
7242:
7172:
7111:is uniquely determined by its
6993:{\displaystyle 2{\sqrt {d-1}}}
6912:Erdős–Rényi random graph model
6865:
6794:
6480:
6404:
6119:(or neighborhood) of a vertex
6030:. Every Moore graph is a cage.
6016:
5945:
5840:
5699:
5430:
5312:
5293:
5240:
5206:
5002:
4841:
4670:
4422:
4242:
3983:
3946:on a nonempty set of vertices.
3936:
3934:onto which it can be embedded.
3634:
3556:
3538:
3491:
3336:
3324:
2605:
2586:
2579:
2530:
2305:
2066:
1743:
1694:
1612:
1396:
1124:
1058:
1048:
1027:
892:
782:
555:
13:
1:
9116:Israel Journal of Mathematics
9016:
8953:4. The width of a
8811:
8634:
8591:
8366:
8264:Turán's brick factory problem
8042:
8004:
7997:
7842:
7677:strongly connected components
7228:
6650:
6636:
6452:
6280:, having one vertex for each
6215:
6032:
5565:(shortest cycle length), and
5372:
5351:
5279:
5220:
4908:
4884:
4764:
4745:
4563:
4100:to the number of vertices in
4077:to the number of vertices in
4054:to the number of vertices in
3865:
3852:. A one-edge cut is called a
3767:
3704:
3671:
3613:
3580:
3159:. Degree is sometimes called
3074:
3069:
3030:
2968:vertices is commonly denoted
2483:strongly connected components
2441:
2283:
2059:
2020:-clique is a clique of order
1749:
1464:
1174:, and the other has a vertex
1020:
930:
548:
433:
199:
9204:10.1016/0095-8956(73)90038-5
9048:10.1016/0095-8956(86)90062-6
8908:1. A synonym for
8418:
8168:
8110:-cliques together on shared
8102:is a graph formed by gluing
8070:
8016:
7775:
7737:
7709:
7706:strong perfect graph theorem
7354:is the number of its edges,
7262:
7221:
7121:
7036:
7022:The ability to get from one
6953:
6618:strong perfect graph theorem
6560:
6397:
6096:
5855:
5784:A subgraph of a given graph
5443:An inescapable section of a
5213:
5085:
4936:
4922:
4868:
4848:
4794:strong perfect graph theorem
4483:include both types of edges.
4379:
4285:
4177:-factor is a factor that is
4028:
3907:
3859:
3569:
2944:-cycle is a cycle of length
2887:
2868:
2854:
2658:to itself is an isomorphism.
2633:after earlier removals. See
2537:
2463:
2389:complete multipartite graphs
1880:
1821:
1742:is its chromatic index; see
1564:
1480:
1263:
1258:
1113:
1073:
985:
638:
628:. Inspired by the notion of
568:
547:is its matching number (see
313:
231:
61:
7:
9225:(2), Elsevier BV: 512–530,
8996:List of graph theory topics
8973:
8959:
8851:
8839:
8657:
8603:
8571:
8481:
8469:
8212:
7782:
7751:
7744:
7657:
7510:
7505:
7473:
7049:
7023:
6910:generated according to the
6904:quasi-random graph sequence
6898:quasi-random graph sequence
6840:
6801:
6721:
6671:
6459:
6409:
6207:
6200:
6091:
6085:2. A lower-case
5990:
5706:
5424:
5406:
5326:
5271:
5173:
5113:
5106:
5099:
5058:
4976:
4929:
4834:
4645:
4501:
4429:
4278:
4181:-regular. In particular, a
4016:
3995:
3967:
3872:
3853:
3828:
3680:
3641:
3585:
3497:
3411:
3341:. (Not to be confused with
3330:
3300:
3256:
3255:is the minimum degree; see
3092:of a graph is the smallest
2737:
2598:
2406:then this graph is denoted
2335:
2191:
1681:to graphs, an element of a
1642:
1313:
1244:
1158:
1009:
977:
874:
730:
669:
496:
10:
9598:
9513:Diestel, Reinhard (2017),
9268:10.1016/j.jctb.2016.07.001
9231:10.1016/j.jctb.2008.10.002
9095:Introduction to Algorithms
8833:
8786:which joins a sequence of
8615:
8563:
8463:
8390:
8224:
7767:
7582:; in the other direction,
7457:
7304:
7165:
7129:
7029:
6825:
6602:
6588:
6391:
6185:
5964:
5828:
5813:
5778:
5746:
5624:
5577:1. This is the
5319:
5234:
5065:
4810:homomorphically equivalent
4775:
4226:
3847:
3692:
3654:of the corresponding sets.
3597:
3591:
3462:
3448:
3434:
3369:
3312:
3263:
3210:it is an even number. The
3036:
2841:
2523:
2349:vertices is often denoted
2314:{\displaystyle {\bar {G}}}
2145:
2054:of the maximal cliques in
1929:
1828:
1777:
1668:1. Synonym for
1533:
1331:
685:2. Synonym for
445:
214:
29:
9582:Glossaries of mathematics
9525:10.1007/978-3-662-53622-3
9166:10.1007/978-3-662-53622-3
8845:
8818:
8731:
8694:
8669:
8579:
8480:s have not been assigned
8475:
8035:
7991:
7669:
7612:
7563:
7520:of its adjacency matrix.
7493:
7409:
7374:, the number of vertices.
7320:
7269:
7105:reconstruction conjecture
7093:reconstruction conjecture
7066:
6939:
6916:
6814:
6697:
6625:perfectly orderable graph
6595:
6499:
6473:
6352:
6314:
5942:Robertson–Seymour theorem
5924:has a subgraph that is a
5908:all have small diameter.
5892:and contracting edges in
5794:
5550:
5493:
5417:
4855:
4711:
4594:
4485:
4347:
4335:
4233:
4219:
4213:-factors. For instance a
4167:
3835:
3483:
3476:
3381:
3122:
3023:reconstruction conjecture
2915:
2909:
2698:
2272:An undirected graph is a
2125:
2109:
2005:
1913:
1701:
1669:
1624:
1597:
1594:reconstruction conjecture
1540:
1410:
1344:
1324:
1040:, but sometimes includes
771:
760:
736:
712:
698:
53:
9397:Harris, John M. (2000),
9191:J. Combin. Theory Ser. B
8902:
8886:
8868:is a graph all of whose
8778:is a finite or infinite
8721:is used in notation for
8506:complete bipartite graph
8236:
8142:, the bags that contain
8028:
7959:Topological graph theory
7908:complete bipartite graph
7873:
7679:of directed graphs, see
7532:
7417:
7397:
6733:
6644:4. A perfect
6466:
6360:2. A type of
6321:
6257:
5952:
5866:
5862:max-flow min-cut theorem
5849:
5657:
5571:
5500:
5379:
4896:
4683:
4623:-free. For instance the
4465:
4453:
4441:
4415:
4303:is said to be forbidden.
4255:
3349:
3283:
3224:
3144:; the minimum degree of
2960:-cycle is a triangle. A
2898:
2758:
2717:
2553:-vertex-connected graphs
2517:A graph that contains a
2362:complete bipartite graph
2186:
1957:
1772:
1756:
1662:
1131:
1017:complete bipartite graph
899:
719:
507:
391:, there is an edge from
38:glossary of graph theory
9307:Graph Classes: A Survey
9001:Gallery of named graphs
8768:
8644:, sometimes denoted by
8533:{\displaystyle K_{3,3}}
8268:
8082:
8040:without repeated edges.
7984:
7935:{\displaystyle K_{3,3}}
7626:
7344:
7336:
7179:
6707:is a graph that has an
6515:
6441:transitive orientations
6298:
6276:is a special case of a
6267:strongly chordal graphs
6193:
5669:
5638:
5590:
5531:
5437:
5340:
5028:maximum independent set
4804:homomorphic equivalence
4785:
4372:
4151:
4008:
3882:, sometimes denoted by
3803:
3717:
3011:
2753:
2612:
2511:
2479:triconnected components
1980:
1895:-choosable if it has a
1802:chordal bipartite graph
1656:such that if rooted at
1586:
1552:
1270:
1251:
658:
601:{\displaystyle x\leq y}
32:Gallery of named graphs
9548:"Chain - graph theory"
9092:(2001), "B.4 Graphs",
9029:Farber, M.; Hahn, G.;
8955:directed acyclic graph
8534:
8452:universally quantified
8062:transitive orientation
8048:Having to do with the
7936:
7757:A subgraph of a graph
7726:strongly chordal graph
7719:strongly regular graph
7704:2. For the
7586:is the square root of
7425:algebraic graph theory
7091:In the context of the
7002:
6994:
6357:, the number of edges.
6236:
6014:(closed under minors).
4773:(closed under minors).
4741:directed acyclic graph
4261:For a set of vertices
3955:
3774:
3007:directed acyclic graph
2999:
2836:
2564:-edge-connected graphs
2475:biconnected components
2315:
2166:
1927:of chords of a circle.
1795:strongly chordal graph
1709:
1652:of a tree is a vertex
1476:2-edge-connected graph
1222:
1195:
1055:biconnected components
1033:Usually a synonym for
963:
705:
634:partially ordered sets
602:
576:directed acyclic graph
457:directed acyclic graph
425:
405:
385:
353:
333:
194:
189:
184:
179:
174:
169:
164:
159:
154:
149:
144:
139:
134:
129:
124:
119:
114:
109:
104:
99:
94:
89:
84:
79:
74:
69:
48:, systems of nodes or
9082:Leiserson, Charles E.
8850:s have been assigned
8802:if they are repeated.
8535:
8486:s; the opposite of a
8446:3. In the
8416:-uniform hypergraphs.
7937:
7522:Spectral graph theory
6995:
6835:proper interval graph
6614:perfect graph theorem
6437:Eulerian orientations
6288:-element subset of a
5979:Modular decomposition
5033:2. In the
4905:hypohamiltonian graph
4792:characterized by the
4576:-coloring of a graph
4187:factor-critical graph
3822:is sometimes written
3294:as a synonym for the
2832:Cube-connected cycles
2823:, another name for a
2793:of a hypercube graph.
2745:factor-critical graph
2566:(removing fewer than
2555:(removing fewer than
2316:
2278:partially ordered set
1495:cube-connected cycles
1386:. The branchwidth of
1223:
1221:{\displaystyle B_{i}}
1196:
1194:{\displaystyle b_{i}}
603:
426:
406:
386:
354:
334:
9144:Cormen et al. (2001)
8709:
8704:
8549:
8544:
8511:
8353:
8202:, or the order of a
8066:comparability graphs
8058:transitive reduction
7972:totally disconnected
7913:
7868:
7437:symmetric difference
7350:The size of a graph
7216:
7028:to another within a
6971:
6934:
6875:
6838:indifference graphs.
6786:degree distributions
6775:Power graph analysis
6554:is the pathwidth of
6494:
6433:acyclic orientations
6381:topological ordering
6231:
6068:
6063:
5774:maximal planar graph
5687:
5466:
5461:
5363:
5358:
5335:
4917:
4625:triangle-free graphs
4549:
4544:
4405:
4400:
4146:
3744:
3739:
3596:, represented as an
3064:branch-decomposition
2994:
2894:symmetric difference
2497:of a directed graph
2296:
1506:
1501:
1405:branch-decomposition
1360:branch-decomposition
1354:branch-decomposition
1319:1. In a
1205:
1178:
958:
885:whose removal would
586:
564:symmetric difference
415:
411:towards a vertex of
395:
363:
343:
339:of a directed graph
323:
308:
246:
9437:1998Natur.393..440W
9302:Brandstädt, Andreas
8766:-minor-free graphs.
8690:Vizing's conjecture
8450:, a vertex that is
8349:are not neighbors).
8220:triangle-free graph
8050:transitive property
7966:Topological sorting
7860:is a supergraph of
7836:as its sources and
7665:strength of a graph
7552:split decomposition
7384:small-world network
7378:small-world network
7200:th root of a graph
7147:is a graph that is
7042:Has an affirmative
6790:scale-free networks
6719:crossings per edge.
6429:strong orientations
6385:degeneracy ordering
5698:Synonym for vertex
5399:vertex connectivity
5189:intervals of a line
5161:intersection number
5026:is the size of the
5014:independence number
4992:comparability graph
4753:hereditary property
4666:Hadwiger conjecture
4203:graph factorization
3762:is the edge set of
3658:dissociation number
3577:asymmetric relation
2922:cyclic permutations
2669:is a minimal graph
2574:connected component
2471:connected component
2274:comparability graph
63:Contents:
18:Edge (graph theory)
9483:10.1007/BFb0067356
9344:10.1007/BFb0060121
9130:10.1007/BF02764716
8988:Mathematics portal
8900:to a simple cycle.
8882:well-covered graph
8866:well-colored graph
8743:2. The
8623:articulation point
8530:
8504:is a name for the
8408:-uniform for some
8188:chordal completion
8128:tree decomposition
8122:tree decomposition
8054:transitive closure
7990:A closed trail, a
7932:
7906:is a name for the
7890:3. The
7882:2. The
7693:strong orientation
7465:geometric spanners
7285:articulation point
7159:regular tournament
7151:-regular for some
7065:if there exists a
6990:
6693:Petersen's theorem
6684:2. The
6543:path decomposition
6537:path decomposition
6313:2. See
6304:1. See
6117:open neighbourhood
6046:multiple adjacency
5451:knot (mathematics)
5185:intersection graph
5136:intersection graph
5055:indifference graph
5039:bicircular matroid
4822:graph homomorphism
4735:3. The
4724:2. The
4717:1. The
4664:3. The
4657:2. The
4532:1. The
4522:Grötzsch's theorem
4513:2. The
4495:. For instance, a
4359:2. The
3949:2. The
3575:1. The
3397:direct predecessor
3128:1. The
3120:-inductive graphs.
3058:path decomposition
3052:tree decomposition
2982:2. The
2926:Hamiltonian cycles
2863:articulation point
2661:3. The
2652:graph homomorphism
2431:chordal completion
2321:of a simple graph
2311:
2214:states that every
2212:four color theorem
2176:. For instance, a
2052:intersection graph
1925:intersection graph
1813:intersection graph
1679:algebraic topology
1582:Graph canonization
1486:1. The
1292:; a collection of
1218:
1191:
972:tree decomposition
952:graph automorphism
868:articulation point
824:direct predecessor
803:is said to be the
598:
421:
401:
381:
349:
329:
240:for vertex subset
9534:978-3-662-53621-6
9492:978-3-540-06096-3
9431:(6684): 440–442,
9410:978-0-387-98736-1
9353:978-3-540-04629-5
9321:978-0-89871-432-6
9175:978-3-662-53621-6
9086:Rivest, Ronald L.
9078:Cormen, Thomas H.
8194:, the order of a
7952:topological graph
7852:is a subgraph of
7797:superconcentrator
7485:perfect matchings
7292:separation number
7278:separating vertex
7255:The second order
6988:
6509:is a neighbor of
6488:outerplanar graph
6415:1. An
6272:5. An
6251:handshaking lemma
5914:topological minor
5880:of another graph
5644:1. An
5527:graph enumeration
5301:graph isomorphism
5239:with an opposite
5179:1. An
5134:2. An
5008:1. An
4477:undirected graphs
4447:In the theory of
4128:bounded expansion
3990:Graph enumeration
3942:1. An
3790:ear decomposition
3784:ear decomposition
3727:of a plane graph
3481:in which all the
3208:handshaking lemma
3005:Abbreviation for
2948:; for instance a
2934:peripheral cycles
2787:Halved cube graph
2780:Folded cube graph
2456:achromatic number
2451:complete coloring
2308:
2251:complete coloring
2174:complement graphs
1809:chord of a circle
1766:is a neighbor of
1451:is a cycle and a
1445:planarity testing
1038:-vertex-connected
664:1. An
462:2. An
441:achromatic number
424:{\displaystyle A}
404:{\displaystyle v}
352:{\displaystyle G}
332:{\displaystyle A}
319:An absorbing set
16:(Redirected from
9589:
9562:
9561:
9560:
9558:
9544:
9538:
9537:
9510:
9504:
9503:
9470:
9464:
9463:
9420:
9414:
9413:
9394:
9388:
9387:
9375:
9366:
9364:
9331:
9325:
9324:
9298:
9292:
9291:
9279:
9273:
9271:
9270:
9260:
9240:
9234:
9233:
9214:
9208:
9207:
9206:
9186:
9180:
9178:
9153:
9147:
9141:
9135:
9133:
9132:
9107:
9101:
9099:
9074:
9053:
9051:
9050:
9026:
9006:Graph algorithms
8990:
8985:
8984:
8945:
8939:
8933:
8927:
8921:
8912:
8898:universal vertex
8870:greedy colorings
8854:
8848:
8842:
8836:
8814:
8806:weakly connected
8765:
8752:Wagner's theorem
8720:
8713:
8683:Vizing's theorem
8654:
8643:
8630:
8624:
8618:
8612:
8606:
8574:
8539:
8537:
8536:
8531:
8529:
8528:
8490:
8484:
8478:
8472:
8466:
8458:unweighted graph
8441:threshold graphs
8433:universal vertex
8431:2. A
8424:1. A
8415:
8411:
8407:
8403:
8399:
8396:A hypergraph is
8374:undirected graph
8348:
8344:
8340:
8311:
8307:
8303:
8282:
8277:
8248:2. A
8209:
8201:
8193:
8185:
8181:
8165:
8161:
8157:
8153:
8149:
8145:
8141:
8137:
8133:
8117:
8113:
8109:
8099:
8095:2. A
8088:1. A
8038:
8000:
7994:
7980:
7950:1. A
7941:
7939:
7938:
7933:
7931:
7930:
7863:
7859:
7855:
7851:
7839:
7835:
7831:
7827:
7823:
7820:
7816:
7812:
7808:
7804:
7791:
7785:
7764:
7760:
7747:
7743:A subgraph of a
7724:4. A
7717:3. A
7712:
7699:
7689:
7683:
7654:
7647:
7622:
7599:2. A
7591:
7585:
7581:
7572:
7559:Vertex splitting
7545:2. A
7538:1. A
7528:
7369:
7365:
7353:
7326:1. A
7317:
7313:
7300:
7286:
7272:
7245:
7237:searching number
7231:
7211:
7207:
7203:
7199:
7175:
7154:
7150:
7142:
7138:
7118:
7110:
7082:
7076:
7069:
7064:
7058:
7052:
7046:
7032:
7026:
6999:
6997:
6996:
6991:
6989:
6978:
6966:
6949:
6882:quasi-line graph
6833:3. A
6828:
6810:
6804:
6765:
6761:
6757:
6751:
6747:
6739:1. A
6718:
6714:
6667:
6658:peripheral cycle
6656:1. A
6639:
6633:perfect matching
6631:3. A
6623:2. A
6608:1. A
6598:
6585:
6581:
6577:
6573:
6557:
6553:
6548:
6512:
6508:
6476:
6462:
6400:
6394:
6374:
6368:
6355:
6350:
6346:
6334:
6327:
6326:
6317:
6308:
6295:
6287:
6260:
6225:
6203:
6182:
6176:
6165:
6154:
6138:
6134:
6130:
6126:
6122:
6088:
6080:
6008:
6003:
5999:
5948:
5939:
5935:
5931:
5923:
5919:
5911:
5907:
5903:
5895:
5891:
5887:
5883:
5875:
5858:
5852:
5822:2. A
5807:2. A
5787:
5759:
5755:
5742:maximal matching
5739:
5735:
5723:maximum matching
5718:perfect matching
5702:
5682:
5634:
5621:
5617:
5613:
5609:
5544:2. A
5540:
5496:
5491:
5483:
5447:
5433:
5427:
5414:
5409:
5404:
5396:
5375:
5329:
5315:
5289:
5268:
5256:
5243:
5237:
5223:
5209:
5201:
5197:
5170:
5166:
5109:
5095:
5073:induced subgraph
5061:
5025:
4998:
4973:
4969:
4965:
4961:
4956:incidence matrix
4950:incidence matrix
4932:
4911:
4864:
4858:
4844:
4820:1. A
4767:
4762:
4758:
4708:
4704:
4700:
4692:
4678:Hamiltonian path
4642:
4638:
4634:
4622:
4618:
4614:
4610:
4606:
4591:
4587:
4583:
4579:
4575:
4560:
4509:Herbert Grötzsch
4493:greedy algorithm
4425:
4394:functional graph
4388:functional graph
4382:
4368:Frucht's theorem
4331:
4326:
4322:
4318:
4302:
4298:
4281:
4272:
4268:
4264:
4248:The first order
4229:
4216:
4212:
4208:
4192:
4184:
4180:
4176:
4142:is a polynomial.
4141:
4137:
4133:
4122:
4114:
4110:
4103:
4099:
4095:
4091:
4087:
4080:
4076:
4072:
4068:
4064:
4057:
4053:
4049:
4045:
4041:
4036:Cheeger constant
3951:order-zero graph
3892:
3881:
3868:
3862:
3856:
3850:
3844:
3840:s whose removal
3838:
3825:
3821:
3817:
3770:
3765:
3761:
3734:
3730:
3670:if it induces a
3637:
3623:
3609:
3600:
3594:
3588:
3583:
3566:
3559:
3554:
3548:
3541:
3536:
3530:
3523:
3518:
3512:
3506:
3500:
3494:
3486:
3479:
3465:
3451:
3437:
3405:direct successor
3391:
3345:
3339:
3333:
3259:
3254:
3243:
3239:
3205:
3197:
3186:
3170:
3166:
3163:; the degree of
3158:
3147:
3143:
3135:
3119:
3115:
3111:
3107:
3103:
3099:
3096:for which it is
3095:
3087:
3083:
3065:
3059:
3053:
3039:
3033:
3020:
2978:
2967:
2959:
2951:
2947:
2943:
2918:
2912:
2904:1. A
2890:
2878:of a graph is a
2864:
2826:
2815:
2806:
2688:
2684:
2681:and vice versa.
2680:
2676:
2672:
2668:
2657:
2650:such that every
2649:
2642:2. A
2637:
2632:
2628:
2622:
2618:1. A
2608:
2593:Edge contraction
2582:
2569:
2563:
2558:
2552:
2533:
2519:universal vertex
2508:
2504:
2500:
2449:4. A
2444:
2438:perfect matching
2425:
2405:
2386:
2371:
2367:
2359:
2348:
2341:1. A
2332:
2328:
2324:
2320:
2318:
2317:
2312:
2310:
2309:
2301:
2291:complement graph
2247:acyclic coloring
2233:
2229:
2225:
2221:
2208:bipartite graphs
2197:1. A
2155:
2137:
2128:
2119:
2103:are exactly the
2102:
2097:
2093:
2076:
2072:A synonym for a
2062:
2041:
2037:
2023:
2019:
1998:
1976:Vizing's theorem
1963:1. A
1910:
1907:for which it is
1906:
1902:
1894:
1877:
1869:
1861:
1850:
1846:
1835:chromatic number
1831:
1807:5. A
1800:4. A
1793:3. A
1786:2. A
1769:
1765:
1752:
1746:
1741:
1730:
1726:
1697:
1689:Cheeger constant
1672:
1659:
1655:
1638:
1620:caterpillar tree
1600:
1536:
1527:
1523:
1453:peripheral cycle
1416:1. A
1406:
1393:
1389:
1385:
1381:
1377:
1373:
1369:
1365:
1327:
1306:3. A
1302:
1295:
1291:
1276:1. A
1266:
1261:
1247:
1239:4. A
1235:
1231:
1227:
1225:
1224:
1219:
1217:
1216:
1200:
1198:
1197:
1192:
1190:
1189:
1173:
1169:
1161:
1156:
1152:
1148:
1140:
1127:
1110:
1106:
1102:
1061:
1051:
1037:
1023:
1006:
1002:
998:
973:
940:
927:
923:
915:
909:
895:
889:
883:
877:
862:
849:
844:
832:
825:
820:
814:
807:
806:direct successor
802:
796:
785:
780:
774:
769:
763:
758:
745:
739:
733:
715:
701:
687:universal vertex
681:
677:
672:
627:
623:
619:
615:
611:
607:
605:
604:
599:
581:
551:
546:
534:
529:
518:
493:
489:
485:
481:
476:adjacency matrix
470:adjacency matrix
464:acyclic coloring
430:
428:
427:
422:
410:
408:
407:
402:
390:
388:
387:
382:
358:
356:
355:
350:
338:
336:
335:
330:
303:
292:
281:
270:
243:
239:
234:
233:induced subgraph
229:
221:Square brackets
64:
44:is the study of
21:
9597:
9596:
9592:
9591:
9590:
9588:
9587:
9586:
9567:
9566:
9565:
9556:
9554:
9546:
9545:
9541:
9535:
9511:
9507:
9493:
9471:
9467:
9421:
9417:
9411:
9395:
9391:
9377:
9376:
9369:
9354:
9332:
9328:
9322:
9299:
9295:
9281:
9280:
9276:
9241:
9237:
9215:
9211:
9187:
9183:
9176:
9154:
9150:
9142:
9138:
9108:
9104:
9090:Stein, Clifford
9075:
9056:
9027:
9023:
9019:
8986:
8979:
8976:
8962:
8905:
8889:
8877:
8861:
8829:
8821:
8807:
8771:
8764:
8758:
8734:
8727:windmill graphs
8718:
8714:
8711:
8707:
8697:
8677:Vadim G. Vizing
8672:
8660:
8645:
8641:
8637:
8599:
8594:
8582:
8566:
8554:
8547:
8518:
8514:
8512:
8509:
8508:
8497:
8459:
8448:logic of graphs
8426:universal graph
8421:
8413:
8409:
8405:
8401:
8397:
8393:
8369:
8361:
8356:
8346:
8342:
8334:
8321:
8313:
8309:
8305:
8302:
8293:
8285:
8275:
8271:
8257:Turán's theorem
8239:
8227:
8215:
8207:
8199:
8191:
8183:
8179:
8171:
8163:
8159:
8155:
8151:
8147:
8143:
8139:
8135:
8131:
8123:
8115:
8111:
8103:
8097:
8085:
8078:transpose graph
8073:
8045:
8031:
8024:traceable graph
8019:
8007:
7987:
7973:
7947:
7920:
7916:
7914:
7911:
7910:
7899:
7876:
7871:
7861:
7857:
7853:
7849:
7845:
7837:
7833:
7829:
7828:to a vertex in
7825:
7821:
7818:
7814:
7810:
7806:
7802:
7798:
7778:
7770:
7762:
7758:
7754:
7740:
7672:
7660:
7649:
7646:
7637:
7629:
7621:independent set
7615:
7587:
7583:
7577:
7570:
7566:
7535:
7513:
7508:
7496:
7476:
7460:
7420:
7412:
7400:
7379:
7367:
7366:. The variable
7355:
7351:
7347:
7339:
7323:
7315:
7311:
7307:
7293:
7279:
7265:
7257:logic of graphs
7252:
7238:
7224:
7219:
7209:
7205:
7201:
7197:
7182:
7168:
7160:
7152:
7148:
7140:
7136:
7132:
7124:
7116:
7108:
7100:
7088:
7078:
7072:
7060:
7054:
7039:
7019:
7005:
6977:
6972:
6969:
6968:
6964:
6961:Ramanujan graph
6956:
6942:
6937:
6928:category theory
6919:
6899:
6883:
6878:
6868:
6856:
6843:
6817:
6797:
6763:
6759:
6753:
6749:
6743:
6736:
6724:
6716:
6712:
6700:
6679:Julius Petersen
6674:
6653:
6646:1-factorization
6605:
6591:
6583:
6579:
6575:
6571:
6563:
6555:
6551:
6546:
6538:
6518:
6510:
6506:
6502:
6497:
6483:
6469:
6455:
6412:
6407:
6362:logic of graphs
6348:
6347:. The variable
6336:
6332:
6328:
6324:
6323:
6301:
6289:
6281:
6239:
6234:
6218:
6210:
6196:
6188:
6178:
6175:
6167:
6156:
6148:
6140:
6139:may be denoted
6136:
6132:
6128:
6124:
6120:
6112:
6107:
6099:
6094:
6086:
6073:
6066:
6056:
6047:
6035:
6028:Edward F. Moore
6019:
6001:
5997:
5993:
5967:
5955:
5937:
5933:
5929:
5921:
5917:
5909:
5905:
5901:
5893:
5889:
5885:
5881:
5873:
5869:
5845:
5836:minimal element
5831:
5816:
5797:
5785:
5781:
5762:maximal element
5757:
5753:
5749:
5737:
5726:
5709:
5695:
5690:
5680:
5672:
5660:
5641:
5627:
5619:
5615:
5611:
5600:
5593:
5574:
5553:
5538:
5534:
5503:
5489:
5474:
5471:
5464:
5440:
5420:
5412:
5402:
5387:
5384:
5368:
5361:
5343:
5338:
5322:
5308:
5296:
5282:
5274:
5258:
5246:
5230:
5216:
5199:
5195:
5176:
5168:
5164:
5149:interval graphs
5128:
5116:
5102:
5088:
5068:
5050:
5035:graphic matroid
5016:
5010:independent set
5005:
4987:
4986:incomparability
4979:
4971:
4967:
4963:
4959:
4951:
4939:
4925:
4920:
4899:
4887:
4876:hypercube graph
4871:
4851:
4837:
4830:Hadwiger number
4817:
4808:Two graphs are
4805:
4788:
4780:
4760:
4756:
4748:
4714:
4706:
4702:
4698:
4690:
4686:
4673:
4659:Hadwiger number
4648:
4640:
4636:
4632:
4620:
4616:
4612:
4608:
4604:
4600:
4589:
4585:
4581:
4577:
4573:
4569:
4558:
4554:
4547:
4538:greedy coloring
4529:
4504:
4497:greedy coloring
4488:
4473:directed graphs
4468:
4456:
4444:
4432:
4418:
4410:
4403:
4389:
4375:
4350:
4338:
4324:
4320:
4316:
4308:
4300:
4296:
4288:
4270:
4266:
4262:
4258:
4250:logic of graphs
4245:
4236:
4222:
4214:
4210:
4206:
4198:
4190:
4182:
4178:
4174:
4170:
4163:graph embedding
4154:
4149:
4139:
4135:
4131:
4120:
4112:
4111:-regular graph
4108:
4101:
4097:
4093:
4089:
4085:
4078:
4074:
4070:
4066:
4062:
4055:
4051:
4047:
4043:
4039:
4031:
4019:
4011:
3998:
3986:
3970:
3958:
3939:
3915:graph embedding
3910:
3898:
3883:
3879:
3875:
3831:
3823:
3819:
3815:
3806:
3798:
3785:
3777:
3763:
3752:
3749:
3742:
3732:
3728:
3720:
3707:
3695:
3683:
3659:
3652:disjoint unions
3644:
3630:
3616:
3572:
3562:
3550:
3544:
3532:
3526:
3514:
3508:
3502:
3472:
3458:
3444:
3430:
3414:
3406:
3398:
3384:
3372:
3352:
3327:
3315:
3303:
3286:
3266:
3245:
3241:
3233:
3230:
3220:Hadwiger number
3212:degree sequence
3199:
3188:
3180:
3172:
3171:may be denoted
3168:
3164:
3149:
3145:
3137:
3133:
3125:
3117:
3113:
3109:
3105:
3101:
3097:
3093:
3085:
3081:
3077:
3072:
3046:
3018:
3014:
3002:
2997:
2977:
2969:
2965:
2957:
2949:
2945:
2941:
2901:
2871:
2857:
2844:
2839:
2824:
2811:
2804:
2773:Hypercube graph
2761:
2756:
2740:
2720:
2701:
2686:
2682:
2678:
2674:
2670:
2666:
2655:
2647:
2630:
2626:
2620:
2615:
2601:
2589:
2575:
2567:
2561:
2556:
2550:
2545:connected graph
2540:
2526:
2514:
2506:
2502:
2498:
2490:
2466:
2424:
2407:
2392:
2385:
2373:
2369:
2365:
2358:
2350:
2346:
2338:
2330:
2326:
2322:
2300:
2299:
2297:
2294:
2293:
2286:
2269:
2231:
2227:
2223:
2219:
2194:
2189:
2169:
2162:closure problem
2148:
2112:
2100:
2095:
2091:
2083:
2069:
2039:
2028:
2021:
2017:
2008:
2001:claw-free graph
1997:
1991:
1983:
1960:
1948:
1932:
1916:
1908:
1904:
1900:
1892:
1888:
1883:
1875:
1867:
1864:chromatic index
1852:
1848:
1837:
1824:
1780:
1775:
1767:
1763:
1759:
1732:
1728:
1717:
1714:
1704:
1690:
1665:
1657:
1653:
1645:
1627:
1615:
1607:
1589:
1572:
1567:
1555:
1543:
1525:
1522:
1514:
1511:
1504:
1488:butterfly graph
1483:
1467:
1413:
1399:
1391:
1387:
1383:
1379:
1375:
1371:
1367:
1363:
1355:
1347:
1334:
1321:graph embedding
1316:
1300:
1293:
1290:
1281:
1273:
1254:
1233:
1229:
1212:
1208:
1206:
1203:
1202:
1201:for each block
1185:
1181:
1179:
1176:
1175:
1171:
1167:
1154:
1150:
1146:
1138:
1134:
1121:biregular graph
1116:
1108:
1104:
1085:
1081:bipartite graph
1076:
1068:
1046:
1035:
1030:
1012:
1004:
1000:
996:
988:
980:
966:
961:
947:
933:
925:
921:
913:
907:
902:
882:connected graph
870:
852:
834:
828:
816:
810:
798:
787:
776:
765:
748:
722:
708:
694:
679:
675:
661:
653:
641:
625:
621:
617:
613:
609:
587:
584:
583:
579:
571:
558:
537:
520:
516:
512:
499:
491:
487:
483:
479:
471:
448:
436:
416:
413:
412:
396:
393:
392:
364:
361:
360:
344:
341:
340:
324:
321:
320:
316:
311:
294:
283:
272:
261:
249:
241:
237:
225:
222:
217:
212:
211:
210:
209:
65:
34:
28:
23:
22:
15:
12:
11:
5:
9595:
9585:
9584:
9579:
9564:
9563:
9552:britannica.com
9539:
9533:
9505:
9491:
9465:
9415:
9409:
9389:
9367:
9352:
9326:
9320:
9293:
9274:
9251:(1): 391–416,
9235:
9209:
9197:(3): 225–255,
9181:
9174:
9148:
9146:, p. 529.
9136:
9123:(4): 390–408,
9102:
9054:
9020:
9018:
9015:
9014:
9013:
9008:
9003:
8998:
8992:
8991:
8975:
8972:
8971:
8970:
8967:windmill graph
8963:
8960:
8958:
8951:
8948:
8915:
8906:
8903:
8901:
8890:
8887:
8885:
8878:
8875:
8873:
8862:
8859:
8857:
8830:
8828:weighted graph
8827:
8825:
8822:
8819:
8817:
8808:
8805:
8803:
8772:
8769:
8767:
8762:
8755:
8750:3.
8748:
8741:
8737:1.
8735:
8732:
8730:
8715:
8710:
8706:
8703:
8702:
8701:
8698:
8695:
8693:
8688:3.
8686:
8681:2.
8679:
8675:1.
8673:
8670:
8668:
8661:
8658:
8656:
8638:
8635:
8633:
8608:whose removal
8600:
8598:separating set
8597:
8595:
8592:
8590:
8583:
8580:
8578:
8567:
8564:
8562:
8555:
8550:
8546:
8543:
8542:
8541:
8527:
8524:
8521:
8517:
8498:
8495:
8493:
8489:weighted graph
8460:
8457:
8455:
8444:
8439:and connected
8429:
8422:
8419:
8417:
8394:
8391:
8389:
8370:
8367:
8365:
8362:
8359:
8355:
8352:
8351:
8350:
8341:(this implies
8330:
8317:
8304:(this implies
8298:
8289:
8272:
8269:
8267:
8262:4.
8260:
8255:3.
8253:
8246:
8242:1.
8240:
8237:
8235:
8228:
8225:
8223:
8216:
8213:
8211:
8172:
8169:
8167:
8124:
8121:
8119:
8093:
8086:
8083:
8081:
8074:
8071:
8069:
8046:
8043:
8041:
8032:
8029:
8027:
8020:
8017:
8015:
8008:
8005:
8003:
7988:
7985:
7983:
7974:
7971:
7969:
7964:3.
7962:
7957:2.
7955:
7948:
7945:
7943:
7929:
7926:
7923:
7919:
7900:
7897:
7895:
7888:
7880:
7877:
7874:
7870:
7867:
7866:
7865:
7846:
7843:
7841:
7799:
7796:
7794:
7779:
7776:
7774:
7771:
7768:
7766:
7755:
7752:
7750:
7741:
7738:
7736:
7733:Meyniel graphs
7729:
7722:
7715:
7702:
7673:
7670:
7668:
7661:
7658:
7656:
7641:
7630:
7627:
7625:
7616:
7613:
7611:
7604:
7597:
7567:
7564:
7562:
7557:3.
7555:
7543:
7536:
7533:
7531:
7514:
7511:
7509:
7506:
7504:
7497:
7494:
7492:
7481:spanning trees
7477:
7474:
7472:
7461:
7458:
7456:
7421:
7418:
7416:
7413:
7410:
7408:
7401:
7398:
7396:
7395:in the network
7380:
7377:
7375:
7348:
7345:
7343:
7340:
7337:
7335:
7332:
7324:
7321:
7319:
7308:
7305:
7303:
7294:
7291:
7289:
7280:
7277:
7275:
7266:
7263:
7261:
7253:
7250:
7248:
7239:
7236:
7234:
7225:
7222:
7218:
7215:
7214:
7213:
7190:
7183:
7180:
7178:
7169:
7166:
7164:
7161:
7158:
7156:
7133:
7130:
7128:
7125:
7122:
7120:
7101:
7099:reconstruction
7098:
7096:
7089:
7086:
7084:
7040:
7037:
7035:
7020:
7015:
7013:
7006:
7003:
7001:
6987:
6984:
6981:
6976:
6957:
6954:
6952:
6951:of any vertex.
6943:
6940:
6936:
6933:
6932:
6931:
6920:
6917:
6915:
6900:
6897:
6895:
6884:
6881:
6877:
6874:
6873:
6872:
6869:
6866:
6864:
6857:
6854:
6852:
6848:graph property
6844:
6841:
6839:
6831:
6822:
6818:
6815:
6813:
6798:
6795:
6793:
6780:3.
6778:
6773:2.
6771:
6737:
6734:
6732:
6725:
6722:
6720:
6701:
6698:
6696:
6691:3.
6689:
6686:Petersen graph
6682:
6677:1.
6675:
6672:
6670:
6661:
6654:
6651:
6649:
6642:
6629:
6621:
6606:
6603:
6601:
6592:
6589:
6587:
6564:
6561:
6559:
6539:
6536:
6534:
6531:shortest paths
6519:
6516:
6514:
6503:
6500:
6496:
6493:
6492:
6491:
6484:
6481:
6479:
6470:
6467:
6465:
6456:
6453:
6451:
6448:directed graph
6444:
6413:
6410:
6408:
6405:
6403:
6388:
6377:
6358:
6329:
6322:
6320:
6311:
6302:
6299:
6297:
6270:
6263:
6254:
6247:
6240:
6237:
6233:
6230:
6229:
6228:
6219:
6216:
6214:
6211:
6208:
6206:
6199:A synonym for
6197:
6194:
6192:
6189:
6186:
6184:
6171:
6144:
6113:
6110:
6108:
6105:
6103:
6100:
6097:
6095:
6092:
6090:
6083:
6074:
6069:
6065:
6062:
6061:
6060:
6057:
6054:
6052:
6048:
6045:
6043:
6036:
6033:
6031:
6020:
6017:
6015:
5994:
5991:
5989:
5984:3.
5982:
5977:2.
5975:
5970:1.
5968:
5965:
5963:
5956:
5953:
5951:
5870:
5867:
5865:
5846:
5841:
5839:
5832:
5829:
5827:
5820:
5817:
5814:
5812:
5805:
5802:modular graphs
5798:
5795:
5793:
5790:maximum clique
5782:
5779:
5777:
5769:
5766:maximal clique
5750:
5747:
5745:
5710:
5707:
5705:
5696:
5693:
5689:
5686:
5685:
5684:
5673:
5670:
5668:
5665:neighbourhoods
5661:
5658:
5656:
5651:2.
5649:
5646:adjacency list
5642:
5639:
5637:
5630:A synonym for
5628:
5625:
5623:
5594:
5591:
5589:
5586:
5575:
5572:
5570:
5554:
5551:
5549:
5542:
5535:
5532:
5530:
5523:
5520:graph coloring
5516:Graph labeling
5508:vertex-labeled
5504:
5501:
5499:
5472:
5467:
5463:
5460:
5459:
5458:
5446:directed graph
5441:
5438:
5436:
5421:
5418:
5416:
5385:
5380:
5378:
5369:
5364:
5360:
5357:
5356:
5355:
5352:disjoint union
5344:
5341:
5337:
5334:
5333:
5332:
5323:
5320:
5318:
5309:
5306:
5304:
5297:
5294:
5292:
5283:
5280:
5278:
5275:
5272:
5270:
5231:
5229:inverted arrow
5228:
5226:
5217:
5214:
5212:
5203:
5192:
5181:interval graph
5177:
5174:
5172:
5141:chordal graphs
5132:
5129:
5126:
5124:
5117:
5114:
5112:
5103:
5100:
5098:
5089:
5086:
5084:
5081:induced cycles
5069:
5066:
5064:
5051:
5048:
5046:
5031:
5006:
5003:
5001:
4988:
4985:
4983:
4980:
4977:
4975:
4952:
4949:
4947:
4940:
4937:
4935:
4926:
4923:
4919:
4916:
4915:
4914:
4900:
4897:
4895:
4888:
4885:
4883:
4872:
4869:
4867:
4852:
4849:
4847:
4838:
4835:
4833:
4826:
4818:
4815:
4813:
4806:
4803:
4801:
4798:chordal graphs
4789:
4786:
4784:
4781:
4776:
4774:
4749:
4746:
4744:
4733:
4722:
4715:
4712:
4710:
4701:of fewer than
4687:
4684:
4682:
4674:
4671:
4669:
4662:
4655:
4651:1.
4649:
4646:
4644:
4629:triangle graph
4611:, that is, if
4601:
4595:
4593:
4570:
4564:
4562:
4555:
4550:
4546:
4543:
4542:
4541:
4530:
4527:
4525:
4520:3.
4518:
4515:Grötzsch graph
4511:
4507:1.
4505:
4502:
4500:
4491:Produced by a
4489:
4486:
4484:
4469:
4466:
4464:
4457:
4454:
4452:
4445:
4442:
4440:
4433:
4430:
4428:
4419:
4416:
4414:
4411:
4406:
4402:
4399:
4398:
4397:
4390:
4387:
4385:
4376:
4373:
4371:
4366:3.
4364:
4357:
4353:1.
4351:
4348:
4346:
4339:
4336:
4334:
4309:
4306:
4304:
4289:
4286:
4284:
4259:
4256:
4254:
4246:
4243:
4241:
4237:
4234:
4232:
4225:A synonym for
4223:
4220:
4218:
4199:
4196:
4194:
4171:
4168:
4166:
4155:
4152:
4148:
4145:
4144:
4143:
4124:
4105:
4082:
4059:
4032:
4029:
4027:
4024:expander graph
4020:
4017:
4015:
4012:
4009:
4007:
3999:
3996:
3994:
3987:
3984:
3982:
3971:
3968:
3966:
3959:
3956:
3954:
3947:
3944:edgeless graph
3940:
3937:
3935:
3924:toroidal graph
3911:
3908:
3906:
3903:edgeless graph
3899:
3897:edgeless graph
3896:
3894:
3876:
3873:
3871:
3832:
3829:
3827:
3807:
3804:
3802:
3799:
3796:
3794:
3786:
3783:
3781:
3778:
3775:
3773:
3750:
3745:
3741:
3738:
3737:
3736:
3721:
3718:
3716:
3712:dominating set
3708:
3705:
3703:
3700:domatic number
3696:
3693:
3691:
3684:
3681:
3679:
3660:
3657:
3655:
3648:
3645:
3642:
3640:
3631:
3628:
3626:
3617:
3614:
3612:
3603:
3573:
3570:
3568:
3555:is said to be
3490:have the same
3473:
3470:
3468:
3459:
3456:
3454:
3445:
3442:
3440:
3431:
3428:
3426:
3419:directed graph
3415:
3412:
3410:
3407:
3404:
3402:
3399:
3396:
3394:
3385:
3382:
3380:
3377:directed graph
3373:
3370:
3368:
3353:
3350:
3348:
3328:
3325:
3323:
3316:
3313:
3311:
3304:
3301:
3299:
3287:
3284:
3282:
3269:In a graph of
3267:
3264:
3262:
3231:
3225:
3223:
3216:
3176:
3126:
3123:
3121:
3078:
3075:
3073:
3070:
3068:
3047:
3044:
3042:
3015:
3012:
3010:
3003:
3000:
2996:
2993:
2992:
2991:
2980:
2973:
2940:of a graph. A
2930:induced cycles
2902:
2899:
2897:
2872:
2869:
2867:
2858:
2855:
2853:
2845:
2842:
2840:
2837:
2835:
2830:8.
2828:
2819:7.
2817:
2801:
2796:5.
2794:
2785:4.
2783:
2778:3.
2776:
2771:2.
2769:
2764:1.
2762:
2759:
2757:
2754:
2752:
2741:
2738:
2736:
2721:
2718:
2716:
2709:
2702:
2699:
2697:
2690:
2659:
2640:
2616:
2613:
2611:
2602:
2599:
2597:
2590:
2587:
2585:
2576:
2573:
2571:
2541:
2538:
2536:
2527:
2524:
2522:
2515:
2512:
2510:
2491:
2488:
2486:
2467:
2464:
2462:
2459:
2447:
2434:
2427:
2411:
2377:
2354:
2343:complete graph
2339:
2336:
2334:
2307:
2304:
2287:
2284:
2282:
2270:
2267:
2265:
2258:
2255:total coloring
2235:
2230:-colorable or
2203:
2199:graph coloring
2195:
2192:
2190:
2187:
2185:
2170:
2167:
2165:
2158:
2149:
2146:
2144:
2140:
2131:
2122:
2113:
2110:
2108:
2084:
2081:
2079:
2070:
2067:
2065:
2009:
2006:
2004:
1995:
1984:
1981:
1979:
1972:
1969:
1961:
1958:
1956:
1949:
1946:
1944:
1933:
1930:
1928:
1917:
1914:
1912:
1889:
1886:
1884:
1881:
1879:
1825:
1822:
1820:
1805:
1798:
1791:
1784:
1781:
1778:
1776:
1773:
1771:
1760:
1757:
1755:
1715:
1710:
1708:
1705:
1702:
1700:
1691:
1688:
1686:
1675:
1666:
1663:
1661:
1646:
1643:
1641:
1628:
1625:
1623:
1616:
1613:
1611:
1608:
1605:
1603:
1590:
1587:
1585:
1577:canonical form
1573:
1570:
1568:
1565:
1563:
1556:
1553:
1551:
1544:
1541:
1539:
1518:
1512:
1507:
1503:
1500:
1499:
1498:
1491:
1484:
1481:
1479:
1468:
1465:
1463:
1456:
1421:
1414:
1411:
1409:
1400:
1397:
1395:
1356:
1353:
1351:
1348:
1345:
1343:
1335:
1332:
1330:
1317:
1314:
1312:
1308:book embedding
1304:
1297:
1285:
1274:
1271:
1269:
1255:
1252:
1250:
1237:
1215:
1211:
1188:
1184:
1164:
1143:
1135:
1132:
1130:
1117:
1114:
1112:
1077:
1074:
1072:
1069:
1067:binding number
1066:
1064:
1044:
1031:
1028:
1026:
1013:
1010:
1008:
989:
986:
984:
981:
978:
976:
967:
964:
960:
957:
956:
955:
948:
945:
943:
934:
931:
929:
903:
900:
898:
871:
866:
864:
848:inverted arrow
744:directed graph
723:
720:
718:
709:
706:
704:
695:
692:
690:
683:
662:
659:
657:
654:
651:
649:
642:
639:
637:
597:
594:
591:
572:
569:
567:
559:
556:
554:
513:
508:
506:
503:
500:
497:
495:
486:when vertices
472:
469:
467:
460:
449:
446:
444:
437:
434:
432:
420:
400:
380:
377:
374:
371:
368:
348:
328:
317:
314:
310:
307:
306:
305:
250:
248:Prime symbol '
247:
245:
223:
220:
216:
213:
208:
207:
202:
197:
192:
187:
182:
177:
172:
167:
162:
157:
152:
147:
142:
137:
132:
127:
122:
117:
112:
107:
102:
97:
92:
87:
82:
77:
72:
66:
60:
58:
26:
9:
6:
4:
3:
2:
9594:
9583:
9580:
9578:
9575:
9574:
9572:
9553:
9549:
9543:
9536:
9530:
9526:
9522:
9518:
9517:
9509:
9502:
9498:
9494:
9488:
9484:
9480:
9476:
9469:
9462:
9458:
9454:
9450:
9446:
9445:10.1038/30918
9442:
9438:
9434:
9430:
9426:
9419:
9412:
9406:
9402:
9401:
9393:
9386:
9382:
9381:
9374:
9372:
9363:
9359:
9355:
9349:
9345:
9341:
9337:
9330:
9323:
9317:
9313:
9309:
9308:
9303:
9297:
9290:
9286:
9285:
9278:
9269:
9264:
9259:
9254:
9250:
9246:
9239:
9232:
9228:
9224:
9220:
9213:
9205:
9200:
9196:
9192:
9185:
9177:
9171:
9167:
9163:
9159:
9152:
9145:
9140:
9131:
9126:
9122:
9118:
9117:
9112:
9106:
9097:
9096:
9091:
9087:
9083:
9079:
9073:
9071:
9069:
9067:
9065:
9063:
9061:
9059:
9049:
9044:
9040:
9036:
9032:
9025:
9021:
9012:
9009:
9007:
9004:
9002:
8999:
8997:
8994:
8993:
8989:
8983:
8978:
8968:
8964:
8956:
8952:
8949:
8946:
8940:
8934:
8928:
8922:
8916:
8913:
8907:
8899:
8895:
8891:
8883:
8879:
8871:
8867:
8863:
8855:
8849:
8843:
8837:
8831:
8823:
8815:
8809:
8801:
8797:
8793:
8789:
8785:
8781:
8777:
8773:
8761:
8756:
8753:
8749:
8746:
8742:
8740:
8736:
8728:
8724:
8716:
8708:
8699:
8691:
8687:
8684:
8680:
8678:
8674:
8666:
8662:
8652:
8648:
8639:
8631:
8625:
8619:
8613:
8607:
8601:
8588:
8584:
8576:
8575:
8568:
8560:
8556:
8553:
8548:
8525:
8522:
8519:
8515:
8507:
8503:
8502:utility graph
8499:
8496:utility graph
8491:
8485:
8479:
8473:
8467:
8461:
8453:
8449:
8445:
8442:
8438:
8434:
8430:
8427:
8423:
8395:
8387:
8383:
8379:
8375:
8371:
8363:
8357:
8338:
8333:
8329:
8325:
8320:
8316:
8301:
8297:
8292:
8288:
8283:
8274:Two vertices
8273:
8265:
8261:
8258:
8254:
8251:
8247:
8245:
8241:
8233:
8229:
8221:
8217:
8205:
8197:
8189:
8177:
8173:
8129:
8125:
8107:
8101:
8094:
8091:
8087:
8079:
8075:
8067:
8063:
8059:
8055:
8051:
8047:
8039:
8033:
8025:
8021:
8013:
8009:
8001:
7995:
7989:
7981:
7975:
7967:
7963:
7960:
7956:
7953:
7949:
7927:
7924:
7921:
7917:
7909:
7905:
7904:Thomsen graph
7901:
7898:Thomsen graph
7893:
7892:Lovász number
7889:
7885:
7881:
7878:
7872:
7847:
7840:as its sinks.
7800:
7792:
7790:directed path
7786:
7780:
7772:
7756:
7748:
7742:
7734:
7730:
7727:
7723:
7720:
7716:
7713:
7707:
7703:
7700:
7694:
7690:
7684:
7678:
7674:
7666:
7662:
7652:
7645:
7640:
7635:
7631:
7623:
7617:
7609:
7608:lattice graph
7605:
7602:
7598:
7595:
7590:
7580:
7576:
7568:
7560:
7556:
7553:
7548:
7544:
7541:
7537:
7529:
7523:
7519:
7515:
7502:
7498:
7490:
7486:
7482:
7478:
7470:
7469:tree spanners
7466:
7462:
7454:
7450:
7446:
7442:
7438:
7434:
7430:
7429:vector spaces
7426:
7422:
7414:
7406:
7402:
7394:
7390:
7385:
7381:
7373:
7363:
7359:
7349:
7341:
7333:
7329:
7325:
7309:
7301:
7295:
7287:
7281:
7273:
7267:
7258:
7254:
7246:
7240:
7232:
7226:
7220:
7195:
7191:
7188:
7187:rooted graphs
7184:
7176:
7170:
7162:
7146:
7145:regular graph
7134:
7126:
7114:
7106:
7102:
7094:
7090:
7081:
7075:
7070:
7063:
7057:
7053:
7047:
7041:
7033:
7027:
7021:
7018:
7011:
7007:
6985:
6982:
6979:
6974:
6962:
6958:
6950:
6944:
6938:
6929:
6925:
6921:
6913:
6909:
6908:random graphs
6905:
6901:
6893:
6889:
6885:
6879:
6870:
6862:
6858:
6849:
6845:
6836:
6832:
6829:
6823:
6819:
6811:
6809:directed path
6805:
6799:
6791:
6787:
6783:
6779:
6776:
6772:
6769:
6756:
6746:
6742:
6738:
6730:
6726:
6710:
6706:
6702:
6694:
6690:
6687:
6683:
6680:
6676:
6668:
6662:
6659:
6655:
6647:
6643:
6640:
6634:
6630:
6626:
6622:
6619:
6615:
6611:
6610:perfect graph
6607:
6599:
6593:
6569:
6565:
6544:
6540:
6532:
6528:
6527:induced paths
6524:
6520:
6504:
6498:
6489:
6485:
6477:
6471:
6463:
6457:
6449:
6445:
6442:
6438:
6434:
6430:
6426:
6422:
6418:
6414:
6401:
6395:
6389:
6386:
6382:
6378:
6375:
6369:
6363:
6359:
6356:
6344:
6340:
6330:
6318:
6312:
6309:
6307:neighbourhood
6303:
6293:
6285:
6279:
6275:
6271:
6268:
6264:
6261:
6255:
6252:
6248:
6245:
6241:
6235:
6226:
6220:
6212:
6204:
6198:
6190:
6181:
6174:
6170:
6163:
6159:
6152:
6147:
6143:
6118:
6114:
6111:neighbourhood
6101:
6084:
6081:
6079:neighbourhood
6075:
6072:
6067:
6058:
6049:
6041:
6037:
6029:
6025:
6021:
6013:
6009:
5995:
5987:
5983:
5980:
5976:
5973:
5972:Modular graph
5969:
5961:
5957:
5949:
5943:
5932:. A graph is
5927:
5915:
5899:
5898:shallow minor
5879:
5871:
5863:
5859:
5853:
5847:
5844:
5837:
5833:
5825:
5824:Meyniel graph
5821:
5818:
5810:
5806:
5803:
5799:
5791:
5783:
5775:
5770:
5767:
5763:
5751:
5743:
5733:
5729:
5724:
5719:
5715:
5711:
5703:
5697:
5694:magnification
5691:
5678:
5674:
5666:
5662:
5654:
5653:List coloring
5650:
5647:
5643:
5635:
5629:
5607:
5603:
5599:
5595:
5587:
5584:
5580:
5576:
5568:
5564:
5560:
5559:shortest path
5555:
5547:
5543:
5536:
5528:
5524:
5521:
5517:
5513:
5509:
5505:
5497:
5487:
5481:
5477:
5473:
5470:
5465:
5456:
5452:
5448:
5442:
5434:
5428:
5422:
5410:
5408:clique number
5400:
5394:
5390:
5386:
5383:
5376:
5370:
5367:
5362:
5353:
5349:
5345:
5339:
5330:
5324:
5316:
5310:
5307:isoperimetric
5302:
5298:
5290:
5284:
5276:
5266:
5262:
5254:
5250:
5244:
5238:
5232:
5224:
5219:A synonym of
5218:
5210:
5204:
5193:
5190:
5186:
5182:
5178:
5162:
5158:
5157:clique graphs
5154:
5150:
5146:
5145:circle graphs
5142:
5137:
5133:
5130:
5122:
5118:
5110:
5104:
5096:
5090:
5082:
5078:
5077:induced paths
5074:
5070:
5062:
5056:
5052:
5044:
5040:
5036:
5032:
5029:
5023:
5019:
5015:
5011:
5007:
4999:
4997:comparability
4993:
4989:
4981:
4957:
4953:
4945:
4941:
4933:
4927:
4921:
4912:
4906:
4901:
4893:
4889:
4881:
4877:
4873:
4865:
4859:
4853:
4845:
4839:
4831:
4827:
4823:
4819:
4811:
4807:
4799:
4795:
4790:
4782:
4779:
4772:
4768:
4754:
4750:
4742:
4738:
4734:
4731:
4727:
4723:
4720:
4716:
4696:
4688:
4679:
4675:
4667:
4663:
4660:
4656:
4654:
4653:Hugo Hadwiger
4650:
4630:
4626:
4602:
4598:
4571:
4567:
4556:
4553:
4548:
4539:
4535:
4534:Grundy number
4531:
4528:Grundy number
4523:
4519:
4516:
4512:
4510:
4506:
4498:
4494:
4490:
4482:
4478:
4474:
4470:
4462:
4458:
4450:
4449:random graphs
4446:
4438:
4437:shortest path
4434:
4426:
4420:
4412:
4409:
4404:
4395:
4391:
4383:
4377:
4369:
4365:
4362:
4358:
4356:
4355:Robert Frucht
4352:
4344:
4340:
4332:
4314:
4313:forcing graph
4310:
4307:forcing graph
4294:
4290:
4282:
4276:
4260:
4251:
4247:
4238:
4230:
4224:
4204:
4200:
4197:factorization
4188:
4172:
4164:
4160:
4156:
4150:
4129:
4125:
4118:
4106:
4083:
4060:
4037:
4033:
4025:
4021:
4013:
4004:
4003:Eulerian path
4000:
3991:
3988:
3980:
3976:
3972:
3964:
3960:
3952:
3948:
3945:
3941:
3933:
3929:
3925:
3921:
3916:
3912:
3904:
3900:
3890:
3886:
3877:
3869:
3863:
3857:
3851:
3845:
3839:
3833:
3813:
3808:
3800:
3791:
3787:
3779:
3771:
3759:
3755:
3751:
3748:
3743:
3726:
3722:
3713:
3709:
3701:
3697:
3689:
3685:
3677:
3674:with maximum
3673:
3669:
3665:
3661:
3653:
3649:
3646:
3638:
3632:
3624:
3618:
3610:
3608:directed path
3604:
3601:
3595:
3589:
3584:
3578:
3574:
3565:
3560:
3553:
3547:
3542:
3535:
3529:
3524:
3517:
3511:
3505:
3501:
3495:
3489:
3487:
3480:
3474:
3471:directed path
3466:
3460:
3457:directed line
3452:
3446:
3443:directed edge
3438:
3432:
3424:
3420:
3416:
3408:
3400:
3392:
3390:directed path
3386:
3378:
3374:
3366:
3362:
3358:
3354:
3346:
3340:
3334:
3329:
3321:
3320:diamond graph
3317:
3309:
3308:shortest path
3305:
3297:
3293:
3288:
3280:
3276:
3272:
3268:
3260:
3252:
3248:
3237:
3232:
3229:
3221:
3217:
3213:
3209:
3203:
3195:
3191:
3184:
3179:
3175:
3162:
3156:
3152:
3141:
3131:
3127:
3091:
3079:
3066:
3060:
3054:
3048:
3045:decomposition
3040:
3034:
3028:
3024:
3016:
3008:
3004:
2998:
2989:
2985:
2981:
2976:
2972:
2963:
2955:
2939:
2935:
2931:
2927:
2923:
2919:
2913:
2907:
2903:
2895:
2891:
2885:
2881:
2877:
2873:
2865:
2859:
2850:
2846:
2833:
2829:
2822:
2818:
2814:
2810:
2802:
2799:
2795:
2792:
2788:
2784:
2781:
2777:
2774:
2770:
2767:
2763:
2750:
2746:
2742:
2734:
2730:
2726:
2722:
2714:
2710:
2707:
2706:spanning tree
2703:
2695:
2691:
2664:
2660:
2653:
2645:
2641:
2638:
2624:
2617:
2609:
2603:
2594:
2591:
2583:
2577:
2565:
2554:
2546:
2542:
2534:
2528:
2520:
2516:
2496:
2492:
2484:
2480:
2476:
2472:
2468:
2460:
2457:
2452:
2448:
2445:
2439:
2435:
2432:
2428:
2422:
2418:
2414:
2410:
2403:
2399:
2395:
2390:
2384:
2380:
2376:
2363:
2357:
2353:
2344:
2340:
2302:
2292:
2288:
2279:
2275:
2271:
2268:comparability
2263:
2259:
2256:
2252:
2248:
2244:
2243:list coloring
2240:
2239:edge coloring
2236:
2217:
2213:
2209:
2204:
2200:
2196:
2183:
2179:
2175:
2171:
2163:
2159:
2156:
2150:
2141:
2138:
2132:
2129:
2123:
2120:
2118:neighbourhood
2114:
2106:
2089:
2085:
2077:
2071:
2063:
2057:
2053:
2049:
2045:
2035:
2031:
2027:
2026:clique number
2014:
2010:
2002:
1994:
1989:
1985:
1977:
1973:
1970:
1966:
1962:
1954:
1953:circumference
1950:
1947:circumference
1942:
1938:
1934:
1926:
1922:
1918:
1898:
1897:list coloring
1890:
1873:
1872:edge coloring
1865:
1859:
1855:
1844:
1840:
1836:
1832:
1826:
1818:
1814:
1810:
1806:
1803:
1799:
1796:
1792:
1789:
1788:chordal graph
1785:
1782:
1761:
1753:
1747:
1739:
1735:
1724:
1720:
1716:
1713:
1706:
1698:
1692:
1684:
1683:chain complex
1680:
1676:
1673:
1667:
1651:
1647:
1639:
1633:
1629:
1621:
1617:
1609:
1606:carving width
1601:
1595:
1591:
1583:
1578:
1574:
1561:
1557:
1549:
1545:
1537:
1531:
1521:
1517:
1513:
1510:
1505:
1496:
1492:
1489:
1485:
1477:
1473:
1469:
1461:
1460:bridged graph
1457:
1454:
1450:
1446:
1442:
1438:
1434:
1430:
1426:
1422:
1419:
1415:
1407:
1401:
1361:
1357:
1349:
1340:
1336:
1328:
1322:
1318:
1309:
1305:
1298:
1289:
1284:
1279:
1275:
1267:
1262:
1256:
1248:
1242:
1238:
1213:
1209:
1186:
1182:
1165:
1162:
1144:
1136:
1128:
1122:
1118:
1100:
1096:
1092:
1088:
1082:
1078:
1070:
1062:
1056:
1052:
1043:
1039:
1032:
1024:
1018:
1014:
994:
990:
982:
974:
968:
962:
953:
949:
941:
935:
919:
911:
904:
896:
890:
884:
878:
872:
869:
860:
856:
851:of the arrow
850:
842:
838:
831:
826:
819:
813:
808:
801:
795:
791:
786:
779:
775:
768:
764:
756:
752:
746:
740:
735:, such as an
734:
728:
724:
716:
710:
702:
696:
688:
684:
673:
667:
663:
655:
652:anti-triangle
647:
643:
635:
631:
595:
592:
589:
577:
573:
565:
560:
552:
544:
540:
535:
527:
523:
514:
511:
504:
501:
477:
473:
465:
461:
458:
454:
450:
442:
438:
418:
398:
378:
372:
369:
366:
346:
326:
318:
312:
301:
297:
290:
286:
279:
275:
268:
264:
259:
255:
251:
235:
228:
224:
218:
206:
203:
201:
198:
196:
193:
191:
188:
186:
183:
181:
178:
176:
173:
171:
168:
166:
163:
161:
158:
156:
153:
151:
148:
146:
143:
141:
138:
136:
133:
131:
128:
126:
123:
121:
118:
116:
113:
111:
108:
106:
103:
101:
98:
96:
93:
91:
88:
86:
83:
81:
78:
76:
73:
71:
68:
67:
57:
55:
51:
47:
43:
39:
33:
19:
9577:Graph theory
9555:, retrieved
9551:
9542:
9516:Graph Theory
9515:
9508:
9474:
9468:
9428:
9424:
9418:
9399:
9392:
9379:
9335:
9329:
9306:
9296:
9283:
9277:
9248:
9244:
9238:
9222:
9218:
9212:
9194:
9190:
9184:
9158:Graph Theory
9157:
9151:
9139:
9120:
9114:
9111:GrĂĽnbaum, B.
9105:
9094:
9041:(1): 21–39,
9038:
9034:
9024:
8932:clique-width
8876:well-covered
8860:well-colored
8799:
8795:
8794:. A walk is
8791:
8759:
8745:Wagner graph
8739:Klaus Wagner
8723:wheel graphs
8664:
8650:
8646:
8570:
8569:Synonym for
8558:
8551:
8437:wheel graphs
8381:
8377:
8360:unary vertex
8336:
8331:
8327:
8323:
8318:
8314:
8299:
8295:
8290:
8286:
8281:neighborhood
8105:
7976:Synonym for
7650:
7643:
7638:
7588:
7578:
7551:
7501:sparse graph
7445:vertex space
7433:binary field
7392:
7388:
7371:
7361:
7357:
7328:simple graph
7268:Synonym for
7251:second order
7212:in the root.
7112:
7087:recognizable
7079:
7073:
7061:
7055:
7045:reachability
7017:reachability
6948:eccentricity
6861:pseudoforest
6855:pseudoforest
6754:
6744:
6705:planar graph
6666:eccentricity
6373:second order
6342:
6338:
6291:
6283:
6278:Kneser graph
6179:
6172:
6168:
6161:
6157:
6150:
6145:
6141:
6106:neighborhood
6070:
6055:multiplicity
6012:minor-closed
6011:
5809:median graph
5731:
5727:
5605:
5601:
5582:
5578:
5567:longest path
5512:edge-labeled
5511:
5507:
5479:
5475:
5468:
5392:
5388:
5381:
5365:
5325:Synonym for
5264:
5260:
5252:
5248:
5127:intersection
5120:
5091:Synonym for
5049:indifference
5043:pseudoforest
5021:
5017:
4966:when vertex
4829:
4816:homomorphism
4771:minor-closed
4770:
4736:
4729:
4725:
4718:
4596:
4565:
4551:
4481:Mixed graphs
4407:
4378:Synonym for
4361:Frucht graph
4330:quasi-random
4274:
4117:spectral gap
3978:
3974:
3920:planar graph
3888:
3884:
3812:simple graph
3797:eccentricity
3757:
3753:
3746:
3668:dissociation
3667:
3663:
3629:disconnected
3622:disconnected
3619:Cause to be
3579:between two
3563:
3551:
3545:
3533:
3527:
3515:
3509:
3503:
3482:
3429:directed arc
3375:Synonym for
3344:disconnected
3295:
3291:
3274:
3270:
3250:
3246:
3235:
3227:
3219:
3201:
3193:
3189:
3182:
3177:
3173:
3160:
3154:
3150:
3139:
3026:
2988:vector space
2974:
2970:
2952:-cycle is a
2884:vector space
2812:
2798:Partial cube
2748:
2725:vertex cover
2578:Synonym for
2529:Cause to be
2495:condensation
2489:condensation
2420:
2416:
2412:
2408:
2401:
2397:
2393:
2382:
2378:
2374:
2355:
2351:
2226:colors, and
2216:planar graph
2088:clique-width
2082:clique-width
2055:
2047:
2044:clique graph
2033:
2029:
1992:
1941:circuit rank
1921:circle graph
1887:choosability
1857:
1853:
1842:
1838:
1817:circle graph
1737:
1733:
1722:
1718:
1711:
1637:eccentricity
1571:canonization
1548:cactus graph
1519:
1515:
1508:
1448:
1440:
1436:
1432:
1428:
1424:
1287:
1282:
1098:
1094:
1090:
1086:
1041:
1015:Synonym for
946:automorphism
858:
854:
840:
836:
833:. The arrow
829:
817:
811:
799:
793:
789:
777:
766:
754:
750:
727:ordered pair
693:arborescence
645:
644:Synonym for
542:
538:
525:
521:
515:For a graph
509:
299:
295:
288:
284:
277:
273:
266:
262:
254:prime symbol
226:
42:Graph theory
37:
35:
8926:branchwidth
8894:wheel graph
8717:The letter
8611:disconnects
8386:mixed graph
8250:Turán graph
8178:of a graph
8130:of a graph
7946:topological
7884:theta graph
7698:orientation
7601:squaregraph
7594:half-square
7575:graph power
7540:split graph
7518:eigenvalues
7453:cycle space
7194:graph power
7135:A graph is
6892:line graphs
6867:pseudograph
6796:predecessor
6748:of a graph
6741:graph power
6570:of a graph
6545:of a graph
6482:outerplanar
6425:tournaments
6417:orientation
6406:orientation
6367:first order
6224:empty graph
6051:multigraph.
6024:Moore graph
6018:Moore graph
5960:mixed graph
5926:subdivision
5843:minimum cut
5736:of a graph
5610:of a graph
5455:knot theory
5295:isomorphism
5288:isomorphism
5163:of a graph
5153:line graphs
5121:independent
5004:independent
4962:and column
4840:A directed
4672:Hamiltonian
4603:A graph is
4315:is a graph
4244:first order
4159:plane graph
4130:if all its
4038:of a graph
3985:enumeration
3938:empty graph
3843:disconnects
3522:predecessor
3423:mixed graph
3326:diconnected
3279:dense graph
3277:nodes. See
3029:. See also
2984:cycle space
2962:cycle graph
2886:having the
2821:Cubic graph
2809:graph power
2791:half-square
2665:of a graph
2646:is a graph
2588:contraction
2090:of a graph
2075:block graph
2068:clique tree
2058:. See also
2046:of a graph
2038:of a graph
1937:cycle space
1911:-choosable.
1891:A graph is
1614:caterpillar
1596:. See also
1530:cycle graph
1398:branchwidth
1241:block graph
1029:biconnected
995:of a graph
939:alternating
918:binary tree
747:. An arrow
578:, a subset
557:alternating
533:independent
482:and column
236:of a graph
9571:Categories
9258:1504.06176
9017:References
8911:degeneracy
8636:vertex set
8629:cut vertex
8593:vertex cut
8559:vertex set
8368:undirected
8232:null graph
8044:transitive
8012:tournament
8006:tournament
7844:supergraph
7441:edge space
7427:, several
7331:otherwise.
6782:Power laws
6768:leaf power
6652:peripheral
6454:out-degree
6294:− 1)
6286:− 1)
6217:null graph
6040:multigraph
6034:multigraph
6007:hereditary
6004:. Compare
5986:Modularity
5896:. It is a
5633:degeneracy
5598:line graph
5546:leaf power
5486:line graph
5405:or to the
5281:isomorphic
5094:degenerate
4892:hypergraph
4886:hypergraph
4863:hypergraph
4763:. Compare
4747:hereditary
3725:dual graph
3706:dominating
3666:is called
3615:disconnect
3507:to vertex
3298:of a node.
3090:degeneracy
3076:degeneracy
3071:degenerate
2766:Cube graph
2729:edge cover
2636:degeneracy
2285:complement
2262:degeneracy
2182:cocoloring
2154:transitive
2136:transitive
1472:bridgeless
1466:bridgeless
932:augmenting
888:disconnect
666:apex graph
630:antichains
435:achromatic
258:line graph
205:References
36:This is a
30:See also:
8944:treewidth
8938:pathwidth
8920:bandwidth
8602:A set of
8420:universal
8244:Pál Turán
8176:treewidth
8170:treewidth
8072:transpose
8018:traceable
7887:smallest.
7777:successor
7739:subforest
7688:component
7682:connected
7648:for some
7527:expansion
7449:cut space
7431:over the
7299:pathwidth
7264:self-loop
7244:pathwidth
7223:saturated
7174:transpose
7123:rectangle
7038:reachable
6983:−
6955:Ramanujan
6888:claw-free
6709:embedding
6568:pathwidth
6562:pathwidth
6274:odd graph
6244:odd girth
6098:neighbour
5947:forbidden
5701:expansion
5432:absorbing
5314:expansion
5242:direction
5215:invariant
5208:pathwidth
5087:inductive
4970:and edge
4944:incidence
4938:incidence
4924:in-degree
4880:hypercube
4870:hypercube
4850:hyperedge
4843:hyperedge
4568:-coloring
4424:embedding
4287:forbidden
4030:expansion
3909:embedding
3834:A set of
3636:connected
3571:direction
3558:reachable
3540:successor
3493:direction
3338:connected
2876:cut space
2870:cut space
2856:cut point
2607:transpose
2581:component
2539:connected
2532:connected
2465:component
2306:¯
1882:choosable
1856: ′(
1823:chromatic
1745:chromatic
1736: ′(
1696:expansion
1566:canonical
1482:butterfly
1126:bipartite
1115:biregular
1075:bipartite
1060:component
1050:connected
993:bandwidth
987:bandwidth
928:children.
910:-ary tree
894:component
784:direction
682:vertices.
640:anti-edge
593:≤
570:antichain
376:∖
370:∈
315:absorbing
298: ′(
9557:25 March
9031:Hell, P.
8974:See also
8961:windmill
8841:vertices
8813:directed
8788:vertices
8780:sequence
8659:vertices
8605:vertices
8471:vertices
8378:directed
8214:triangle
7999:Eulerian
7979:edgeless
7753:subgraph
7659:strength
7512:spectrum
7507:spectral
7475:spanning
7230:matching
6842:property
6729:polytree
6723:polytree
6673:Petersen
6638:matching
6421:polytree
6411:oriented
6209:non-edge
6093:neighbor
5992:monotone
5872:A graph
5714:matching
5708:matching
5374:complete
5273:isolated
5222:property
5175:interval
5115:internal
5101:infinite
4978:incident
4910:critical
4836:hyperarc
4766:monotone
4647:Hadwiger
4503:Grötzsch
4431:geodesic
4193:-factor.
4018:expander
3997:Eulerian
3969:endpoint
3932:manifold
3874:edge set
3867:cut edge
3830:edge cut
3769:edge set
3688:distance
3682:distance
3672:subgraph
3643:disjoint
3587:vertices
3582:adjacent
3413:directed
3302:diameter
3226:Δ,
3032:critical
2739:critical
2600:converse
2443:matching
2337:complete
2193:coloring
2105:cographs
2061:biclique
1751:coloring
1650:centroid
1644:centroid
1528:-vertex
1315:boundary
1022:complete
1011:biclique
979:balanced
781:, and a
732:vertices
646:non-edge
620:or from
550:matching
498:adjacent
200:See also
50:vertices
9501:0335362
9461:4429113
9453:9623998
9433:Bibcode
9362:0253932
9312:105–121
8565:valency
8392:uniform
8384:. In a
8226:trivial
8204:bramble
7856:, then
7769:subtree
7711:perfect
7573:is the
7459:spanner
7306:sibling
7167:reverse
7131:regular
6784:in the
6628:graphs.
6604:perfect
6590:pendant
6399:bramble
6187:network
5966:modular
5950:minors.
5857:cut-set
5830:minimal
5815:Meyniel
5780:maximum
5748:maximal
5626:linkage
5484:is the
5321:isthmus
5067:induced
4778:hexagon
4580:(where
4381:induced
4115:is the
3861:isthmus
3694:domatic
3371:digraph
3314:diamond
3265:density
3234:Δ(
3215:edges).
3161:valency
3138:Δ(
2889:cut-set
2843:cut-set
2807:is the
2713:cograph
2525:connect
2202:colors.
2178:cograph
2147:closure
2050:is the
1931:circuit
1923:is the
1862:is the
1779:chordal
1339:bramble
1333:bramble
1265:cut-set
1260:minimal
1232:. When
845:is the
536:), and
447:acyclic
230:is the
215:Symbols
9531:
9499:
9489:
9459:
9451:
9425:Nature
9407:
9360:
9350:
9318:
9172:
8941:, and
8853:weight
8838:whose
8820:weight
8800:closed
8792:chains
8733:Wagner
8696:volume
8671:Vizing
8665:vertex
8587:vertex
8581:vertex
8573:degree
8483:weight
8468:whose
8052:. The
7784:vertex
7746:forest
7708:, see
7671:strong
7614:stable
7592:. The
7565:square
7495:sparse
7489:factor
7411:source
7322:simple
7051:vertex
7025:vertex
6941:radius
6924:quiver
6918:quiver
6816:proper
6803:vertex
6699:planar
6501:parent
6461:degree
6364:; see
6202:vertex
5854:whose
5796:median
5728:α
5552:length
5492:; see
5449:. See
5426:stable
5419:kernel
5389:κ
5382:κ
5328:bridge
5183:is an
5108:finite
5060:proper
5018:α
4994:; see
4931:degree
4737:height
4730:height
4726:height
4719:height
4713:height
4487:greedy
4349:Frucht
4343:forest
4337:forest
4280:bridge
4275:havens
4253:edges.
4235:finite
4221:family
4169:factor
3855:bridge
3766:; see
3676:degree
3549:, and
3499:vertex
3383:dipath
3365:simple
3361:simple
3332:Strong
3258:degree
3247:δ
3244:, and
3228:δ
3151:δ
3130:degree
3124:degree
3088:. The
2956:and a
2789:, the
2700:cotree
2481:, and
2440:; see
2281:order.
2111:closed
2030:ω
2024:. The
2013:clique
2007:clique
1915:circle
1854:χ
1839:χ
1734:χ
1719:χ
1712:χ
1703:cherry
1632:center
1626:center
1542:cactus
1532:; see
1524:is an
1418:bridge
1412:bridge
1346:branch
1246:forest
1160:forest
1142:block.
1103:where
1057:, see
1053:; for
876:vertex
759:has a
671:planar
539:α
522:α
510:α
453:forest
296:χ
285:χ
274:α
263:α
46:graphs
9457:S2CID
9380:level
9284:depth
9253:arXiv
8904:width
8888:wheel
8835:graph
8784:edges
8617:graph
8465:graph
8382:mixed
8238:Turán
8196:haven
8100:-tree
8030:trail
7875:theta
7547:split
7534:split
7419:space
7405:snark
7399:snark
7372:order
7071:from
7031:graph
6827:color
6735:power
6468:outer
6393:haven
6325:order
5954:mixed
5912:is a
5878:minor
5876:is a
5868:minor
5659:local
5583:depth
5579:depth
5573:level
5563:girth
5502:label
5236:arrow
4898:hypo-
4860:in a
4739:of a
4695:haven
4685:haven
4681:path.
4599:-free
4467:graph
4461:girth
4455:girth
4443:giant
4417:genus
4265:, an
4257:-flap
4228:class
4157:In a
3928:genus
3864:, or
3849:graph
3599:arrow
3593:graph
3590:in a
3561:from
3537:is a
3519:is a
3464:arrow
3450:arrow
3436:arrow
3357:digon
3351:digon
3296:level
3292:depth
3285:depth
3198:, or
3061:, or
3038:hypo-
3027:cards
2986:is a
2954:digon
2938:girth
2906:cycle
2900:cycle
2880:GF(2)
2760:cubic
2749:hypo-
2733:union
2719:cover
2654:from
2623:-core
2423:, ...
2404:, ...
2188:color
1965:class
1959:class
1830:color
1774:chord
1758:child
1664:chain
1535:cycle
1133:block
1123:is a
879:in a
788:from
741:in a
721:arrow
574:In a
54:edges
9559:2018
9529:ISBN
9487:ISBN
9449:PMID
9405:ISBN
9385:NIST
9348:ISBN
9316:ISBN
9289:NIST
9170:ISBN
8847:edge
8796:open
8776:walk
8770:walk
8725:and
8663:See
8614:the
8557:See
8500:The
8477:edge
8474:and
8380:and
8345:and
8326:) =
8308:and
8270:twin
8174:The
8154:and
8108:+ 1)
8090:tree
8084:tree
8076:The
8037:walk
7993:walk
7986:tour
7902:The
7817:and
7805:and
7691:. A
7685:and
7663:The
7634:star
7628:star
7346:size
7338:sink
7282:See
7271:loop
7227:See
7196:: a
7181:root
7171:See
7143:. A
7113:deck
7103:The
7068:path
7048:. A
7010:ends
6766:. A
6616:and
6597:leaf
6594:See
6566:The
6529:and
6523:path
6517:path
6475:face
6472:See
6458:See
6396:and
6370:and
6354:size
6316:walk
6300:open
6221:See
6195:node
6115:The
5677:loop
5671:loop
5640:list
5592:line
5533:leaf
5495:line
5453:and
5439:knot
5429:and
5348:join
5346:The
5342:join
5311:See
5079:and
4954:The
4857:edge
4787:hole
4459:The
4374:full
4325:G(n)
4153:face
4010:even
3979:head
3975:tail
3901:The
3846:the
3837:edge
3818:and
3805:edge
3719:dual
3686:The
3633:Not
3543:of
3485:edge
3478:path
3461:See
3447:See
3433:See
3387:See
3318:The
3200:deg(
3049:See
3013:deck
2917:tour
2911:walk
2874:The
2860:See
2755:cube
2663:core
2644:core
2614:core
2513:cone
2493:The
2360:. A
2289:The
2127:walk
2086:The
1999:. A
1988:claw
1982:claw
1951:The
1748:and
1731:and
1693:See
1671:walk
1630:The
1599:deck
1588:card
1560:cage
1554:cage
1402:See
1326:face
1286:1,1,
1278:book
1272:book
1253:bond
1107:and
991:The
901:-ary
821:the
815:and
773:head
770:, a
762:tail
738:edge
714:edge
711:See
700:tree
660:apex
490:and
474:The
439:The
252:The
9521:doi
9479:doi
9441:doi
9429:393
9340:doi
9263:doi
9249:122
9227:doi
9199:doi
9162:doi
9125:doi
9043:doi
8844:or
8782:of
8626:or
8372:An
8276:u,v
8206:of
8198:of
8190:of
7813:of
7653:≥ 2
7423:In
7077:to
7004:ray
6821:be.
6788:of
6762:in
6486:An
6259:ear
6238:odd
6177:or
6155:or
6135:in
5928:of
5920:if
5916:of
5884:if
5851:cut
5510:or
5488:of
5411:of
5401:of
5233:An
5198:to
5187:of
5071:An
5053:An
4942:An
4854:An
4588:to
4572:An
4475:or
4161:or
4022:An
4001:An
3963:end
3961:An
3957:end
3788:An
3776:ear
3525:of
3335:ly
3167:in
3001:DAG
2852:it.
2849:cut
2838:cut
2677:to
2168:co-
1996:1,3
1874:of
1866:of
1439:.
1362:of
1228:of
1089:= (
965:bag
827:to
809:to
792:to
729:of
725:An
707:arc
632:in
624:to
616:to
608:in
9573::
9550:,
9527:,
9497:MR
9495:,
9485:,
9455:,
9447:,
9439:,
9427:,
9383:,
9370:^
9358:MR
9356:,
9346:,
9314:,
9287:,
9261:,
9247:,
9223:99
9221:,
9195:15
9193:,
9168:,
9121:14
9119:,
9088:;
9084:;
9080:;
9057:^
9039:40
9037:,
8965:A
8935:,
8929:,
8923:,
8892:A
8880:A
8864:A
8832:A
8810:A
8774:A
8585:A
8462:A
8339:))
8294:=
8284::
8148:uv
8126:A
8034:A
8022:A
8010:A
7781:A
7642:1,
7632:A
7499:A
7403:A
7382:A
7364:)|
6959:A
6922:A
6902:A
6859:A
6846:A
6800:A
6727:A
6703:A
6541:A
6521:A
6345:)|
6290:(2
6038:A
6022:A
5958:A
5848:A
5730:′(
5712:A
5675:A
5561:,
5299:A
5263:,
5251:,
4890:A
4874:A
4751:A
4689:A
4676:A
4392:A
4341:A
4311:A
4291:A
4201:A
3913:A
3858:,
3824:xy
3723:A
3710:A
3678:1.
3531:,
3513:,
3475:A
3417:A
3355:A
3187:,
3080:A
3055:,
2979:.
2932:,
2928:,
2847:A
2723:A
2543:A
2477:,
2469:A
2419:,
2415:,
2400:,
2396:,
2011:A
1986:A
1919:A
1851:.
1648:A
1618:A
1575:A
1558:A
1546:A
1470:A
1447:,
1358:A
1337:A
1257:A
1119:A
1079:A
950:A
905:A
897:s.
873:A
857:,
839:,
797:;
753:,
553:).
541:′(
519:,
276:′(
56:.
40:.
9523::
9481::
9443::
9435::
9365:.
9342::
9272:.
9265::
9255::
9229::
9201::
9179:.
9164::
9134:.
9127::
9100:.
9052:.
9045::
8947:.
8914:.
8763:5
8760:K
8719:W
8712:W
8705:W
8667:.
8655:.
8653:)
8651:G
8649:(
8647:V
8642:G
8632:.
8577:.
8561:.
8552:V
8545:V
8540:.
8526:3
8523:,
8520:3
8516:K
8492:.
8414:2
8410:k
8406:k
8402:k
8398:k
8354:U
8347:v
8343:u
8337:v
8335:(
8332:G
8328:N
8324:u
8322:(
8319:G
8315:N
8310:v
8306:u
8300:G
8296:N
8291:G
8287:N
8234:.
8210:.
8208:G
8200:G
8192:G
8184:G
8180:G
8166:.
8164:G
8160:G
8156:v
8152:u
8144:v
8140:v
8136:G
8132:G
8116:1
8112:k
8106:k
8104:(
8098:k
8068:.
8002:.
7982:.
7942:.
7928:3
7925:,
7922:3
7918:K
7869:T
7864:.
7862:H
7858:G
7854:G
7850:H
7838:O
7834:I
7830:T
7826:S
7822:O
7819:T
7815:I
7811:S
7807:O
7803:I
7793:.
7763:G
7759:G
7749:.
7714:.
7701:.
7651:n
7644:n
7639:K
7624:.
7589:G
7584:G
7579:G
7571:G
7530:.
7393:N
7389:L
7368:m
7362:G
7360:(
7358:E
7356:|
7352:G
7318:.
7316:v
7312:v
7302:.
7288:.
7274:.
7247:.
7233:.
7217:S
7210:k
7206:G
7202:G
7198:k
7189:.
7177:.
7155:.
7153:d
7149:d
7141:d
7137:d
7117:G
7109:G
7083:.
7080:y
7074:x
7062:x
7056:y
7034:.
7000:.
6986:1
6980:d
6975:2
6965:d
6935:R
6914:.
6876:Q
6830:.
6812:.
6764:G
6760:k
6755:G
6750:G
6745:G
6717:k
6713:k
6641:.
6600:.
6584:G
6580:G
6576:G
6572:G
6558:.
6556:G
6552:G
6547:G
6533:.
6511:v
6507:v
6495:P
6478:.
6464:.
6450:.
6402:.
6376:.
6349:n
6343:G
6341:(
6339:V
6337:|
6333:G
6319:.
6310:.
6292:n
6284:n
6282:(
6269:.
6262:.
6232:O
6227:.
6205:.
6180:N
6173:G
6169:N
6164:)
6162:v
6160:(
6158:N
6153:)
6151:v
6149:(
6146:G
6142:N
6137:G
6133:v
6129:v
6125:v
6121:v
6087:n
6082:.
6071:N
6064:N
6002:G
5998:G
5938:H
5934:H
5930:H
5922:G
5918:G
5910:H
5906:H
5902:G
5894:G
5890:G
5886:H
5882:G
5874:H
5864:.
5804:.
5786:G
5758:G
5754:G
5738:G
5734:)
5732:G
5704:.
5688:M
5681:1
5636:.
5622:.
5620:G
5616:G
5612:G
5608:)
5606:G
5604:(
5602:L
5539:1
5498:.
5490:G
5482:)
5480:G
5478:(
5476:L
5469:L
5462:L
5457:.
5435:.
5415:.
5413:G
5403:G
5395:)
5393:G
5391:(
5377:.
5366:K
5359:K
5336:J
5317:.
5291:.
5269:.
5267:)
5265:y
5261:x
5259:(
5255:)
5253:x
5249:y
5247:(
5225:.
5211:.
5202:.
5200:v
5196:u
5191:.
5171:.
5169:G
5165:G
5111:.
5097:.
5063:.
5045:.
5030:.
5024:)
5022:G
5020:(
5000:.
4972:j
4968:i
4964:j
4960:i
4934:.
4918:I
4882:.
4800:.
4761:G
4757:G
4707:k
4703:k
4699:X
4693:-
4691:k
4643:.
4641:H
4637:H
4633:H
4621:H
4617:H
4613:H
4609:H
4605:H
4597:H
4592:.
4590:G
4586:H
4582:H
4578:G
4574:H
4566:H
4561:.
4559:G
4552:H
4545:H
4427:.
4408:G
4401:G
4384:.
4333:.
4321:H
4317:H
4301:H
4297:H
4271:X
4267:X
4263:X
4231:.
4215:1
4211:k
4207:k
4191:1
4183:1
4179:k
4175:k
4147:F
4140:r
4136:r
4132:r
4121:d
4113:G
4109:d
4104:.
4102:S
4098:S
4094:S
4090:G
4086:G
4081:.
4079:S
4075:S
4071:G
4067:S
4063:G
4058:.
4056:S
4052:S
4048:G
4044:S
4040:G
3981:.
3893:.
3891:)
3889:G
3887:(
3885:E
3880:G
3870:.
3826:.
3820:y
3816:x
3772:.
3764:G
3760:)
3758:G
3756:(
3754:E
3747:E
3740:E
3735:.
3733:G
3729:G
3664:G
3639:.
3625:.
3611:.
3602:.
3567:.
3564:x
3552:y
3546:x
3534:y
3528:y
3516:x
3510:y
3504:x
3488:s
3467:.
3453:.
3439:.
3393:.
3379:.
3367:.
3347:)
3281:.
3275:n
3271:n
3261:.
3253:)
3251:G
3249:(
3242:G
3238:)
3236:G
3204:)
3202:v
3196:)
3194:G
3192:(
3190:d
3185:)
3183:v
3181:(
3178:G
3174:d
3169:G
3165:v
3157:)
3155:G
3153:(
3146:G
3142:)
3140:G
3134:G
3118:k
3114:k
3110:k
3106:k
3102:k
3098:k
3094:k
3086:k
3082:k
3067:.
3019:G
2995:D
2975:n
2971:C
2966:n
2958:3
2950:2
2946:k
2942:k
2882:-
2866:.
2825:3
2816:.
2813:G
2805:G
2708:.
2687:G
2683:H
2679:H
2675:G
2671:H
2667:G
2656:G
2648:G
2639:.
2631:k
2627:k
2621:k
2610:.
2584:.
2568:k
2562:k
2557:k
2551:k
2535:.
2521:.
2509:.
2507:G
2503:G
2499:G
2485:.
2446:.
2426:.
2421:c
2417:b
2413:a
2409:K
2402:c
2398:b
2394:a
2383:b
2381:,
2379:a
2375:K
2370:b
2366:a
2356:n
2352:K
2347:n
2333:.
2331:G
2327:G
2323:G
2303:G
2232:k
2228:k
2224:k
2220:k
2157:.
2139:.
2130:.
2121:.
2107:.
2101:2
2096:G
2092:G
2078:.
2056:G
2048:G
2040:G
2036:)
2034:G
2032:(
2022:k
2018:k
1993:K
1909:k
1905:k
1901:k
1893:k
1878:.
1876:G
1868:G
1860:)
1858:G
1849:G
1845:)
1843:G
1841:(
1819:.
1768:v
1764:v
1754:.
1740:)
1738:G
1729:G
1725:)
1723:G
1721:(
1699:.
1674:.
1658:v
1654:v
1640:.
1538:.
1526:n
1520:n
1516:C
1509:C
1502:C
1497:.
1478:.
1449:H
1441:H
1437:H
1433:H
1429:H
1425:H
1408:.
1394:.
1392:G
1388:G
1384:e
1380:G
1376:e
1372:G
1368:G
1364:G
1329:.
1301:4
1294:n
1288:n
1283:K
1234:G
1230:G
1214:i
1210:B
1187:i
1183:b
1172:G
1168:G
1163:.
1155:G
1151:G
1147:G
1139:G
1109:V
1105:U
1101:)
1099:E
1097:,
1095:V
1093:,
1091:U
1087:G
1063:.
1045:2
1042:K
1036:2
1025:.
1005:G
1001:G
997:G
975:.
959:B
942:.
926:k
922:k
914:k
908:k
863:.
861:)
859:y
855:x
853:(
843:)
841:x
837:y
835:(
830:y
818:x
812:x
800:y
794:y
790:x
778:y
767:x
757:)
755:y
751:x
749:(
717:.
703:.
680:k
676:k
636:.
626:x
622:y
618:y
614:x
610:S
596:y
590:x
580:S
545:)
543:G
528:)
526:G
524:(
517:G
492:j
488:i
484:j
480:i
431:.
419:A
399:v
379:A
373:G
367:v
347:G
327:A
309:A
302:)
300:G
291:)
289:G
287:(
280:)
278:G
269:)
267:G
265:(
244:.
242:S
238:G
227:G
195:Z
190:Y
185:X
180:W
175:V
170:U
165:T
160:S
155:R
150:Q
145:P
140:O
135:N
130:M
125:L
120:K
115:J
110:I
105:H
100:G
95:F
90:E
85:D
80:C
75:B
70:A
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.