Simple Graphs

Question 1

What is a simple graph?

Answer 1

G(V, E) Where V and E denote vertex and edges

Question 2

What is the order of a graph?

Answer 2

p(g) = |v(g)|

Question 3

what is the size of a graph?

Answer 3

q(g) = |e(g)|

Question 4

What is graph density

Answer 4

How close the number of edges are to max amount of edges
q(g) / binom(p(g))(2)

Question 5

What is an r-regular graph?

Answer 5

Degree of vertex v = degree of all vertices
deg(v) = r forall v in V(G, where r is in Natural number and r <= p
r denotes amount of edges

Question 6

What is a complete graph?

Answer 6

Kn = n-1 regular graph

Question 7

What is an empty graph?

Answer 7

bar(Kn) is a graph with n vertices but with an empty set of edges

Question 8

What is a k-partite graph?

Answer 8

V(G) can be partitioned into k subsets, such that no two vertices of Vi are adjacent to each other.
That means that no vertices in their sets are adjacent, rather adjacent to the vertices in their opposite sets.

Question 9

What is a complete k-partite graph?

Answer 9

Knk is a k-partite graph such that each pair of vertices not in the same subset are adjacent. Every possible edge is on the vertex.

Question 10

What is a complete balanced k-partite graph?

Answer 10

K(kxn) is a complete k-partite graph such that each subset contain n vertices

Therefore, k = num sets, n = num vertices

Question 11

What isa a directed graph?

Answer 11

Graph in which edges have a direction called an arc, denoted by (v, w) or vw (with a arrow)

Question 12

What is a weighted graph?

Answer 12

Each edge or arc is assigned a pos real number.

Learn notation in notes

Question 13

How do you calculate the total weight of a weighted graph?

Answer 13

W(G) = sum of the edges of weights in the graph

Question 14

What is a proper subgraph?

Answer 14

When subgraph is not identical to its parent

Question 15

What is a spanning subgraph?

Answer 15

Subgraph such that vertex set is equal to that of the original graph
therefore V(H) = V(G), E(H) subset E(G)

Question 16

What is a vertex induced subgraph?

Answer 16

Selection of vertices from larger graph including all the edges that connect these vertices

Subgraph S(G) whose vertex set V({S}G) = Subset of V(G). It has an edge set E({S}G) that contains all edges in G whose end-points are both in S

Study notation on notes

Question 17

What is an edge induced subgraph?

Answer 17

{T}G by taking subset of the edge set of G, with the vertex set being the end points of those edges.

Study notation on notes