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 1 of 2: from “acyclic” to “hereditary”.
- acyclic adj Containing no cycles.
- acyclical adj Synonym of acyclic.
- algebraic graph theory noun The subbranch of graph theory in which algebraic methods are applied to problems about graphs.
- antichain noun A subset, A, of a partially ordered set, (P, ≤), such that no two elements of A are comparable with respect to ≤.
- antidirected adj Having arcs that alternate between forward and backward arcs.
- arborescence noun A directed rooted tree in which all vertices can be reached from the root.
- arc noun A directed edge.
- arrow noun A directed edge.
- bandwidth noun The minimum, over all orderings of vertices of a given graph, of the length of the longest edge.
- Bellman-Ford algorithm noun An algorithm that computes single-source shortest paths in a weighted digraph, capable (unlike the faster Dijkstra's algorithm) of handling…
- betweenness noun A measure of the number of geodesic paths through a node or edge.
- biclique noun A special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.
- bicomponent noun A component having two nodes.
- binding number noun The smallest possible ratio of the number of neighbours of a proper subset of vertices to the size of the subset.
- bipartite adj Having vertices that can be divided into two independent sets (see bigraph)
- block graph noun A type of undirected graph in which every biconnected component (block) is a clique.
- bramble noun A collection of mutually touching connected subgraphs, where two subgraphs touch if they share a vertex or each includes one endpoint of an…
- branch noun A path of vertices of degree 2, ending at vertices whose degree is not 2.
- breadth noun The length of the longest path between two vertices in a graph.
- bridge noun An edge which, if removed, changes a connected graph to one that is not connected.
- bridgeless adj Having no bridges.
- cage noun A regular graph that has as few vertices as possible for its girth.
- card noun A graph formed from a given graph by deleting one vertex.
- caterpillar tree noun A tree consisting of only a path (the spine or stalk of the tree) and vertices directly connected to (i.e. one edge away from) that path; a…
- centroid noun Given a tree of n nodes, either (1) a unique node whose removal would split the tree into subtrees of fewer than n/2 nodes, or (2) either…
- centroidal adj Having a single centroid.
- cherry noun A subtree consisting of a node with exactly two leaves.
- Chinese postman problem noun The problem of finding the shortest closed path or circuit that visits every edge of a (connected) undirected graph.
- chord noun An edge that is not part of a cycle but connects two vertices of the cycle.
- chordal adj For a graph, in which all cycles of four or more vertices have a chord.
- chorded adj Containing a chord.
- chordless adj Lacking chords.
- chromatic adj Relating to colorings of graphs.
- chromatic number noun The smallest number of colours needed to colour a given graph (i.e., to assign a colour to each vertex such that no two vertices connected…
- circuit noun A closed trail.
- circumference noun The length of the longest cycle of a graph.
- claw noun A tree with one internal vertex and three leaves.
- clique noun A subgraph isomorphic to a complete graph.
- clique tree noun A tree-structured graph used to represent the structural relationships between the maximal cliques of an undirected graph, particularly…
- clique width noun A graph parameter that measures the structural complexity of a graph, particularly how simply it can be built using a small set of vertex…
- closed adj Whose first and last vertices are the same, forming a closed loop.
- clustering coefficient noun A quantitative measure of how often the nodes of a graph cluster together, defined as the ratio of the number of links among the nodes to…
- cocoloring noun The assignment of a color to each vertex of a graph such that each color class forms an independent set in the graph or its complement.
- collider noun A node in a causal graph that has at least two incoming edges.
- color verb To assign colors to the vertices of a graph (or the regions of a map) so that no two vertices connected by an edge (regions sharing a…
- coloring noun An assignment of a color to each vertex of a graph, usually such that no two vertices connected by an edge are given the same color.
- complete bipartite graph noun A biclique, a bipartite graph such that every vertex of one set is connected to every vertex of the other.
- component noun A connected subgraph that is not part of any larger connected subgraph.
- condensation noun For a given directed graph G, a directed acyclic graph with one vertex for each strongly connected component of G, and an edge connecting…
- connected adj Having a path, either directed or undirected, connecting every pair of vertices.
- converse noun Synonym of transpose.
- cop number noun For a given undirected graph, the minimum number of cops that suffices to ensure a win (i.e. a capture of the robber) in a certain…
- coreachable adj Mutually reachable, that is, for any two nodes n1 and n2, they are coreachable iff n1 is reachable from n2 and n2 is reachable from n1.
- crossing noun A pair of intersecting edges.
- crown graph noun An undirected graph with 2n vertices in the two sets { u₁, u₂, ..., uₙ } and { v₁, v₂, ..., vₙ } and with an edge from uᵢ to vⱼ whenever i…
- cut noun The partition of a graph’s vertices into two subgroups.
- cutwidth noun The minimum number of edges that cross any cut between lower-numbered and higher-numbered vertices in an optimal linear arrangement of the…
- cycle noun A closed walk or path, with or without repeated vertices allowed.
- cyclomatic adj Used to describe the number of edges that must be removed from a graph to ensure that no graph cycle remains; equal to the number of edges…
- dag noun A directed acyclic graph; an ordered pair (V,E) such that E is a subset of some partial ordering relation on V.
- deck noun The multiset of graphs formed from a single graph by deleting a single vertex in all possible ways.
- dedecoration noun Decimation (the elimination of points from a lattice); the inverse of decoration.
- degree noun The number of edges that a vertex takes part in; a valency.
- demigenus noun The minimal integer n such that the given graph can be drawn without crossing itself on a sphere with n cross-caps.
- dendrimer noun A graph formed of branches from a central core.
- depth-first search noun An algorithm for traversing a tree or graph where one starts at the root and explores as far as possible along each branch before…
- diameter noun The maximum eccentricity over all vertices in a graph.
- dicycle noun directed cycle
- digon noun A pair of parallel undirected edges in a multigraph.
- digraph noun A directed graph.
- directed adj Having the properties of a directed graph.
- directed graph noun A graph in which the edges are ordered pairs, so that, if the edge (a, b) is in the graph, the edge (b, a) need not be in the graph and is…
- dismantlable adj The property of a graph such that its vertices can be listed in an order such that, for every vertex, the vertex is a subdominant vertex…
- disperser noun A particular kind of bipartite graph.
- dominate verb To precede another node of a directed graph in all paths from the start of the graph to the other node.
- dominating set noun A set of vertices of a graph, such that each vertex in that graph is either in that set or adjacent to a vertex in that set.
- dominator noun A node that dominates another.
- dual graph noun A graph derived from some plane graph in such a way that the derived graph has a vertex corresponding to each face of the given graph, an…
- ear noun A path whose endpoints may coincide but in which otherwise there are no repetitions of vertices or edges.
- eccentricity noun The farthest distance from a vertex to any other vertex.
- edge noun A connected pair of vertices in a graph.
- edge contraction noun An operation performed on an edge in a graph which deletes the edge, replaces its endpoints with a single new vertex, and replaces edges…
- Euler genus noun The minimal integer n such that the given graph can be drawn without crossing itself on a sphere with n cross-caps or with n/2 handles.
- Euler line noun An Eulerian path, a looped path through a graph that passes along every edge exactly once.
- Eulerian adj Having an Eulerian circuit.
- expander noun A kind of sparse graph with strong connectivity properties.
- extractor noun A particular kind of bipartite graph.
- flap noun A connected component of the induced subgraph formed by deleting a set of vertices.
- forest noun A graph with no cycles; i.e., a graph made up of trees.
- four color problem noun The problem of coloring a map with no more than four colors, such that no two adjacent regions have the same color.
- genus noun A natural number representing any of several related measures of the complexity of a given manifold or graph.
- girth noun The length of the shortest cycle in a graph.
- graph noun A set of vertices (or nodes) connected together by edges; (formally) an ordered pair of sets (V,E), where the elements of V are called…
- graph minor noun A graph which can be formed from some specified graph by performing vertex deletions, edge deletions, and edge contractions on the…
- Grötzsch graph noun A triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is a member of an infinite sequence of…
- half-edge noun An edge that is attached to only one node, rather than connecting two of them, or is connected in only one direction
- Hamiltonian adj That visits each vertex exactly once.
- Hamiltonian cycle noun A Hamiltonian path with an additional connection between the first and last vertices visited, forming a cycle.
- haven noun A certain type of function on sets of vertices in an undirected graph, able to be used by an evader to win a pursuit-evasion game on the…
- hereditary adj Of a property of graphs: such that if G has the property, so must every induced subgraph of G.