In discrete mathematics, and more specifically in

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

consists of a set of vertices and a set of edges (unordered pairs of vertices), while a

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

consists of a set of vertices and a set of arcs (ordered pairs of vertices). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another. From the point of view of graph theory, vertices are treated as featureless and indivisible

objects Object may refer to: General meanings * Object (philosophy), a thing, being, or concept ** Object (abstract), an object which does not exist at any particular time or place ** Physical object, an identifiable collection of matter * Goal, an ...

, although they may have additional structure depending on the application from which the graph arises; for instance, a

semantic network A semantic network, or frame network is a knowledge base that represents semantic relations between concepts in a network. This is often used as a form of knowledge representation. It is a directed or undirected graph consisting of vertices, ...

is a graph in which the vertices represent concepts or classes of objects. The two vertices forming an edge are said to be the endpoints of this edge, and the edge is said to be incident to the vertices. A vertex ''w'' is said to be adjacent to another vertex ''v'' if the graph contains an edge (''v'',''w''). The neighborhood of a vertex ''v'' is an

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

of the graph, formed by all vertices adjacent to ''v''.

Types of vertices

The degree of a vertex, denoted 𝛿(v) in a graph is the number of edges incident to it. An isolated vertex is a vertex with degree zero; that is, a vertex that is not an endpoint of any edge (the example image illustrates one isolated vertex). :File:Small Network.png; example image of a network with 8 vertices and 10 edges A leaf vertex (also pendant vertex) is a vertex with degree one. In a directed graph, one can distinguish the outdegree (number of outgoing edges), denoted 𝛿⁺(v), from the indegree (number of incoming edges), denoted 𝛿⁻(v); a source vertex is a vertex with indegree zero, while a sink vertex is a vertex with outdegree zero. A simplicial vertex is one whose neighbors form a

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

: every two neighbors are adjacent. A

universal vertex In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. (It is not to be confused ...

is a vertex that is adjacent to every other vertex in the graph. A cut vertex is a vertex the removal of which would disconnect the remaining graph; a

vertex separator In graph theory, a vertex subset is a vertex separator (or vertex cut, separating set) for nonadjacent vertices and if the removal of from the graph separates and into distinct connected components. Examples Consider a grid graph with ...

is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. A

k-vertex-connected graph In graph theory, a connected graph is said to be -vertex-connected (or -connected) if it has more than vertices and remains connected whenever fewer than vertices are removed. The vertex-connectivity, or just connectivity, of a graph is th ...

is a graph in which removing fewer than ''k'' vertices always leaves the remaining graph connected. An independent set is a set of vertices no two of which are adjacent, and a

vertex cover In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimiza ...

is a set of vertices that includes at least one endpoint of each edge in the graph. The vertex space of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices. A graph is

vertex-transitive In geometry, a polytope (e.g. a polygon or polyhedron) or a tiling is isogonal or vertex-transitive if all its vertices are equivalent under the symmetries of the figure. This implies that each vertex is surrounded by the same kinds of face in ...

if it has symmetries that map any vertex to any other vertex. In the context of

graph enumeration In combinatorics, an area of mathematics, graph enumeration describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the gr ...

and

graph isomorphism In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) ar ...

it is important to distinguish between labeled vertices and unlabeled vertices. A labeled vertex is a vertex that is associated with extra information that enables it to be distinguished from other labeled vertices; two graphs can be considered isomorphic only if the correspondence between their vertices pairs up vertices with equal labels. An unlabeled vertex is one that can be substituted for any other vertex based only on its adjacencies in the graph and not based on any additional information. Vertices in graphs are analogous to, but not the same as, vertices of polyhedra: the skeleton of a polyhedron forms a graph, the vertices of which are the vertices of the polyhedron, but polyhedron vertices have additional structure (their geometric location) that is not assumed to be present in graph theory. The

vertex figure In geometry, a vertex figure, broadly speaking, is the figure exposed when a corner of a polyhedron or polytope is sliced off. Definitions Take some corner or vertex of a polyhedron. Mark a point somewhere along each connected edge. Draw line ...

of a vertex in a polyhedron is analogous to the neighborhood of a vertex in a graph.

References

* * Berge, Claude, ''Théorie des graphes et ses applications''. Collection Universitaire de Mathématiques, II Dunod, Paris 1958, viii+277 pp. (English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition. Dover, New York 2001) * * * *

External links

* {{DEFAULTSORT:Vertex (Graph Theory) Graph theory

Types of vertices

See also

References

External links