Search

Abstract: An -labeling of a graph is an assignment of nonnegative integers to its vertices so that adjacent vertices get labels at least two apart and vertices at distance two get distinct labels. The -number of a graph G, denoted by , is the minimum range of labels taken over all of its -labelings. We show that the -number of the Cartesian product of any two cycles is 6, 7 or 8. In addition, we provide complete characterizations for the products of two cycles with -number exactly equal to each one of these values. [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is an assignment of nonnegative integers to its vertices so that adjacent vertices get labels at least two apart and vertices at distance two get distinct labels. A graph is said to be -critical if is the minimum span taken over all of its -labelings, and every proper subgraph has an -labeling with span strictly smaller than . Georges and Mauro have studied 5-critical trees with maximum degree by examining their path-like substructures. They also presented an infinite family of 5-critical trees of maximum degree . We generalize these results for -critical trees with . [Copyright &y& Elsevier]

The spectrum allocation problem in wireless communications can be modeled through vertex labelings of a graph, wherein each vertex represents a transmitter and edges connect vertices whose corresponding transmitters are operating in close proximity. One well-known model is the L ( 2 , 1 ) -labeling of a graph G in which a function f maps the vertices of G to the nonnegative integers such that if vertices x and y are adjacent, then | f ( x ) − f ( y ) | ≥ 2 , and if x and y are at distance two, then | f ( x ) − f ( y ) | ≥ 1 . The λ -number of G is the minimum span over all L ( 2 , 1 ) -labelings of G . Informally, an amalgamation of two graphs G 1 and G 2 along a fixed graph G 0 is the simple graph obtained by identifying the vertices of two induced subgraphs isomorphic to G 0 , one in G 1 and the other in G 2 . In this work, we supply a tight upper bound for the λ -number of amalgamations of several Cartesian products of complete graphs along a complete graph and find the exact λ -numbers for certain infinite subclasses of amalgamations of this form. A surprising relationship between the former upper bound and the minimum makespan scheduling problem is highlighted. [ABSTRACT FROM AUTHOR]

Abstract: The problem of assigning frequencies to transmitters in a radio network can be modeled through vertex labelings of a graph, wherein each vertex represents a transmitter and edges connect vertices whose corresponding transmitters are operating in close proximity. In one such model, an -labeling of a graph G is employed, which is an assignment fof nonnegative integers to the vertices of G such that if vertices x and y are adjacent, , and if x and y are at distance two, . The -number of G is the minimum span over all -labelings of G. Informally, an amalgamation of two graphs and along a fixed graph is the simple graph obtained by identifying the vertices of two induced subgraphs isomorphic to , one of and the other of . We provide upper bounds for the -number of the amalgamation of graphs along a given graph by determining the exact -number of amalgamations of complete graphs along a complete graph. We also provide the exact -numbers of amalgamations of rectangular grids along a path, or more specifically, of the Cartesian products of a path and a star with spokes of arbitrary lengths. [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is an assignment of nonnegative integers to the vertices of such that if vertices and are adjacent, , and if and are at distance two, . The -number of is the minimum span over all -labelings of . A generalized Petersen graph (GPG) of order consists of two disjoint copies of cycles on vertices together with a perfect matching between the two vertex sets. By presenting and applying a novel algorithm for identifying GPG-specific isomorphisms, this paper provides exact values for the -numbers of all GPGs of orders 9, 10, 11, and 12. For all but three GPGs of these orders, the -numbers are 5 or 6, improving the recently obtained upper bound of 7 for GPGs of orders 9, 10, 11, and 12. We also provide the -numbers of several infinite subclasses of GPGs that have useful representations on Möbius strips. [Copyright &y& Elsevier]

Abstract: In the classical channel assignment problem, transmitters that are sufficiently close together are assigned transmission frequencies that differ by prescribed amounts, with the goal of minimizing the span of frequencies required. This problem can be modeled through the use of an L(2,1)-labeling, which is a function f from the vertex set of a graph G to the non-negative integers such that 2 if xand y are adjacent vertices and if xand y are at distance two. The goal is to determine the -number of , which is defined as the minimum span over all L(2,1)-labelings of G, or equivalently, the smallest number k such that G has an L(2,1)-labeling using integers from . Recent work has focused on determining the -number of generalized Petersen graphs (GPGs) of order n. This paper provides exact values for the -numbers of GPGs of orders 5, 7, and 8, closing all remaining open cases for orders at most 8. It is also shown that there are no GPGs of order 4, 5, 8, or 11 with -number exactly equal to the known lower bound of 5, however, a construction is provided to obtain examples of GPGs with -number 5 for all other orders. This paper also provides an upper bound for the number of distinct isomorphism classes for GPGs of any given order. Finally, the exact values for the -number of n-stars, a subclass of the GPGs inspired by the classical Petersen graph, are also determined. These generalized stars have a useful representation on Möebius strips, which is fundamental in verifying our results. [Copyright &y& Elsevier]