Home » Subject » Graph Theory
Importance: Low ✭
Author(s):
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: pet_petros
on: December 3rd, 2007
Solved by:
Conjecture   Does there exist graphs $ G $ and $ H $ from Class 1 such that there Cartesian product is from Class 2?

It is known that there are graphs $ G $ and $ H $ which are from Class 2 and their product is from Class 1. Our problem asks the symmetric question. Let us also note that from the classical result of A. Kotzig we imply that there are no regular graphs $ G $ and $ H $ satisfying the conjecture.

2 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options