Search

In a zero forcing process , an initial vertex coloring of a graph is updated iteratively according to the following conversion rule: an uncolored vertex becomes colored if it is the only uncolored neighbor of some colored vertex. In this process, a zero forcing set is an initial set of colored vertices such that all the remaining vertices will ultimately change from uncolored to colored, and the zero forcing number is the minimum cardinality of a zero forcing set. We investigate two related concepts: a zero blocking set is the complement of a set which is not a zero forcing set, and the zero blocking number is the minimum cardinality of a zero blocking set. We provide a tight upper bound for the zero blocking number of Cartesian products of two arbitrary graphs. Exact values that are smaller than this general upper bound are also established when one of the graphs in the product is a cycle and the other is a path with at least as many vertices as the cycle. [ABSTRACT FROM AUTHOR]

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]

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]