Explanation Given information: Assume that n, m and k are all nonnegative integers. Proof: Let G and G ′ be isomorphic graphs and let the graph G contain m simple circuits of length k (with k a positive integer). We then need to show that G ′ has m simple circuits of length k as well. Let V ( G ) be the set of vertices of G and let V ( G ′ ) be the set of vertices of G ′ . Let E ( G ) be the set of edges of G and let E ( G’ ) be the set of edges of G ′ . Since G and G ′ are isomorphic, there exists two one-to-one correspondences Thus G ′ then contains m simple circuits of length k as well and thus having m simple circuits of length k is an invariant for graph isomorphism. g : V ( G ) → V ( G ' ) and h : E ( G ) → E ( G ' ) such that v is an endpoint of e ⇔ g ( v ) is an endpoint of h ( e ) . Let a simple circuit of length k in G be v 1 e 1 v 2 e 2 .... v k e k v 1 with v i ∈ V ( G ) and e i ∈ E ( G ) for i = 1 , 2 , ... , k . This then implies that the walk contains at least one edge and e 1 , e 2 , ... , e k contains no repeated edges and v 1 , v 2 , ... , v k contains no repeated vertices . g ( v 1 ) h ( e 1 ) g ( v 2 ) h ( e 2 ) .... g ( v k ) h ( e k ) g ( v 1 ) is then a walk of length k in G ' , because v is an endpoint of e ⇔ g ( v ) is an endpoint of h ( e )

5th Edition

ISBN: 9780357097717

Author: EPP

Publisher: CENGAGE L

See similar textbooks

Videos

Question

Chapter 10.3, Problem 26ES

To determine

To prove:

Prove that the property (has m simple circuits of length k ) is an invariant for graph isomorphism.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 10.3, Problem 25ES

Chapter 10.3, Problem 27ES

Students have asked these similar questions

Which diagram(s) represent the following relationships An injective function from A to B? A surjective function from A to B? An injective function from B to A? A surjective function from B to A?

int/PlayerHomework.aspx?homeworkId=689099898&questionId=1&flushed=false&cid=8120746¢erw BP Physical Geograph... HW Score: 0%, 0 of 13 points ○ Points: 0 of 1 Determine if the values of the variables listed are solutions of the system of equations. 2x - y = 4 3x+5y= - 6 x=1, y = 2; (1,-2) Is (1, 2) a solution of the system of equations? L No Yes iew an example Get more help - A

Determine if each statement is true or false. If the statement is false, provide a brief explanation: a) There exists x = R such that √x2 = -x. b) Let A = {x = ZIx = 1 (mod 3)} and B = {x = ZIx is odd}. Then A and B are disjoint. c) Let A and B be subsets of a universal set U. If x = A and x/ € A - B,then x = An B.| E d) Let f : RR be defined by f (x) = 1 x + 2 1. Then f is surjective.

Chapter 10 Solutions

DISCRETE MATHEMATICS WITH APPLICATION (

Ch. 10.1 - Let G be a graph and let v and w be vertices in G....Ch. 10.1 - A graph is connected if, any only if, _____.Ch. 10.1 - Removing an edge from a circuit in a graph does...Ch. 10.1 - An Euler circuit in graph is _____.Ch. 10.1 - Prob. 5TY Ch. 10.1 - Prob. 6TY Ch. 10.1 - Prob. 7TY Ch. 10.1 - If a graph G has a Hamiltonian circuit, then G has...Ch. 10.1 - A travelling salesman problem involves finding a...Ch. 10.1 - In the graph below, determine whether the...

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

To prove: Prove that the property (has m simple circuits of length k ) is an invariant for graph isomorphism.

Videos

To prove: Prove that the property (has m simple circuits of length k ) is an invariant for graph isomorphism.

Want to see the full answer?

Chapter 10 Solutions

To prove:

Prove that the property (has m simple circuits of length k ) is an invariant for graph isomorphism.