Optimal <named-content content-type="inline-formula"><math display="inline"><semantics><mrow><mi>L</mi><mo>(</mo><mi>d</mi><mo>,</mo><mn>1</mn><mo>)</mo></mrow></semantics></math></named-content>-Labeling of Certain Direct Graph Bundles Cycles over Cycles and Cartesian Graph Bundles Cycles over Cycles

Abstract

An L(d,1)-labeling of a graph G=(V,E) is a function f from the vertex set V(G) to the set of nonnegative integers such that the labels on adjacent vertices differ by at least d and the labels on vertices at distance two differ by at least one, where d≥1. The span of f is the difference between the largest and the smallest numbers in f(V). The λ1d-number of G, denoted by λ1d(G), is the minimum span over all L(d,1)-labelings of G. We prove that λ1d(X)≤2d+2, with equality if 1≤d≤4, for direct graph bundle X=Cm×σℓCn and Cartesian graph bundle X=Cm□σℓCn, if certain conditions are imposed on the lengths of the cycles and on the cyclic ℓ-shift σℓ.

Keywords

• L ( d , 1 ) -labeling%22%2C%22default_operator%22%3A%22AND%22%7D%7D%7D"> <named-content content-type="inline-formula"> <mml:math id="mm10001"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:semantics> </mml:math></named-content>-labeling
• λ 1 d -number%22%2C%22default_operator%22%3A%22AND%22%7D%7D%7D"> <named-content content-type="inline-formula"> <mml:math id="mm10002"> <mml:semantics> <mml:mrow> <mml:msubsup> <mml:mi>λ</mml:mi> <mml:mn>1</mml:mn> <mml:mi>d</mml:mi> </mml:msubsup> </mml:mrow> </mml:semantics> </mml:math></named-content>-number
• direct product of graph
• direct graph bundle
• Cartesian product of graph
• Cartesian graph bundle