GTGLOSSARY

Generated from GTGLOSSARY.tex. Hover over dotted glossary terms inside definitions.

The hovercard behavior is provided by glossaryhovercards/glossary-hovercards.js?v=696067a07b40.

Notation

$\mathcal M$: Multiset construction.
$\mathcal M_{\le2}(V)$: Multisets from $V$ of cardinality at most $2$.
incidence: $\iota_G:$$E$$\to$$\mathcal M_{\le2}(V)$.
multiplicity: $m_X(x)$.
$d$: Regular degree parameter.
$\alpha$: Independence number.
$\delta$: Minimum degree.
$\kappa$: Vertex connectivity.
$\lambda$: Nontrivial adjacency eigenvalue in spectral contexts.
$\prime$: Context mark for a derived graph or parameter.
alpha: ≡ $\alpha$.
delta: ≡ $\delta$.
kappa: ≡ $\kappa$.
prime: ≡ $\prime$.
Prime symbol: ≡ $\prime$.
chi: ≡ $\chi$.
chi(G): ≡ chromatic number.
Delta(G): ≡ maximum degree.
G: Ambient graph.
H: Subgraph or pattern graph.
V: Vertex set.
E: Edge set.
K: Complete-graph prefix.
L: Line-graph operator.
W: Walk or vertex subset fixed by context.
$\binom V2$: Two-element subsets of $V$.
$P_n$: Path graph on $n$ vertices.
$\square$: Cartesian graph product.
$\times$: Direct graph product.
$\sqcup$: Disjoint union.
$\setminus$: Set difference.

Canonical Core

Objects

vertex: $v\in $$V$.
edge: $e\in $$E$.
endpoint: Member of $\partial e$.
loop: $\partial e=\{v,v\}$.
multiple edge: Shares $\partial e$.
simple graph: ≡ simple.
multigraph: Repeated endpoint multisets.
pseudograph: Multigraph with loops.
hypergraph: Finite hyperedges.

Directed Objects

directed graph: $($$V$$,$$A$$,$$t$$,$$h$$)$.
arc: $a\in A$.
tail: $t(a)$.
head: $h(a)$.
DAG: Directed graph with no directed cycle.
oriented graph: ≡ oriented.

Incidence

incident: $m_{\partial e}(v)$$>0$.
adjacent: Shared edge or endpoint.
neighbor: Adjacent vertex.
neighborhood: $N_G(v)=\{u:uv\in $$E$$\}$.
degree: $\deg_G(v)=\sum_e $$m_{\partial e}(v)$.
in-degree: Entering arc count.
out-degree: Leaving arc count.

Walks

walk: Incidence-respecting sequence.
trail: Walk with distinct edges.
path: Walk with distinct vertices.
cycle: Closed positive-length path.
acyclic: No cycle.
Eulerian: Uses every edge.
Hamiltonian: Uses every vertex.

Substructure

subgraph: $H$$\le $$G$ by subset incidence.
induced subgraph: $G$$[S]$ keeps exactly edges inside $S$.
spanning subgraph: $V$$($$H$$)=$$V(G)$.

Connectivity

connected: Every vertex pair has a path.
component: Maximal connected subgraph.
strongly connected: Directed paths both ways.
weakly connected: Connected underlying graph.

Trees

tree: Unique path between vertex pairs.
forest: Tree components.
rooted tree: Root paths define parent, child, ancestor, descendant, leaf, depth, height.

Classes and Sets

regular: Constant degree.
complete: $E$$=$$\binom V2$.
bipartite: $V$$=X$$\sqcup$$ Y$ with crossing edges.
non-edge: Element of $\binom V2$$\setminus$$ $$E$.
clique: Induces complete graph.
independent set: Induces edgeless graph.
matching: Disjoint endpoints.

Coloring

coloring: Map from graph objects to colors.
$\chi$: Minimum proper vertex colors.

Geometry

planar: Sphere embedding with intersections only at endpoints.
embedding: Surface drawing.
face: Complement component.
genus: Minimum orientable genus.

Metrics

distance: Minimum path length.
eccentricity: Maximum distance from a vertex.
radius: Minimum eccentricity.
diameter: Maximum eccentricity.
girth: Minimum cycle length.
circumference: Maximum cycle length.

Cuts and Maps

partition: Pairwise disjoint nonempty blocks whose union is the set.
equivalence relation: Reflexive symmetric transitive relation.
cut: Vertex partition plus crossing edges.
edge cut: Edge deletion raises component count.
vertex cut: Vertex deletion raises component count.
bridge: Singleton edge cut.
cut vertex: Singleton vertex cut.
isomorphism: Incidence-preserving bijection.
local isomorphism: Isomorphism on each neighborhood.
automorphism: Self-isomorphism.
homomorphism: Adjacency-preserving map.
quotient: Object induced on equivalence classes.
quotient set: Set of equivalence classes.
quotient object: Quotient with inherited structure.
quotient map: Map sending each element to its equivalence class.
quotient graph: Graph on partition blocks with edge inherited from adjacent original vertices.
covering map: Surjective local isomorphism.
covering graph: Domain of a covering map.
minor: Deletions and contractions.

Constructors

Class Modifiers

critical: Minimal source-extremal member.
maximal: Feasible object with no feasible proper superobject.
minimal: Feasible object with no feasible proper subobject.
maximum: Feasible object of largest cardinality.

Operations

dual: Planar face-edge dual.
orientation: Edge direction choice.
converse: Reversed arcs.
transpose: Reversed arcs.
join: Disjoint union plus cross edges.
closure: Least supergraph containing $G$ with the named property.
decomposition: Indexed pieces whose union recovers the object.

Exact Source-Term Entries

Core Variants

graph: $G$$=($$V$$,$$E$$,\iota)$.
vertex set: $V$$($$G$$)$.
edge set: $E$$($$G$$)$.
size: $|$$E(G)$$|$.
size of a graph: ≡ size.
order: $|$$V(G)$$|$.
simple: Injective $\iota:$$E$$\to$$\binom V2$.
multiple: ≡ multiple edge.
multiple adjacency: Distinct edges sharing endpoints.
directed: Uses arcs with tail and head.
undirected: Uses endpoint sets without orientation.
mixed: Edges and arcs.
unweighted graph: ≡ unweighted.
unweighted: Graph with unit edge weights.
network: Graph with extra weights, capacities, or flow data.
connect: Add or witness a path between vertices.
disconnect: Delete vertices or edges so connectivity fails.
disjoint: Having empty intersection.
finite: Having finite vertex and edge sets.
infinite: Not finite.
trivial: One vertex and no edge.
anti-triangle: Independent set of size $3$.
triangle: Cycle of length $3$.
digon: Directed cycle of length $2$.
hyperedge: Edge incident with any finite vertex subset.
hyperarc: Directed hyperedge with tail set and head set.
quiver: ≡ directed graph.

Classes

complete graph: $E$$=$$\binom V2$.
Complete graphs: ≡ complete graph.
empty graph: $E$$=\emptyset$.
null graph: ≡ empty graph.
edgeless graph: $E$$=\emptyset$.
totally disconnected graph: ≡ empty graph.
totally disconnected: ≡ empty graph.
bipartite graph: ≡ bipartite.
complete bipartite graph: All crossings.
Complete bipartite graphs: ≡ complete bipartite graph.
complete multipartite graph: Independent parts, complete cross edges.
multipartite graph: Vertex partition with no edge inside one part.
k-partite graph: $k$ parts.
tripartite graph: $3$-partite graph.
balanced k-partite graph: $k$ parts, sizes differ by at most $1$.
equipartite graph: Multipartite graph with equal part sizes.
connected graph: ≡ connected.
connected component: ≡ component.
disconnected graph: ≡ disconnected.
disconnected: Graph with at least two components.
biconnected: Connected after deleting any one vertex.
biconnected component: Maximal biconnected subgraph.
bridgeless: Has no bridge.
acyclic graph: Graph with no cycle.
directed acyclic graph: ≡ DAG.
D-separation: Separation in a directed acyclic graphical model.
regular graph: ≡ regular.
k-regular graph: Regular with degree $k$.
cubic graph: ≡ cubic.
cubic: $3$-regular graph.
biregular graph: ≡ biregular.
biregular: Bipartite with constant degree on each part.
semiregular: ≡ biregular.
planar graph: ≡ planar.
plane graph: Planar with a fixed embedding.
outerplanar graph: ≡ outerplanar.
outerplane graph: Outerplanar with a fixed embedding.
outerplanar: Planar with all vertices on the outer face.
outer: On the unbounded face of a plane graph.
perfect graph: ≡ perfect.
split graph: ≡ split.
chordal graph: ≡ chordal.
chordal: Every cycle of length at least $4$ has a chord.
cograph: Graph generated from one vertex by complement and disjoint union.
threshold graph: Graph generated by adding isolated or universal vertices.
interval graph: Intersection graph of intervals.
indifference: Unit interval graph.
comparability: Graph whose edges admit a transitive orientation.
incomparability: Complement of a comparability graph.
functional graph: Directed graph of a function $V$$\to $$V$.
pseudoforest: Each component has at most one cycle.
unicyclic graph: Connected with exactly one cycle.
snark: Bridgeless cubic with chromatic index $4$.
Snarks: ≡ snark.
tournament: Orientation of a complete graph.
regular tournament: Tournament with $\deg^-=\deg^+$ at every vertex.
traceable graph: ≡ traceable.
traceable: Graph containing a Hamiltonian path.
Hamiltonian graph: Graph containing a Hamiltonian cycle.
Hamiltonian connected graph: Every vertex pair has a Hamiltonian path.
Eulerian digraph: Closed directed trail uses every arc.
strongly regular graph: Regular with common-neighbor counts set by adjacency.
Strongly regular graphs: ≡ strongly regular graph.
ultrahomogeneous graph: Partial isomorphisms extend to automorphisms.
universal graph: Contains every graph in its class.
quasi-line graph: Every neighborhood is two cliques.
pancyclic graph: Graph with cycles of every length from $3$ to $|$$V$$|$.
sparse: Has $O(|$$V$$|)$ or otherwise few edges in the stated class.
Dense graph: Graph with edge count comparable to $|$$V$$|^2$.
Sparse graph: ≡ sparse.
small-world network: Short distances plus high clustering.
Scale-free network: Network with heavy-tailed degree distribution.

Families And Notation

C_3: Cycle graph on $3$ vertices.
C_4: Cycle graph on $4$ vertices.
C_5: Cycle graph on $5$ vertices.
C_6: Cycle graph on $6$ vertices.
K_1: Complete graph on $1$ vertex.
K_2: Complete graph on $2$ vertices.
K_3: Complete graph on $3$ vertices.
K_4: Complete graph on $4$ vertices.
K_5: Complete graph on $5$ vertices.
K_6: Complete graph on $6$ vertices.
K_7: Complete graph on $7$ vertices.
K_8: Complete graph on $8$ vertices.
K_n: Complete graph on $n$ vertices.
K_mn: Complete bipartite graph with part sizes $m,n$.
K_{2,3}: Complete bipartite graph with part sizes $2,3$.
K_{2,4}: Complete bipartite graph with part sizes $2,4$.
K_{3,3}: Complete bipartite graph with part sizes $3,3$.
K_{3,4}: Complete bipartite graph with part sizes $3,4$.
utility graph: ≡ $K_{3,3}$.
cycle graph: Graph isomorphic to a cycle.
path graph: Graph isomorphic to a path.
star: Complete bipartite graph $K_{1,n}$.
Star (graph theory): ≡ star.
wheel graph: ≡ wheel.
Wheel graphs: ≡ wheel.
fan graph: Path plus one universal hub.
friendship graph: Edge-disjoint triangles sharing one common vertex.
Friendship graphs: ≡ friendship graph.
windmill graph: ≡ windmill.
ladder graph: Cartesian product $P_n$$\square$$ $$K_2$.
hypercube: Graph on binary strings adjacent at Hamming distance $1$.
Hypercube graph: ≡ hypercube.
Fibonacci cube: Hypercube induced by strings avoiding consecutive $1$s.

Walks Paths And Cycles

directed path: Directed walk with distinct vertices.
dipath: ≡ directed path.
directed cycle: Closed directed path.
Cycles: ≡ cycle.
even cycle: Cycle of even length.
odd cycle: Cycle of odd length.
hole: Induced cycle of length at least $4$.
chord: Edge joining nonconsecutive vertices of a cycle.
length: Number of edges in a walk.
length of a path or walk: ≡ length.
length of a cycle: Number of edges in a cycle.
route: ≡ walk.
tour: Closed walk.
Hamiltonian path: Path using every vertex.
Hamiltonian cycle: Cycle using every vertex.
Eulerian path: Trail using every edge.
Eulerian cycle: Closed trail using every edge.
Shortest path: Path of minimum length between fixed endpoints.
Shortest path problem: Compute shortest paths in a weighted graph.
geodesic: Shortest path.
reachability: Existence of a directed path.
reachable: Having a directed path from the source vertex.
internal: Not an endpoint of the path under discussion.
internally disjoint: Sharing no internal vertices.
initial vertex: Tail or first vertex of a directed walk.
terminal vertex: Head or last vertex of a directed walk.
beginning: Initial vertex.
end: Terminal vertex.
ray: One-way infinite path.

Trees And Rooted Structures

free tree: ≡ tree.
ordered tree: Rooted tree with ordered children.
positional tree: Rooted tree whose child positions are named.
binary tree: Rooted tree with at most two children per node.
Binary search tree: Binary tree ordered by key.
Full binary tree: Binary tree whose internal nodes have two children.
k-ary tree: Rooted tree with at most $k$ children per node.
k-ary: ≡ k-ary tree.
-ary: Arity suffix for rooted trees.
Child node: ≡ child.
child: Vertex adjacent below its parent in a rooted tree.
Parent node: ≡ parent.
parent: Neighbor immediately above a vertex in a rooted tree.
Root node: ≡ root.
root: Distinguished vertex of a rooted tree.
Root (graph theory): ≡ root.
leaf: Vertex of a tree with no child.
Leaf node: ≡ leaf.
branch: Root-to-leaf path or subtree at a child.
depth: Distance from the root.
height: Maximum depth below a node.
level: Vertices of equal depth.
Level structure: Partition by distance from a root.
sibling: Vertices with the same parent.
descendant: Vertex below another in the rooted order.
subtree: Descendant tree or connected tree subgraph.
subforest: Subgraph that is a forest.
arborescence: Directed rooted tree with unique root paths.
polytree: DAG whose underlying graph is a tree.
Family tree: ↝ rooted tree. Parent arcs encode descent.
Evolutionary tree: ↝ phylogenetic tree. Leaves encode taxa.
tree data structure: ↝ rooted tree. Records are vertices, pointers edges.
Tree structure: ↝ rooted tree. Containment gives the parent map.
abstract syntax tree: ↝ rooted tree. Operators internal, operands or tokens leaves.
parse tree: ↝ rooted tree. Productions internal, terminals leaves.
Junction tree: Tree decomposition with running-intersection bags.
tree decomposition: Tree-indexed bags cover vertices and edges with running intersection.
treewidth: Minimum bag size minus $1$ over tree decompositions.
path decomposition: Tree decomposition whose index tree is a path.
pathwidth: Minimum width over path decompositions.
branch-decomposition: Branching decomposition of edge or vertex separations.
branchwidth: Minimum width over branch decompositions.
SPQR tree: Decomposes a biconnected graph into triconnected components.
clique tree: Tree of maximal cliques of a chordal.
cotree: Tree of a cograph complement-union construction.
cover tree: Metric tree for nearest-neighbor search.

Incidence And Parameters

degree sequence: Nonincreasing sequence of vertex degrees.
maximum degree: $\Delta($$G$$)=\max_{v\in V}$$\deg_G(v)$.
clique number: $\omega($$G$$)$.
independence number: $\alpha$$($$G$$)$.
chromatic number: $\chi$$($$G$$)$.
chromatic index: $\chi$$'($$G$$)$.
matching number: Maximum matching size.
density: $2|$$E$$|/(|$$V$$|(|$$V$$|-1))$ for simple $G$.
Cheeger constant: Min boundary-to-volume ratio.
expander: Sparse family with uniformly large expansion.
expansion: Boundary growth of vertex sets.
bandwidth: Minimum maximum label difference across edges.
degeneracy: Maximum over subgraphs of their minimum degree.
degenerate: Having bounded degeneracy in context.
binding number: Minimum $|$$N$$(S)|/|S|$ over admissible vertex sets.
dominating set: Vertex set meeting every closed neighborhood.
dominating: Belonging to or defining a dominating set.
dominate: A vertex dominates its closed neighborhood.
domatic: Partition into dominating sets.
eternal dominating set: Dominating set maintained under attacks.
Wiener index of a graph: Sum of all vertex-pair distances.
Wiener index of a vertex: Sum of distances from the vertex to all vertices.
Wiener polynomial of an undirected graph: Distance-count polynomial.
crossing number: Minimum number of edge crossings in a drawing.
thickness: Minimum number of planar subgraphs whose union is $G$.
strength: Minimum edge-density ratio defining graph strength.
volume: Sum of degrees in the set under discussion.
Node influence metric: Vertex-influence parameter.

Coloring

color: Element assigned by a coloring.
colored: Equipped with a coloring.
proper: Adjacent objects receive distinct colors.
chromatic: Concerning graph coloring.
Edge coloring: Proper coloring of edges.
n-edge colouring: Edge coloring with $n$ colors.
n-vertex colouring: Vertex coloring with $n$ colors.
Graph two-coloring: Proper vertex coloring with two colors.
Acyclic coloring: Proper coloring whose two-color subgraphs are forests.
Circular coloring: Cycle-valued coloring with separation constraints.
Complete coloring: Coloring in which every color pair appears on an edge.
achromatic: Maximum color count in a complete proper coloring.
Exact coloring: Coloring using exactly the stated number of colors.
Fractional coloring: Linear-program relaxation of vertex coloring.
H-coloring: Homomorphism to $H$.
H-free: Excludes $H$ by source containment.
H-free graph: No specified copy of $H$.
List coloring: Proper coloring from vertex color lists.
List edge-coloring: Proper edge coloring from edge color lists.
choosability: Minimum list size guaranteeing list coloring.
choosable: Having the stated list-coloring property.
Incidence coloring: Coloring incidences so adjacent incidences differ.
Total coloring: Colors vertices and edges with incidence constraints.
Strong coloring: Coloring meeting every part of a vertex partition.
Subcoloring: Vertex coloring whose color classes induce cluster graphs.
Cocoloring: Color classes are cliques or independent sets.
Uniquely colorable graph: One proper coloring up to color permutation.
Grundy number: Max greedy colors over vertex orders.
Harmonious coloring: Each color pair appears on at most one edge.
Graceful labeling: Vertex labeling inducing distinct edge labels.
Graph labeling: Assignment of labels to vertices, edges, or both.

Cuts Separations And Minors

cut set: Vertex or edge set whose deletion disconnects the graph.
cut-set: ≡ cut set.
bond: Minimal nonempty edge cut.
separating set: ≡ cut set.
separation number: Minimum size of a cut set of the stated kind.
disconnecting set: ≡ cut set.
minimum cut: Cut of minimum capacity or cardinality.
connectivity: Minimum vertex cut size.
k-connected: ≡ $k$-connected.
k-edge-connected: ≡ $k$-edge-connected.
block: Maximal connected subgraph without a cut vertex.
contraction: Identification of the endpoints of an edge.
edge contraction: ≡ contraction.
vertex identification: Quotient merging specified vertices.
identified: Vertex identification quotient.
unidentified: No vertex identification quotient.
topological: By subdividing or suppressing degree-$2$ vertices.
core: Graph admitting no homomorphism to a proper subgraph.
kernel: Absorbing independent set in a directed graph.
absorbing: Every outside vertex has an arc to the set.
transitive: Closed under directed reachability of length two.
condensation: DAG of strongly connected components.
strongly connected component: Maximal strongly connected subgraph.
diconnected: Strongly connected in directed context.

Covers Quotients And Lifts

fiber: Preimage of one base vertex.
lift: ≡ covering graph.
h-lift: Covering graph with every fiber size $h$.
double cover: Covering graph with every fiber size $2$.
2-fold cover: ≡ double cover.
bipartite double cover: $G$$\times$$ $$K_2$.
universal covering graph: Tree covering graph of a connected graph.
universal cover: ≡ universal covering graph.
universal covering: ≡ universal covering graph.
non-backtracking: Walk with no immediate edge reversal.
covering transformation group: Automorphisms preserving the covering map.
abelian covering graph: Covering graph with abelian covering transformation group.
topological crystal: Infinite abelian covering graph of a finite multigraph.
planar cover: Planar covering graph.
voltage graph: Graph with group-labeled darts.
dart: Oriented incidence of an edge.
derived graph: Graph induced from a voltage graph and group states.

Automata Order And Stochastic Extensions

transition system: States with transition relation.
labeled transition system: Transition system with edge labels.
finite automaton: Finite labeled transition system with start and accepting states.
NFA: Finite automaton with set-valued next-state relation.
DFA: Finite automaton with one next state for each state-symbol pair.
regular language: Language accepted by a finite automaton.
regular expression: Algebraic expression denoting a regular language.
generalized regular expression: Regular expression extended by context-fixed regular operations.
bisimulation: Relation between states matching labeled transitions both ways.
bisimilarity: Equivalence induced by existence of a bisimulation.
partition refinement: Splitting blocks until the stability predicate is constant on blocks.
subgraph isomorphism: Injective isomorphism from a pattern graph to a subgraph.
state graph: Graph whose vertices are states and edges are transitions.
partial order: Reflexive antisymmetric transitive relation.
poset: Set equipped with a partial order.
lattice (order-theoretic): Partial order with meet and join for every pair.
lattice: ≡ lattice (order-theoretic).
Hasse diagram: Transitive-reduction drawing of a finite partial order.
Laplacian: Degree diagonal matrix minus adjacency matrix.
normalized Laplacian: Degree-normalized form of the Laplacian.
stationary distribution: Probability vector fixed by a transition matrix.
mixing time: Least time to reach the stated distance from stationarity.
doubly stochastic: Nonnegative matrix with every row sum and column sum $1$.
linear forest: Forest whose components are paths.
biclique closure: In a bipartite graph, add every vertex complete to the opposite side.

Algorithms And Problems

A* algorithm: Shortest-path search using $g+h$ priority.
Ant colony algorithm: Pheromone-trail walk metaheuristic.
Baum–Welch algorithm: EM for hidden Markov models.
Bellman–Ford algorithm: SSSP allowing negative weights.
Best-first search: Expands best-priority frontier vertex.
Boruvka's algorithm: MST by cheapest outgoing component edges.
Breadth-first search: Traversal by nondecreasing start distance.
Depth-first search: Recursively explores an unvisited neighbor.
Depth-limited search: Depth-first search with a maximum depth bound.
Dijkstra's algorithm: SSSP for nonnegative weights.
FKT algorithm: Counts planar perfect matchings by Pfaffian orientation.
Flood fill: Search marking all vertices reachable under an adjacency rule.
Flooding algorithm: Distributed broadcast along graph edges.
Floyd–Warshall algorithm: Dynamic program for all-pairs shortest paths.
Graph exploration algorithm: Discovers a graph by moving through it.
Iterative deepening depth-first search: DFS with increasing depth bound.
Kruskal's algorithm: MST by sorted cycle-free edges.
Maximum-cardinality search: Orders by most numbered neighbors.
Nearest neighbour algorithm: Greedy tour by nearest unvisited vertex.
Prim's algorithm: MST grown by cheapest boundary edge.
Spring-based algorithm: Force-directed drawing.
Topological sorting: Linear order respecting DAG arcs.
Tree search algorithm: Search over a rooted state tree.
Tree traversal: Systematic visitation of rooted-tree vertices.
Inorder traversal: Left subtree, node, right subtree.
Pre-order traversal: Rooted-tree traversal visiting node before children.
Post-order traversal: Rooted-tree traversal visiting children before node.
Backward inorder traversal: Right subtree, node, left subtree.
Euler tour technique: Turns subtree queries into interval queries.
Viterbi algorithm: Dynamic program for the most likely hidden-state path.
Canadian traveller problem: Shortest path with edges revealed en route.
Clique problem: Decide or find a clique of specified size.
Hamiltonian path problem: Decide whether a Hamiltonian path exists.
Independent set problem: Decide or find a size-$k$ independent set.
Traveling salesman problem: Minimum-weight Hamiltonian cycle problem.
Bottleneck traveling salesman problem: Hamiltonian cycle minimizing max edge weight.
Vertex cover problem: Decide or find a vertex set meeting every edge.
Route inspection problem: Minimum closed walk covering all edges.
Degree diameter problem: Max order for fixed degree and diameter.
Museum guard problem: Visibility-cover problem for polygonal regions.
Graph coloring game: Game of constrained color assignments.
Shannon switching game: Two-player game on connecting or cutting a graph.

Represented Domains

Hidden Markov model: ↝ Bayesian network. State chain plus emissions.
Mind map: ↝ graph. Concepts vertices, associations edges.
Knowledge representation: ↝ conceptual graph. Symbols and relations encode facts.
Logical graph: ↝ graph. Graph syntax for logic.
Existential graph: ↝ Logical graph. Enclosures and cuts encode logic.
Entitative graph: ↝ Logical graph. Graph syntax for propositions.
Cladistics: ↝ phylogenetic tree. Leaves taxa, splits shared traits.
Phenetics: ↝ tree. Similarity induces clusters.
Scientific classification: ↝ rooted tree. Ranks form containment.
Ahnentafel: ↝ binary tree. Ancestor numbers follow parent positions.
Decision tree: ↝ rooted tree. Tests internal, outcomes leaves.
Game tree: ↝ rooted tree. States vertices, moves edges.
Technology tree: ↝ DAG. Dependencies order technologies.
Fault tree: ↝ rooted tree. Gates combine component failures.
Suffix tree: ↝ tree. Edges substrings, leaves suffixes.
Trie: ↝ tree. Root paths encode prefixes.
Patricia trie: ↝ Trie. Maximal unary paths are compressed.
Heap: ↝ tree. Parent keys ordered against child keys.
Binary heap: ↝ Heap. Shape is a complete binary tree.
Binomial heap: ↝ Heap. Forest of binomial trees.
Fibonacci heap: ↝ Heap. Lazy heap-ordered forest.
2-3 heap: ↝ Heap. Heap using nodes of degree two or three.
AVL tree: ↝ Binary search tree. Child heights differ by at most one.
Red–black tree: ↝ Binary search tree. Colors enforce log height.
Splay tree: ↝ Binary search tree. Access rotates item to root.
Self-balancing binary search tree: ↝ Binary search tree. Rebalances to log height.
B-tree: ↝ tree. Multiway search tree with balanced leaves.
B*-tree: ↝ B-tree. Higher-occupancy variant.
R-tree: ↝ tree. Bounding rectangles index objects.
Quadtree: ↝ tree. Spatial nodes have four children.
Octree: ↝ tree. Spatial nodes have eight children.
Kd-tree: ↝ tree. Alternating coordinate splits.
Binary space partitioning: ↝ binary tree. Internal nodes split space.
PQ tree: ↝ tree. Leaves permute under P and Q constraints.
T-tree: ↝ tree. Ordered in-memory search tree.

Remaining Source Terms

-flap: Subgraph attached across a small boundary in a separation.
20-fullerene: Fullerene graph on $20$ vertices.
24-fullerene: Fullerene graph on $24$ vertices.
26-fullerene graph: Fullerene graph on $26$ vertices.
60-fullerene: Fullerene graph on $60$ vertices.
70-fullerene: Fullerene graph on $70$ vertices.
Adjacency algebra: Algebra generated by a graph adjacency matrix.
Amalgamation: Gluing graphs along an identified subgraph.
Andrásfai graph: Triangle-free circulant.
Arrangement graph: Arrangements adjacent by swaps.
Balaban 10-cage: Cubic $10$-cage.
Balaban 11-cage: Cubic $11$-cage.
Bidiakis cube: Cubic symmetric graph on $12$ vertices.
Biggs–Smith graph: Cubic symmetric graph on $102$ vertices.
Bivariegated graph: Edges split into perfect matching and cycles.
Blanuša snark (first): First Blanuša cubic snark.
Blanuša snark (second): Second Blanuša cubic snark.
Book (graph theory): Triangles sharing one common edge.
Bouquet graph: One vertex with loops.
Brinkmann graph: Brinkmann's named regular.
Brouwer–Haemers graph: Strongly regular graph from Brouwer and Haemers.
Bull graph: Triangle with two disjoint pendant edges.
Butterfly graph: ≡ butterfly.
C: Cycle prefix or color set by context.
Cage (graph theory): ≡ cage.
Cameron graph: Strongly regular graph associated with Cameron.
Cayley graph: Graph generated from a group and generator set.
Cayley's formula: Number of labeled trees on $n$ vertices is $n^{n-2}$.
Chromatic polynomial: Polynomial counting proper $q$-colorings.
Chvátal graph: Triangle-free $4$-chromatic $4$-regular, $12$ vertices.
Circle graph: Intersection graph of chords of a circle.
Clebsch graph: Triangle-free strongly regular graph on $16$ vertices.
Clique graph: Intersection graph of maximal cliques.
Cliques: ≡ clique.
Cocktail party graph: Complete multipartite graph with parts of size $2$.
Common graph: Random coloring minimizes monochromatic-copy density.
Coxeter graph: Cubic symmetric graph on $28$ vertices.
Critical graph: Graph minimal for losing a stated coloring property.
Crown graph: $K_{n,n}$ with a perfect matching removed.
Cube-connected cycles: Network replacing hypercube vertices by cycles.
Cycle space: Vector space of Eulerian edge sets over $\mathbb F_2$.
Dürer graph: Skeleton of Dürer's solid.
De Bruijn graph: Directed graph of overlapping strings of fixed length.
Desargues graph: Generalized Petersen graph $G$$(10,3)$.
Diamond graph: ≡ diamond.
Dipole graph: Two vertices joined by parallel edges.
Disperser: Bipartite with expansion against large subsets.
Distance regular graph: Intersection numbers determined by distance.
Distance-transitive graph: Aut transitive on vertex pairs at each distance.
Dodecahedron: Skeleton graph of the dodecahedron.
Double-star snark: Cubic snark obtained from two star-like components.
Dual polyhedron: Vertices correspond to original faces.
Dyck graph: Cubic symmetric graph on $32$ vertices.
Edge-transitive graph: Automorphism group transitive on edges.
Ellingham–Horton 54-graph: Ellingham-Horton cubic on $54$ vertices.
Ellingham–Horton 78-graph: Ellingham-Horton cubic on $78$ vertices.
Empty tree: Tree with no vertices.
Entanglement (graph measure): Game measure of directed cyclicity.
Erdős–Gyárfás conjecture: Conjecture on power-of-two cycle lengths.
Errera graph: Planar used in four-color-history counterexamples.
Exponential tree: Rooted tree with exponentially changing level sizes.
Extractor: Bipartite inducing randomness extraction.
Extremal graph theory: Max or min graphs under constraints.
Flower snark: Infinite family of cubic snarks.
Folded cube graph: Quotient graph of a hypercube by antipodal identification.
Folkman graph: Semisymmetric graph on $20$ vertices.
Foster graph: Cubic symmetric graph on $90$ vertices.
Four color theorem: Every planar is $4$-colorable.
Frankl–Rödl graph: Forbidden-intersection graph family.
Franklin graph: Cubic bipartite on $12$ vertices.
Frequency partition: Partition by equal frequency or degree class.
Frucht: Automorphism realization by graphs.
Frucht graph: Cubic with trivial automorphism group.
Frucht's theorem: Every finite group is a graph automorphism group.
Fullerene graphs: Cubic planar with pentagonal and hexagonal faces.
Gear: Wheel with a vertex inserted on each rim edge.
Generalized Petersen graph: $G$$(n,k)$ with cycle, spokes, inner star polygon.
Gewirtz graph: Strongly regular graph on $56$ vertices.
Goldberg–Seymour conjecture: Chromatic-index conjecture for multigraphs.
Goldner–Harary graph: Maximal planar on $11$ vertices.
Golomb graph: Named small graph from Golomb.
Grötzsch: Triangle-free planar are $3$-colorable.
Grötzsch graph: Smallest triangle-free $4$-chromatic graph.
Graph drawing: Geometric placement of vertices and edges.
Graph homomorphism: ≡ homomorphism.
Graph partition: Partition of vertices or edges under graph constraints.
Graph pebbling: Reachability game moving pebbles along edges with cost.
Graph property: Isomorphism-invariant predicate on graphs.
Graph reduction: Transformation to a smaller equivalent graph instance.
Graph triangulation: Addition of edges to make a graph chordal.
Graph-structured stack: Stack alternatives form a DAG.
Graphon: Symmetric measurable function representing dense-graph limits.
Grassmann graph: Subspaces adjacent by codimension-one intersection.
Gray graph: Semisymmetric cubic on $54$ vertices.
Hadwiger: No $K_t$ minor implies $(t-1)$-colorability conjecture.
Half graph: Bipartite with nested neighborhoods.
Hall–Janko graph: Strongly regular graph from the Hall-Janko group.
Halved cube graph: One hypercube part, distance-$2$ adjacency.
Hamming graph: Cartesian product of complete graphs.
Hanoi graph: State graph of the Tower of Hanoi puzzle.
Harries graph: Cubic symmetric graph on $70$ vertices.
Harries–Wong graph: Cubic symmetric graph on $70$ vertices.
Heawood graph: Incidence graph of the Fano plane.
Hedgehog (hypergraph): Hyperedges share a structured core.
Helly family: Pairwise intersection implies total intersection.
Helm: Wheel with a pendant edge at each cycle vertex.
Henson graph: Countable homogeneous $K_n$-free graph.
Herschel graph: Small non-Hamiltonian polyhedral graph.
Hexagonal truncated trapezohedron graph: Its polyhedron skeleton.
Higman–Sims graph: Strongly regular graph from the Higman-Sims group.
Hoffman graph: Graph with Hoffman-style vertex labeling or spectral role.
Hoffman–Singleton graph: Moore graph of degree $7$ and diameter $2$.
Hofman Graph H(12,4): Named Hoffman graph $H$$(12,4)$.
Holt graph: Smallest half-transitive graph.
Horton graph: Cubic used in Hamiltonicity counterexamples.
Icosahedron: Skeleton graph of the icosahedron.
Intersection (Line) Graphs of hypergraphs: Hyperedges adjacent when intersecting.
Johnson graph: Graph on $k$-subsets adjacent by one-element exchange.
Kőnig's lemma: Infinite finitely branching tree has an infinite path.
Kautz graph: Strings with unequal adjacent symbols, shift adjacency.
Keller's conjecture: Cube tiling conjecture via Keller graphs.
King's graph: Chess king move graph on a board.
Kittell graph: Small hypohamiltonian graph.
Klein graph: Cubic symmetric graph associated with the Klein quartic.
Kneser graph: Graph on $k$-subsets adjacent when disjoint.
Knight's graph: Chess knight move graph on a board.
Knight's tour: Hamiltonian path or cycle in a knight's graph.
Labyrinth: Maze represented as a graph.
Laws of Form: Diagrammatic calculus representable by graphs.
Line graph: ≡ line.
Link popularity: Directed-link count or centrality in a Web.
Ljubljana graph: Cubic symmetric graph on $112$ vertices.
Lobster: Tree whose non-leaf deletion yields a caterpillar.
Local McLaughlin graph: McLaughlin local SRG.
Lollipop graph: Clique joined to a path by a bridge.
Loupekine snark (first): First Loupekine cubic snark.
Loupekine snark (second): Second Loupekine cubic snark.
Möbius ladder: Cycle with opposite vertices joined.
Möbius–Kantor graph: Generalized Petersen graph $G$$(8,3)$.
Mac Lane's planarity criterion: Planar iff cycle space has sparse basis.
Markström graph: Small $4$-regular graph with no short cycles.
Max flow min cut theorem: Maximum flow value equals minimum cut capacity.
Maze: ↝ graph. Cells are vertices and passages are edges.
Maze generation algorithm: Builds a spanning-tree passage graph.
McGee graph: Unique cubic $7$-cage.
McKay–Miller–Širán graph: Finite-field degree-diameter graph.
Meredith graph: Cubic used in coloring and connectivity examples.
Meyniel: Every odd cycle of length at least $5$ has at least two chords.
Minimum spanning tree: Spanning tree of minimum total edge weight.
Moore graph: Regular attaining the Moore bound.
Moser spindle: Unit-distance graph requiring four colors.
N: Neighborhood operator or natural-number parameter by context.
Nauru graph: Generalized Petersen graph $G$$(12,5)$.
Neighbor-joining: Builds phylogenetic trees from distances.
Nested triangles graph: Recursively nested triangle graph.
Octahedron: Skeleton graph of the octahedron.
Odd graph: Kneser graph $K$$(2k-1,k-1)$.
Open Shortest Path First: Routing by shortest paths.
Pairwise compatibility graph: Leaf graph under tree-distance bounds.
Paley graph: Graph over a finite field with quadratic-residue adjacencies.
Pancake graph: Cayley graph of permutations generated by prefix reversals.
Pappus graph: Levi graph of the Pappus configuration.
Path analysis (paths and cycles): Study of paths and cycles in a graph.
Perfect order: Greedy-optimal order on every induced subgraph.
Perkel graph: Distance-regular graph on $57$ vertices.
Petersen: Kneser graph $K$$(5,2)$.
Petersen graph: ≡ Petersen.
Platonic solids: Skeleton graphs of the five regular convex polyhedra.
Poussin graph: Planar used in four-color-history counterexamples.
Pre-topological order: Order compatible with preorder or reachability.
Queen's graph: Chess queen move graph on a board.
Rado graph: Countable random graph.
Ramanujan: $d$-regular with nontrivial eigenvalue $\lambda$ satisfying $|$$\lambda$$|\le2\sqrt{d-1}$.
Ramsey's theorem: Large structures contain homogeneous substructures.
Random graph: Probability distribution on graphs.
Reconstruction conjecture: Graphs with $|$$V$$|\ge3$ are determined by decks.
Recursive tree: New vertices attach to older vertices.
Robertson graph: Small named graph of Robertson.
Robertson–Seymour theorem: Minor-closed classes have finite forbidden minors.
Rook's graph: Cartesian product of two complete graphs.
Schläfli graph: Strongly regular graph on $27$ vertices.
Semi-symmetric graphs: Regular edge-transitive, not vertex-transitive.
Seven Bridges of Königsberg: Eulerian-trail problem on its multigraph.
Shannon multigraph: Three-vertex multigraph extremal for edge coloring.
Shrikhande graph: SRG on $\mathbb Z_4^2$ with six generators.
Shuffle-exchange network: Uses shuffle and exchange links.
Sierpinski graph: Recursive gasket-address graph.
Snark (graph theory): ≡ snark.
Sousselier graph: Hypohamiltonian graph of Sousselier.
Sparse graph code: Code represented by a sparse bipartite.
Spectral graph theory: Graphs via matrix eigenvalues.
Sperner's lemma: Labeled triangulation lemma implying fixed-point results.
Square brackets [ ]: Closed interval or grouping notation.
Steiner tree: Minimum connected subgraph spanning required terminals.
String graph: Intersection graph of curves in the plane.
Sudoku graph: Graph whose proper colorings encode Sudoku constraints.
Sylvester graph: Strongly regular graph associated with Sylvester.
Symmetric graphs: Arc-transitive graphs.
Szekeres snark: Cubic snark on $50$ vertices.
Tadpole graph: Cycle graph joined to a path.
Tait's conjecture: Hamiltonian-cycle conjecture for cubic polyhedral graphs.
Thomsen graph: Complete bipartite graph $K_{3,3}$.
Three-cottage problem: Puzzle equivalent to $K_{3,3}$ nonplanarity.
Tietze graph: Cubic related to Petersen by expansion.
Total graph: Vertices are $V(G)$$\cup $$E(G)$ with adjacency or incidence.
Tree (descriptive set theory): Prefix-closed set of finite sequences.
Tree (set theory): Poset with well-ordered predecessor sets.
Tree rotation: Local parent-child swap.
Trellis (graph): Layered graph used for paths through state sequences.
Truncated cube: Skeleton graph of the truncated cube.
Truncated dodecahedron: Skeleton graph of the truncated dodecahedron.
Truncated icosahedron: Skeleton graph of the truncated icosahedron.
Truncated octahedron: Skeleton graph of the truncated octahedron.
Truncated solids: Skeleton graphs of truncated polyhedra.
Truncated tetrahedron: Skeleton graph of the truncated tetrahedron.
Turán: Complete multipartite with balanced parts.
Turán graph: ≡ Turán.
Turán number: Maximum edges in an $H$-free graph on $n$ vertices.
Turán's theorem: $K_{r+1}$-free edge maximum is Turán.
Tutte 12-cage: Cubic $12$-cage.
Tutte graph: Non-Hamiltonian cubic polyhedral graph.
Tutte's fragment: Fragment used to build the Tutte graph.
Tutte–Coxeter graph: Cubic symmetric $8$-cage.
Vertex-transitive graph: Automorphism group transitive on vertices.
Visibility graph: Graph joining mutually visible geometric objects.
Vizing: For simple $G$, $\Delta$$\le$$\chi$$'\le$$\Delta$$+1$.
Wagner: Planarity and minor theory associated with Wagner's theorem.
Wagner graph: Möbius ladder on $8$ vertices.
Watkins snark: Cubic snark of Watkins.
Web: Web-like graph family or directed hyperlink graph.
Wells graph: Distance-regular graph on $32$ vertices.
Wiener–Araya graph: Hypohamiltonian graph with Wiener-Araya construction.
Young–Fibonacci graph: Graded graph on Young-Fibonacci words.
alternating: Alternating between two types along a walk or cycle.
antichain: Set of mutually incomparable elements.
apex: Vertex whose deletion gives a graph in the stated class.
augmenting: Improving by an alternating path or similar exchange.
bag: Vertex subset in a decomposition.
balanced: Parts or degrees differ by at most one.
ball: Vertices within a fixed distance of a center.
bipartite wheels: Bipartite wheel-like graph family.
book: Triangles sharing one common edge.
boundary: Vertices or edges crossing from a set to its complement.
bramble: Touching connected subgraphs certifying treewidth.
butterfly: Two triangles sharing one vertex.
cactus: Graph in which any two cycles share at most one vertex.
cage: Regular of minimum order for given degree and girth.
canonical: Chosen representative invariant under isomorphism.
canonization: Computation of a canonical representative.
card: One vertex-deleted subgraph in a reconstruction deck.
carving width: Width of an edge-separation decomposition.
caterpillar: Tree whose leaf deletion leaves a path.
center: Vertices of minimum eccentricity.
centroid: Deletion leaves no component larger than half the tree.
chain: Totally ordered path-like substructure.
cherry: Two leaves with the same parent.
chi0(G): Achromatic number notation.
circle: Cycle or circular intersection domain by context.
class: Isomorphism-closed graph collection.
claw: Complete bipartite graph $K_{1,3}$.
clique-width: Min labels for labeled graph construction.
closed: Includes the relevant endpoints or closure operation.
co-: Complement-class prefix.
cogwheels: Wheel-like graph family with alternating attachments.
commuting graph: Graph joining group elements that commute.
complement: Graph on $V$ with edge set $\binom V2$$\setminus$$ $$E$.
cone: Join of a graph with one new universal vertex.
cover: Family of subobjects whose union contains the target.
crossing: Interior intersection of drawn edges.
cube: ≡ hypercube.
cut space: Vector space generated by graph cuts over $\mathbb F_2$.
de Bruijn sequences: Cyclic strings containing each length-$k$ word once.
deck: Multiset of vertex-deleted cards.
diagram: Graphical representation of a relation or structure.
diamond: $K_4$ minus one edge.
direct predecessor: Parent or previous vertex in a directed order.
direct successor: Child or immediate next vertex in a directed order.
direction: Orientation assigned to an edge.
dissociation number: Max vertex set inducing degree at most $1$.
dodecahedral graph: ≡ Dodecahedron.
ear: Path whose internal vertices are new and endpoints are old.
ear decomposition: Sequence adding ears to build a graph.
embeddable: Having an embedding in the stated surface or host.
enumeration: Counting or listing graphs in a class.
even: Divisible by $2$.
factor: Spanning subgraph.
factorization: Partition of edges into factors.
family: Parameterized graph class.
first order: Logic over vertices with quantification over elements only.
forbidden: Excluded subgraph, induced subgraph, minor, or pattern.
forcing graph: Graph gadget enforcing choices in reductions.
free edge: Edge incident with an unconstrained or free vertex.
free vertex: Vertex not constrained by the current matching or embedding.
full: Contains all allowed edges under the stated rule.
gear graph: ≡ Gear.
giant: Component with order linear in the random graph.
graph invariant: Isomorphism-invariant graph value.
greedy: Algorithm making a locally optimal admissible choice.
haven: Maps small vertex sets to connected large sides.
helm graph: ≡ Helm.
hereditary: Closed under induced subgraphs.
hexagon: Cycle of length $6$.
homomorphic: Preserved by a graph homomorphism.
homomorphic equivalence: Homomorphisms exist in both directions.
hypo-: Prefix meaning deletion of one vertex has the property.
improper: Violating the proper coloring separation condition.
in-neighborhood: Vertices with arcs into the vertex.
independent: ≡ independent set.
induced: Contains exactly all edges of $G$ on the chosen vertices.
inductive: Defined or proved by vertex deletion or construction order.
intersection: Common elements of sets or subgraphs.
interval: Ordered or geometric interval used as a vertex model.
invariant: ≡ graph invariant.
inverted arrow: Reversed directed edge symbol.
isolated: Having degree $0$.
isolated vertex: Vertex of degree $0$.
isomorphic: Related by an isomorphism.
isoperimetric: Concerning minimum boundary size for given volume.
k-clique: Clique of size $k$.
k-colorable graph: Graph with a proper $k$-coloring.
k-factor: Spanning $k$-regular subgraph.
k-spanner: Spanning distance approximator.
k-th power: Distance power.
knot: Vertex or crossing unit in an embedded diagram.
label: Value assigned to a vertex, edge, or incidence.
line: Edge, arc, or line graph by context.
linkage: Collection of vertex-disjoint paths joining prescribed pairs.
list: Assigned allowable color set.
lobster graph: ≡ Lobster.
local: Restricted to a neighborhood or bounded-radius subgraph.
magnification: Replace vertices by sets and edges by complete joins.
median: Vertex lying on shortest paths among triples in median graphs.
modular: Distance identity satisfying modular graph conditions.
monotone: Preserved under specified additions or deletions.
odd: Not divisible by $2$.
open: Excluding the base vertex or boundary element.
oriented: Orientation of a simple.
out-neighborhood: Vertices reached by arcs leaving the vertex.
outer face: Unbounded face of a plane graph.
partite set: One block of a multipartite vertex partition.
pendant: Incident with a leaf.
perfect: $\chi$$($$H$$)=\omega($$H$$)$ for every induced $H$.
perfect matching: Matching covering every vertex.
peripheral: Having eccentricity equal to graph diameter.
peripheral vertex: ≡ peripheral.
power: Graph joining vertices within a bounded distance.
predecessor: Earlier vertex in a rooted or directed order.
property: ≡ Graph property.
quasi-random graph sequence: Sequence with equivalent random-like properties.
recognizable: Definable by a finite algebraic or logical graph expression.
reconstruction: Recovery of a graph from its deck.
rectangle: Four-cycle or rectangular grid cell by context.
reverse: Reversal of all arcs or of a directed walk.
saturated: Edge-maximal subject to avoiding a forbidden graph.
searching number: Minimum searchers needed to clear a graph.
second order: Logic allowing quantification over vertex or edge sets.
simplicial vertex: Vertex whose neighborhood is a clique.
sink: Vertex with out-degree $0$.
source: Vertex with in-degree $0$.
space: Ambient set of graph objects or embeddings.
spanner: ≡ $k$-spanner.
spanning: Using all vertices.
spanning matching: Matching in a spanning subgraph context.
spanning tree: Tree spanning all vertices.
spectral: Concerning eigenvalues of graph matrices.
spectrum: Multiset of eigenvalues of a graph matrix.
split: Vertices partition into a clique and an independent set.
square: Cycle of length $4$ or graph square by context.
square bracket: ≡ Square brackets {[} {]}.
stable: ≡ independent set.
strong: Directed or coloring strength property fixed by context.
successor: Later vertex in a rooted or directed order.
superconcentrator: DAG with disjoint paths between equal-size input and output sets.
supergraph: Graph containing another graph as a subgraph.
theta: Union of three internally disjoint paths with common endpoints.
theta graph: ≡ theta.
truncated icosahedral graph: ≡ Truncated icosahedron.
twin: Vertices with equal open or closed neighborhoods.
unary vertex: Vertex with one child in a rooted tree.
uniform: Hypergraph whose edges have equal size.
universal: Adjacent to every other vertex.
web graph: ≡ Web.
weight: Numerical value assigned to graph elements.
weight of a subgraph: Sum of weights of its selected elements.
weighted: Equipped with weights.
weighted graph: Graph with vertex or edge weights.
well-colored: Graph whose greedy colorings use a fixed number of colors.
well-covered: Graph whose maximal independent sets have equal size.
wheel: Cycle plus one universal hub.
width: Maximum bag size or separation order in a decomposition.
windmill: Edge-disjoint cliques sharing one common vertex.

Synonyms

node: ≡ vertex.
vertices: ≡ vertex.
point: ≡ vertex.
link: ≡ edge.
undirected edge: ≡ edge.
edges: ≡ edge.
neighbour: ≡ neighbor.
neighbourhood: ≡ neighborhood.
digraph: ≡ directed graph.
directed arc: ≡ arc.
directed edge: ≡ arc.
directed line: ≡ arc.
arrow: ≡ arc.
in degree: ≡ in-degree.
out degree: ≡ out-degree.
circuit: ≡ cycle.
self-loop: ≡ loop.
multiple edges: ≡ multiple edge.
valency: ≡ degree.
isthmus: ≡ bridge.
cut edge: ≡ bridge.
articulation point: ≡ cut vertex.
cut point: ≡ cut vertex.
separating vertex: ≡ cut vertex.
stable set: ≡ independent set.
staset: ≡ independent set.
anti-edge: ≡ non-edge.
biclique: ≡ complete bipartite graph.
Eulerian circuit: ≡ Eulerian cycle.
Eulerian tour: ≡ Eulerian cycle.
Eulerian trail: ≡ Eulerian path.
traceable path: ≡ Hamiltonian path.
Tree (graph theory): ≡ tree.
Path (graph theory): ≡ path.
Matching (graph theory): ≡ matching.
Complement of a graph: ≡ complement.
A-star search algorithm: ≡ A* algorithm.
proper vertex colouring: ≡ proper coloring.
proper edge colouring: ≡ proper coloring.

Representations

adjacency matrix: ↝ graph. $M_{uv}=|\{e:\partial e=\{u,v\}\}|$.
incidence matrix: ↝ graph. $B_{v,e}=$$m_{\partial e}(v)$.
adjacency list: ↝ graph. Map $v\mapsto $$N_G(v)$.
graphical model: ↝ graph. Vertices are variables. Edges or arcs encode dependence constraints.
Bayesian network: ↝ directed graph. Acyclic graphical model with arcs encoding factorization order.
Markov random field: ↝ graphical model. Undirected Markov dependence graph.
conceptual graph: ↝ graph. Labeled concept-relation graph.
phylogenetic tree: ↝ tree. Leaf-labeled ancestry tree.