Authors:R. Rajarajachozhan, R. Sampathkumar Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A modular [math]-coloring, [math] of a graph [math] is a coloring of the vertices of [math] with the elements in [math] the set of integers modulo [math] having the property that for every two adjacent vertices of [math] the sums of the colors of their neighbors are different in [math] The minimum [math] for which [math] has a modular [math]-coloring is the modular chromatic number of [math] This paper is concerned with the modular chromatic number of the Cartesian products [math] [math] and [math] Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-11-24T02:51:55Z DOI: 10.1142/S1793830917500756

Authors:Kairi Kangro, Mozhgan Pourmoradnasseri, Dirk Oliver Theis Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A dispersed Dyck path (DDP) of length [math] is a lattice path on [math] from [math] to [math] in which the following steps are allowed: “up” [math]; “down” [math]; and “right” [math]. An ascent in a DDP is an inclusion-wise maximal sequence of consecutive up steps. A 1-ascent is an ascent consisting of exactly 1 up step. We give a closed formula for the total number of 1-ascents in all dispersed Dyck paths of length [math], #A191386 in Sloane’s OEIS. Previously, only implicit generating function relations and asymptotics were known. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-11-15T07:55:29Z DOI: 10.1142/S179383091750077X

Authors:A. Mallika, R. Kala Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a commutative ring with identity. The cozero-divisor graph of [math], denoted by [math], is a graph whose vertex set is [math], the set of all non-zero and non-unit elements of [math]. Two distinct vertices [math] and [math] in [math] are adjacent if and only if [math] and [math]. The Crosscap of a graph [math], denoted by [math], is the minimum integer [math] such that the graph can be embedded in the non-orientable surface [math]. The planar graph is called [math]-outerplanar if removing all the vertices incident on the outer face yields a [math]-outerplanar. The Outerplanarity index of a graph [math] is the smallest [math] such that [math] is [math]-outerplanar. In this paper, we characterize the class of rings [math] (up to isomorphism) for which [math]. Further we characterize all finite rings [math] (up to isomorphism) for which [math] has an outerplanarity index two. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-11-14T07:59:36Z DOI: 10.1142/S1793830917500744

Authors:Jose Torres-Jimenez, Jose Carlos Perez-Torres, Gildardo Maldonado-Martinez Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A hypergraph [math] with vertex set [math] and edge set [math] differs from a graph in that an edge can connect more than two vertices. An r-uniform hypergraph [math] is a hypergraph with hyperedges of size [math]. For an r-uniform hypergraph [math], an r-uniform clique is a subset [math] of [math] such as every subset of [math] elements of [math] belongs to [math]. We present hClique, an exact algorithm to find a maximum r-uniform clique for [math]-uniform graphs. In order to evidence the performance of hClique, 32 random [math]-graphs were solved. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-11-14T07:59:36Z DOI: 10.1142/S1793830917500781

Authors:Gurupada Maity, Sankar Kumar Roy Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. This paper explores the study of fuzzy transportation problem (FTP) using multi-choice goal-programming approach. Generally, the decision variable in transportation problem (TP) is considered as real variable, but here the decision variable in each node is chosen from a set of multi-choice fuzzy numbers. Here, we formulate a mathematical model of FTP considering fuzzy goal to the objective function. Thereafter, the solution procedure of the proposed model is developed through multi-choice goal programming approach. The proposed approach is not only improved the applicability of goal programming in real world situations but also provided useful insight about the solution of a new class of TP. A real-life numerical experiment is incorporated to analyze the feasibility and usefulness of this paper. The conclusions about our proposed work including future studies are discussed last. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-11-13T09:12:16Z DOI: 10.1142/S1793830917500768

Authors:Pinkimani Goswami, Madan Mohan Singh, Bubu Bhuyan Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. At Eurocrypt ’99, Paillier showed a cryptographic application of the group [math], the multiplicative group modulo [math] where [math] is some RSA modulus. In this paper, we have present a new public key cryptosystem over [math] where [math] is a product of two safe primes, which is based on two intractable problems namely, integer factorization and partial discrete logarithm problem over [math], the group of quadratic residues modulo [math]. This scheme is a combination of BCP (Bresson–Catalano–Pointcheval) cryptosystem, proposed by Bresson et al. at Asiacrypt ’03 and the Rabin–Paillier scheme proposed by Galindo et al. at PKC 2003. We will show that the one-wayness of this new scheme equally depends on the Computational Diffie–Hellman assumption and factoring assumption. We will also prove that the proposed scheme is more secure than the BCP cryptosystem and the Rabin–Paillier cryptosystem. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-26T08:34:37Z DOI: 10.1142/S179383091750080X

Authors:Zichong Chen Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a tree of given order [math] with diameter [math] and [math] the number of subtrees of [math]. In this paper, we show that: μ(T) ≤ d − 2 2 d 2 + d 2 + 1 d 2 + 1 2n−d−1 + n − 1 and the equality holds if and only if [math]; (2) If [math] and [math], then μ(T) ≥ 3ℓ5n−2ℓ−1 3 + 2n − 2 − ℓ and the equality holds if and only if [math], where [math] (mod 3) with [math], and [math] (mod 3) with [math]; (3) If [math], [math] and [math] (mod [math]) for [math] with [math], then μ(T) ≥ 32−r35n+2r3−6 3 + (6 − 2r3)5n+2r3−6 6 + 2n − 6 + r3 if [math], μ(T) ≥ 32−r35n+2r3−6 3 + 5n+2r3−3 6 + 32−r35n+2r3−9 6 + 2n − 6 + r3 if [math], and the equalities hold if and only if [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-26T08:34:37Z DOI: 10.1142/S1793830918500015

Authors:Yi Zhang, Mei Lu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A matching of a [math]-uniform hypergraph is a set of pairwise disjoint edges. A [math]-matching in a [math]-uniform hypergraph [math] is a matching of size [math]. Let [math] be a [math]-uniform hypergraph of order [math] and [math]. If [math] for any two adjacent vertices [math], and [math], then [math] contains a [math]-matching. This result is an extension of a work of Bollobás, Daykin and Erdős [Sets of independent edges of a hypergraph, Quart. J. Math. Oxford 21 (1976) 25–32]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-19T09:04:45Z DOI: 10.1142/S1793830917500720

Authors:Ishwar Baidari, Preeti Savant Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we present a new index called min–max distance degree index, [math] for molecular graphs. It appears that this index correlates well with properties of 33 and 28 nonanes like, energy of formation and density, and its correlation coefficient is 0.812 and 0.754, respectively. The basic mathematical features and graph operations are presented. In addition, the linear regression analysis of predicted and experimental boiling point of acyclic hydrocarbons is shown, where predicted boiling point is determined by implementing this index with Wiener’s model. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-19T09:04:45Z DOI: 10.1142/S1793830917500732

Authors:Muhammad Naeem, Muhammad Kamran Siddiqui Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a graph. A total labeling [math] is called totally irregular total [math]-labeling of [math] if every two distinct vertices [math] and [math] in [math] satisfy [math] and every two distinct edges [math] and [math] in [math] satisfy [math] where [math] and [math] The minimum [math] for which a graph [math] has a totally irregular total [math]-labeling is called the total irregularity strength of [math], denoted by [math] In this paper, we determined the total irregularity strength of disjoint union of [math] isomorphic copies of generalized Petersen graph. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-19T09:04:44Z DOI: 10.1142/S1793830917500719

Authors:M. Al Tahan, B. Davvaz Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Cyclic hypergroups are of great importance due to their applications to many fields in mathematics. In this paper, we classify all commutative single power cyclic hypergroups of order three and period two. Moreover, we prove some new interesting properties regarding cyclic hypergroups. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-10T01:55:30Z DOI: 10.1142/S1793830917500707

Authors:Gruia Calinescu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Given an edge-weighted undirected hypergraph [math] and an even-sized set of vertices [math], a T-cut is a partition of [math] into two parts [math] and [math] such that [math] is odd. A T-join in [math] for [math] is a set of hyperedges [math] such that for every T-cut [math] there is a hyperedge [math] intersecting both [math] and [math]. A directed hypergraph has for every hyperedge exactly one vertex, called the head, and several vertices, that are tails. A directed hypergraph is strongly connected if there exists at least one directed path between any two vertices of the hypergraph, where a directed path is defined to be a sequence of vertices and hyperedges for which each hyperedge has as one of its tails the vertex preceding it and as its head the vertex following it in the sequence. Orienting an undirected hypergraph means choosing a head for each hyperedge. We prove that every edge-weighted undirected hypergraph that admits a strongly connected orientation has a T-join of total weight at most 7/8 times the total weight of all the edges of the hypergraph, and sketch an improvement to 4/5. We also exhibit a series of example showing that one cannot improve the constant above to [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-28T04:13:02Z DOI: 10.1142/S1793830917500689

Authors:R. Vasanthi, K. Subramanian Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a simple and connected graph. A dominating set [math] is said to be a vertex covering transversal dominating set if it intersects every minimum vertex covering set of [math]. The vertex covering transversal domination number [math] is the minimum cardinality among all vertex covering transversal dominating sets of [math]. A vertex covering transversal dominating set of minimum cardinality [math] is called a minimum vertex covering transversal dominating set or simply a [math]-set. In this paper, we prove some general theorems on the vertex covering transversal domination number of a simple connected graph. We also provide some results about [math]-sets and try to classify those sets based on their intersection with the minimum vertex covering sets. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-28T04:13:02Z DOI: 10.1142/S1793830917500690

Authors:G. L. Chia, W. Hemakul, S. Singhun Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The square of a graph [math] is the graph obtained from [math] by adding edges joining those pairs of vertices whose distance from each other in [math] is two. If [math] is connected, then the cyclomatic number of [math] is defined as [math]. Graphs with cyclomatic number not more than [math] whose square are panconnected have been characterized, among other things, in [G. L. Chia, S. H. Ong and L. Y. Tan, On graphs whose square have strong Hamiltonian properties, Discrete Math. 309 (2009) 4608–4613, G. L. Chia, W. Hemakul and S. Singhun, Graphs with cyclomatic number two having panconnected square, Discrete Math. 311 (2011) 850–855]. Here, we show that if [math] has cyclomatic number [math] and [math] is panconnected, then [math] is one of the eight families of graphs, [math], defined in the paper. Further, we obtain necessary and sufficient conditions for three larger families of graphs (which contains [math] as special cases) whose square are panconnected. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-28T04:13:02Z DOI: 10.1142/S1793830917500677

Authors:Muhammad Imran, Shehnaz Akhter Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The topological indices are useful tools to the theoretical chemists that are provided by the graph theory. They correlate certain physicochemical properties such as boiling point, strain energy, stability, etc. of chemical compounds. For a graph [math], the double graph [math] is a graph obtained by taking two copies of graph [math] and joining each vertex in one copy with the neighbors of corresponding vertex in another copy and strong double graph SD[math] of the graph [math] is the graph obtained by taking two copies of the graph [math] and joining each vertex [math] in one copy with the closed neighborhood of the corresponding vertex in another copy. In this paper, we compute the general sum-connectivity index, general Randi[math] index, geometric–arithmetic index, general first Zagreb index, first and second multiplicative Zagreb indices for double graphs and strong double graphs and derive the exact expressions for these degree-base topological indices for double graphs and strong double graphs in terms of corresponding index of original graph [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-12T03:28:08Z DOI: 10.1142/S1793830917500665

Authors:William F. Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we consider dominating sets [math] and [math] such that [math] and [math] are disjoint and there exists a perfect matching between them. Let [math] denote the cardinality of smallest such sets [math] in [math] (provided they exist, otherwise [math]). This concept was introduced in [W. F. Klostermeyer, M. E. Messinger and A. Angeli Ayello, An eternal domination problem in grids, Theory Appl. Graphs 4(1) (2017) 23pp.] in the context of studying a certain graph protection problem. We characterize the trees [math] for which [math] equals a certain graph protection parameter and for which [math], where [math] is the independence number of [math]. We also further study this parameter in graph products, e.g., by giving bounds for grid graphs, and in graphs of small independence number. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-08T02:37:59Z DOI: 10.1142/S1793830917500653

Authors:Ali Ahmad Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Graphene is an atomic scale honeycomb lattice made of the carbon atoms. Graph theory has given scientific expert an assortment of helpful apparatuses, for example, topological indices. A topological index [math] of a graph [math] is a number with the property that for each graph [math] isomorphic to [math] [math]. In this paper, we exhibit correct expressions for some topological indices for para-line graph of honeycomb networks and graphene. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-05T01:20:36Z DOI: 10.1142/S1793830917500641

Authors:K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner, H. C. Wauck Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Permutation sorting, one of the fundamental steps in pre-processing data for the efficient application of other algorithms, has a long history in mathematical research literature and has numerous applications. Two special-purpose sorting operations are considered in this paper: context directed swap, (cds) and context directed reversal, (cdr). These are special cases of sorting operations that were studied in prior work on permutation sorting. Moreover, cds and cdr have been postulated to model molecular sorting events that occur in the genome maintenance program of certain species of single-celled organisms called ciliates. This paper investigates mathematical aspects of these two sorting operations. The main result of this paper is a generalization of previously discovered characterizations of cds-sortability of a permutation. The combinatorial structure underlying this generalization suggests natural combinatorial two-player games. These games are the main mathematical innovation of this paper. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-25T07:18:08Z DOI: 10.1142/S179383091750063X

Authors:Blanca Isabel Niel Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The resolutions of the different Shortest and Longest Euclidean Hamiltonian Path Problems on the vertices of simple regular [math]-Gons, by means of a geometric and arithmetic algorithm allow us to define winding indexes for Euclidean Hamiltonian cycles. New statements characterize orientation of non-necessarily regular Hamiltonian cycles on the [math]th roots of the unity embedded in the plane and deal with the existence of reflective bistarred Hamiltonian tours on vertices of coupled [math]-Gons. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-08T07:40:05Z DOI: 10.1142/S1793830917500616

Authors:Jyhmin Kuo, Hung-Lin Fu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A set of vertices of a graph whose removal leaves an acyclic graph is referred as a decycling set, or a feedback vertex set, of the graph. The minimum cardinality of a decycling set of a graph [math] is referred to as the decycling number of [math]. For [math], the generalized de Bruijn digraph [math] is defined by congruence equations as follows: [math] and [math]. In this paper, we give a systematic method to find a decycling set of [math] and give a new upper bound that improve the best known results. By counting the number of vertex-disjoint cycles with the idea of constrained necklaces, we obtain new lower bounds on the decycling number of generalized de Bruijn digraphs. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-08T07:40:05Z DOI: 10.1142/S1793830917500628

Authors:Farzad Shaveisi Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A simple graph [math] is called [math]-bounded if for every two nonadjacent vertices [math] of [math] there exists a vertex [math] such that [math], where [math] denotes the set of neighbors of the vertex [math] in [math]. In this paper, some properties of [math]-bounded graphs are studied. It is shown that any bipartite [math]-bounded graph is a complete bipartite graph with at most two horns; in particular, any [math]-bounded tree is either a star or a two-star graph. Also, we prove that any non-end vertex of every [math]-bounded graph is contained in either a triangle or a rectangle. Among other results, it is shown that all regular [math]-bounded graphs are strongly regular graphs. Finally, we determine that how many edges can an [math]-bounded graph have' Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-07T03:22:01Z DOI: 10.1142/S1793830917500604

Authors:Faïçal Bouazizi, Zaineb Guetif, Sami Hidouri Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In the present paper, we propose two new simple algorithms for computing the minimal polynomial of cos([math]) based on Galois theory. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-28T11:42:46Z DOI: 10.1142/S1793830917500598

Authors:K. Selvakumar, P. Subbulakshmi, Jafar Amjadi Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a commutative ring with identity. We consider a simple graph associated with [math], denoted by [math], whose vertex set is the set of all non-trivial ideals of [math] and two distinct vertices [math] and [math] are adjacent whenever [math] or [math]. In this paper, we characterize the commutative Artinian non-local ring [math] for which [math] has genus one and crosscap one. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-19T06:43:50Z DOI: 10.1142/S1793830917500586

Authors:Tran Dan Thu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. We introduce a generic identity based on the Ahlswede–Zhang (AZ) function, which can be considered as a template to establish AZ-style identities. Many AZ-style identities can be derived from the generic identity. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-17T02:56:03Z DOI: 10.1142/S1793830917500574