Glossary of graph theory - Knowledge (XXG)

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.

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

9532: 9490: 9408: 9351: 9319: 9173: 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

2693: 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. 8263: 9475:

Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs)

9581: 8816:

graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.

4665: 2470: 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.

9010: 5860:

has minimum total weight, possibly restricted to cuts that separate a designated pair of vertices; they are characterized by the

4292: 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

4035: 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.

5009: 5941: 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.

9115: 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

7705: 7676: 6617: 6116: 5664: 4894:

is a generalization of a graph in which each edge (called a hyperedge in this context) may have more than two endpoints.

4793: 2482: 1952: 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

45: 5981:, a decomposition of a graph into subgraphs within which all vertices connect to the rest of the graph in the same way. 1111:

are the subsets of vertices of each color. However, unless the graph is connected, it may not have a unique 2-coloring.

8995: 6911: 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. 2544: 2494: 2388: 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. 9093: 6416: 5925: 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

8011: 7104: 7092: 6770:

is a closely related concept, derived from a power of a tree by taking the subgraph induced by the tree's leaves.

6624: 6424: 6384: 4866:, having any number of endpoints, in contrast to the requirement that edges of graphs have exactly two endpoints. 3089: 3022: 2261: 1593: 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.

8505: 7958: 7907: 5861: 2549: 2361: 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.

1034: 1016: 5012:

is a set of vertices that induces an edgeless subgraph. It may also be called a stable set or a coclique. The

4521: 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, 5667:

of the vertices in the graph. For instance, a graph is locally finite if all of its neighborhoods are finite.

1649: 9000: 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.

5713: 5518:

refers to several different problems of assigning labels to graphs subject to certain constraints. See also

5027: 3687: 2429:

2. A completion of a given graph is a supergraph that has some desired property. For instance, a

1801: 31: 9519:, Graduate Texts in Mathematics, vol. 173, Berlin, Heidelberg: Springer Berlin Heidelberg, p. 2, 6777:

is a method for analyzing complex networks by identifying cliques, bicliques, and stars within the network.

1971:

2. A color class of a colored graph is the set of vertices or edges having one particular color.

8954: 8689: 8203: 8061: 7725: 7718: 7424: 6440: 6266: 5188: 4740: 3006: 2560: 2478: 1794: 1475: 1338: 575: 456: 9217:

van der Holst, Hein (March 2009), "A polynomial-time algorithm to find a linkless embedding of a graph",

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.

451:

1. A graph is acyclic if it has no cycles. An undirected acyclic graph is the same thing as a

9576: 8787: 8586: 8259:

states that Turán graphs have the maximum number of edges among all clique-free graphs of a given order.

7521: 7479:

A subgraph is spanning when it includes all of the vertices of the given graph. Important cases include

6834: 6731:

is an oriented tree; equivalently, a directed acyclic graph whose underlying undirected graph is a tree.

6613: 6387:(an order in which each vertex has minimum degree in the induced subgraph of it and all later vertices). 5985: 5978: 4904: 4186: 3675: 3129: 2831: 2744: 2474: 2277: 2012: 1494: 1417: 1054: 633: 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,

49: 9301: 8981: 8256: 6692: 6213:

A non-edge or anti-edge is a pair of vertices that are not adjacent; the edges of the complement graph.

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

9432: 9081: 8451: 8195: 8057: 7546: 7436: 7404: 6923: 6774: 6380: 6243: 5773: 5562: 4694: 4460: 3650:

2. The disjoint union of two or more graphs is a graph whose vertex and edge sets are the

2937: 2905: 2893: 1359: 1299:

2. Another type of graph, also called a book, or a quadrilateral book, is a collection of

563: 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.

8783: 8775: 8751: 8682: 8376:

is a graph in which the two endpoints of each edge are not distinguished from each other. See also

8219: 8089: 8065: 8049: 7965: 7664: 7633: 7488: 7383: 6785: 6612:

is a graph in which, in every induced subgraph, the chromatic number equals the clique number. The

6522: 6432: 5988:

of a graph clustering, the difference of the number of cross-cluster edges from its expected value.

5676: 5398: 5160: 5013: 4991: 4752: 4624: 4557:

A variable often used to denote a graph, especially when another graph has already been denoted by

4508: 4367: 4342: 4202: 4026:

is a graph whose edge expansion, vertex expansion, or spectral expansion is bounded away from zero.

3927: 3576: 2662: 2643: 2273: 1987: 1975: 1559: 1277: 452: 4796:

as being the graphs with no odd holes or odd anti-holes. The hole-free graphs are the same as the

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

9456: 9252: 8987: 8881: 8187: 8127: 8053: 7692: 7009: 6903: 6789: 6542: 6428: 6089:

is often used (especially in computer science) to denote the number of vertices in a given graph.

5450: 5184: 5135: 5054: 5038: 4821: 4809: 3962: 2921: 2848: 2651: 2430: 2211: 2051: 1964: 1924: 1812: 1678: 1581: 951: 867: 9311: 9305: 9110: 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: 8388:, an undirected edge is again one in which the endpoints are not distinguished from each other. 6183:. When the openness or closedness of a neighborhood is not specified, it is assumed to be open. 9528: 9486: 9448: 9404: 9347: 9315: 9169: 7951: 7832:. Some sources require in addition that a superconcentrator be a directed acyclic graph, with 7464: 6487: 6250: 5913: 5526: 5300: 4943: 4514: 4127: 3989: 3789: 3207: 2925: 2786: 2779: 2455: 2450: 2250: 1444: 440: 8510: 7912: 6586:. It is also known as interval thickness, vertex separation number, or node searching number. 4061:

2. The vertex expansion, vertex isoperimetric number, or magnification of a graph

585: 466:

of an undirected graph is a proper coloring in which every two color classes induce a forest.

9520: 9478: 9440: 9339: 9262: 9226: 9198: 9161: 9124: 9077: 9042: 9005: 8897: 8432: 8373: 7891: 7558: 7484: 6657: 6632: 6296:-element set, and an edge connecting two subsets when their corresponding sets are disjoint. 5741: 5722: 5717: 5347: 5072: 4955: 4677: 4492: 4476: 4393: 3950: 3359:

is a simple cycle of length two in a directed graph or a multigraph. Digons cannot occur in

2933: 2751:, used for graphs which do not have a property but for which every one-vertex deletion does. 2732: 2592: 2518: 2437: 2290: 2246: 2173: 1834: 1808: 1619: 1471: 1452: 686: 475: 463: 9500: 9361: 6967:-regular graph, such that the second-largest eigenvalue of its adjacency matrix is at most 5541:. A leaf edge or pendant edge is the edge connecting a leaf vertex to its single neighbour. 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

2924:

and reversals of the walk produce the same cycle. Important special types of cycle include

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

1204: 1177: 455:. An acyclic directed graph, which is a digraph without directed cycles, is often called a 9496: 9357: 9336:

The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968)

8869: 8676: 8447: 8440: 8425: 8077: 8023: 7596:

of a bipartite graph is the subgraph of its square induced by one side of the bipartition.

7256: 6960: 6927: 6887: 6708: 6678: 6645: 6361: 6027: 5835: 5761: 5034: 4875: 4658: 4537: 4496: 4421:

The genus of a graph is the minimum genus of a surface onto which it can be embedded; see

4249: 4162: 3914: 3211: 2772: 2207: 2161: 2133:

3. A graph is transitively closed if it equals its own transitive closure; see

2000: 1863: 1487: 1320: 1120: 1080: 992: 8243: 7610:

defined from points in the plane with integer coordinates connected by unit-length edges.

4913:, used for graphs which have a property but for which every one-vertex deletion does not. 4299:

is one of the graphs that does not occur as a subgraph, induced subgraph, or minor, then

502:

1. The relation between two vertices that are both endpoints of the same edge.

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.

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

9089: 8966: 8726: 8249: 7801:

A superconcentrator is a graph with two designated and equal-sized subsets of vertices

7415:

A source, in a directed graph, is a vertex with no incoming edges (in-degree equals 0).

7008:

A ray, in an infinite graph, is an infinite simple path with exactly one endpoint. The

6847: 6685: 6447: 5789: 5765: 5645: 5519: 5515: 5180: 5148: 4628: 4472: 4023: 3943: 3923: 3902: 3711: 3699: 3651: 3418: 3376: 2342: 2254: 2198: 1576: 1307: 414: 394: 342: 322: 253: 17: 9547: 7342:

A sink, in a directed graph, is a vertex with no outgoing edges (out-degree equals 0).

9570: 9514: 9203: 9047: 8865: 8501: 7903: 7732: 7607: 7524:

is the branch of graph theory that uses spectra to analyze graphs. See also spectral

7480: 7428: 7144: 6907: 6609: 6530: 6436: 5971: 5897: 5823: 5801: 5655:

is a variation of graph coloring in which each vertex has a list of available colors.

5652: 5558: 5140: 5080: 4797: 4652: 4533: 4436: 4354: 4312: 4002: 3319: 3307: 3136:(or its maximum degree) is the maximum of the degrees of its vertices, often denoted 2929: 2705: 2501:

is a directed acyclic graph with one vertex for each strongly connected component of

2242: 2238: 2025: 1896: 1871: 1787: 1682: 1459: 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.

9460: 8744: 8738: 7636:

is a tree with one internal vertex; equivalently, it is a complete bipartite graph

7500: 7468: 7444: 7327: 7186: 7016: 6860: 6704: 6526: 6277: 5826:

is a graph in which every odd cycle of length five or more has at least two chords.

5808: 5566: 5156: 5144: 5076: 5042: 4668:

is the conjecture that the Hadwiger number is never less than the chromatic number.

4448: 4360: 4158: 4116: 3919: 3811: 3364: 3360: 3021:

by deleting a single vertex in all possible ways, especially in the context of the

2987: 2883: 2797: 2724: 2245:(proper coloring with each vertex restricted to a subset of the available colors), 2215: 2087: 2043: 1940: 1920: 1816: 1631: 1547: 1490:

has five vertices and six edges; it is formed by two triangles that share a vertex.

726: 41: 8312:

are neighbors), and they are false twins if they have the same open neighborhood:

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 9398: 7185:

1. A designated vertex in a graph, particularly in directed trees and

5940:

as a minor. A family of graphs is minor-closed if it is closed under minors; the

4946:

in a graph is a vertex-edge pair such that the vertex is an endpoint of the edge.

4524:

that triangle-free planar graphs can always be colored with at most three colors.

4283:

of a cycle, which is either a flap of the cycle vertices or a chord of the cycle.

2689:, and is a core in the sense that all of its self-homomorphisms are isomorphisms. 2115:

1. A closed neighborhood is one that includes its central vertex; see

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.

9189:

Woodall, D. R. (1973), "The Binding Number of a Graph and its Anderson Number",

8893: 8722: 8436: 8385: 8364:

In a rooted tree, a unary vertex is a vertex which has exactly one child vertex.

7883: 7600: 7593: 7574: 7539: 7452: 7193: 6740: 6023: 5959: 5877: 5842: 5454: 4517:, the smallest triangle-free graph requiring four colors in any proper coloring. 4480: 3422: 3278: 2983: 2961: 2820: 2808: 2790: 2124:

2. A closed walk is one that starts and ends at the same vertex; see

1936: 1529: 1240: 917: 256:

is often used to modify notation for graph invariants so that it applies to the

9378: 9282: 9267: 9230: 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

5996:

A monotone property of graphs is a property that is closed under subgraphs: if

5194:

2. The interval in a graph is the union of all shortest paths from

4329: 1797:

is a chordal graph in which every cycle of length six or more has an odd chord.

505:

2. The relation between two distinct edges that share an end vertex.

9524: 9165: 9085: 9030: 8977: 8231: 7517: 7440: 6963:

is a graph whose spectral expansion is as large as possible. That is, it is a

6891: 6767: 6039: 5597: 5545: 5485: 5167:

is the minimum total number of elements in any intersection representation of

5152: 4891: 4014:

Divisible by two; for instance, an even cycle is a cycle whose length is even.

3724: 3132:

of a vertex in a graph is its number of incident edges. The degree of a graph

2765: 2728: 2181: 1303:-cycles joined at a shared edge; the Cartesian product of a star with an edge. 906: 665: 257: 2685:

is unique up to isomorphism. It can be represented as an induced subgraph of

8175: 7448: 6781: 6567: 6273: 4879: 2875: 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), 629: 9338:, Lecture Notes in Mathematics, vol. 110, Springer, pp. 223–230, 5123:) if they do not have any vertex in common, except the first and last ones. 4134:-shallow minors have a ratio of edges to vertices bounded by a function of 1170:

is a bipartite graph where one partite set consists of the cut-vertices of

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

9477:, Lecture Notes in Mathematics, vol. 303, Springer, pp. 43–54, 9304:; Le, Van Bang; Spinrad, Jeremy (1999), "Chapter 7: Forbidden Subgraph", 8779: 6728: 6420: 5663:

A local property of a graph is a property that is determined only by the

4812:

if there exist two homomorphisms, one from each graph to the other graph.

4277:, functions that map small sets of vertices to their flaps. See also the 3931: 6127:. The closed neighbourhood is defined in the same way but also includes 5057:

is another name for a proper interval graph or unit interval graph; see

3063: 1427:

is a maximal connected subgraph separated from the rest of the graph by

1404: 9482: 9343: 9129: 7848:

A graph formed by adding vertices, edges, or both to a given graph. If

5725:

is a matching that uses as many edges as possible; the matching number

5285:

Two graphs are isomorphic if there is an isomorphism between them; see

4777: 2712: 2237:

3. Many variations of coloring have been studied, including

2177: 2104: 9033:; Miller, D. J. (1986), "Concerning the achromatic number of graphs", 8622: 7284: 6752:

is another graph on the same vertex set; two vertices are adjacent in

6446:

2. Oriented graph, used by some authors as a synonym for a

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

3218:

2. The homomorphism degree of a graph is a synonym for its

3057: 3051: 2862: 1462:

is a graph in which every cycle of four or more vertices has a bridge.

971: 924:-ary tree is said to be complete if every internal vertex has exactly 823: 9310:, SIAM Monographs on Discrete Mathematics and Applications, pp. 8685:

that the chromatic index is at most one more than the maximum degree.

8096: 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

3206:. The total degree is the sum of the degrees of all vertices; by the 2619: 916:

children. A 1-ary tree is just a path. A 2-ary tree is also called a

6249:

2. An odd vertex is a vertex whose degree is odd. By the

3240:(using the Greek letter delta) is the maximum degree of a vertex in 805: 9257: 8884:

is a graph all of whose maximal independent sets are the same size.

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

5900:

if it can be formed as a minor in such a way that the subgraphs of

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

4755:

of graphs is a property that is closed under induced subgraphs: if

1622:

or caterpillar is a tree in which the internal nodes induce a path.

881: 9444: 8488: 7978: 7432: 7127:

A simple cycle consisting of exactly four edges and four vertices.

6513:

along the incoming edge, the one that is directed toward the root.

5445: 4759:

has a hereditary property, then so must every induced subgraph of

3356: 2953: 2879: 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.

2180:

is a graph produced by operations that include complementation; a

2151:

1. For the transitive closure of a directed graph, see

1562:

is a regular graph with the smallest possible order for its girth.

954:

is a symmetry of a graph, an isomorphism from the graph to itself.

847: 743: 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.

7789: 6808: 6715:-planar graph is one that can be drawn in the plane with at most 6306: 6253:

every finite undirected graph has an even number of odd vertices.

6078: 4996: 3607: 3389: 2210:

are the graphs that have colorings with only two colors, and the

2164:

is the problem of finding a closure of minimum or maximum weight.

2117: 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 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 9384: 9288: 8931: 8610: 8280: 7655:. The special case of a star with three leaves is called a claw. 7044: 6947: 6688:, a 10-vertex 15-edge graph frequently used as a counterexample. 6665: 6372: 5423:

A kernel of a directed graph is a set of vertices which is both

4783:

A simple cycle consisting of exactly six edges and six vertices.

3842: 3621: 3605:

2. The asymmetric relation between two vertices in a

3343: 1903:

available colors. The choosability of the graph is the smallest

1770:

along an outgoing edge, one that is directed away from the root.

1636: 1431:. That is, it is a maximal subgraph that is edge-disjoint from 1280:, book graph, or triangular book is a complete tripartite graph 8925: 8454:

in a formula may be called a universal vertex for that formula.

7697: 7620: 6366: 6242:

1. An odd cycle is a cycle whose length is odd. The

6223: 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.

5287: 3521: 3041:(graphs that do not have a property that is held by all cards). 3035:(graphs that have a property that is not held by any card) and 2218:

can be colored with at most four colors. A graph is said to be

2074: 1847:

is the minimum number of colors needed in a proper coloring of

938: 532: 530:(using the Greek letter alpha) is its independence number (see 8910: 8628: 6871:

A pseudograph is a graph or multigraph that allows self-loops.

6006: 5944:

characterizes minor-closed families as having a finite set of

5811:

is a graph in which every three vertices have a unique median.

5632: 5331:, in the sense of an edge whose removal disconnects the graph. 5093: 4862: 3930:

of a graph is the minimum possible genus of a two-dimensional

2914:. As a walk it may be either be a closed walk (also called a 2635: 2387:. The same terminology and notation has also been extended to 2329:, with an edge for each two vertices that are not adjacent in 2153: 2135: 1833:. Chromatic graph theory is the theory of graph coloring. The 1443:

may be a set of vertices. A chord is a one-edge bridge. In

887: 27:

List of definitions of terms and concepts used in graph theory

8943: 8937: 8919: 8917:

2. For other graph invariants known as width, see

7687: 7681: 7526: 7298: 7243: 7173: 6123:

is the subgraph induced by all vertices that are adjacent to

5946: 5700: 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.

5431: 5313: 5241: 5207: 4878:

is a graph formed from the vertices and edges of a geometric

4842: 4423: 3635: 3557: 3539: 3492: 3337: 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

2768:, the eight-vertex graph of the vertices and edges of a cube. 2606: 2604:

The converse graph is a synonym for the transpose graph; see

2580: 2531: 2260:

4. The coloring number of a graph is one plus the

2094:

is the minimum number of distinct labels needed to construct

1744: 1695: 1125: 1059: 1049: 893: 783: 656:

A three-vertex independent set, the complement of a triangle.

59: 8812: 8186:. It can also be defined in terms of the clique number of a 7998: 7229: 6894:. They are used in the structure theory of claw-free graphs. 6637: 5373: 5221: 4909: 4765: 4607:-free if it does not have an induced subgraph isomorphic to 3866: 3768: 3581: 3031: 2442: 2060: 1750: 1084:

colored with two colors. Bipartite graphs are often written

1021: 549: 9098:(2 ed.), MIT Press and McGraw-Hill, pp. 1080–1084 8134:

is a tree whose nodes are labeled with sets of vertices of

7710: 6660:

or non-separating cycle is a cycle with at most one bridge.

6398: 5856: 4479:

according to whether the edges have an orientation or not.

4380: 4034:

1. The edge expansion, isoperimetric number, or

3860: 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.

2888: 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

1264: 1259: 232: 9143: 8852: 8840: 8604: 8572: 8482: 8470: 7783: 7745: 7115:, a multiset of graphs formed by removing one vertex from 7050: 7024: 6802: 6582:. It is always between the bandwidth and the treewidth of 6460: 6201: 5425: 5407: 5327: 5107: 5059: 4930: 4279: 4273:. The flap terminology is commonly used in the context of 4123:

of its adjacency matrix and the second-largest eigenvalue.

3854: 3586: 3498: 3331: 3257: 2735:– taken vertex-wise and edge-wise – is equal to the graph. 1245: 1159: 875: 731: 670: 582:

of vertices that are pairwise incomparable, i.e., for any

8834: 8692:

on the domination number of Cartesian products of graphs.

8616: 8464: 7467:, graphs whose vertices are points in a geometric space; 7030: 6826: 6695:

that every bridgeless cubic graph has a perfect matching.

6392: 5235: 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.

4227: 4205:

is a partition of the edges of the graph into factors; a

3848: 3598: 3592: 3463: 3449: 3435: 3322:

is an undirected graph with four vertices and five edges.

3037: 2711:

2. A rooted tree structure used to describe a

1829: 1534: 668:

is a graph in which one vertex can be removed, leaving a

8846: 8476: 8036: 7992: 7270: 7067: 6596: 6474: 6353: 6315: 6000:

has a monotone property, then so must every subgraph of

5744:

is a matching to which no additional edges can be added.

5494: 4856: 3926:

is a graph that has such an embedding onto a torus. The

3836: 3484: 3477: 2916: 2910: 2775:, a higher-dimensional generalization of the cube graph. 2126: 1727:(using the Greek letter chi) is the chromatic number of 1670: 1598: 1325: 772: 761: 737: 713: 699: 8754:

characterizing planar graphs by their forbidden minors.

6390:

4. For the order of a haven or bramble, see

6258: 5850: 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: 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", 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. 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 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 9373: 9371: 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 8: 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 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 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 8518: 8512: 7920: 7914: 7483:, spanning subgraphs that are trees, and 7439:of sets as its vector sum operation. The 7192:2. The inverse operation to a 6977: 6972: 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 2300: 2299: 2297: 1677:2. When applying methods from 1403: 1342:the maximum order of any of its brambles. 1212: 1206: 1185: 1179: 1145:2. The block graph of a graph 587: 416: 396: 364: 344: 324: 9403:, New York: Springer-Verlag, p. 5, 9156:Diestel, Reinhard (2017), "1.1 Graphs", 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 9021: 8621: 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. 970: 822: 375: 271:is the independence number of a graph; 9072: 9070: 9068: 9066: 9064: 9062: 9060: 9058: 8218:A cycle of length three in a graph. A 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 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 8640:The set of vertices of a given graph 6945:The radius of a graph is the minimum 6926:is a directed multigraph, as used in 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 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. 804: 7: 8708: 8548: 8357: 7872: 7569:1. The square of a graph 7220: 6938: 6879: 6498: 6235: 6067: 6010:(closed under induced subgraphs) or 5691: 5465: 5362: 5339: 4921: 4548: 4404: 4150: 4092:, of the number of vertices outside 3743: 2998: 1505: 1019:or complete bipartite subgraph; see 962: 880: 312: 293:is the chromatic number of a graph; 218: 8729:. The notation is not standardized. 8487: 8118:-tree according to this definition. 7977: 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. 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 2892:s of the graph as its elements and 2570:edges cannot disconnect the graph). 1899:whenever each vertex has a list of 846: 742: 494:are adjacent, and a zero otherwise. 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: 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: 8930: 8609: 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 7043: 6946: 6664: 6435:, orientations that are acyclic; 6371: 6131:itself. The open neighborhood of 4050:, of the number of edges leaving 3841: 3620: 3342: 1635: 1382:in the two subtrees separated by 1137:1. A block of a graph 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} 9011:Glossary of areas of mathematics 8980: 8924: 8747:, an eight-vertex Möbius ladder. 8620:. A one-vertex cut is called an 7696: 7619: 6365: 6222: 5936:-minor-free if it does not have 5569:between two vertices in a graph. 5525:2. In the context of 5286: 4769:(closed under all subgraphs) or 4293:forbidden graph characterization 3662:A subset of vertices in a graph 3520: 3496:. If a directed path leads from 2694:Dulmage–Mendelsohn decomposition 2073: 2064:, a complete bipartite subgraph. 1974:3. In the context of 1827:Having to do with coloring; see 937: 531: 8909: 8627: 8443:always have a universal vertex. 6335:is the number of its vertices, 6005: 5631: 5092: 4861: 4846:having a source and target set. 4119:between the largest eigenvalue 2634: 2234:-chromatic if this is possible. 2152: 2134: 886: 204: 52:connected in pairs by lines or 9400:Combinatorics and Graph Theory 8942: 8936: 8918: 8896:is a graph formed by adding a 8872:use the same number of colors. 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 6119:(or neighborhood) of a vertex 6030:. Every Moore graph is a cage. 5945: 5699: 5430: 5312: 5240: 5206: 4841: 4422: 3946:on a nonempty set of vertices. 3934:onto which it can be embedded. 3634: 3556: 3538: 3491: 3336: 2605: 2579: 2530: 2305: 1743: 1694: 1124: 1058: 1048: 892: 782: 1: 9116:Israel Journal of Mathematics 8953:4. The width of a 8811: 8264:Turán's brick factory problem 7997: 7677:strongly connected components 7228: 6636: 6280:, having one vertex for each 5565:(shortest cycle length), and 5372: 5351: 5220: 4908: 4764: 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: 3671: 3580: 3159:. Degree is sometimes called 3030: 2968:vertices is commonly denoted 2483:strongly connected components 2441: 2059: 2020:-clique is a clique of order 1749: 1174:, and the other has a vertex 1020: 548: 199: 9204:10.1016/0095-8956(73)90038-5 9048:10.1016/0095-8956(86)90062-6 8908:1. A synonym for 8110:-cliques together on shared 8102:is a graph formed by gluing 7709: 7706:strong perfect graph theorem 7354:is the number of its edges, 7022:The ability to get from one 6618:strong perfect graph theorem 6397: 5855: 5784:A subgraph of a given graph 5443:An inescapable section of a 4794:strong perfect graph theorem 4483:include both types of edges. 4379: 4177:-factor is a factor that is 3859: 2944:-cycle is a cycle of length 2887: 2658:to itself is an isomorphism. 2633:after earlier removals. See 2389:complete multipartite graphs 1742:is its chromatic index; see 1263: 1258: 628:. Inspired by the notion of 547:is its matching number (see 231: 9225:(2), Elsevier BV: 512–530, 8996:List of graph theory topics 8851: 8839: 8603: 8571: 8481: 8469: 7782: 7744: 7049: 7023: 6910:generated according to the 6904:quasi-random graph sequence 6898:quasi-random graph sequence 6801: 6459: 6200: 6085:2. A lower-case 5424: 5406: 5326: 5106: 5058: 4929: 4278: 4181:-regular. In particular, a 3853: 3585: 3497: 3341:. (Not to be confused with 3330: 3256: 3255:is the minimum degree; see 3092:of a graph is the smallest 2406:then this graph is denoted 1681:to graphs, an element of a 1244: 1158: 874: 730: 669: 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: 8463: 7582:; in the other direction, 7029: 6825: 6391: 5577:1. This is the 5234: 4810:homomorphically equivalent 4226: 3847: 3654:of the corresponding sets. 3597: 3591: 3462: 3448: 3434: 3210:it is an even number. The 3036: 2349:vertices is often denoted 2314:{\displaystyle {\bar {G}}} 2054:of the maximal cliques in 1828: 1668:1. Synonym for 1533: 685:2. Synonym for 29: 9582:Glossaries of mathematics 9525:10.1007/978-3-662-53622-3 9166:10.1007/978-3-662-53622-3 8845: 8480:s have not been assigned 8475: 8035: 7991: 7520:of its adjacency matrix. 7374:, the number of vertices. 7269: 7105:reconstruction conjecture 7093:reconstruction conjecture 7066: 6625:perfectly orderable graph 6595: 6473: 6352: 6314: 5942:Robertson–Seymour theorem 5924:has a subgraph that is a 5908:all have small diameter. 5892:and contracting edges in 5493: 4855: 4213:-factors. For instance a 3835: 3483: 3476: 3023:reconstruction conjecture 2915: 2909: 2272:An undirected graph is a 2125: 1669: 1597: 1594:reconstruction conjecture 1324: 1040:, but sometimes includes 771: 760: 736: 712: 698: 53: 9397:Harris, John M. (2000), 9191:J. Combin. Theory Ser. B 8868:is a graph all of whose 8778:is a finite or infinite 8721:is used in notation for 8506:complete bipartite graph 8142:, the bags that contain 7959:Topological graph theory 7908:complete bipartite graph 7679:of directed graphs, see 6644:4. A perfect 6360:2. A type of 6257: 5862:max-flow min-cut theorem 5849: 4623:-free. For instance the 4303:is said to be forbidden. 3144:; the minimum degree of 2960:-cycle is a triangle. A 2553:-vertex-connected graphs 2517:A graph that contains a 2362:complete bipartite graph 1017:complete bipartite graph 391:, there is an edge from 38:glossary of graph theory 9307:Graph Classes: A Survey 9001:Gallery of named graphs 8644:, sometimes denoted by 8533:{\displaystyle K_{3,3}} 8040:without repeated edges. 7935:{\displaystyle K_{3,3}} 6707:is a graph that has an 6441:transitive orientations 6276:is a special case of a 6267:strongly chordal graphs 5028:maximum independent set 4804:homomorphic equivalence 3882:, sometimes denoted by 2479:triconnected components 1895:-choosable if it has a 1802:chordal bipartite graph 1656:such that if rooted at 601:{\displaystyle x\leq y} 32:Gallery of named graphs 18:Subgraph (graph theory) 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 6994: 6357:, the number of edges. 6014:(closed under minors). 4773:(closed under minors). 4741:directed acyclic graph 4261:For a set of vertices 3007:directed acyclic graph 2564:-edge-connected graphs 2475:biconnected components 2315: 1927:of chords of a circle. 1795:strongly chordal graph 1652:of a tree is a vertex 1476:2-edge-connected graph 1222: 1195: 1055:biconnected components 1033:Usually a synonym for 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) 8511: 8202:, or the order of a 8066:comparability graphs 8058:transitive reduction 7972:totally disconnected 7913: 7437:symmetric difference 7350:The size of a graph 7028:to another within a 6971: 6838:indifference graphs. 6786:degree distributions 6775:Power graph analysis 6554:is the pathwidth of 6433:acyclic orientations 6381:topological ordering 5774:maximal planar graph 4625:triangle-free graphs 3596:, represented as an 3064:branch-decomposition 2894:symmetric difference 2497:of a directed graph 2296: 1405:branch-decomposition 1360:branch-decomposition 1354:branch-decomposition 1319:1. In a 1205: 1178: 885:whose removal would 586: 564:symmetric difference 415: 411:towards a vertex of 395: 363: 343: 339:of a directed graph 323: 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: 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: 9512: 9511: 9507: 9493: 9472: 9471: 9467: 9422: 9421: 9417: 9411: 9396: 9395: 9391: 9377: 9376: 9369: 9354: 9333: 9332: 9328: 9322: 9300: 9299: 9295: 9281: 9280: 9276: 9242: 9241: 9237: 9216: 9215: 9211: 9188: 9187: 9183: 9176: 9155: 9154: 9150: 9142: 9138: 9109: 9108: 9104: 9090:Stein, Clifford 9076: 9075: 9056: 9028: 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: 8514: 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: 7916: 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: 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: 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: 1208: 1203: 1202: 1201:for each block 1181: 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: 584: 583: 579: 571: 558: 537: 520: 516: 512: 499: 491: 487: 483: 479: 471: 448: 436: 413: 412: 393: 392: 361: 360: 341: 340: 321: 320: 316: 311: 294: 283: 272: 261: 249: 241: 237: 225: 222: 217: 212: 211: 210: 209: 65: 62: 34: 28: 23: 22: 15: 12: 11: 5: 9595: 9593: 9585: 9584: 9579: 9569: 9568: 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: 61: 60: 58: 26: 24: 14: 13: 10: 9: 6: 4: 3: 2: 9594: 9583: 9580: 9578: 9575: 9574: 9572: 9553: 9549: 9543: 9540: 9536: 9530: 9526: 9522: 9518: 9517: 9509: 9506: 9502: 9498: 9494: 9488: 9484: 9480: 9476: 9469: 9466: 9462: 9458: 9454: 9450: 9446: 9445:10.1038/30918 9442: 9438: 9434: 9430: 9426: 9419: 9416: 9412: 9406: 9402: 9401: 9393: 9390: 9386: 9382: 9381: 9374: 9372: 9368: 9363: 9359: 9355: 9349: 9345: 9341: 9337: 9330: 9327: 9323: 9317: 9313: 9309: 9308: 9303: 9297: 9294: 9290: 9286: 9285: 9278: 9275: 9269: 9264: 9259: 9254: 9250: 9246: 9239: 9236: 9232: 9228: 9224: 9220: 9213: 9210: 9205: 9200: 9196: 9192: 9185: 9182: 9177: 9171: 9167: 9163: 9159: 9152: 9149: 9145: 9140: 9137: 9131: 9126: 9122: 9118: 9117: 9112: 9106: 9103: 9097: 9096: 9091: 9087: 9083: 9079: 9073: 9071: 9069: 9067: 9065: 9063: 9061: 9059: 9055: 9049: 9044: 9040: 9036: 9032: 9025: 9022: 9016: 9012: 9009: 9007: 9004: 9002: 8999: 8997: 8994: 8993: 8989: 8983: 8978: 8973: 8968: 8964: 8959: 8956: 8952: 8949: 8946: 8940: 8934: 8928: 8922: 8916: 8913: 8907: 8902: 8899: 8895: 8891: 8886: 8883: 8879: 8874: 8871: 8867: 8863: 8858: 8855: 8849: 8843: 8837: 8831: 8826: 8823: 8818: 8815: 8809: 8804: 8801: 8797: 8793: 8789: 8785: 8781: 8777: 8773: 8768: 8761: 8756: 8753: 8749: 8746: 8742: 8740: 8736: 8731: 8728: 8724: 8716: 8709: 8704: 8699: 8694: 8691: 8687: 8684: 8680: 8678: 8674: 8669: 8666: 8662: 8657: 8652: 8648: 8639: 8634: 8631: 8625: 8619: 8613: 8607: 8601: 8596: 8591: 8588: 8584: 8579: 8576: 8575: 8568: 8563: 8560: 8556: 8553: 8549: 8544: 8525: 8522: 8519: 8515: 8507: 8503: 8502:utility graph 8499: 8496:utility graph 8494: 8491: 8485: 8479: 8473: 8467: 8461: 8456: 8453: 8449: 8445: 8442: 8438: 8434: 8430: 8427: 8423: 8418: 8395: 8390: 8387: 8383: 8379: 8375: 8371: 8366: 8363: 8358: 8353: 8338: 8333: 8329: 8325: 8320: 8316: 8301: 8297: 8292: 8288: 8283: 8274:Two vertices 8273: 8268: 8265: 8261: 8258: 8254: 8251: 8247: 8245: 8241: 8236: 8233: 8229: 8224: 8221: 8217: 8212: 8205: 8197: 8189: 8177: 8173: 8168: 8129: 8125: 8120: 8107: 8101: 8094: 8091: 8087: 8082: 8079: 8075: 8070: 8067: 8063: 8059: 8055: 8051: 8047: 8042: 8039: 8033: 8028: 8025: 8021: 8016: 8013: 8009: 8004: 8001: 7995: 7989: 7984: 7981: 7975: 7970: 7967: 7963: 7960: 7956: 7953: 7949: 7944: 7927: 7924: 7921: 7917: 7909: 7905: 7904:Thomsen graph 7901: 7898:Thomsen graph 7896: 7893: 7892:Lovász number 7889: 7885: 7881: 7878: 7873: 7868: 7847: 7842: 7840:as its sinks. 7800: 7795: 7792: 7790:directed path 7786: 7780: 7775: 7772: 7767: 7756: 7751: 7748: 7742: 7737: 7734: 7730: 7727: 7723: 7720: 7716: 7713: 7707: 7703: 7700: 7694: 7690: 7684: 7678: 7674: 7669: 7666: 7662: 7657: 7652: 7645: 7640: 7635: 7631: 7626: 7623: 7617: 7612: 7609: 7608:lattice graph 7605: 7602: 7598: 7595: 7590: 7580: 7576: 7568: 7563: 7560: 7556: 7553: 7548: 7544: 7541: 7537: 7532: 7529: 7523: 7519: 7515: 7510: 7505: 7502: 7498: 7493: 7490: 7486: 7482: 7478: 7473: 7470: 7469:tree spanners 7466: 7462: 7457: 7454: 7450: 7446: 7442: 7438: 7434: 7430: 7429:vector spaces 7426: 7422: 7417: 7414: 7409: 7406: 7402: 7397: 7394: 7390: 7385: 7381: 7376: 7373: 7363: 7359: 7349: 7344: 7341: 7336: 7333: 7329: 7325: 7320: 7309: 7304: 7301: 7295: 7290: 7287: 7281: 7276: 7273: 7267: 7262: 7258: 7254: 7249: 7246: 7240: 7235: 7232: 7226: 7221: 7216: 7195: 7191: 7188: 7187:rooted graphs 7184: 7179: 7176: 7170: 7165: 7162: 7157: 7146: 7145:regular graph 7134: 7129: 7126: 7121: 7114: 7106: 7102: 7097: 7094: 7090: 7085: 7081: 7075: 7070: 7063: 7057: 7053: 7047: 7041: 7036: 7033: 7027: 7021: 7018: 7014: 7011: 7007: 7002: 6985: 6982: 6979: 6974: 6962: 6958: 6953: 6950: 6944: 6939: 6934: 6929: 6925: 6921: 6916: 6913: 6909: 6908:random graphs 6905: 6901: 6896: 6893: 6889: 6885: 6880: 6875: 6870: 6865: 6862: 6858: 6853: 6849: 6845: 6840: 6836: 6832: 6829: 6823: 6819: 6814: 6811: 6809:directed path 6805: 6799: 6794: 6791: 6787: 6783: 6779: 6776: 6772: 6769: 6756: 6746: 6742: 6738: 6733: 6730: 6726: 6721: 6710: 6706: 6702: 6697: 6694: 6690: 6687: 6683: 6680: 6676: 6671: 6668: 6662: 6659: 6655: 6650: 6647: 6643: 6640: 6634: 6630: 6626: 6622: 6619: 6615: 6611: 6610:perfect graph 6607: 6602: 6599: 6593: 6588: 6569: 6565: 6560: 6544: 6540: 6535: 6532: 6528: 6527:induced paths 6524: 6520: 6515: 6504: 6499: 6494: 6489: 6485: 6480: 6477: 6471: 6466: 6463: 6457: 6452: 6449: 6445: 6442: 6438: 6434: 6430: 6426: 6422: 6418: 6414: 6409: 6404: 6401: 6395: 6389: 6386: 6382: 6378: 6375: 6369: 6363: 6359: 6356: 6344: 6340: 6330: 6321: 6318: 6312: 6309: 6307:neighbourhood 6303: 6298: 6293: 6285: 6279: 6275: 6271: 6268: 6264: 6261: 6255: 6252: 6248: 6245: 6241: 6236: 6231: 6226: 6220: 6215: 6212: 6207: 6204: 6198: 6193: 6190: 6185: 6181: 6174: 6170: 6163: 6159: 6152: 6147: 6143: 6118: 6114: 6111:neighbourhood 6109: 6104: 6101: 6096: 6091: 6084: 6081: 6079:neighbourhood 6075: 6072: 6068: 6063: 6058: 6053: 6049: 6044: 6041: 6037: 6032: 6029: 6025: 6021: 6016: 6013: 6009: 5995: 5990: 5987: 5983: 5980: 5976: 5973: 5972:Modular graph 5969: 5964: 5961: 5957: 5952: 5949: 5943: 5932:. A graph is 5927: 5915: 5899: 5898:shallow minor 5879: 5871: 5866: 5863: 5859: 5853: 5847: 5844: 5840: 5837: 5833: 5828: 5825: 5824:Meyniel graph 5821: 5818: 5813: 5810: 5806: 5803: 5799: 5794: 5791: 5783: 5778: 5775: 5770: 5767: 5763: 5751: 5746: 5743: 5733: 5729: 5724: 5719: 5715: 5711: 5706: 5703: 5697: 5694:magnification 5692: 5687: 5678: 5674: 5669: 5666: 5662: 5657: 5654: 5653:List coloring 5650: 5647: 5643: 5638: 5635: 5629: 5624: 5607: 5603: 5599: 5595: 5590: 5587: 5584: 5580: 5576: 5571: 5568: 5564: 5560: 5559:shortest path 5555: 5550: 5547: 5543: 5536: 5531: 5528: 5524: 5521: 5517: 5513: 5509: 5505: 5500: 5497: 5487: 5481: 5477: 5473: 5470: 5466: 5461: 5456: 5452: 5448: 5442: 5437: 5434: 5428: 5422: 5417: 5410: 5408:clique number 5400: 5394: 5390: 5386: 5383: 5379: 5376: 5370: 5367: 5363: 5358: 5353: 5349: 5345: 5340: 5335: 5330: 5324: 5319: 5316: 5310: 5307:isoperimetric 5305: 5302: 5298: 5293: 5290: 5284: 5279: 5276: 5271: 5266: 5262: 5254: 5250: 5244: 5238: 5232: 5227: 5224: 5219:A synonym of 5218: 5213: 5210: 5204: 5193: 5190: 5186: 5182: 5178: 5173: 5162: 5158: 5157:clique graphs 5154: 5150: 5146: 5145:circle graphs 5142: 5137: 5133: 5130: 5125: 5122: 5118: 5113: 5110: 5104: 5099: 5096: 5090: 5085: 5082: 5078: 5077:induced paths 5074: 5070: 5065: 5062: 5056: 5052: 5047: 5044: 5040: 5036: 5032: 5029: 5023: 5019: 5015: 5011: 5007: 5002: 4999: 4997:comparability 4993: 4989: 4984: 4981: 4976: 4957: 4953: 4948: 4945: 4941: 4936: 4933: 4927: 4922: 4917: 4912: 4906: 4901: 4896: 4893: 4889: 4884: 4881: 4877: 4873: 4868: 4865: 4859: 4853: 4848: 4845: 4839: 4834: 4831: 4827: 4823: 4819: 4814: 4811: 4807: 4802: 4799: 4795: 4790: 4785: 4782: 4779: 4775: 4772: 4768: 4754: 4750: 4745: 4742: 4738: 4734: 4731: 4727: 4723: 4720: 4716: 4711: 4696: 4688: 4683: 4679: 4675: 4670: 4667: 4663: 4660: 4656: 4654: 4653:Hugo Hadwiger 4650: 4645: 4630: 4626: 4602: 4598: 4594: 4571: 4567: 4563: 4556: 4553: 4549: 4544: 4539: 4535: 4534:Grundy number 4531: 4528:Grundy number 4526: 4523: 4519: 4516: 4512: 4510: 4506: 4501: 4498: 4494: 4490: 4485: 4482: 4478: 4474: 4470: 4465: 4462: 4458: 4453: 4450: 4449:random graphs 4446: 4441: 4438: 4437:shortest path 4434: 4429: 4426: 4420: 4415: 4412: 4409: 4405: 4400: 4395: 4391: 4386: 4383: 4377: 4372: 4369: 4365: 4362: 4358: 4356: 4355:Robert Frucht 4352: 4347: 4344: 4340: 4335: 4332: 4314: 4313:forcing graph 4310: 4307:forcing graph 4305: 4294: 4290: 4285: 4282: 4276: 4260: 4255: 4251: 4247: 4242: 4238: 4233: 4230: 4224: 4219: 4204: 4200: 4197:factorization 4195: 4188: 4172: 4167: 4164: 4160: 4156: 4151: 4146: 4129: 4125: 4118: 4106: 4083: 4060: 4037: 4033: 4028: 4025: 4021: 4016: 4013: 4008: 4004: 4003:Eulerian path 4000: 3995: 3991: 3988: 3983: 3980: 3976: 3972: 3967: 3964: 3960: 3955: 3952: 3948: 3945: 3941: 3936: 3933: 3929: 3925: 3921: 3916: 3912: 3907: 3904: 3900: 3895: 3890: 3886: 3877: 3872: 3869: 3863: 3857: 3851: 3845: 3839: 3833: 3828: 3813: 3808: 3803: 3800: 3795: 3791: 3787: 3782: 3779: 3774: 3771: 3759: 3755: 3751: 3748: 3744: 3739: 3726: 3722: 3717: 3713: 3709: 3704: 3701: 3697: 3692: 3689: 3685: 3680: 3677: 3674:with maximum 3673: 3669: 3665: 3661: 3656: 3653: 3649: 3646: 3641: 3638: 3632: 3627: 3624: 3618: 3613: 3610: 3608:directed path 3604: 3601: 3595: 3589: 3584: 3578: 3574: 3569: 3565: 3560: 3553: 3547: 3542: 3535: 3529: 3524: 3517: 3511: 3505: 3501: 3495: 3489: 3487: 3480: 3474: 3471:directed path 3469: 3466: 3460: 3457:directed line 3455: 3452: 3446: 3443:directed edge 3441: 3438: 3432: 3427: 3424: 3420: 3416: 3411: 3408: 3403: 3400: 3395: 3392: 3390:directed path 3386: 3381: 3378: 3374: 3369: 3366: 3362: 3358: 3354: 3349: 3346: 3340: 3334: 3329: 3324: 3321: 3320:diamond graph 3317: 3312: 3309: 3308:shortest path 3305: 3300: 3297: 3293: 3288: 3283: 3280: 3276: 3272: 3268: 3263: 3260: 3252: 3248: 3237: 3232: 3229: 3224: 3221: 3217: 3213: 3209: 3203: 3195: 3191: 3184: 3179: 3175: 3162: 3156: 3152: 3141: 3131: 3127: 3122: 3091: 3079: 3074: 3069: 3066: 3060: 3054: 3048: 3045:decomposition 3043: 3040: 3034: 3028: 3024: 3016: 3011: 3008: 3004: 2999: 2994: 2989: 2985: 2981: 2976: 2972: 2963: 2955: 2939: 2935: 2931: 2927: 2923: 2919: 2913: 2907: 2903: 2898: 2895: 2891: 2885: 2881: 2877: 2873: 2868: 2865: 2859: 2854: 2850: 2846: 2841: 2836: 2833: 2829: 2822: 2818: 2814: 2810: 2802: 2799: 2795: 2792: 2788: 2784: 2781: 2777: 2774: 2770: 2767: 2763: 2758: 2753: 2750: 2746: 2742: 2737: 2734: 2730: 2726: 2722: 2717: 2714: 2710: 2707: 2706:spanning tree 2703: 2698: 2695: 2691: 2664: 2660: 2653: 2645: 2641: 2638: 2624: 2617: 2612: 2609: 2603: 2598: 2594: 2591: 2586: 2583: 2577: 2572: 2565: 2554: 2546: 2542: 2537: 2534: 2528: 2523: 2520: 2516: 2511: 2496: 2492: 2487: 2484: 2480: 2476: 2472: 2468: 2463: 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: 2335: 2302: 2292: 2288: 2283: 2279: 2275: 2271: 2268:comparability 2266: 2263: 2259: 2256: 2252: 2248: 2244: 2243:list coloring 2240: 2239:edge coloring 2236: 2217: 2213: 2209: 2204: 2200: 2196: 2191: 2186: 2183: 2179: 2175: 2171: 2166: 2163: 2159: 2156: 2150: 2145: 2141: 2138: 2132: 2129: 2123: 2120: 2118:neighbourhood 2114: 2109: 2106: 2089: 2085: 2080: 2077: 2071: 2066: 2063: 2057: 2053: 2049: 2045: 2035: 2031: 2027: 2026:clique number 2014: 2010: 2005: 2002: 1994: 1989: 1985: 1980: 1977: 1973: 1970: 1966: 1962: 1957: 1954: 1953:circumference 1950: 1947:circumference 1945: 1942: 1938: 1934: 1929: 1926: 1922: 1918: 1913: 1898: 1897:list coloring 1890: 1885: 1880: 1873: 1872:edge coloring 1865: 1859: 1855: 1844: 1840: 1836: 1832: 1826: 1821: 1818: 1814: 1810: 1806: 1803: 1799: 1796: 1792: 1789: 1788:chordal graph 1785: 1782: 1777: 1772: 1761: 1756: 1753: 1747: 1739: 1735: 1724: 1720: 1716: 1713: 1709: 1706: 1701: 1698: 1692: 1687: 1684: 1683:chain complex 1680: 1676: 1673: 1667: 1662: 1651: 1647: 1642: 1639: 1633: 1629: 1624: 1621: 1617: 1612: 1609: 1606:carving width 1604: 1601: 1595: 1591: 1586: 1583: 1578: 1574: 1569: 1564: 1561: 1557: 1552: 1549: 1545: 1540: 1537: 1531: 1521: 1517: 1513: 1510: 1506: 1501: 1496: 1492: 1489: 1485: 1480: 1477: 1473: 1469: 1464: 1461: 1460:bridged graph 1457: 1454: 1450: 1446: 1442: 1438: 1434: 1430: 1426: 1422: 1419: 1415: 1410: 1407: 1401: 1396: 1361: 1357: 1352: 1349: 1344: 1340: 1336: 1331: 1328: 1322: 1318: 1313: 1309: 1305: 1298: 1289: 1284: 1279: 1275: 1270: 1267: 1262: 1256: 1251: 1248: 1242: 1238: 1213: 1209: 1186: 1182: 1165: 1162: 1144: 1136: 1131: 1128: 1122: 1118: 1113: 1100: 1096: 1092: 1088: 1082: 1078: 1073: 1070: 1065: 1062: 1056: 1052: 1043: 1039: 1032: 1027: 1024: 1018: 1014: 1009: 994: 990: 985: 982: 977: 974: 968: 963: 958: 953: 949: 944: 941: 935: 930: 919: 911: 904: 899: 896: 890: 884: 878: 872: 869: 865: 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: 719: 716: 710: 705: 702: 696: 691: 688: 684: 673: 667: 663: 658: 655: 652:anti-triangle 650: 647: 643: 638: 635: 631: 595: 592: 589: 577: 573: 568: 565: 560: 555: 552: 544: 540: 535: 527: 523: 514: 511: 507: 504: 501: 496: 477: 473: 468: 465: 461: 458: 454: 450: 445: 442: 438: 433: 418: 398: 378: 372: 369: 366: 346: 326: 318: 313: 308: 301: 297: 290: 286: 279: 275: 268: 264: 259: 255: 251: 246: 235: 228: 224: 219: 214: 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.

Index