Back to Search
Start Over
The minimum span of -labelings of generalized flowers.
- Source :
-
Discrete Applied Mathematics . Jan2015, Vol. 181, p139-151. 13p. - Publication Year :
- 2015
-
Abstract
- Given a positive integer d, an L(d, 1)-labeling of a graph G is an assignment of nonnegative integers to its vertices such that adjacent vertices must receive integers at least d apart, and vertices at distance two must receive integers at least one apart. The λd-number of G is the minimum k so that G has an L(d, 1)-labeling using labels in {0, 1, ..., k}. Informally, an amalgamation of two disjoint graphs G1 and G2 along a fixed graph G0 is the simple graph obtained by identifying the vertices of two induced subgraphs isomorphic to G0, one in G1 and the other in G2. A flower is an amalgamation of two or more cycles along a single vertex. We provide the exact λ2-number of a generalized flower which is the Cartesian product of a path Pn and a flower, or equivalently, an amalgamation of cylindrical rectangular grids along a certain Pn. In the process, we provide general upper bounds for the λd-number of the Cartesian product of P n and any graph G, using circular L(d+1, 1)-labelings of G where the labels {0, 1, ..., k} are arranged sequentially in a circle and the distance between two labels is the shortest distance on the circle. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 181
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 109255095
- Full Text :
- https://doi.org/10.1016/j.dam.2014.10.010