Distance-two labellings of Hamming graphs
Lists
Only you see this
Abstract
Let j≥k≥0<math><mi is="true">j</mi><mo is="true">≥</mo><mi is="true">k</mi><mo is="true">≥</mo><mn is="true">0</mn></math> be integers. An ℓ<math><mi is="true">ℓ</mi></math>-L(j,k)<math><mi is="true">L</mi><mrow is="true"><mo is="true">(</mo><mi is="true">j</mi><mo is="true">,</mo><mi is="true">k</mi><mo is="true">)</mo></mrow></math>-labelling of a graph G=(V,E)<math><mi is="true">G</mi><mo is="true">=</mo><mrow is="true"><mo is="true">(</mo><mi is="true">V</mi><mo is="true">,</mo><mi is="true">E</mi><mo is="true">)</mo></mrow></math> is a mapping ϕ:V→{0,1,2,…,ℓ}<math><mi is="true">ϕ</mi><mo is="true">:</mo><mi is="true">V</mi><mo is="true">→</mo><mrow is="true"><mo is="true">{</mo><mn is="true">0</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">,</mo><mn is="true">2</mn><mo is="true">,</mo><mo is="true">…</mo><mo is="true">,</mo><mi is="true">ℓ</mi><mo is="true">}</mo></mrow></math> such that |ϕ(u)−ϕ(v)|≥j<math><mrow is="true"><mo is="true">|</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">v</mi><mo is="true">)</mo></mrow><mo is="true">|</mo></mrow><mo is="true">≥</mo><mi is="true">j</mi></math> if u,v<math><mi is="true">u</mi><mo is="true">,</mo><mi is="true">v</mi></math> are adjacent and |ϕ(u)−ϕ(v)|≥k<math><mrow is="true"><mo is="true">|</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">v</mi><mo is="true">)</mo></mrow><mo is="true">|</mo></mrow><mo is="true">≥</mo><mi is="true">k</mi></math> if they are distance two apart. Let λj,k(G)<math><msub is="true"><mrow is="true"><mi is="true">λ</mi></mrow><mrow is="true"><mi is="true">j</mi><mo is="true">,</mo><mi is="true">k</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math> be the smallest integer ℓ<math><mi is="true">ℓ</mi></math> such that G<math><mi is="true">G</mi></math> admits an ℓ<math><mi is="true">ℓ</mi></math>-L(j,k)<math><mi is="true">L</mi><mrow is="true"><mo is="true">(</mo><mi is="true">j</mi><mo is="true">,</mo><mi is="true">k</mi><mo is="true">)</mo></mrow></math>-labelling. Define λ¯j,k(G)<math><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">λ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mi is="true">j</mi><mo is="true">,</mo><mi is="true">k</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math> to be the smallest ℓ<math><mi is="true">ℓ</mi></math> if G<math><mi is="true">G</mi></math> admits an ℓ<math><mi is="true">ℓ</mi></math>-L(j,k)<math><mi is="true">L</mi><mrow is="true"><mo is="true">(</mo><mi is="true">j</mi><mo is="true">,</mo><mi is="true">k</mi><mo is="true">)</mo></mrow></math>-labelling with ϕ(V)={0,1,2,…,ℓ}<math><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">V</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><mrow is="true"><mo is="true">{</mo><mn is="true">0</mn><mo is="true">,</mo><mn is="true">1</mn><mo is="true">,</mo><mn is="true">2</mn><mo is="true">,</mo><mo is="true">…</mo><mo is="true">,</mo><mi is="true">ℓ</mi><mo is="true">}</mo></mrow></math> and ∞<math><mi is="true">∞</mi></math> otherwise. An ℓ<math><mi is="true">ℓ</mi></math>-cyclic L(j,k)<math><mi is="true">L</mi><mrow is="true"><mo is="true">(</mo><mi is="true">j</mi><mo is="true">,</mo><mi is="true">k</mi><mo is="true">)</mo></mrow></math>-labelling is a mapping ϕ:V→Zℓ<math><mi is="true">ϕ</mi><mo is="true">:</mo><mi is="true">V</mi><mo is="true">→</mo><msub is="true"><mrow is="true"><mi mathvariant="double-struck" is="true">Z</mi></mrow><mrow is="true"><mi is="true">ℓ</mi></mrow></msub></math> such that |ϕ(u)−ϕ(v)|ℓ≥j<math><msub is="true"><mrow is="true"><mrow is="true"><mo is="true">|</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">v</mi><mo is="true">)</mo></mrow><mo is="true">|</mo></mrow></mrow><mrow is="true"><mi is="true">ℓ</mi></mrow></msub><mo is="true">≥</mo><mi is="true">j</mi></math> if u,v<math><mi is="true">u</mi><mo is="true">,</mo><mi is="true">v</mi></math> are adjacent and |ϕ(u)−ϕ(v)|ℓ≥k<math><msub is="true"><mrow is="true"><mrow is="true"><mo is="true">|</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">u</mi><mo is="true">)</mo></mrow><mo is="true">−</mo><mi is="true">ϕ</mi><mrow is="true"><mo is="true">(</mo><mi is="true">v</mi><mo is="true">)</mo></mrow><mo is="true">|</mo></mrow></mrow><mrow is="true"><mi is="true">ℓ</mi></mrow></msub><mo is="true">≥</mo><mi is="true">k</mi></math> if they are distance two apart, where |x|ℓ=min{x,ℓ−x}<math><msub is="true"><mrow is="true"><mrow is="true"><mo is="true">|</mo><mi is="true">x</mi><mo is="true">|</mo></mrow></mrow><mrow is="true"><mi is="true">ℓ</mi></mrow></msub><mo is="true">=</mo><mo is="true">min</mo><mrow is="true"><mo is="true">{</mo><mi is="true">x</mi><mo is="true">,</mo><mi is="true">ℓ</mi><mo is="true">−</mo><mi is="true">x</mi><mo is="true">}</mo></mrow></math> for x<math><mi is="true">x</mi></math> between 0 and ℓ<math><mi is="true">ℓ</mi></math>. Let σj,k(G)<math><msub is="true"><mrow is="true"><mi is="true">σ</mi></mrow><mrow is="true"><mi is="true">j</mi><mo is="true">,</mo><mi is="true">k</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math> be the smallest ℓ−1<math><mi is="true">ℓ</mi><mo is="true">−</mo><mn is="true">1</mn></math> of such a labelling, and define σ¯j,k(G)<math><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">σ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mi is="true">j</mi><mo is="true">,</mo><mi is="true">k</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math> similarly to λ¯j,k(G)<math><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">λ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mi is="true">j</mi><mo is="true">,</mo><mi is="true">k</mi></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></math>. We determine λ2,0<math><msub is="true"><mrow is="true"><mi is="true">λ</mi></mrow><mrow is="true"><mn is="true">2</mn><mo is="true">,</mo><mn is="true">0</mn></mrow></msub></math>, λ¯2,0<math><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">λ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mn is="true">2</mn><mo is="true">,</mo><mn is="true">0</mn></mrow></msub></math>, σ2,0<math><msub is="true"><mrow is="true"><mi is="true">σ</mi></mrow><mrow is="true"><mn is="true">2</mn><mo is="true">,</mo><mn is="true">0</mn></mrow></msub></math> and σ¯2,0<math><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">σ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mn is="true">2</mn><mo is="true">,</mo><mn is="true">0</mn></mrow></msub></math> for all Hamming graphs Kq1□Kq2□⋯□Kqd<math><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">1</mn></mrow></msub></mrow></msub><mi is="true">□</mi><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub></mrow></msub><mi is="true">□</mi><mo is="true">⋯</mo><mi is="true">□</mi><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mi is="true">d</mi></mrow></msub></mrow></msub></math> (d≥2<math><mi is="true">d</mi><mo is="true">≥</mo><mn is="true">2</mn></math>, q1≥q2≥⋯≥qd≥2<math><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">1</mn></mrow></msub><mo is="true">≥</mo><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub><mo is="true">≥</mo><mo is="true">⋯</mo><mo is="true">≥</mo><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mi is="true">d</mi></mrow></msub><mo is="true">≥</mo><mn is="true">2</mn></math>) and give optimal labellings, with the only exception being 2q≤σ¯2,0(Kq□Kq)≤2q+1<math><mn is="true">2</mn><mi is="true">q</mi><mo is="true">≤</mo><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">σ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mn is="true">2</mn><mo is="true">,</mo><mn is="true">0</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><mi is="true">q</mi></mrow></msub><mi is="true">□</mi><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><mi is="true">q</mi></mrow></msub><mo is="true">)</mo></mrow><mo is="true">≤</mo><mn is="true">2</mn><mi is="true">q</mi><mo is="true">+</mo><mn is="true">1</mn></math> for q≥4<math><mi is="true">q</mi><mo is="true">≥</mo><mn is="true">4</mn></math>. We also prove the following “sandwich theorem”: If q1<math><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">1</mn></mrow></msub></math> is sufficiently large then λ2,1(G)=λ¯2,1(G)=σ¯2,1(G)=σ2,1(G)=λ1,1(G)=λ¯1,1(G)=σ¯1,1(G)=σ1,1(G)=q1q2−1<math><msub is="true"><mrow is="true"><mi is="true">λ</mi></mrow><mrow is="true"><mn is="true">2</mn><mo is="true">,</mo><mn is="true">1</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">λ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mn is="true">2</mn><mo is="true">,</mo><mn is="true">1</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">σ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mn is="true">2</mn><mo is="true">,</mo><mn is="true">1</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><msub is="true"><mrow is="true"><mi is="true">σ</mi></mrow><mrow is="true"><mn is="true">2</mn><mo is="true">,</mo><mn is="true">1</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><msub is="true"><mrow is="true"><mi is="true">λ</mi></mrow><mrow is="true"><mn is="true">1</mn><mo is="true">,</mo><mn is="true">1</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">λ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mn is="true">1</mn><mo is="true">,</mo><mn is="true">1</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><msub is="true"><mrow is="true"><mover accent="false" is="true"><mrow is="true"><mi is="true">σ</mi></mrow><mo accent="true" is="true">¯</mo></mover></mrow><mrow is="true"><mn is="true">1</mn><mo is="true">,</mo><mn is="true">1</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><msub is="true"><mrow is="true"><mi is="true">σ</mi></mrow><mrow is="true"><mn is="true">1</mn><mo is="true">,</mo><mn is="true">1</mn></mrow></msub><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow><mo is="true">=</mo><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">1</mn></mrow></msub><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub><mo is="true">−</mo><mn is="true">1</mn></math> for any graph G<math><mi is="true">G</mi></math> between Kq1□Kq2<math><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">1</mn></mrow></msub></mrow></msub><mi is="true">□</mi><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub></mrow></msub></math> and Kq1□Kq2□⋯□Kqd<math><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">1</mn></mrow></msub></mrow></msub><mi is="true">□</mi><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msub></mrow></msub><mi is="true">□</mi><mo is="true">⋯</mo><mi is="true">□</mi><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">q</mi></mrow><mrow is="true"><mi is="true">d</mi></mrow></msub></mrow></msub></math>, and moreover we give a labelling which is optimal for these eight invariants simultaneously.
BibTeX
@article{chang2009distance,
author = {Gerard J. Chang and Changhong Lu and Sanming Zhou},
title = {{Distance-two labellings of Hamming graphs}},
journal = {Discret. Appl. Math.},
year = {2009},
doi = {10.1016/j.dam.2009.01.001},
}Loading related content...