AN UPPER BOUND FOR THE REPRESENTATION NUMBER OF GRAPHS WITH FIXED ORDER

Darren A. Narayan

Department of Mathematics and Statistics, Rochester Institute of Technology, Rochester, NY 14623

                             dansma@rit.edu

Received: 4/30/03, Revised: 7/17/03, Accepted: 7/31/03, Published: 8/7/03

Abstract

A graph has a representation modulo n if there exists an injective map f: {V (G)} → {0, 1, …, n − 1} such that vertices u and v are adjacent if and only if |f(u) − f(v)| is relatively prime to n. The representation number is the smallest n such that G has a representation modulo n. We seek the maximum value for the representation number over graphs of a fixed order. Erdős and Evans provided an upper bound in their proof that every finite graph can be represented modulo some positive integer. In this note we improve this bound and show that the new bound is best possible.

1. Introduction

Let G be a finite graph with vertices {v_{1}, …, v_{r}}. A representation of G modulo n is an assignment of distinct labels to the vertices such that the label a_{i} assigned to vertex v_{i} is in {0, 1, …, n − 1} and such that |a_{i} − a_{j}| and n are relatively prime if and only if (v_{i}, v_{j}) ∈ E(G). Erdős and Evans [1] showed that every finite graph can be represented modulo some positive integer. The representation number of a graph G, denoted rep (G), is the smallest n such that G has a representation modulo n.

Modular representations have received considerable attention in recent years as a source of open problems (see [4] and [7]). Representation numbers for various classes of graphs were determined in [2] and [3], but little is known for many families of graphs, including bipartite graphs and trees.

The existence proof in [1] is elegant but gives an unnecessarily large upper bound for the representation number. For a graph of order r, the value n is the product of r primes, each greater than 3^{\binom{r}{2}}. Our bound is the product of the first r − 1 primes greater than or equal to r − 1. In fact we show that this significantly smaller bound is best possible over all graphs of order r.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 3 (2003), #A12 2

We also mention a connection to a result involving orthogonal latin square graphs. An orthogonal latin square graph is one whose vertices can be labeled with latin squares of the same order and same symbols such that two vertices are adjacent if and only if the corresponding latin squares are orthogonal. Lindner, E. Mendelsohn, N. S. Mendelsohn, and Wolk [5] showed that every finite graph is an orthogonal latin square graph. A shorter proof of this result was given by Erdős and Evans [1] after establishing that every finite graph can be represented modulo some positive integer. An even more simple proof of the theorem from [5] can be obtained using the upper bound found in this note.

2. Dimensions and representations

A product representation of length t assigns distinct vectors of length t to each vertex so that vertices u and v are adjacent if and only if their vectors differ in every position. The product dimension of a graph, denoted pdim G, is the minimum length of such a representation of G.

As developed in [2] and [3], there is a close correspondence between product representation and modular representation. From a representation of a graph G modulo a product of primes q_{1}, …, q_{t}, we obtain a product representation of length t as follows. The vector for vertex v is (v_{1}, …, v_{t}), where v_{i} ≡ a(mod q_{i}) and v_{i} ∈ {0, …, q_{i−1}} for 1 ≤ i ≤ t. If u has vector (u_{1}, …, u_{t}) and v has vector (v_{1}, …, v_{t}), then the modular representation implies that u and v are adjacent if and only if u_{i} ≠ v_{i} for all i, making this assignment a product representation.

Conversely, given a product representation, a modular representation can be obtained by choosing distinct primes for the coordinates, provided that the prime for each coordinate is larger than the number of values used in that coordinate. The numbers assigned to the vertices can then be obtained using the Chinese Remainder Theorem. The resulting modular representation generated from the product representation is called the coordinate representation.

We use p_{i} to denote the ith prime, and for any prime p_{i} we use p_{i+1}, p_{i+2}, …, p_{i+k} to denote the next k primes larger than p_{i}. The seminal work on product dimension was done by Lovász, Nešetřil, and Pultr [6]. We first restate one of their results and then a result from [3] as Lemmas 1 and 2. The graph K_{r−1} + K_{1} is the disjoint union of K_{r−1} and K_{1}.

Lemma 1 For r ≥ 3, the maximum product dimension of an r−vertex graph is r − 1, achieved by K_{r−1} + K_{1}.

Lemma 2 Let p_{s} be the smallest prime that is at least r − 1. Then rep (K_{r−1} + K_{1}) = p_{s}p_{s+1} ⋯ p_{s+r−2}.

By converting from product representations to modular representations, we show that for all r ≥ 3, K_{r−1} + K_{1} is the r-vertex graph with largest representation number. For graphs with at most two vertices, it is straightforward to show that rep (K_{1}) = 1, rep (K_{2}) = 2, and rep (2K_{1}) = 4.

Theorem 3 For r ≥ 3, the maximum of rep (G) over graphs of order r is p_{s}p_{s+1} ⋯ p_{s+r−2}, where p_{s} is the smallest prime that is at least r − 1.

Proof. The sharpness of the upper bound follows from Lemma 2. To prove the upper bound, let G have order r, and begin with a product representation of length r − 1 provided by Lemma 1. By relabeling if necessary, we may assume that the values used in coordinate i are {0, 1, …, c_{i} − 1} for some positive integer c_{i} and that coordinates are indexed such that c_{1} ≤ ⋯ ≤ c_{r−1}.

If G is not complete, then c_{1} ≤ r − 1. Thus we may associate p_{s+i−1} with the ith coordinate and the corresponding coordinate representation of G is a representation modulo p_{s} ⋯ p_{s+r−2}. If G is complete, then rep (G) is the smallest prime that is at least r, which is smaller than the claimed upper bound.

3. Conclusion

We note that the construction given in the proof of Theorem 3 will not always give the representation number, since the representation number need not be a product of distinct primes. The case mentioned earlier, rep(2K_{1}) = 4, is one of infinitely many examples. Therefore, finding the representation number of a graph is a different problem from finding the product dimension of a graph. Since the representation number of a graph depends upon the distribution of primes and prime powers, tools from number theory may be valuable for future studies. There are many open problems involving modular repesentations. Representation numbers have been determined for only a few graph families (see [2] and [3]). Little is known about representation numbers for some multipartite graphs, including the most basic cases involving trees and complete bipartite graphs.

Acknowledgements

The author is indebted to a referee for many valuable suggestions, including an improved presentation of the proof of Theorem 3. This work was partially supported by a RIT College of Science Dean’s Summer Research Fellowship Grant and a Reidler Foundation Grant. Thanks to Anthony Evans and Garth Isaak for useful discussions. Finally the author thanks Dustin Sheffield, now an undergraduate at Virginia Tech, for preliminary computer simulations.

References

[1] P. Erdős and A. B. Evans, Representations of graphs and orthogonal latin square graphs, J. Graph Theory 13 (1989) 593-595.

[2] A. B. Evans, G. H. Fricke, C. C. Maneri, T. A. McKee and M. Perkel, Representations of graphs modulo n, J. Graph Theory 18 (1994) 801-815.

[3] A. B. Evans, G. Isaak and D. A. Narayan, Representations of graphs modulo n. Discrete Math 223 (2000) 109-123.

[4] J. A. Gallian, A dynamic survey of graph labeling, Electronic. J. Combin. 5 (2002), 1-106.

[5] C. C. Lindner, E. Mendelsohn, N. S. Mendelsohn, and B. Wolk, Orthogonal latin square graphs, J. Graph Theory 3 (1979) 325-338.

[6] L. Lovász, J. Nešetřil, and A. Pultr. On a product dimension of graphs, J. Combin. Theory B 29 (1980), 47-67.

[7] D. B. West, (ed.) Research Problems, Discrete Math 257 (2002) 599-624.