Chapter 10: Q56SE (page 738)
Devise an algorithm for finding the second shortest path between two vertices in a simple connected weighted graph.
It found that the second case may be that it doesn’t exist.
Over 30 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Suppose that\({\bf{G}}\)is a connected multi graph with\({\bf{2k}}\)vertices of odd degree. Show that there exist\({\bf{k}}\)sub graphs that have\({\bf{G}}\)as their union, where each of these subgraphs has an Euler path and where no two of these subgraphs have an edge in common. (Hint: Add\({\bf{k}}\)edges to the graph connecting pairs of vertices of odd degree and use an Euler circuit in this larger graph.)
\(\)
A dominating set of vertices in a simple graph is a set of vertices such that every other vertex is adjacent to at least one vertex of this set. A dominating set with the least number of vertices is called a minimum dominating set. Find a minimum dominating set for the given graph.
Show that if \({\bf{G}}\) is a simple graph with at least 11 vertices, then either \({\bf{G}}\)or\({\bf{\bar G}}\), the complement of \({\bf{G}}\), is non-planar.
The distance between two distinct vertices\({{\bf{v}}_{\bf{1}}}\)and\({{\bf{v}}_{\bf{2}}}\)of a connected simple graph is the length (number of edges) of the shortest path between\({{\bf{v}}_{\bf{1}}}\)and\({{\bf{v}}_{\bf{2}}}\). The radius of a graph is the minimum over all vertices\({\bf{v}}\)of the maximum distance from\({\bf{v}}\)to another vertex. The diameter of a graph is the maximum distance between two distinct vertices. Find the radius and diameter of
a)\({{\bf{K}}_{\bf{6}}}\)
b)\({{\bf{K}}_{{\bf{4,5}}}}\)
c)\({{\bf{Q}}_{\bf{3}}}\)
d)\({{\bf{C}}_{\bf{6}}}\)
Question: Show that \(g\left( n \right) \ge \frac{n}{3}\). (Hint: Consider the polygon with \(3k\) vertices that resembles a comb with \(k\) prongs, such as the polygon with \(15\) sides shown here.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
