Discrete Mathematics, Algorithms and Applications

A Roman dominating function (RDF) on a graph G = (V, E) is a function f : V → {0, 1, 2} such that every vertex v ∈ V with f(v) = 0 has at least one neighbor u ∈ V with f(u) = 2. The weight of a RDF is the value f(V(G)) = Σ_u∈V(G) f(u). The minimum weight of a RDF on a graph G is called the Roman domination number, denoted by γ_R(G). The Roman bondage number b_R(G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E′ ⊆ E(G) for which γ_R(G - E′) > γ_R(G). In this paper, we first show that the decision problem for determining b_R(G) is NP-hard even for bipartite graphs and then we establish some sharp bounds for b_R(G) and characterizes all graphs attaining some of these bounds.

A graph G is said to be domatically co-critical, if d(G + uv) > d(G), for any two nonadjacent vertices u, v in G. In this paper, we present few more newly found results and list some more open problems for further research.

An upper bound for sorting permutations with an operation estimates the diameter of the corresponding Cayley graph and an exact upper bound equals the diameter. Computing tight upper bounds for various operations is of theoretical and practical (e.g., interconnection networks, genetics) interest. Akers and Krishnamurthy gave a Ω(n! n²) time method that examines n! permutations to compute an upper bound, f(Γ), to sort any permutation with a given transposition tree T, where Γ is the Cayley graph corresponding to T. We compute two intuitive upper bounds γ and δ′ each in O(n²) time for the same, by working solely with the transposition tree. Recently, Ganesan computed β, an estimate of the exact upper bound for the same, in O(n²) time. Our upper bounds are tighter than f(Γ) and β, on average and in most of the cases. For a class of trees, we prove that the new upper bounds are tighter than β and f(Γ).

In this paper, we address the problem of gathering information in one node (sink) of a radio network where interference constraints are present: when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most d_T in the graph, but when doing so it generates interferences that do not allow nodes at distance up to d_I(d_I ≥ d_T) to listen to other transmissions. We are interested in finding a gathering protocol, that is an ordered sequence of rounds (each round consists of noninterfering simultaneous transmissions) such that w(u) messages are transmitted from any node u to a fixed node called the sink. Our aim is to find a gathering protocol with the minimum number of rounds (called gathering time). In this article, we focus on the specific case where the network is a path with the sink at an end vertex of the path and where the traffic is unitary (w(u) = 1 for all u); indeed this simple case appears to be already very difficult. We first give a new lower bound and a protocol with a gathering time that differ only by a constant independent of the length of the path. Then we present a method to construct incremental protocols. An incremental protocol for the path on n + 1 vertices is obtained from a protocol for n vertices by adding new rounds and new calls to some rounds but without changing the calls of the original rounds. We show that some of these incremental protocols are optimal for many values of d_T and d_I (in particular when d_T is prime). We conjecture that this incremental construction always gives optimal protocols. Finally, we derive an approximation algorithm when the sink is placed in an arbitrary vertex in the path.

Localization is one of the fundamental tasks for underwater sensors networks (USNs). It is required for data tagging, target detection, route protocols, and so on. In this paper, we propose an efficient low-cost range-free localization scheme for 3D underwater sensor networks (3D-LRLS) without any additional hardware infrastructure. In our scheme, each anchor node has variable transmission power levels. At first, the power levels of each anchor are decided by the Delaunay triangulation for the network space. Then, ordinary sensors listen to the beacons sent from the anchor nodes. Based on the beacon messages, each node calculates its location individually by a low computational complexity method. The extensive simulation results demonstrate that 3D-LRLS is efficient in terms of both localization ratio and localization accuracy.

Let G be a nontrivial, simple, finite, connected and undirected graph. A graphoidal decomposition (GD) of G is a collection ψ of paths and cycles in G that are internally disjoint such that every edge of G lies in exactly one member of ψ. As a variation of GD the notion of induced graphoidal decomposition (IGD) was introduced in [S. Arumugam, Path covers in graphs (2006)] which is a GD all of whose members are either induced paths or induced cycles. The minimum number of elements in such a decomposition of a graph G is called the IGD number, denoted by η_i(G). In this paper, we extend the study of the parameter η_i by establishing bounds for η_i(G) in terms of the diameter, girth and the maximum degree along with characterization of graphs achieving the bounds.

In this paper, we associate the graph Γ_I(N) to an ideal I of a near-ring N. We exhibit some properties and structure of Γ_I(N). For a commutative ring R, Beck conjectured that both chromatic number and clique number of the zero-divisor graph Γ(R) of R are equal. We prove that Beck's conjecture is true for Γ_I(N). Moreover, we characterize all right permutable near-rings N for which the graph Γ_I(N) is finitely colorable.