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]

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]

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: 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]