کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418992 | 681731 | 2015 | 13 صفحه PDF | دانلود رایگان |
Given a positive integer dd, an L(d,1)L(d,1)-labeling of a graph GG is an assignment of nonnegative integers to its vertices such that adjacent vertices must receive integers at least dd apart, and vertices at distance two must receive integers at least one apart. The λdλd-number of GG is the minimum kk so that GG has an L(d,1)L(d,1)-labeling using labels in {0, 1, …, kk}. Informally, an amalgamation of two disjoint graphs G1G1 and G2G2 along a fixed graph G0G0 is the simple graph obtained by identifying the vertices of two induced subgraphs isomorphic to G0G0, one in G1G1 and the other in G2G2. A flower is an amalgamation of two or more cycles along a single vertex. We provide the exact λ2λ2-number of a generalized flower which is the Cartesian product of a path PnPn and a flower, or equivalently, an amalgamation of cylindrical rectangular grids along a certain PnPn. In the process, we provide general upper bounds for the λdλd-number of the Cartesian product of PnPn and any graph GG, using circular L(d+1,1)L(d+1,1)-labelings of GG where the labels {0, 1, …, kk} are arranged sequentially in a circle and the distance between two labels is the shortest distance on the circle.
Journal: Discrete Applied Mathematics - Volume 181, 30 January 2015, Pages 139–151