Necklace enumeration with adjacency restrictions

Summary

Introduction

Let G, H be two finite graphs (possibly with loops but with no multiple edges) having vertex sets V(G), V(H) and edge sets E(G), E(H). An edge joining vertices u and v is denoted by [u, v] and, therefore, a loop at u by [u, u], A function f : V(G) → V(H) is called a homomorphism if it preserves adjacencies, i. e. if [u, v] ∈ E(G) implies [f(u), f(v)] ∈ E(H). The set of all such homomorphisms is denoted by hom(G, H). The set of all one-one homomorphisms from G to itself forms the automorphism group of G denoted by aut(G). It is often desirable to regard f, g ∈ hom(G, H) as equivalent if there exists a ∈ aut(G) such that f = ga. The set of equivalence classes is denoted by hom(G, H)/aut(G).

A colouring of a graph G is a function k : V(G) → C where C is a finite set whose elements are called colours. The following general problem is of some interest: how many colourings of G are there subjec to certain specified adjacency restrictions - i. e. as well as C a matrix B is given with (B)_ij = 1 (or 0) if colour i may (or may not) be adjacent to colour j. Of course, B may be regarded as the adjacency matrix of a graph H. Each colouring of G (subject to the restrictions) corresponds to an element of hom(G, H) and conversely.