Additional material to the paper
"Containment Properties of Product and Power Graphs"

Antonio Fernández, Tom Leighton, José Luis López-Presa

Contents



1  Containment of power graphs

In this section of the paper we refer to this webpage for additional material that helps to verify the following theorem:

Theorem 3: Let G and H be connected graphs such that |G|=|H|, even then Gr ⊆ Hr does not imply G ⊆ H.

1.1  Graphs G and H

The graphs G and H used to prove this theorem are the following:



These graphs have been handled with computer programs. To do so, we have the following files that contain the graphs encodings: graph G and graph H.

1.2  The squares of graphs G and H

From the above graphs G and H, we have obtained the graphs G2 and H2 using a computer program we have named square.

1.3  Finding the mapping

In order to find mappings, we have a computer program we have named subgraph that tries to find a mapping between two given graphs. The program is very naive and uses a brute force approach.

Using this program we have verified that G is not contained in H, and we have found (after several weeks of computation) the following mapping from G2 to H2.

1.4  Verifying the mapping

In order to make sure the mapping found is correct we have also used a computer program we have named verify.

1.5  Programs

The following file programs.zip contains all the source code of the programs and the data files. It contains also a makefile for Unix users.

This document was translated from LATEX by HEVEA.