or each of the classes Ci below determine the smallest n for which Cicontains nonisomorphic n-vertex graphs with the same degree sequence:(a) C1 = { all graphs }, (b) C2 = { loopless graphs }, (c) C3 = { simplegraphs }
Question
or each of the classes Ci below determine the smallest n for which Cicontains nonisomorphic n-vertex graphs with the same degree sequence:(a) C1 = { all graphs }, (b) C2 = { loopless graphs }, (c) C3 = { simplegraphs }
Solution
(a) C1 = { all graphs }: The smallest n for which C1 contains nonisomorphic n-vertex graphs with the same degree sequence is n=3. The two nonisomorphic graphs are the path graph and the cycle graph, both with degree sequence (2, 2, 2).
(b) C2 = { loopless graphs }: The smallest n for which C2 contains nonisomorphic n-vertex graphs with the same degree sequence is n=4. The two nonisomorphic graphs are the path graph and the star graph, both with degree sequence (2, 2, 1, 1).
(c) C3 = { simple graphs }: The smallest n for which C3 contains nonisomorphic n-vertex graphs with the same degree sequence is n=4. The two nonisomorphic graphs are the path graph and the star graph, both with degree sequence (2, 2, 1, 1).
Similar Questions
Which of the following sequences can not be the degree sequence of any graph when the degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order ?I. 7, 6, 5, 4, 4, 3, 2, 1II. 6, 6, 6, 6, 3, 3, 2, 2III. 7, 6, 6, 4, 4, 3, 2, 2IV. 8, 7, 7, 6, 4, 2, 1, 1 OptionsII and IIIII and IVI and IIIII Only
Which of the following statements is not true for isomorphic graphs?a.Number of vertices in both the graphs must be same.b.Number of edges in both the graphs must be same.c.They have n+1 connected componentsd.Degree sequence of both the graphs must be same.
A simple undirected graph with all vertices having the same degree is called:a.Complete graphb.Bipartite graphc.Regular graphd.Eulerian graph
Graph isomorphism is concerned with:A. The number of vertices and edgesB. The degrees of verticesC. The labeling of vertices and edgesD. The structural equivalence of graphs
A graph in which every vertex has the same degree is called a:A. Complete graphB. Cycle graphC. Regular graphD. Bipartite graph
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.