Studied by 0 people
Looks like no one added any tags here yet for you.
graph
a finite nonempty set V of vertices and a set E (edges)of 2-element subsets of V
adjacent vertices
vertices connected by an edge
nonadjacent vertices
vertices that are not connected by an edge
neighbor
a vertex adjacent to another vertex
neighborhood
the set of neighbors (adjacent vertices) of a vertex
incident
an edge is "incident" to it's connected vertices
order
number of vertices
size
number of edges
trivial graph
a graph with only one vertex
nontrivial graph
a graph with at least two vertices
empty graph
a graph with no edges
degree
the number of neighbors of a vertex
isolated vertex
a vertex with no neighbors
end vertex
a vertex of degree 1
regular graph
a graph where all vertices have the same degree
proper subgraph
a subgraph that does not equal the graph
induced subgraph
a subgraph containing all of the edges of the graph that have both endpoints in it's subset
spanning subgraph
a subgraph that contains all of the vertices of the original graph
complete graph
a graph where every two distinct vertices are adjacent
complement
a graph with two distinct adjacent vertices if and only if those vertices are nonadjacent in G
isomorphic
two graphs where there exists a bijective function such that two vertices are adjacent in G if and only if they are adjacent in H
multigraph
a graph with parallel edges
parallel edges
multiple edges between the same pair of vertices
loop
an edge joining a vertex to itself
pseudograph
a graph with both parallel edges and loops
walk
a sequence of adjacent vertices of a graph
initial vertex
where a walk begins
terminal vertex
where a walk ends
trivial walk
a walk of length 0
walk length
the number of edges in a walk
trail
a walk with no repeated edges
path
a walk with no repeated vertices
open walk
a walk in which the initial and terminal vertices are not the same
closed walk
a walk in which the initial and terminal vertices are the same
circuit
a closed trail of length 3 or more
cycle
a circuit with no repeated vertices (except the initial/terminal vertex)
even cycle
a cycle of even length
odd cycle
a cycle of odd length
bipartite graph
a graph that can be split into two subsets such that there are only edges between vertices belonging to different subsets
complete bipartite graph
a graph where every vertex of each subset is connected to every vertex of the other subset
k-partite graph
a graph that is partitioned into k subsets
complete multipartite graph
a k-partite graph such that every vertex of each subset is connected to every vertex of every other subset
Eulerian graph
a connected graph that contains a trail or circuit in which every vertex is visited exactly once
Hamiltonian graph
a graph that contains a cycle that visits every vertex of the graph exactly once
weighted graph
a graph in which every edge is assigned a number
Note 
Flashcard (55)