E-resources
-
Lladó, Anna; Mokhtar, Hamid; Serra, Oriol; Zhou, Sanming
Discrete Applied Mathematics, 12/2021, Volume: 304Journal Article
An L(h1,h2,…,hl)-labelling of a graph G is a mapping ϕ:V(G)→{0,1,2,…} such that for 1≤i≤l and each pair of vertices u,v of G at distance i, we have |ϕ(u)−ϕ(v)|≥hi. The span of ϕ is the difference between the largest and smallest labels assigned to the vertices of G by ϕ, and λh1,h2,…,hl(G) is defined as the minimum span over all L(h1,h2,…,hl)-labellings of G. In this paper we study λh,1,…,1 for Cartesian products of graphs, where (h,1,…,1) is an l-tuple with l≥3. We prove that, under certain natural conditions, the value of this and three related invariants on a graph H which is the Cartesian product of l graphs attain a common lower bound. In particular, the chromatic number of the lth power of H equals this lower bound plus one. We further obtain a sandwich theorem which extends the result to a family of subgraphs of H which contain a certain subgraph of H. All these results apply in particular to the class of Hamming graphs: if q1≥⋯≥qd≥2 and 3≤l≤d then the Hamming graph H=Hq1,q2,…,qd satisfies λql,1,…,1(H)=q1q2…ql−1 whenever q1q2…ql−1>3(ql−1+1)ql…qd. In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.