Partial Profiles of Quasi-Complete Graphs

Pedro Lopes Center for Analysis, Geometry, and Dynamical Systems Department of Mathematics Instituto Superior Técnico University of Lisbon Av. Rovisco Pais 1049-001 Lisbon Portugal

                pelopes@math.tecnico.ulisboa.pt

Abstract We enumerate graph homomorphisms to quasi-complete graphs, i.e., graphs obtained from complete graphs by removing one edge. The source graphs are complete graphs, quasi-complete graphs, cycles, paths, wheels and broken wheels. These enumerations give rise to sequences of integers with two indices; one of the indices is the number of vertices of the source graph, and the other index is the number of vertices of the target graph.

1 Introduction

We believe that the enumeration of graph homomorphisms [8] to a given graph is an interesting problem in itself to which not much attention has been devoted – except perhaps for the chromatic polynomials of a few families of graphs [11]. In this article we take up the task of calculating the numbers of homomorphisms to the so-called quasi-complete graphs, i.e., graphs obtained from complete graphs by removing one edge. We take for source graphs, complete graphs, quasi-complete graphs, paths, cycles, wheels and broken wheels. Specifically, we provide formulas for the numbers of these homomorphisms in terms of the numbers of vertices of source and target graphs.

The availability of such formulas may aid in the characterization and/or the identification of graphs [4], leaning on Lovász’ theorem [10]. Furthermore, it may help supporting or providing counter-examples to the reconstruction conjecture [1]. In fact, “ … the reconstruction conjecture is equivalent to the assertion that it is enough to know all numbers hom(F, G) with |V (F)| < |V (G)| in order to recover the isomorphism type of G.” [1, 1st paragraph, p. 317]. In this context, having a catalog of numbers hom(F, G), for a significant number of pairs of graphs (F, G), could lead to finding a pair of non-isomorphic graphs, G and G′, for which hom(F, G) = hom(F, G′) for all F with |V (F)| < |V (G)|. In this case there would be a counter-example to the reconstruction conjecture. Otherwise, it would be supporting evidence for the conjecture.

We remark that other aspects of graph homomorphisms are currently the object of research. These include, but do not exhaust, topics like extremal issues in graph homomorphisms [9, 2, 3, 7] or the complexity of enumeration of graph homomorphisms [5]. We emphasize that the present contribution is to the exact enumeration of these homomorphisms.

We now recall the definitions of graph, of graph homomorphism, and of other objects used here in order to develop the notation and the terminology. A graph is a finite set of points, called vertices, along with a set of unordered pairs of distinct vertices, called edges. If there is an edge joining vertices i and j, it is denoted ij. In this case, we say that vertices i and j are adjacent. A graph is denoted by capital letters G or H. The set of vertices of graph G is denoted V (G) and the set of edges of G is denoted E(G). A homomorphism, f, from a graph G to a graph H, is a map from V (G) to V (H) which preserves adjacency, i.e., whenever ij is an edge of G, f(i)f(j) is an edge of H [8]. The set of homomorphisms from G to H is denoted Hom(G, H) and its cardinality hom(G, H). Also, bij(G, H), sur(G, H) and inj(G, H) denote the cardinality of the bijective homomorphisms, the surjective homomorphisms and the injective homomorphisms of Hom(G, H).

Let (H_{1}, H_{2}, H_{3}, …) be a fixed sequence of all non-isomorphic graphs. Given a graph G, the profile of G (or Lovász vector of G) is the sequence of non-negative integers (n_{1}, n_{2}, n_{3}, …), where n_{i} = hom(H_{i}, G). Lovász [10] introduced the profile of a graph in order to prove that graphs with the same profile are isomorphic modulo twins. We use the term partial profile of a given graph since we only calculate a subsequence (albeit infinite) of the n_{i}’s.

For each graph G, the chromatic polynomial of G, χ_{G}(m), is the number of homomorphisms from G to the complete graph, K_{m}, for each m greater than or equal to the chromatic number of G, χ_{G}(m) = hom(G, K_{m}) [11]. As such, all the known chromatic polynomials evaluated at a specific positive integer m, provide a partial profile of the complete graph K_{m}.

The rest of this article is organized as follows. In Section 2 we prove the formulas we obtained for the numbers of graph homomorphisms. The target graphs are always quasicomplete graphs; except for Subsection 2.3, each subsection in Section 2 is devoted to a particular kind for source graph. In Subsection 2.3 we provide auxiliary formulas to help in the calculations of the subsequent enumerations. In Section 3 we formulate a few questions for future work. In Section 4 we acknowledge our financial sponsors, hosts, and colleagues.

2 Counting homomorphisms to quasi-complete graphs

For any integer m ≥ 3, we let K_{m} denote the complete graph on m vertices, i.e., the graph on m vertices such that any two vertices are adjacent. For any integer m ≥ 3, we define the quasi-complete graph on m vertices to be the graph obtained from K_{m} by removing one edge. We denote it K_{m}^{1}. Furthermore, the edge that has been removed in order to obtain it from K_{m} is referred to as the exceptional edge. The vertices which make up this edge are denoted A and B throughout the article.

In this section, we obtain formulas for calculating the numbers of homomorphisms into quasi-complete graphs from certain graphs in terms of the numbers of vertices. Except for Subsection 2.3, the title of each subsection identifies which class of graphs is being used as source graph.

2.1 The source graphs are complete graphs

Proposition 1. For integers n ≥ 3, m ≥ 3,

hom(K_{n}, K_{m}^{1}) = \begin{cases}0, & if n ≥ m; \\ (m − 1)! · 2, & if n = m − 1; \\ n!\binom{m−2}{n−1} · 2 + \binom{m−2}{n}n!, & if n ≤ m − 2. \end{cases}

In particular,

hom(K_{n}, K_{m}^{1}) = inj(K_{n}, K_{m}^{1}), sur(K_{n}, K_{m}^{1}) = bij(K_{n}, K_{m}^{1}) = 0,

for all n ≤ m − 1.

Proof. Homomorphisms from complete graphs to any given graph are one-to-one since any two vertices in a complete graph are adjacent. In this way, if n > m, then, there are no homomorphisms from K_{n} to K_{m}^{1}.

If n = m, then any one-to-one map from K_{n} to K_{m}^{1} has to send distinct vertices of K_{n} to the vertices of the exceptional edge of K_{m}^{1}, thereby mapping adjacent vertices to non-adjacent vertices. Again, there are no homomorphisms in this case.

If n = m − 1, then the image of a homomorphism cannot contain both vertices of the exceptional edge as pointed out above. On the other hand, it has to contain at least one of these two vertices, for otherwise there would not be enough vertices in the image. The problem is then reduced to distribute the n vertices of K_{n}, in a one-to-one fashion, over the m − 1(= n) vertices of K_{m}^{1} which contain exactly one of the vertices of the exceptional edge, or over those that contain the other vertex of the exceptional edge. This is

n! · 2 = (m − 1)! · 2.

Now, for n < m−1. As in the preceding case, the image of a homomorphism may contain exactly one vertex of the exceptional edge. In this case, after selecting one of the vertices from the exceptional edge, the n vertices of K_{n} are distributed over a subset of n vertices from the set of m−1 vertices of K_{m}^{1} which contain the selected vertex of the exceptional edge (but not the other one). Then, one of the vertices of K_{n} has to be mapped to this vertex (n possibilities). The remaining n − 1 vertices of K_{n} have to be mapped, in a one-to-one fashion, to the vertices of K_{m}^{1} but the vertices of the exceptional edge, to ensure adjacency is preserved (\binom{m−2}{n−1}(n − 1)! possibilities). The other vertex of the exceptional edge is then selected and the preceding reasoning is repeated yielding

2n\binom{m − 2}{n − 1}(n − 1)! = 2n!\binom{m − 2}{n − 1}.

Since n < m − 1, it is still possible to construct homomorphisms whose image do not contain either of the vertices of the exceptional edge. In this case, the n vertices of K_{n} are mapped in a one-to-one fashion to the m − 2 vertices of K_{m}^{1}, except the vertices from the exceptional edge. There are

\binom{m − 2}{n}n!

such possibilities.

Clearly, the numbers inj(K_{n}, K_{m}^{1}) coincide with the numbers hom(K_{n}, K_{m}^{1}) since the source graphs are complete graphs. For the same reason, sur(K_{n}, K_{m}^{1}) = bij(K_{n}, K_{m}^{1}) = 0.

2.2 The source graphs are quasi-complete graphs

Proposition 2. For integers n ≥ 3, m ≥ 3,

hom(K_{n}^{1}, K_{m}^{1}) = \begin{cases}0, & if n ≥ m + 1; \\ 2(n − 1)! + 2(n − 2)!, & if m = n; \\ \frac{2(m − 2)!}{(m − n)!} + \frac{(2(n − 1) + 3)(m − 2)!}{(m − n − 1)!} + \frac{(m − 2)!}{(m − n − 2)!}, & if m > n. \end{cases}

Also,

bij(K_{n}^{1}, K_{n}^{1}) = sur(K_{n}^{1}, K_{n}^{1}) = inj(K_{n}^{1}, K_{n}^{1}) = (n − 2)!2,

and

inj(K_{n}^{1}, K_{m}^{1})

= \frac{2(m − 2)!}{(m − n)!} + \frac{2(n − 1)(m − 2)!(m − n − 1)}{(m − n)!} + \frac{2(m − 2)!}{(m − n − 1)!} + \frac{(m − 2)!}{(m − n − 2)!}, m > n,

and

bij(K_{n}^{1}, K_{m}^{1}) = sur(K_{n}^{1}, K_{m}^{1}) = 0, for m > n.

Proof. We regard K_{n}^{1} as consisting of K_{n−1} formed by vertices 1, 2, …, n − 1 and then adjoining vertex n making it adjacent to all other vertices but 1. Concerning K_{m}^{1}, we denote the vertices of the exceptional edge A and B.

Any homomorphism from K_{n}^{1} to K_{m}^{1} has to map the K_{n−1} in K_{n}^{1} to a complete subgraph of K_{m}^{1} with n−1 vertices. It follows that, if n−1 > m−1, i.e., if n > m, then hom(K_{n}^{1}, K_{m}^{1}) = 0.

If m = n, then there are two complete subgraphs of K_{m}^{1} with n − 1 vertices, one containing vertex A, and the other one containing vertex B. It follows that the image of each homomorphism, in this m = n case, has to involve at least one of A and B.

The homomorphisms that involve both have to map 1 to A and n to B, or 1 to B and n to A. The other n − 2 vertices are permuted among the n − 2 vertices of K_{m}^{1} other than A and B. So the homomorphisms that involve both A and B, i.e., the bijective ones, are

bij(K_{n}^{1}, K_{n}^{1}) = sur(K_{n}^{1}, K_{n}^{1}) = inj(K_{n}^{1}, K_{n}^{1}) = (n − 2)!2.

Now, for the homomorphisms that involve exactly one of A or B. The K_{n−1} of K_{n}^{1} is mapped to either one of the two complete subgraphs of K_{m}^{1} with n − 1 vertices mentioned above, and vertex n is mapped to the same vertex 1 is mapped to. These are (n − 1)!2. Then,

hom(K_{n}^{1}, K_{n}^{1}) = (n − 1)!2 + (n − 2)!2.

Now, suppose n < m. Besides homomorphisms involving both A and B, and homomorphisms involving either A or B (exclusively), there are now homomorphisms which do not involve A or B.

The ones that involve both A and B are injective. Also, 1 is mapped to A and n is mapped to B, or 1 is mapped to B and n is mapped to A, while the remaining n − 2 vertices are permuted over the m − 2 vertices of K_{m}^{1} other than A and B. These are, then,

2\binom{m − 2}{n − 2}(n − 2)!.

Now, for the homomorphisms that involve exactly A or B. One of the n vertices has to be mapped to A (respect., B, and for this reason there will be an overall 2 factor). Consider the vertices 1, 2, …, n − 1 forming the K_{n−1} in K_{n}^{1}. One of these is mapped to A (n − 1 possibilities). Then the remaining n − 2 vertices of K_{n−1} are distributed over n − 2 of m − 2 vertices of K_{m}^{1} (other than A and B). Finally, vertex n can either be mapped to the vertex 1 has been mapped to, or to one of the remaining m − 2 − (n − 1) = m − n − 1 vertices of K_{m}^{1} (these latter homomorphisms are injective). If vertex n is mapped to A, then vertex 1 is not mapped to A (this situation has already been contemplated) and the remaining n − 1 vertices of K_{n}, including vertex 1, are distributed over the remaining m − 2 vertices of K_{m}^{1}. Thus,

2(n − 1)\binom{m − 2}{n − 2}(n − 2)!(1 + (m − n − 1)) + 2\binom{m − 2}{n − 1}(n − 1)!

is the number of homomorphisms that involve exactly one of A or B. The injective homomorphisms among these are

2(n − 1)\binom{m − 2}{n − 2}(n − 2)!(m − n − 1) + 2\binom{m − 2}{n − 1}(n − 1)!.

Finally, those that do not involve A nor B are

\binom{m − 2}{n}n! + \binom{m − 2}{n − 1}(n − 1)!,

where the left summand counts the injective ones of these homomorphisms, and the right summand counts the homomorphisms which map 1 and n to the same vertex. Then, for n < m,

inj(K_{n}^{1}, K_{m}^{1})

= 2\binom{m − 2}{n − 2}(n−2)!+2(n−1)\binom{m − 2}{n − 2}(n−2)!(m−n−1)+2\binom{m − 2}{n − 1}(n−1)!+\binom{m − 2}{n}n!,

and

hom(K_{n}^{1}, K_{m}^{1}) = 2\binom{m − 2}{n − 2}(n − 2)! + 2(n − 1)\binom{m − 2}{n − 2}(n − 2)!(m − n)

+ 2\binom{m − 2}{n − 1}(n − 1)! + \binom{m − 2}{n}n! + \binom{m − 2}{n − 1}(n − 1)!.

The proof is complete.

2.3 Auxiliary material

This section is intended as auxiliary material for the understanding of the proofs of Propositions 5 and 6.

Definition 3. For each integer i ≥ 1, we define the (directed) graph G_{i} as follows. The vertices of G_{i} are 0’s and 1’s. The vertices are drawn on different levels and the levels are displayed vertically; higher levels are drawn below lower levels. The graph G_{i} has i levels, 1, 2, …, i. The first level is the top level, the last level is the bottom level, the other levels are the intermediate levels. The first level has only one vertex, a 0. Likewise, the last level has only one vertex, a 0. The edges connect vertices on consecutive levels only and are directed from top to bottom (and this is why we omit the arrows on the edges). Graph G_{1} is formed by only one vertex, a 0; graph G_{2} is formed by two vertices (two 0’s) and an edge connecting them (see Figure 1). For i > 2, graph G_{i} is constructed in the following way. For each 1 < j < i, each vertex on level j is the endpoint of exactly one edge stemming from level j − 1. Up to and including level i − 2, from each 0 stems an edge to a 0, and an edge to a 1, whereas from each 1 stems only one edge to a 0. From each vertex on level i − 1 stems one edge to the vertex, 0, on the bottom level. Graph G_{3} is depicted in Figure 1. It has three levels, the first one with a 0, the second one with a 0 and a 1, and the third one with one 0. See also Figure 2 for graphs G_{4} and G_{5}.

Definition 4. Leaning on the definition of the directed graphs G_{i}, see Definition 3 above, we now define polynomials on a variable m, the p_{i}(m) and the q_{i}(m). By definition,

p_{0} ≡ 1, q_{0} ≡ 1.

For integer i ≥ 1, the p_{i} and q_{i} are to be read off the corresponding graph G_{i} as follows. Fix integer i ≥ 1. Each (maximal) directed path on G_{i} (with respect to the number of vertices), starting at the 0 on the top level and ending at the 0 on the bottom level, gives rise to a summand of p_{i} (respect., q_{i}), formed by the product of i factors among 2, (m − 2), and (m − 3) (respect., 2, (m − 2), (m − 3), and (m − 1)). Some of these factors may be missing or may be repeated in a given summand.

The 0 on the top level stands for an (m − 2) factor. Each 1 stands for a 2 factor. A 0 stemming from a 1 stands always for an (m − 2) factor. A 0 on any intermediate level and stemming from a 0 stands for an (m−3) factor; on the bottom level, it stands for an (m−3) for p_{i}, whereas it stands for an (m − 1) for the q_{i}. So, for each directed path starting at the 0 on the top level and ending at the 0 on the bottom level, the 0’s and the 1’s stand for the indicated factors, and the edges of the path are to be considered as an instruction for multiplying the factors connected by the edges.

The sum of these products over all maximal directed paths of G_{i}, starting at the top 0 and ending at the bottom 0, yields the p_{i} (respect., q_{i}).

Here are some examples:

p_{1}(m) = m − 2, q_{1}(m) = m − 2;
p_{2}(m) = (m − 2)(m − 3), q_{2}(m) = (m − 2)(m − 1);

p_{3}(m) = (m − 2)(m − 3)(m − 3) + (m − 2)2(m − 2),
q_{3}(m) = (m − 2)(m − 3)(m − 1) + (m − 2)2(m − 2);

p_{4}(m) = (m − 2)(m − 3)(m − 3)(m − 3) + (m − 2)(m − 3)2(m − 2) + (m − 2)2(m − 2)(m − 3),

q_{4}(m) = (m − 2)(m − 3)(m − 3)(m − 1) + (m − 2)(m − 3)2(m − 2) + (m − 2)2(m − 2); p_{5}(m) = (m − 2)(m − 3)(m − 3)(m − 3)(m − 3) + (m − 2)(m − 3)(m − 3)2(m − 2)+ +(m−2)(m−3)2(m−2)(m−3)+(m−2)2(m−2)(m−3)(m−3)+(m−2)2(m−2)2(m−2),

q_{5}(m) = (m − 2)(m − 3)(m − 3)(m − 3)(m − 1) + (m − 2)(m − 3)(m − 3)2(m − 2)+ +(m−2)(m−3)2(m−2)(m−1)+(m−2)2(m−2)(m−3)(m−1)+(m−2)2(m−2)2(m−2).

PSfrag replacements

0 1

Figure 1: Graphs G_{1} (left), G_{2} (middle), and G_{3} (right).

PSfrag replacements

0 1

Figure 2: Graphs G_{4} (left), and G_{5} (right).

2.4 The source graphs are paths

Let n be an integer greater than 1. We remark that a path on n vertices, denoted P_{n}, is a graph with vertices 0, 1, …, n − 1 and edges 01, 12, …, (n − 2)(n − 1).

Proposition 5. For integers n ≥ 2, m ≥ 3,

hom(P_{n}, K_{m}^{1}) = m(m − 1)^{n−1} − ∑_{k=1}^{n−1} s_{n,m}^{k},

where

s_{n,m}^{n−1} = 2,

and, for 1 ≤ k ≤ n − 2,

s_{n,m}^{k} = \frac{1}{2} ∑_{\begin{matrix}\{0=i_{1}<i_{2}<···<i_{k}=n−2\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)]

+ ∑_{\begin{matrix}\{0=i_{1}<i_{2}<···<i_{k}<n−2\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)] · q_{n−2−i_{k}}(m)

+ ∑_{\begin{matrix}\{0<i_{1}<i_{2}<···<i_{k}=n−2\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}} q_{i_{1}}(m) · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)]

+ 2 ∑_{\begin{matrix}\{0<i_{1}<i_{2}<···<i_{k}<n−2\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}} q_{i_{1}}(m) · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)] · q_{n−2−i_{k}}(m),

and the p_{i}’s and q_{i}’s are the polynomials introduced in Definition 4.

Proof. We begin by noting that any homomorphism in Hom(P_{n}, K_{m}^{1}) can be regarded as a homomorphism in Hom(P_{n}, K_{m}). On the other hand, the homomorphisms of Hom(P_{n}, K_{m}) which cannot be regarded as homomorphisms from Hom(P_{n}, K_{m}^{1}), are exactly those that map adjacent vertices of P_{n} to the vertices of the exceptional edge. In this way,

hom(P_{n}, K_{m}^{1}) = hom(P_{n}, K_{m}) − s_{n,m} = m(m − 1)^{n−1} − s_{n,m},

since hom(P_{n}, K_{m}) is the chromatic polynomial of P_{n},

hom(P_{n}, K_{m}) = χ_{P_{n}}(m) = m(m − 1)^{n−1}

[11, eq. (1.9), p. 3], and where s_{n,m} is the cardinality of the set

{f ∈ Hom(P_{n}, K_{m}) | f maps adjacent vertices to the vertices of the exceptional edge.}.

Note further that s_{n,m} = ∑_{k=1}^{n−1} s_{n,m}^{k}, where s_{n,m}^{k} is the cardinality of the set

{f ∈ Hom(P_{n}, K_{m}) | f maps exactly k pairs of adjacent vertices to the vertices of the exceptional edge.}.

We will now prove that s_{n,m}^{k} is given by the expression in the statement. We label vertices in P_{n} 0, 1, …, n − 1 in such a way that the edges are 01, 12, …, (i − 1)i, …, (n − 2)(n − 1). Let A and B be the vertices of the exceptional edge in K_{m}. In order to specify that exactly k pairs of adjacent vertices of P_{n} are mapped to the pair A, B in a given homomorphism, we specify the lowest vertex of each pair of these adjacent vertices. In this way, the sequence

(0 ≤)i_{1} < i_{2} < ⋯ < i_{k}(≤ n − 2)

corresponds to the mapping of each pair of the k adjacent vertices i_{1}(i_{1} + 1), i_{2}(i_{2} + 1), ... , i_{k}(i_{k}+1) injectively into the pair of adjacent vertices, A and B. See Figure 3 for an illustrative example. It depicts the graph P_{11} together with information turning it into a representative of certain homomorphisms in Hom(P_{11}, K_{m}) \ Hom(P_{11}, K_{m}^{1}). These homomorphisms map the vertices in full to the exceptional vertices A, B. Specifically, vertices 0, 1; 3, 4, 5; and 8, 9 are mapped in pairs injectively into A, B. The associated sequence of i_{j}’s is: i_{1} = 0, i_{2} = 3, i_{3} = 4, i_{4} = 8.

PSfrag replacements

0 = i_{1}

1 2 3 = i_{2}

4 = i_{3}

5 6 7 8 = i_{4}

9 10 …

Figure 3: Graph P_{11} together with an assignment to the vertices of the exceptional edge.

Note that i_{j} −i_{j−1} ≠ 2 for j = 2, …, k. In fact, if i_{j_{0}} −i_{j_{0}−1} = 2, then assume i_{j_{0}−1} and i_{j_{0}} are mapped to the same element of {A, B}. Then, i_{j_{0}−1} + 1 is mapped to the other element of {A, B}, in this way contributing with another pair of adjacent vertices, i_{j_{0}−1} +1, i_{j_{0}}, being mapped to A, B, thereby increasing the number of the pairs of these vertices to k + 1, which contradicts the assumption. Assume now i_{j_{0}−1} and i_{j_{0}} are mapped to distinct elements of {A, B}. In this case, i_{j_{0}−1} + 1 has to be mapped to one of them, thereby contradicting preservation of adjacency.

Given a sequence of k pairs being mapped to vertices A and B via their sequence of lower vertices, say

(0 ≤)i_{1} < i_{2} < ⋯ < i_{k}(≤ n − 2),

and i_{j} − i_{j−1} ≠ 2 for j = 2, …, k, we call cluster each maximal subsequence of the latter sequence with respect to the property that each two consecutive terms of the subsequence differ by 1 , i.e., i_{j_{r}} −i_{j_{r}−1} = 1, together with the vertex next to the last term of the maximal subsequence at issue. That is, if i_{j_{0}}, i_{j_{0}} +1, i_{j_{0}} +2, …, i_{j_{0}} +m−1 is such a maximal sequence, then the cluster it gives rise to is i_{j_{0}}, i_{j_{0}} + 1, i_{j_{0}} + 2, …, i_{j_{0}} + m − 1, i_{j_{0}} + m. In the situation depicted in Figure 3 there are 3 maximal sequences: 0; 3, 4; and 8. These give rise to the clusters 0, 1; 3, 4, 5; and 8, 9, respectively.

There are two possible ways of mapping the elements of a cluster, say i_{j_{0}}, i_{j_{0}} + 1, i_{j_{0}} + 2, …, i_{j_{0}} + m, to A and B. Either

i_{j_{0}} ↦ A,  (i_{j_{0}} + 1) ↦ B,  (i_{j_{0}} + 2) ↦ A,  (i_{j_{0}} + 3) ↦ B, …

or

i_{j_{0}} ↦ B,  (i_{j_{0}} + 1) ↦ A,  (i_{j_{0}} + 2) ↦ B,  (i_{j_{0}} + 3) ↦ A, …

Now, assume i_{j_{0}}, i_{j_{0}} + 1, i_{j_{0}} + 2, …, i_{j_{0}} + m and i_{j′_{0}}, i_{j′_{0}} + 1, i_{j′_{0}} + 2, …, i_{j′_{0}} + m′ are two consecutive clusters with i_{j_{0}} + m < i_{j′_{0}}. We call gap the sequence i_{j_{0}} + m + 1 < i_{j_{0}} + m + 2 < ⋯ < i_{j′_{0}} − 1 that lies between consecutive clusters. Should i_{1} > 0, we also call gap the sequence of vertices right before the first cluster, 0, …, i_{1} − 1 . Should i_{k} < n − 2, we also call gap the sequence of vertices right after the last cluster, i_{k} + 2, …, n − 1. In the situation depicted in Figure 3 there are three gaps: 2; 6, 7; and 10.

Then, for each homomorphism from P_{n} to K_{m} that maps exactly k pairs of adjacent vertices into the vertices A and B, there is a sequence of lower vertices as explained above. This sequence gives rise to clusters and gaps. Specifically, the sequence of lower vertices induces a partition of P_{n} into clusters and gaps. We already saw that there are two ways of mapping the vertices in a cluster to A and B. Then, for each cluster, there is a factor of two in the enumeration of these homomorphisms. We now analyze the contribution of the gaps to the counting.

Suppose a gap only has one vertex. Then, this vertex cannot be mapped either to A or to B, for otherwise it would either increase the number of adjacent vertices being mapped to A and B, or it would contradict the preservation of adjacency. This vertex can, then, be mapped to one in m − 2 vertices in K_{m}.

We, now, consider gaps nested between two consecutive clusters. Later, we will consider gaps which make contact with only one cluster: 0, 1, …, i_{1} − 1, when i_{1} > 0, and/or i_{k} + 2, …, n − 1, when i_{k} < n − 2.

Suppose a gap has two elements, say g_{1} < g_{2}. Then, g_{1} cannot be mapped to either A or B, for otherwise it would be included in the cluster preceding it. So, g_{1} can be mapped to one in m − 2 vertices. Then, g_{2} cannot be mapped to the vertex g_{1} has been mapped to, and it also cannot be mapped to A or to B. But it can be mapped to one in m − 3 vertices. The contribution of a two element gap is, then, (m − 2)(m − 3).

Suppose a gap has three elements, say g_{1} < g_{2} < g_{3}. As discussed before, g_{1} and g_{3} cannot be mapped to A or to B. But g_{2} can be mapped to A or to B. Note, however, that if g_{2} is not mapped either to A or to B then g_{3} cannot be mapped also to the vertex g_{2} has been mapped to, whereas if g_{2} has been mapped to A or to B then g_{3} can be mapped to all vertices but A or B. In this way the contribution for the number of homomorphisms from a gap with three elements is (m − 2)2(m − 2) + (m − 2)(m − 3)(m − 3).

Suppose a gap has four elements, g_{1} < g_{2} < g_{3} < g_{4}. We believe this will illustrate what happens in the general case. As above, g_{1} and g_{4} cannot be mapped to A or to B. If g_{2} is mapped to A or to B (2 possibilities), then g_{3} can be mapped to any but A or B (m − 2 possibilities) and, then, g_{4} cannot be mapped to the vertex g_{3} has been mapped to, nor to A nor to B (m − 3 possibilities). In this case, we have (m − 2)2(m − 2)(m − 3). If g_{2} is not mapped to A nor to B, nor to the vertex g_{1} has been mapped to (m−3 possibilities), then g_{3} can be mapped to A or to B (2 possibilities), in which case g_{4} can be mapped to any but A or B (m − 2 possibilities). In this case, we have (m − 2)(m − 3)2(m − 2). Finally, if g_{2} is not mapped to A nor to B, nor to the vertex g_{1} has been mapped to (m − 3 possibilities), and g_{3} is not mapped to A nor B, nor the vertex g_{2} has been mapped to (m−3 possibilities), then g_{4} has only m − 3 possibilities. In this case, we have (m − 2)(m − 3)(m − 3)(m − 3) possibilities.

The contribution for the number of homomorphisms from a gap with four elements is, then, (m − 2)2(m − 2)(m − 3) + (m − 2)(m − 3)2(m − 2) + (m − 2)(m − 3)(m − 3)(m − 3).

0

\begin{cases}0 \\ 1 \end{cases}

i_{j−1} i_{j−1} + 1

i_{j} g_{1} g_{2} g_{3} g_{4} g_{l−1} g_{l} …

Figure 4: l vertices between i_{j−1} + 1 and i_{j}.

Figure 4 now illustrates the general case. We distinguish two sorts of assignments for each vertex of a gap (designated g′_{j}s). Either the vertex is assigned to one of A or B (the “1” assignment), or the vertex is not assigned to A or to B (the “0” assignment). Then 0’s are always associated to the first and last vertices of a gap, g_{1} and g_{l}. The other vertices of the gap can, however, have both 0 or 1 assignments. Let us now see how these assignments contribute to the counting of homomorphisms that map exactly k pairs of adjacent vertices to A and B. The first vertex of the gap can be mapped to one of m−2 vertices since it cannot be mapped to A or to B. Then, g_{2} either receives a type 1 assignment (2 possibilities), or a type 0 assignment (m − 3 possibilities). Then, the possibilities for g_{3} are as follows. If g_{2} received a 1 assignment, then g_{3} has to receive a 0 assignment with m − 2 possibilities. If g_{2} received a 0 assignment, then g_{3} can receive either one of the two types of assignments: if g_{3} receives a type 1 assignment there are 2 possibilities; if g_{3} receives a type 0 assignment there are m − 3 possibilities. So from 1’s stem 0’s with m − 2 possibilities. From 0’s stem either 0’s with m − 3 possibilities or 1’s with 2 possibilities. Note that the product of these factors gives the summands of the polynomial p_{l}(m) (see Definition 4) from the graph G_{l} (see Definition 3). More precisely, each choice of 0 or 1 at each vertex of the gap, subject to the first and the last being assigned 0’s, yields a maximal path in the graph G_{l} which gives rise to the corresponding summand of the p_{l}(m) polynomial. Then p_{l}(m) yields all the possible contributions of the gap with l vertices to the homomorphisms being enumerated.

Finally, recall that each homomorphism with exactly k pairs of adjacent vertices being mapped to the adjacent vertices A and B corresponds to a sequence of lower vertices

(0 ≤)i_{1} < i_{2} < ⋯ < i_{k}(≤ n − 2),

with i_{j} − i_{j−1} ≠ 2 for j = 2, …, k. Then each gap nested between two clusters corresponds to a j such that i_{j} − i_{j−1} > 2 for some j = 2, …, k. The p_{l}(m) polynomial corresponding to this gap has l = i_{j} − i_{j−1} − 2.

Notwithstanding, the gaps may not be nested between two consecutive clusters. Consider the case i_{k} < n − 2. There will be a gap of n − 2 − i_{k} vertices with a cluster to its left but no cluster to its right. For this particular gap, the counting of possibilities is yielded by q_{n−2−i_{k}}(m), where the q_{l}(m)’s are the polynomials introduced in Definition 4. In fact, the attribution of possibilities to the vertices of this gap is the same as for the other gaps, except for the last vertex of this gap, vertex n − 1. Since there is no cluster next to this vertex, then the possibilities attributed to it are either m − 1, if the preceding vertex has had a 0 assignment, or m−2, if the preceding vertex has had a 1 assignment. An analogous situation occurs for i_{1} > 0. In this case, the counting of the possibilities is yielded by q_{i_{1}}(m). In the expression for s_{n,m}^{k} below, we single out the instances where these latter gaps occur.

Then,

s_{n,m}^{n−1} = 2

since in this k = n − 1 situation there is only one cluster (which involves all the vertices of the path P_{n}) and there is no gap. For 1 ≤ k ≤ n − 2,

s_{n,m}^{k} = \frac{1}{2} ∑_{\begin{matrix}\{0=i_{1}<i_{2}<···<i_{k}=n−2\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)]

+ ∑_{\begin{matrix}\{0=i_{1}<i_{2}<···<i_{k}<n−2\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)] · q_{n−2−i_{k}}(m)

+ ∑_{\begin{matrix}\{0<i_{1}<i_{2}<···<i_{k}=n−2\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}} q_{i_{1}}(m) · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)]

+ 2 ∑_{\begin{matrix}\{0<i_{1}<i_{2}<···<i_{k}<n−2\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}} q_{i_{1}}(m) · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)] · q_{n−2−i_{k}}(m),

and the p_{i}’s and q_{i}’s are the polynomials introduced in Definition 4. A 2 right before a p polynomial stands for the two possibilities for the cluster right before (or right after) the gap the p polynomial stands for. The \frac{1}{2} in the first summand above and the 2 factor before the last summand above stand for corrections to these enumerations of gaps when, respectively, each gap is nested between two consecutive clusters, and when there are exactly two gaps which are not nested between two consecutive clusters.

This completes the proof.

2.5 The source graphs are cycles

We remark that a cycle on n vertices, denoted C_{n}, is a graph with vertices 0, 1, …, n − 1 and edges 01, 12, …, (n − 2)(n − 1), (n − 1)0. We take n ≥ 4 for C_{3} is isomorphic with K_{3}.

Proposition 6. For integers n ≥ 4, m ≥ 3,

hom(C_{n}, K_{m}^{1}) = (m − 1)((m − 1)^{n−1} + (−1)^{n}) − ∑_{k=1}^{n} t_{n,m}^{k},

where

t_{n,m}^{n} = 2,  if n is even,
t_{n,m}^{n} = 0,  if n is odd,
t_{n,m}^{n−1} = 0,

and, for 1 ≤ k ≤ n − 2,

t_{n,m}^{k} = ∑_{\begin{matrix}\{0=i_{1}<i_{2}<···<i_{k}=n−1\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)]

+ ∑_{\begin{matrix}\{0=i_{1}<i_{2}<···<i_{k}<n−2\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)] · 2p_{n−i_{k}−2}(m)

+ ∑_{\begin{matrix}\{1<i_{1}<i_{2}<···<i_{k}=n−1\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}} 2p_{i_{1}}(m) · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)]

+ ∑_{\begin{matrix}\{0<i_{1}<i_{2}<···<i_{k}<n−1\} \\ s.t. i_{j}−i_{j−1}≠2 \end{matrix}} 2p_{i_{1}+n−i_{k}−2}(m) · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}>2 \\ 2≤j≤k \end{matrix}} 2 p_{i_{j}−i_{j−1}−2}(m)],

and the p_{i}’s are the polynomials introduced in Definition 4.

Proof. The proof is similar to that of Proposition 5 and will be largely omitted. We remark that

Hom(C_{n}, K_{m}) = χ_{C_{n}}(m) = (m − 1)((m − 1)^{n−1} + (−1)^{n})

[11, eq. (1.13), p. 7].

Observing that Hom(C_{n}, K_{m}^{1}) embeds in Hom(C_{n}, K_{m}), we just have to enumerate the homomorphisms from the latter set which are not from the former set; we denote these t_{n,m}. As before, we obtain t_{n,m} by counting those homomorphisms that map exactly k pairs of adjacent vertices in C_{n} to K_{m}, and, then, adding over k, t_{n,m} = ∑_{k=1}^{n} t_{n,m}^{k}.

The notion of cluster, here, has to be somewhat specialized to encompass the cases of k pairs of vertices with i_{1} = 0 and i_{k} = n − 1. In these situations, the maximal subsequence starting at i_{1} = 0 merges with the maximal subsequence ending at i_{k} = n − 1, forming only one cluster. Especially, when there is only one cluster and there are vertices of the cycle, C_{n}, which are not part of the cluster, then we call gap the set of these vertices. Note that this gap is nested inside the only cluster.

If n is even, then there is a cluster without gaps for k = n; this cluster involves all the vertices in the cycle C_{n}. If n is odd, there is no such situation for otherwise adjacency would be violated. If k = n − 1, then t_{n,m}^{k} = 0 for the pair of vertices apparently left out would contribute another pair of vertices or violate adjacency.

For 1 ≤ k < n − 1, each gap is nested between two clusters or nested inside one cluster (when there is only one cluster and only one gap).

Concerning the homomorphisms in Hom(C_{n}, K_{m})\Hom(C_{n}, K_{m}^{1}), clusters can be mapped in one of two ways and the mappings of gaps are ruled by the graphs introduced in Definition 3 in conjunction with the polynomials p_{l}(m) introduced in Definition 4 (l is the number of the vertices in the gap at issue).

We leave the remaining details to the reader.

Corollary 7. For integer n′ ≥ 2,

hom(C_{2n′+1}, K_{3}^{1}) = 0.

Proof. The homomorphic image of a cycle on an odd number of vertices is a cycle [8]. Since there is no cycle in K_{3}^{1}, this concludes the proof.

2.6 The source graphs are broken wheels

Let n be an integer, n ≥ 3. We remark that a broken wheel on n spokes, denoted BW_{n}, is a graph with n + 1 vertices, formed by a path on n vertices plus an extra vertex, called the hub, which is adjacent to every other vertex. The hub is denoted 0 and the other vertices 1, 2, …, n; the edges are 01, 02, 03, …, 0n (the spokes) and 12, 23, 34, …, (n − 1)n.

Proposition 8. For integers n ≥ 3, m ≥ 3,

hom(BW_{n}, K_{m}^{1}) = m(m − 1)(m − 2)^{n−1} − ∑_{k=1}^{n−1} u_{n,m}^{k},

where

u_{n,m}^{k} = u_{n,m}^{k,0} + u_{n,m}^{k,1},

and, keeping the notation of Proposition 5,

u_{n,m}^{k,0} = (m − 2)s_{n,m−1}^{k} 1 ≤ k ≤ n − 1,

and, for 1 ≤ k ≤ ⌈n/2⌉,

u_{n,m}^{k,1} = 2 ∑_{\begin{matrix}\{1=i_{1}<i_{2}<i_{3}<···<i_{k}=n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}]

+ 2 ∑_{\begin{matrix}\{1<i_{1}<i_{2}<i_{3}<···<i_{k}=n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{1}−2} · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}]

+ 2 ∑_{\begin{matrix}\{1=i_{1}<i_{2}<i_{3}<···<i_{k}<n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}] · (m − 2)(m − 3)^{n−i_{k}−1}

+ 2 ∑_{\begin{matrix}\{1<i_{1}<i_{2}<i_{3}<···<i_{k}<n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}(m − 2)^{2}(m − 3)^{i_{1}+n−i_{k}−3} · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}],

whereas

u_{n,m}^{k,1} = 0 for ⌈n/2⌉ < k ≤ n.

Proof. We remark that

Hom(BW_{n}, K_{m}) = χ_{BW_{n}}(m) = m(m − 1)(m − 2)^{n−1},

by applying the fundamental recursion theorem [11, eq. (1.11), p. 4] to the chromatic polynomial for the wheel graphs [11, eq. (1.23), p. 13].

The strategy will be to observe that Hom(BW_{n}, K_{m}^{1}) embeds in Hom(BW_{n}, K_{m}) and then to count which homomorphisms of the latter set are not in the former set; these are the ones that map at least a pair of adjacent vertices of BW_{n} to the exceptional edge AB in K_{m}. We count these by counting how many homomorphisms there are which map exactly k pairs of adjacent vertices of BW_{n} to K_{m} (we denote these numbers u_{n,m}^{k}), and, then, adding over k from 1 to n − 1.

Concerning these homomorphisms which map adjacent vertices of BW_{n} into the vertices of the exceptional edge of K_{m}, we distinguish two cases. In one case, the hub is mapped to one of the vertices of the exceptional edge, and, in the other one, the hub is not mapped to any of these vertices.

Suppose that, for a given f ∈ Hom(BW_{n}, K_{m}), the hub is part of a pair of vertices in BW_{n} which is mapped to the exceptional edge. Then each pair of adjacent vertices of BW_{n} in this homomorphism which is mapped to the A, B vertices, involves the hub. Otherwise, adjacency would not be preserved, since every other vertex is adjacent to the hub. In short, if one spoke is used, then only spokes are used. This is the 1 situation, as signaled by the

0

\begin{cases}0 \\ 1 \end{cases}

0 1 2 3 4 5 6 g_{l−1} g_{l} …

Figure 5: The broken wheel on 6 spokes, BW_{6}. The vertices drawn in full are assigned to the vertices of the exceptional edge.

upper index 1 in u_{n,m}^{k,1}. Moreover, no two consecutive vertices in the path part of the BW_{n} can be mapped to either of the vertices of the exceptional edge for otherwise, adjacency would not be preserved. Consider one such homomorphism which maps k pairs of vertices to the vertices of the exceptional edge. This homomorphism is clearly identified by describing the vertices on the path part of the broken wheel that are mapped to the other vertex of the pair of exceptional vertices and conversely. On the other hand, each such set of vertices is in one-to-one correspondence with the subsets of k elements from {1, 2, …, n} (the path part of the broken wheel) such that any two elements are more than one unit apart. This sets boundaries on the values of k: 1 ≤ k ≤ ⌈n/2⌉. The rest of the reasoning is analogous (although not the same) to the reasoning associated with (clusters and) gaps made above, in the proofs of Propositions 5 and 6. In Figure 5, we display the broken wheel on 6 spokes along with a representative of a homomorphism to K_{m} mapping 3 pairs of adjacent vertices to the vertices of the exceptional edge and each of these pairs involve the hub, vertex 0. The vertices that are mapped to the vertices of the exceptional edge are drawn in full, and so are the edges connecting them. With the notation used in the expressions for u_{n,m}^{k,1}, this corresponds to i_{1} = 1, i_{2} = 4, i_{3} = 6. Thus, either the hub is mapped to A and vertices 1, 4, and 6 are mapped to B, or the hub is mapped to B, and vertices 1, 4, and 6 are mapped to A, accounting so far for two possibilities. Then, vertex 2 cannot be mapped to A nor to B (m−2 possibilities); vertex 3 cannot be mapped to A, nor to B, nor to the vertex 2 has been mapped to (m − 3 possibilities). Finally, vertex 5 cannot be mapped to A nor to B (m − 2 possibilities). In this way, Figure 5 stands for 2 · (m − 2)(m − 3) · (m − 2) homomorphisms which map exactly 3 pairs of adjacent vertices, each one of which involving the hub, to the vertices of the exceptional edge.

Then, for 1 ≤ k ≤ ⌈n/2⌉,

u_{n,m}^{k,1} = 2 ∑_{\begin{matrix}\{1=i_{1}<i_{2}<i_{3}<···<i_{k}=n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}]

+ 2 ∑_{\begin{matrix}\{1<i_{1}<i_{2}<i_{3}<···<i_{k}=n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{1}−2} · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}]

+ 2 ∑_{\begin{matrix}\{1=i_{1}<i_{2}<i_{3}<···<i_{k}<n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}] · (m − 2)(m − 3)^{n−i_{k}−1}

+ 2 ∑_{\begin{matrix}\{1<i_{1}<i_{2}<i_{3}<···<i_{k}<n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}(m − 2)^{2}(m − 3)^{i_{1}+n−i_{k}−3} · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}],

where the 2 factors stand for the two possibilities of mapping the hub to, A or B.

Suppose, now, that, for a given f ∈ Hom(BW_{n}, K_{m}), the hub is not part of any pair of vertices which are mapped to the exceptional edge. This is the 0 situation, as signaled by the upper index 0 in u_{n,m}^{k,0}. Then, only vertices on the path part of the broken wheel are mapped to the vertices of the exceptional edge. Since the hub can be mapped to every vertex in K_{m} but A or B, there are m − 2 possibilities for it. Let us, now, calculate the possibilities for exactly k pairs of adjacent vertices on the path part of the broken wheel to be mapped to the vertices in the exceptional edge. Since the hub has already taken up one of the vertices we are left with m − 1 vertices in the target, otherwise violating preservation of adjacency. The possibilities for the path part of the broken wheel are, then, s_{n,m−1}^{k}, using the notation of Proposition 5. The total number of possibilities in this 0 situation of mapping k adjacent vertices to A and to B is, then,

u_{n,m}^{k,0} = (m − 2) · s_{n,m−1}^{k}.

This completes the proof.

Corollary 9. For integer n′ ≥ 1,

hom(BW_{2n′+1}, K_{3}^{1}) = 0.

Proof. Omitted.

2.7 The source graphs are wheels

Let n be an integer, n ≥ 3. We remark that a wheel on n spokes, denoted W_{n}, is a graph consisting of n + 1 vertices formed by a cycle on n vertices plus an extra vertex, called the hub, which is adjacent to every other vertex. The hub is denoted 0, and the other vertices 1, 2, …, n; the vertices are 01, 02, 03, …, 0n (the spokes) and 12, 23, 34, …, (n − 1)n, n1.

Proposition 10. For integers n ≥ 3, m ≥ 3,

hom(W_{n}, K_{m}^{1}) = m(m − 2)[(m − 2)^{n−1} + (−1)^{n}] − ∑_{k=1}^{n} v_{n,m}^{k},

where

v_{n,m}^{k} = v_{n,m}^{k,0} + v_{n,m}^{k,1},

and, keeping the notation of Proposition 6,

v_{n,m}^{k,0} = (m − 2)t_{n,m−1}^{k}, 1 ≤ k ≤ n,

and, for 1 ≤ k ≤ ⌊n/2⌋,

v_{n,m}^{k,1} = 2 ∑_{\begin{matrix}\{1<i_{1}<i_{2}<i_{3}<···<i_{k}=n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{1}−2} · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}]

+ 2 ∑_{\begin{matrix}\{1=i_{1}<i_{2}<i_{3}<···<i_{k}<n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}[ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}] · (m − 2)(m − 3)^{n−i_{k}−1}

+ 2 ∑_{\begin{matrix}\{1<i_{1}<i_{2}<i_{3}<···<i_{k}<n\} \\ s.t. i_{j}−i_{j−1}>1, 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{1}+n−i_{k}−2} · [ ∏_{\begin{matrix}i_{j} s.t. \\ i_{j}−i_{j−1}(>1) \\ 2≤j≤k \end{matrix}}(m − 2)(m − 3)^{i_{j}−i_{j−1}−2}],

whereas

v_{n,m}^{k,1} = 0 for ⌊n/2⌋ < k ≤ n.

Proof. We remark that

Hom(W_{n}, K_{m}) = χ_{W_{n}}(m) = m(m − 2)((m − 2)^{n−1} + (−1)^{n})

[11, eq. (1.23), p. 13], and omit the rest of the proof for it is analogous to the one for Proposition 8.

Corollary 11. For integer n′ ≥ 1,

hom(BW_{2n′+1}, K_{3}^{1}) = 0.

Proof. Omitted.

3 Final remarks

We look forward to calculating numbers of homomorphisms from other graphs to the quasicomplete graphs. We would also like to calculate partial profiles of other graphs. Here our plan will be to have for target graphs, graphs obtained from complete graphs by removing increasingly more edges from it. Furthermore, we would like to present our expressions in closed form instead of the way the expressions for hom(P_{n}, K_{m}^{1}), hom(C_{n}, K_{m}^{1}), hom(BW_{n}, K_{m}^{1}) and hom(W_{n}, K_{m}^{1}) are presented. The enumeration of homomorphisms of weighted graphs, which may be of significance in Statistical Mechanics of Exactly Solved Models [6], is also in our plans.

Moreover, in this work, we also calculated the “quasi”-chromatic “polynomials” of several graphs. As a matter of fact, we can regard our work here from the point of view of calculating hom(G, K_{m}^{1}), for fixed G, which we call “quasi”-chromatic “polynomials”. This is also a potentially interesting line of work to pursue.

We plan to address these issues in future work.

4 Acknowledgments

The author acknowledges support by Programa Operacional “Ciência, Tecnologia, Inovação” (POCTI) of the Fundação para a Ciência e a Tecnologia (FCT) cofinanced by the European Community fund FEDER. He thanks the staff at IMPA and especially his host, Marcelo Viana, for hospitality during his stay at this Institution. Finally, he thanks Louis H. Kauffman for suggestions.

References

[1] C. Borgs, J. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Counting graph homomorphisms, in Topics in Discrete Mathematics, Algorithms Combin., Vol. 26, Springer, 2006, pp. 315–371.

[2] P. Csikvári and Z. Lin, Graph homomorphisms between trees, Electron. J. Combin. 21 (2014), Paper 4.9.

[3] P. Csikvári and Z. Lin, Homomorphisms of trees into a path, SIAM J. Discrete Math. 29 (2015), 1406–1422.

[4] Z. Dvořák, On recognizing graphs by numbers of homomorphisms, J. Graph Theory 64 (2010), 330–342.

[5] M. Dyer and C. Greenhill, The complexity of counting graph homomorphisms, Random Structures Algorithms 17 (2000), 260–289.

[6] M. Freedman, L. Lovász, and A. Schrijver, Reflection positivity, rank connectivity, and homomorphisms of graphs, J. Amer. Math. Soc. 20 (2007), 37–51.

[7] D. Galvin, Counting colorings of a regular graph, Graphs Combin. 31 (2015), 629–638.

[8] P. Hell and J. Nešetřil, Graphs and Homomorphisms, Oxford University Press, 2004.

[9] P.-S. Loh, O. Pikhurko, and B. Sudakov, Maximizing the number of q-colorings, Proc. London Math. Soc. 101 (2010), 655–696.

[10] L. Lovász, Operations with structures, Acta Math. Hung. 18 (1967), 321–328.

[11] F. Dong, K. Koh, and K. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific, 2005.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05C15. Keywords: enumeration, sequence of integers, graph, graph homomorphism, complete graph, quasi-complete graph, path, cycle, wheel, broken wheel, Lovász vector of graph (profile of graph).

Received July 19 2015; revised versions received December 29 2015; January 14 2016. Published in Journal of Integer Sequences, January 22 2016.

Return to Journal of Integer Sequences home page.