 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(February 2014) (Learn how and when to remove this message) |
Indiscrete mathematics, and more specifically ingraph theory, avertex (pluralvertices) ornode is the fundamental unit of which graphs are formed: anundirected graph consists of a set of vertices and a set ofedges (unordered pairs of vertices), while adirected graph 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 indivisibleobjects, although they may have additional structure depending on the application from which the graph arises; for instance, asemantic network 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 vertexw is said to be adjacent to another vertexv if the graph contains an edge (v,w). Theneighborhood of a vertexv is aninduced subgraph of the graph, formed by all vertices adjacent to v.
Thedegree of a vertex, denoted 𝛿(v) in a graph is the number of edges incident to it. Anisolated 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).[1] Aleaf vertex (alsopendant 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); asource vertex is a vertex with indegree zero, while asink vertex is a vertex with outdegree zero. Asimplicial vertex is one whoseclosed neighborhood forms aclique: every two neighbors are adjacent. Auniversal vertex is a vertex that is adjacent to every other vertex in the graph.
Acut vertex is a vertex the removal of which would disconnect the remaining graph; avertex separator is a collection of vertices the removal of which would disconnect the remaining graph into small pieces. Ak-vertex-connected graph is a graph in which removing fewer thank vertices always leaves the remaining graph connected. Anindependent set is a set of vertices no two of which are adjacent, and avertex cover is a set of vertices that includes at least one endpoint of each edge in the graph. Thevertex space of a graph is a vector space having a set of basis vectors corresponding with the graph's vertices.
A graph isvertex-transitive if it has symmetries that map any vertex to any other vertex. In the context ofgraph enumeration andgraph isomorphism it is important to distinguish betweenlabeled vertices andunlabeled 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 itsadjacencies in the graph and not based on any additional information.
Vertices in graphs are analogous to, but not the same as,vertices of polyhedra: theskeleton 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. Thevertex figure of a vertex in a polyhedron is analogous to the neighborhood of a vertex in a graph.