vertexvalued

Vertex-valued refers to a construct in graph theory where a value is assigned to each vertex of a graph. Formally, a vertex-valued graph consists of a graph G = (V, E) together with a function f: V -> S, where V is the set of vertices, E the set of edges, and S is a chosen value set (such as the integers, real numbers, or a more general set). The term emphasizes the assignment to vertices rather than to edges or faces.

In practice, vertex-valued descriptions are closely related to, and often overlap with, vertex-weighted graphs and vertex labeling. A vertex-weighted graph assigns a weight to each vertex, typically used to influence algorithmic decisions or to model costs, capacities, or other node attributes. Vertex labeling, a broader concept, assigns labels from a specified set to vertices, with additional constraints such as injectivity, modular arithmetic, or range restrictions. A vertex-valued framework may impose such constraints on the value function f, or it may allow arbitrary assignments.

Examples include a simple graph with V = {a, b, c} and a value function f(a) = 3, f(b) = 1, f(c) = 5, or more generally a graph where vertex values represent resources, priorities, or measurements at nodes. Applications span network analysis, graph signal processing (where signals are defined on vertices), and combinatorial problems that examine how vertex values interact with graph structure.

See also: vertex labeling, vertex-weighted graph, graph signal processing, network analysis.