Chapter 10.2 Graph Terminology and Special Types of Graphs Flashcards
Define adjacent (or neighbors)
Define Neighborhood
Degree of a vertex in an undirected graph
Define isolated
A vertex of degree zero is called isolated.
Define Pendant
A vertex is pendant if and only if it has degree one
THE HANDSHAKING THEOREM
Theroem 1
An undirected graph has a _____ number of vertices of _____ degree.
Define
adjacent to
adjacent from
initial vertex
end vertex
Define
in-degree of a vertex v
out-degree of a vertex v
Thereom
How to find the number of edges graph with directed edges?
Define a complete graph
A complete graph on n vertices, denoted by Kn, is a simple graph that contains exactly one edge between each pair of distinct vertices.
Define Cycles Graph
Cycles A cycle Cn, n ≥ 3, consists of n vertices v1, v2, … , vn and edges {v1, v2}, {v2, v3}, … , {vn-1, vn}, and {vn, V1}
Define Wheels graphs
We obtain a wheel Wn when we add an additional vertex to a cycle Cn, for n ≥ 3, and connect this new vertex to each of the n vertices in Cn, by new edges.
Define n-cube graphs
An n-dimensional hypercube, or n-cube, denoted by Qn, is a graph that has vertices representing the 2n bit strings of length n. Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position.
Define Simple Bipartite Graph
Theroem
A simple graph is bipartite if……………..
Define subgraph
Define subgraph induced
Define Union
