Discrete Mathematics, Algorithms and Applications

Let R be a commutative ring with identity which is not an integral domain. An ideal I of a ring R is called an annihilating ideal if there exists r ∈ R\{0} such that Ir = (0). In this paper, we consider a simple undirected graph associated with R denoted by Ω(R) whose vertex set equals the set of all nonzero annihilating ideals of R and two distinct vertices I, J in this graph are joined by an edge if and only if I + J is also an annihilating ideal of R. In this paper, for any ring R which is not an integral domain, the problem of when Ω(R) is connected is discussed and if Ω(R) is connected, then it is shown that diam(Ω(R)) ≤ 2. Moreover, it is verified that gr(Ω(R)) ∈ {3, ∞}. Furthermore, rings R such that ω(Ω(R)) < ∞ are characterized.

In this paper, we show that the necessary and sufficient condition for the existence of an -factorization of is n ≡ 0 (mod k(k - 1)), for all m > 3. In fact, our result together with a result of Ushio gives a complete solution for the existence of an -factorization of for all m ≥ 3. Further, we have obtained some necessary or sufficient conditions for the existence of an -factorization of , for all even k ≥ 4 and m > 3.

A μ-simultaneous edge coloring of graph G is a set of μ proper edge colorings of G with a same color set such that for each vertex, the sets of colors appearing on the edges incident to that vertex are the same in each coloring and no edge receives the same color in any two colorings. The μ-simultaneous edge coloring of bipartite graphs has a close relation with μ-way Latin trades. Mahdian et al. (2000) conjectured that every bridgeless bipartite graph is 2-simultaneous edge colorable. Luo et al. (2004) showed that every bipartite graphic sequence S with all its elements greater than one, has a realization that admits a 2-simultaneous edge coloring. In this paper, the μ-simultaneous edge coloring of graphs is studied. Moreover, the properties of the extremal counterexample to the above conjecture are investigated. Also, a relation between 2-simultaneous edge coloring of a graph and a cycle double cover with certain properties is shown and using this relation, some results about 2-simultaneous edge colorable graphs are obtained.

Let G be an r-regular graph with order n, and G ∨ H be the graph obtained by joining each vertex of G to each vertex of H. In this paper, we prove that G ∨ K₂ is determined by its signless Laplacian spectrum for r = 1, n - 2. For r = n - 3, we show that G ∨ K₂ is determined by its signless Laplacian spectrum if and only if the complement of G has no triangles.

We count the shortest paths, not necessarily disjoint, between any two vertices in an (n, k)-star graph by counting the minimum factorizations of a permutation in terms of the transpositions corresponding to edges in that graph. This result generalizes a previous one for the star graph, and can be applied to obtain the number of the shortest paths between a pair of vertices in some of the other structures closely related to the (n, k)-star graph, such as the alternating group networks. Furthermore, the techniques made use of in this paper can be applied to solve the same problem for some of the other structures such as the arrangement graph.

Let G be a connected graph. Suppose that a fire breaks out at some vertex. A firefighter starts to protect vertices. At each time interval, the firefighter protects k vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbor on fire. The k-surviving rate ρ_k(G) of G is the average proportion of saved vertices, if the starting vertex of the fire is chosen uniformly at random. A graph G is called k-good if there is a constant c > 0 such that ρ_k(G) ≥ c. We study structural properties of planar graphs and show that planar graphs are 3-good.

In this paper, a new class of square matrix of order pm is introduced, where (p = 3, 4, 5, …), (m = 1, 2, 3, …) and for integers n, x ≥ 1. Fibonacci polynomial coding and decoding methods are followed from matrix and high code rates are obtained.

Motivated from the theory of quantum error correcting codes, we investigate a combinatorial problem that involves a symmetric n-vertices colorable graph and a group of operations (coloring rules) on the graph: find the minimum sequence of operations that maps between two given graph colorings. We provide an explicit algorithm for computing the solution of our problem, which in turn is directly related to computing the distance (performance) of an underlying quantum error correcting code. Computing the distance of a quantum code is a highly non-trivial problem and our method may be of use in the construction of better codes.

In this paper, we present exact formula for the weighted PI index of corona product of two connected graphs in terms of other graph invariants including the PI index, first Zagreb index and second Zagreb index. Then, we apply our result to compute the weighted PI indices of t-fold bristled graph, bottleneck graph, sunlet graph, star graph, fan graph, wheel graph and some classes of bridge graphs.

A median of a sequence π = ( x₁, x₂, …, x_k) of elements of a finite metric space (X, d) is an element x ∈ X for which is a minimum. The function Median with domain the set of all finite sequences on X and defined by Med(π) = {x : x is a median of π} is called the median function on X. In this paper, the median function on finite Boolean lattices is axiomatically characterized via location functions.

An antimean of a sequence π = ( x₁, x₂, …, x_k) of elements of a finite metric space (X, d) is an element x for which is maximum. The function antimean with domain the set of all finite sequences on X and defined by AMean(π) = {x : x is an antimean of π} is called the antimean function on X. In this paper, the antimean function on finite paths is characterized.

The exact value of the Gutman indices of the Cartesian product and the wreath product of graphs are obtained. Using the results obtained here, the exact Gutman indices of the hypercube, torus, grid, Hamming graph and the fence graph are given.

The frequency spectrums are inefficiently utilized and cognitive radio has been proposed for full utilization of these spectrums. The central idea of cognitive radio is to allow the secondary user to use the spectrum concurrently with the primary user with the compulsion of minimum interference. However, designing a model with minimum interference is a challenging task. In this paper, a transmission model based on cyclic generalized polynomial codes discussed in [2] and [15], is proposed for the improvement in utilization of spectrum. The proposed model assures a non interference data transmission of the primary and secondary users. Furthermore, analytical results are presented to show that the proposed model utilizes spectrum more efficiently as compared to traditional models.

Let G be a graph and W a subset of V(G). A subtree with the minimum number of edges that contains all vertices of W is a Steiner tree for W. The number of edges of such a tree is the Steiner distance of W and union of all vertices belonging to Steiner trees for W form a Steiner interval. We describe both of these for the lexicographic product of graphs. We also give a complete answer for the following invariants with respect to the Steiner convexity: the Steiner number, the rank, the hull number, and the Carathéodory number, and a partial answer for the Radon number.

An oversampling-based randomized algorithm is introduced for sorting n keys of any abstract data type on the p processors of a latency-tolerant parallel system such as a bulk-synchronous parallel computer. The algorithm is asymptotically, for large n, optimal in computation and communication compared to the best available sequential sorting algorithm, even when constant factors are taken into consideration. Its parallel time is within a (1 + o(1))/p multiplicative factor of the corresponding sequential method for sorting, improving upon other approaches for a wider range of values of p relative to n. It also improves upon other randomized sorting algorithms that have been developed for latency-tolerant models of computation on the amount of parallel slack (ratio n over p) required to achieve optimal speedup and also, on the associated failure probability. For values of p closer to n than other latency-tolerant randomized approaches, it can be turned into a PRAM-like algorithm but for such cases a speedup of O(p) rather than p/(1 + o(1)) is then achievable. Although the general framework of the proposed algorithm relies on the well-established prior idea of sample-based sorting, there are some novel features in its design such as the choice of splitter size, the way keys are split, and the handling of the base case of the recursive sorting algorithm that contribute to its performance.

A Gray code is a listing structure for a set of combinatorial objects such that some consistent (usually minimal) change property is maintained throughout adjacent elements in the list. While Gray codes for m-ary strings have been considered in the past, we provide a new, simple Gray code for fixed-weight m-ary strings. In addition, we consider a relatively new type of Gray code known as overlap cycles and prove basic existence results concerning overlap cycles for fixed-weight and weight-range m-ary words.

Let G = (V, E) be a graph and p be a positive integer. A subset S ⊆ V is called a p-dominating set of G if every vertex not in S has at least p neighbors in S. The p-domination number is the minimum cardinality of a p-dominating set in G. This paper establishes an exact formula of the p-domination number of all complete multipartite graphs for arbitrary positive integer p.