𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graph isomorphism is in the low hierarchy

✍ Scribed by Uwe Schöning

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
751 KB
Volume
37
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Every Graph Is an Integral Distance Grap
Every Graph Is an Integral Distance Graph in the Plane
✍ Hiroshi Maehara; Katsuhiro Ota; Norihide Tokushige 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 290 KB

We prove that every finite simple graph can be drawn in the plane so that any two vertices have an integral distance if and only if they are adjacent. The proof is constructive.

Remarks on the placeability of isomorphi
Remarks on the placeability of isomorphic trees in a complete graph
✍ Hasunuma, Toru; Shibata, Yukio 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 99 KB 👁 3 views

Let Tp be any tree of order p and A ( T p ) stand for the maximum degree of the vertices of Tp. We prove the following theorem. "If A(Tp) 5 pi, where p > 2i, then Tp is i-placeable in Kp" is true if and only if i = 1, 2, and 3. 0 1996 John Wiley & Sons, Inc. Suppose G is a graph and V ( G ) , E ( G