Search

Abstract: In a majority conversion process, the vertices of a graph can be in one of the two states, colored or uncolored, and these states are dynamically updated so that a vertex becomes colored at a certain time period if at least half of its neighbors were in the colored state in the previous time period. A dynamic monopoly is a set of vertices in a graph that when initially colored will eventually cause all vertices in the graph to become colored. This paper establishes a connection between dynamic monopolies and the well-known feedback vertex sets which are sets of vertices whose removal results in an acyclic graph. More specifically, we show that dynamic monopolies and feedback vertex sets are equivalent in graphs wherein all vertices have degree 2 or 3. We use this equivalence to provide exact values for the minimum size of dynamic monopolies of planar hexagonal grids, as well as upper and lower bounds on the minimum size of dynamic monopolies of cylindrical and toroidal hexagonal grids. For these last two topologies, the respective upper and lower bounds differ by at most one. [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is a function such that if and are adjacent vertices, and if and are at distance 2. Such labelings were introduced as a way of modeling the assignment of frequencies to transmitters operating in close proximity within a communications network. The lambda number of is the minimum over all -labelings of . This paper considers the lambda number of the matched sum of two same-order disjoint graphs, wherein the graphs have been connected by a perfect matching between the two vertex sets. Matched sums have been studied in this context to model possible connections between two different networks with the same number of transmitters. We completely determine the lambda number of matched sums where one of the graphs is a complete graph or a complete graph minus an edge. We conclude by discussing some difficulties that are encountered when trying to generalize this problem by removing more edges from a complete graph. [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. 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]

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: In a graph theoretical model of the spread of fault in distributed computing and communication networks, each element in the network is represented by a vertex of a graph where edges connect pairs of communicating elements, and each colored vertex corresponds to a faulty element at discrete time periods. Majority-based systems have been used to model the spread of fault to a certain vertex by checking for faults within a majority of its neighbors. Our focus is on irreversible majority processes wherein a vertex becomes permanently colored in a certain time period if at least half of its neighbors were in the colored state in the previous time period. We study such processes on planar, cylindrical, and toroidal triangular grid graphs. More specifically, we provide bounds for the minimum number of vertices in a dynamic monopoly defined as a set of vertices that, if initially colored, will result in the entire graph becoming colored in a finite number of time periods. [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is a function from the vertex set of to the set of nonnegative integers such that if , and if , where denotes the distance between the pair of vertices . The lambda number of , denoted , is the minimum range of labels used over all (2,1)-labelings of . An (2,1)-labeling of which achieves the range is referred to as a -labeling. A hole of an (2,1)-labeling is an unused integer within the range of integers used. The hole index of , denoted , is the minimum number of holes taken over all its -labelings. An island of a given -labeling of with holes is a maximal set of consecutive integers used by the labeling. Georges and Mauro [J.P. Georges, D.W. Mauro, On the structure of graphs with non-surjective (2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208–223] inquired about the existence of a connected graph with possessing two -labelings with different ordered sequences of island cardinalities. This paper provides an infinite family of such graphs together with their lambda numbers and hole indices. Key to our discussion is the determination of the path covering number of certain 2-sparse graphs, that is, graphs containing no pair of adjacent vertices of degree greater than 2. [Copyright &y& Elsevier]

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 upper and lower bounds for the zero blocking number of rectangular grids and discuss conditions under which these bounds coincide. We go on to use the same machinery to provide similar results for certain cylindrical and Möbius grids. [ABSTRACT FROM AUTHOR]

Abstract: An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted , is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted , is the minimum number of holes taken over all L(2,1)-labelings with span exactly . Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208–223] conjectured that if G is an r-regular graph and , then must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that and r are relatively prime integers. [Copyright &y& Elsevier]

For a positive integer , a radio k-labeling of a graph is a function from its vertex set to the non-negative integers such that for all pairs of distinct vertices and , we have where is the distance between the vertices and in . The minimum span over all radio -labelings of is called the radio k-chromatic number and denoted by . The most extensively studied cases are the classic vertex colorings (), (2,1)-labelings (), radio labelings (, the diameter of ), and radio antipodal labelings (. Determining exact values or tight bounds for is often non-trivial even within simple families of graphs. We provide general lower bounds for for all cycles when and show that these bounds are exact values when . [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]