This page gathers the 196 dictionary entries belonging to the domain “Graph theory”, as labelled by Wiktionary. Each word leads to its full entry: definitions, etymology, pronunciation, examples. Page 2 of 2: from “hole” to “Yao graph”.
- hole noun A chordless cycle in a graph.
- hypertree noun A form of hypergraph based on trees.
- hypohamiltonian adj Of a graph, not containing a Hamiltonian cycle but such that the removal of any single vertex produces a Hamiltonian graph.
- incidence noun The relation between an edge of a graph and one of the vertices it connects.
- independence number noun The number of vertices in a maximum independent set of a given graph, often denoted as α=α(G).
- independent set noun a set of vertices of a graph, such that no pair of them are adjacent to each other; in other words, a set of vertices which are all…
- induced subgraph noun A graph formed from a subset of the vertices of another graph and all of the edges, connecting pairs of vertices in that subset.
- isthmus noun An edge in a graph whose deletion increases the number of connected components of the graph.
- iterative deepening search noun A type of depth-first search in which each row of the tree is searched incrementally, simulating a breadth-first search with less memory…
- king noun A vertex in a directed graph which can reach every other vertex via a path with a length of at most 2.
- Kneser graph noun A graph K(n, k) (alternatively KG_(n,k)), whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices…
- laceable adj Of a bipartite graph: having a possible Hamiltonian path between any two vertices from different partite sets.
- Laplacian matrix noun A square n×n matrix which describes an undirected graph of n vertices by letting rows and columns correspond to vertices, letting its…
- line noun An edge of a graph.
- line graph noun A graph L(G) which is derived from a given non-oriented graph G such that the vertices of L(G) represent edges of G and so that a clique in…
- loop noun An edge that begins and ends on the same vertex.
- marking noun Any configuration of a Petri net with a number of marks or tokens distributed across it.
- matching noun A set of independent edges in a given graph, i.e. a set of edges which do not intersect, such that pairs of vertices are "matched" to each…
- maximum cut noun A cut whose size is at least the size of any other cut; a partition of the graph's vertices into two complementary sets S and T, such that…
- medial graph noun A graph derived from a given plane graph such that this derived graph has a vertex corresponding to each edge of the given graph, and such…
- minor adj Including both directed and undirected edges.
- Moore graph noun A regular graph of degree d and diameter k whose number of vertices equals the upper bound 1+d∑ᵢ₌₀ᵏ⁻¹(d-1)ⁱ.
- multidigraph noun A directed graph that is permitted to have multiple arcs connecting the same source and target nodes.
- multiflow noun A flow function that operates on the set of edges (ordered pairs of vertices) on the intersection of two related directed graphs.
- multigraph noun A set V (whose elements are called vertices or nodes), taken together with a multiset E, each of whose elements (called an edge or line) is…
- multihypergraph noun A set V (whose elements are called vertices or nodes), taken together with a multiset E, each of whose elements (called an edge or…
- Mycielskian noun A larger graph formed from a given undirected graph by a particular construction that preserves the property of being triangle-free but…
- neighborhood noun The set of all the vertices adjacent to a given vertex.
- node noun A vertex or a leaf in a graph of a network, or other element in a data structure.
- noneven adj Of a digraph, having no cycles of even weight
- open adj Having different first and last vertices.
- order noun The number of vertices in the graph (i.e. the set-theoretic order of the set of vertices of the graph).
- outedge noun An outgoing edge in a digraph, i.e. one that leaves a particular node.
- outerplanar adj Having a planar embedding such that the vertices lie on a circle and the edges lie inside that circle.
- path noun A sequence of vertices from one vertex to another using the arcs (edges). A path does not visit the same vertex more than once (unless it…
- path length noun The number of edges traversed in a given path in a graph.
- pebble verb To place a pebble at (a vertex of a graph) according to certain rules, in a pebble game.
- pebbler noun One who or that which places pebbles at the vertex of a graph, according to certain rules; see pebble game.
- Petersen graph noun An undirected graph with 10 vertices and 15 edges, serving as a simple example and counterexample for many problems in graph theory.
- planar adj Able to be embedded in the plane with no edges intersecting.
- planar graph noun A graph which can be embedded in a plane in such a way that its edges only intersect at vertices, i.e., they do not cross each other.
- pluperfect adj Being or relating to a certain type of graph that complies with a theorem ("pluperfect graph theorem") discovered by D. R. Fulkerson in…
- polygon-circle graph noun A graph (set of connected points) in which each vertex corresponds to a convex polygon circumscribed in a common circle, and in which…
- polytree noun a graph with at most one undirected path between any two vertices. In other words, a directed acyclic graph (DAG) for which there are no…
- postdominate verb A node z postdominates a node n if all paths to the exit node of the graph starting at n must go through z
- preferential attachment noun A positive feedback cycle where the more connected nodes in a graph are more likely to receive new links.
- pseudodigraph noun A graph that resembles a directed graph but violates one of the normal rules, as for example by including a directed loop.
- pseudograph noun A graph that may contain loops as well as multiple edges between vertices
- quadrivalent adj Having all of its vertices of degree four.
- quasi-transitive adj Such that its vertex set can be partitioned into finitely many sets, so that there exists an automorphism mapping a vertex to another…
- radius noun The minimum eccentricity of any vertex, for a given graph.
- Ramanujan graph noun A regular graph whose spectral gap is almost as large as possible, making it an excellent spectral expander. Such graphs are relevant to…
- regular map noun A symmetric tessellation of a closed surface; a decomposition of a two-dimensional manifold into topological disks such that every flag…
- reverse noun Synonym of transpose.
- root noun The single node of a tree that has no parent.
- rooted adj Having a root.
- rose noun A graph with only one vertex.
- s-t cut noun A cut that requires the source and the sink to be in different subsets, and its cut-set only consisting of edges going from the source's…
- semi-complete adj of or pertaining to a graph in which, for any two vertices u, v in the graph, there is another vertex w which is adjacent to both u and v…
- semi-transitive adj Such that there exists a finite vertex set so that for any vertex there exists another vertex in that finite set and an injective…
- semiconnected adj Containing a directed path from u to v or a directed path from v to u for every pair of vertices u, v.
- sink noun A destination vertex in a transportation network.
- size noun The number of edges in a graph.
- source noun A node in a directed graph whose edges all go out from it; one with no entering edges.
- spanner noun A (usually sparse) graph whose shortest path distances approximate those in a dense graph or other metric space.
- splicer noun A union of uniform spanning trees.
- squaregraph noun a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with…
- Steiner point noun An extra vertex that is not a member of the input.
- strength noun The minimum ratio of the number of edges removed from a given graph to components created, over all possible removals.
- strongly connected adj Of a directed graph, such that for every pair of vertices u and v there is a path from u to v and a path from v to u.
- subpath noun A path making up part of a larger path (the superpath).
- superconnected adj Whose every minimum vertex cut leads to isolated vertices.
- thickness noun The minimum number of planar subgraphs which a given graph can decompose into.
- thrackle noun An embedding of a graph in the plane, such that each edge is a Jordan arc and every pair of edges meet once.
- tie noun A connection between two vertices.
- topological sort noun An ordering of the vertices of a directed graph such that if an edge goes from vertex u to vertex v then u precedes v in the ordering.
- tour noun A closed trail.
- tournament noun A digraph obtained by assigning a direction to each edge in an undirected complete graph.
- traceable adj Containing a Hamiltonian path.
- trail noun A walk in which all the edges are distinct.
- transitive adj Such that, for any two vertices there exists an automorphism which maps one to the other.
- transpose adj Created by transposing a specified graph.
- tree noun A connected graph with no cycles or, if the graph is finite, equivalently a connected graph with n vertices and n−1 edges.
- treeness noun The condition of being a tree; acyclicity and connectedness.
- tricomponent noun A component having three nodes.
- Turán graph noun A complete multipartite graph T(n,r) formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and…
- Tutte matrix noun A matrix used to determine whether all of the edges of a graph can be traversed without visiting a vertex more than once.
- unicycle adj Synonym of unicyclic.
- utility graph noun The graph K_(3,3), which has six vertices in two sets of three and nine edges such that every vertex in one set is connected to each vertex…
- valency noun The number of edges connected to a vertex in a graph.
- vertex noun One of the elements of a graph joined or not by edges to other vertices.
- volume noun The sum of the degrees of a set of vertices.
- walk noun A sequence of alternating vertices and edges, where each edge's endpoints are the preceding and following vertices in the sequence. Compare…
- weighted adj having values assigned to its edges
- windmill graph noun The undirected graph Wd(k,n) constructed for k ≥ 2 and n ≥ 2 by joining n copies of the complete graph Kₖ at a shared universal vertex.
- Yao graph noun A kind of geometric spanner, a weighted undirected graph connecting a set of geometric points with the property that, for every pair of…