Podcast
Questions and Answers
A __________ graph is a simple graph in which the set of vertices can be partitioned into two sets X and Y such that every edge is between a vertex in X and a vertex in Y
A __________ graph is a simple graph in which the set of vertices can be partitioned into two sets X and Y such that every edge is between a vertex in X and a vertex in Y
Bipartite
Complete ________ Graph Km,n has m vertices in X and n vertices in Y with an edge between every vertex in X and every vertex in Y
Complete ________ Graph Km,n has m vertices in X and n vertices in Y with an edge between every vertex in X and every vertex in Y
Bipartite
The graph resulting from replacing each arc of a digraph with an edge is called the underlying ________
The graph resulting from replacing each arc of a digraph with an edge is called the underlying ________
Graph
The ________ of a complete graph is called a Tournament
The ________ of a complete graph is called a Tournament
Signup and view all the answers
A ________ graph is a graph with at least one edge and at least one arc
A ________ graph is a graph with at least one edge and at least one arc
Signup and view all the answers
Two graphs are ________ if their sets of vertices and edges are identical
Two graphs are ________ if their sets of vertices and edges are identical
Signup and view all the answers
A graph with no loops is called a ______
A graph with no loops is called a ______
Signup and view all the answers
Two or more edges that join the same pair of distinct vertices are called ______
Two or more edges that join the same pair of distinct vertices are called ______
Signup and view all the answers
A graph with at least one loop is called a ______
A graph with at least one loop is called a ______
Signup and view all the answers
A vertex of a graph that is not an end of any edge is an ______ vertex
A vertex of a graph that is not an end of any edge is an ______ vertex
Signup and view all the answers
A graph that is in one piece, where each vertex can be reached from all other vertices, is called a ______ graph
A graph that is in one piece, where each vertex can be reached from all other vertices, is called a ______ graph
Signup and view all the answers
A graph without any edges is known as a ______ graph
A graph without any edges is known as a ______ graph
Signup and view all the answers
A simple graph with two vertices may have ______ edge or one edge.
A simple graph with two vertices may have ______ edge or one edge.
Signup and view all the answers
Any simple graph with three vertices gives rise to ______ non-isomorphic cases.
Any simple graph with three vertices gives rise to ______ non-isomorphic cases.
Signup and view all the answers
Cyclic Graph Cn = (V, E) (where n > 2) is a graph isomorphic to a graph with V = {v1, v2,..., vn} and E = {{v1, v2}, {v2, v3},..., {vn−1, vn}, {vn, v1}}. Triangle is a cyclic graph with ______ vertices.
Cyclic Graph Cn = (V, E) (where n > 2) is a graph isomorphic to a graph with V = {v1, v2,..., vn} and E = {{v1, v2}, {v2, v3},..., {vn−1, vn}, {vn, v1}}. Triangle is a cyclic graph with ______ vertices.
Signup and view all the answers
The trivial graph is the only graph of order ______.
The trivial graph is the only graph of order ______.
Signup and view all the answers
A graph H = (W, F) is a Subgraph of the graph G = (V, E) if W is a subset of V, and F is a subset of E. Cycle in G - If a subgraph of H of the graph G is a ______ graph.
A graph H = (W, F) is a Subgraph of the graph G = (V, E) if W is a subset of V, and F is a subset of E. Cycle in G - If a subgraph of H of the graph G is a ______ graph.
Signup and view all the answers
Clique in G - A complete subgraph of G. Supergraph of G - Any graph G′ for which a given graph G is a ______.
Clique in G - A complete subgraph of G. Supergraph of G - Any graph G′ for which a given graph G is a ______.
Signup and view all the answers
The spanning subgraph obtained by deleting the edges of F from G is denoted by G − ______.
The spanning subgraph obtained by deleting the edges of F from G is denoted by G − ______.
Signup and view all the answers
If F consists of one edge f, write G − ______.
If F consists of one edge f, write G − ______.
Signup and view all the answers
The graph obtained from G by deleting every vertex in W as well as any edge in E that is adjacent to the vertices in W is denoted by G − ______.
The graph obtained from G by deleting every vertex in W as well as any edge in E that is adjacent to the vertices in W is denoted by G − ______.
Signup and view all the answers
If W consists of a single vertex w, write G − ______.
If W consists of a single vertex w, write G − ______.
Signup and view all the answers
A subgraph G′ of G is a Vertex-Induced Subgraph if there exists a set W of vertices in G such that ⟨W⟩ = ______.
A subgraph G′ of G is a Vertex-Induced Subgraph if there exists a set W of vertices in G such that ⟨W⟩ = ______.
Signup and view all the answers
A subgraph G′ of G is an Edge-Induced Subgraph if there exists a set F of edges in G such that ⟨F⟩ = ______.
A subgraph G′ of G is an Edge-Induced Subgraph if there exists a set F of edges in G such that ⟨F⟩ = ______.
Signup and view all the answers
A vertex v is an isolated vertex if d(v)=0. A vertex v is an end vertex if d(v) = ______
A vertex v is an isolated vertex if d(v)=0. A vertex v is an end vertex if d(v) = ______
Signup and view all the answers
A graph is k-Regular if the degree of each vertex is ______
A graph is k-Regular if the degree of each vertex is ______
Signup and view all the answers
A graph is Regular if there exists a nonnegative integer k that it is ______-regular.
A graph is Regular if there exists a nonnegative integer k that it is ______-regular.
Signup and view all the answers
Conjecture: Given the graph G with size ε ε is the number of edges in G 2ε is the total degree of the vertices in G. A vertex in a graph is an Odd Vertex if the degree is ______
Conjecture: Given the graph G with size ε ε is the number of edges in G 2ε is the total degree of the vertices in G. A vertex in a graph is an Odd Vertex if the degree is ______
Signup and view all the answers
In a digraph, the sum of the outdegrees of all vertices is equal to the number of arcs, which is also equal to the sum of all indegrees of all vertices. Indegree (d−(v)) of that vertex - the number of arcs adjacent to a vertex Outdegree (d+(v)) of that vertex - the number of arcs adjacent from a vertex. This is known as the ______
In a digraph, the sum of the outdegrees of all vertices is equal to the number of arcs, which is also equal to the sum of all indegrees of all vertices. Indegree (d−(v)) of that vertex - the number of arcs adjacent to a vertex Outdegree (d+(v)) of that vertex - the number of arcs adjacent from a vertex. This is known as the ______
Signup and view all the answers
The adjacency matrix of a simple graph is a binary matrix (0, 1) matrix in which each diagonal entry is ______
The adjacency matrix of a simple graph is a binary matrix (0, 1) matrix in which each diagonal entry is ______
Signup and view all the answers
