Abstract
An -labelling of a graph is a mapping such that for and each pair of vertices of at distance , we have . The span of is the difference between the largest and smallest labels assigned to the vertices of by , and is defined as the minimum span over all -labellings of . In this paper we study for Cartesian products of graphs, where is an -tuple with . We prove that, under certain natural conditions, the value of this and three related invariants on a graph which is the Cartesian product of graphs attain a common lower bound. In particular, the chromatic number of the -th power of equals this lower bound plus one. We further obtain a sandwhich theorem which extends the result to a family of subgraphs of which contain a certain subgraph of . All these results apply in particular to the class of Hamming graphs: if and then the Hamming graph satisfies whenever . In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.