Authors:Yuanchao Li, Xiaoxue Hu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The linear [math]-arboricity [math] of a graph [math] is the least integer [math] such that [math] can be partitioned into [math] edge-disjoint forests, whose components are paths of length at most 2. In this paper, we study the linear [math]-arboricity of sparse graphs, and prove the following results: (1) let [math] be a 2-degenerate graph, we have [math]; (2) if [math], then [math]; (3) if [math], then [math]; (4) if [math], then [math]; (5) if [math], then [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-03T08:25:25Z DOI: 10.1142/S1793830917500471

Authors:Xuelian Si, Xiying Yuan Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a connected [math]-uniform hypergraph. The unique positive eigenvector [math] with [math] corresponding to spectral radius [math] is called the principal eigenvector of [math]. In this paper, we present some lower bounds for the spectral radius [math] and investigate the bounds of entries of the principal eigenvector of [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-03T08:25:24Z DOI: 10.1142/S1793830917500483

Authors:Balakrishna Krishnakumari, Mustapha Chellali, Yanamandram B. Venkatakrishnan Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A vertex [math] of a graph [math] is said to ve-dominate every edge incident to [math], as well as every edge adjacent to these incident edges. A set [math] is a vertex-edge dominating set (double vertex-edge dominating set, respectively) if every edge of [math] is [math]-dominated by at least one vertex (at least two vertices) of [math]. The minimum cardinality of a vertex-edge dominating set (double vertex-edge dominating set, respectively) of [math] is the vertex-edge domination number [math] (the double vertex-edge domination number [math], respectively). In this paper, we initiate the study of double vertex-edge domination. We first show that determining the number [math] for bipartite graphs is NP-complete. We also prove that for every nontrivial connected graphs [math], [math], and we characterize the trees [math] with [math] or [math]. Finally, we provide two lower bounds on the double ve-domination number of trees and unicycle graphs in terms of the order [math], the number of leaves and support vertices, and we characterize the trees attaining the lower bound. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-06-19T11:09:15Z DOI: 10.1142/S1793830917500458

Authors:N. K. Sudev, K. P. Chithra, K. A. Germina Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] denote a set of non-negative integers and [math] be its power set. An integer additive set-labeling (IASL) of a graph [math] is an injective set-valued function [math] such that the induced function [math] is defined by [math], where [math] is the sumset of [math] and [math]. An IASL of a signed graph [math] is an IASL of its underlying graph [math] together with the signature [math] defined by [math]. A marking of a signed graph is an injective map [math], defined by [math] for all [math]. Switching of signed graph is the process of changing the sign of the edges in [math] whose end vertices have different signs. In this paper, we discuss certain characteristics of the switched signed graphs of certain types of integer additive set-labeled signed graphs. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-06-19T11:09:14Z DOI: 10.1142/S1793830917500434

Authors:Tita Khalis Maryati, Bijan Davvaz Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. This paper presents a general framework for the study of the relations between hypergraphs and hypergroups based on approximation operators. Indeed, by a given hypergraph [math], an equivalence relation [math] on the set of vertices and using the notion of lower and upper approximations, we investigate two new hyperoperations on the set of vertices. In particular, by considering certain conditions on the equivalence relation [math], we obtain two related [math]-groups and we prove some results in this respect. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-06-19T11:09:13Z DOI: 10.1142/S1793830917500446

Authors:Jose Torres-Jimenez, Idelfonso Izquierdo-Marquez, Daniel Ramirez-Acuna, Rene Peralta Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. For [math], define [math] as the set of integers [math]. Given an integer [math] and a string [math] of length [math] over [math], we count the number of times that each one of the [math] distinct strings of length [math] over [math] occurs as a subsequence of [math]. Our algorithm makes only one scan of [math] and solves the problem in time complexity [math] and space complexity [math]. These are very close to best possible. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-05-29T09:21:56Z DOI: 10.1142/S1793830917500422

Authors:Nader Jafari Rad, Akbar Jahanbani, Doost Ali Mojdeh Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The Estrada index of a simple connected graph [math] of order [math] is defined as [math], where [math] are the eigenvalues of the adjacency matrix of [math]. In this paper, we characterize all tetracyclic graphs of order [math] with maximal Estrada index. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-05-26T08:07:33Z DOI: 10.1142/S1793830917500410

Authors:Sudipta Midya, Sankar Kumar Roy Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we analyze the interval programming using interval and rough interval (RI). Interval programming is one of the tools to tackle uncertainty in mathematical programming. In the real world situations, we often encounter the cases where the data cannot be determined with certainty. So, the value of the data is assessed using an interval. Here, we consider that the parameters of the Fixed-Charge Transportation Problem (FCTP) are imprecise. In our proposed problem, uncertainties are considered in terms of interval and RI. We present a study of the FCTP using the interval programming. An example of the FCTP is included to show the effectiveness and usefulness of our proposed study. Finally, concluding remarks and future scopes of our paper are discussed. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-05-24T06:32:07Z DOI: 10.1142/S1793830917500409

Authors:Sudev Naduvath Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. For a positive integer [math], let [math] be the set of all non-negative integers modulo [math] and [math] be its power set. A modular sumset valuation or a modular sumset labeling of a given graph [math] is an injective function [math] such that the induced function [math] defined by [math]. A modular sumset indexer of a graph [math] is an injective modular sumset valued function [math] such that the induced function [math] is also injective. In this paper, some properties and characteristics of this type of modular sumset labeling of graphs are being studied. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-05-02T09:18:57Z DOI: 10.1142/S1793830917500392

Authors:Krasimir Yordzhev Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. This work examines the problem to describe an efficient algorithm for obtaining [math] Sudoku matrices. For this purpose, we define the concepts of [math] [math]-matrix and disjoint [math]-matrices. The paper, using the set-theoretical approach, describes an algorithm for obtaining [math]-tuples of [math] mutually disjoint [math] matrices. We show that in input [math] mutually disjoint [math] matrices, it is not difficult to receive a Sudoku matrix. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-04-25T10:15:16Z DOI: 10.1142/S1793830917500380

Authors:Taranjot Kaur, Anuradha Sharma Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] denote the finite field of order [math] and characteristic [math] [math] be a positive integer coprime to [math] and let [math] be an integer. In this paper, we develop the theory of constacyclic additive codes of length [math] over [math] and provide a canonical form decomposition for these codes. By placing ordinary, Hermitian and ∗ trace bilinear forms on [math] we determine some isodual constacyclic additive codes of length [math] over [math] Moreover, we explicitly determine basis sets of all self-orthogonal, self-dual and complementary-dual negacyclic additive codes of length [math] over [math] when [math] and enumerate these three class of codes for any integer [math] with respect to the aforementioned trace bilinear forms on [math] Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-04-13T01:50:26Z DOI: 10.1142/S1793830917500379

Authors:Reza Ahmadzadeh, Sohrab Kordrostami, Alireza Amirteimoori Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Recently, network data envelopment analysis (NDEA) models have been developed to evaluate the efficiency of decision making units (DMUs) with internal structures. The network structures range from a simple two-stage process to a complex system. Looking through the literature on two-stage network structures, we see that Li et al. (2012) extended a model by assuming that the inputs to the second stage include both the outputs from the first stage and additional inputs to the second stage. In the current study, a model is proposed to evaluate the performance of these types of general two-stage network structures. To this end, we provide a linear model using fractional programming. In fact, previous models were often nonlinear models which were solved with heuristic methods. But, since the model presented in this paper is a linear model, then it can be solved easily as a linear programming problem. In order to clarify the newly proposed approach of this study, it has been applied to a case of regional Research and Development (R&D) system related to 30 provincial level regions in China and results have been compared with the heuristic method of Li et al. (2012). Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-03-31T09:28:24Z DOI: 10.1142/S1793830917500343

Authors:Jian Gao, Fanghui Ma Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Quadratic residue (QR) codes and their extensions over the finite non-chain ring [math] are studied, where [math], [math] is an odd prime and [math]. A class of Gray maps preserving the self-duality of linear codes from [math] to [math] is given. Under a special Gray map, a self-dual code [math] over [math], a formally self-dual code [math] over [math] and a formally self-dual code [math] over [math] are obtained from extended QR codes. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-03-31T09:28:24Z DOI: 10.1142/S1793830917500355

Authors:M. V. Dhanyamol, Sunil Mathew Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Certain types of transit functions are studied in this paper. Strong intervals and strong gates are introduced. Since there are different metrics available in weighted graphs, different intervals can be studied. Strong intervals and strong convexity arising out of strong geodesics are considered and as a consequence the concept of gate is introduced. Several results related to these definitions are obtained. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-03-31T09:28:23Z DOI: 10.1142/S1793830917500367

Authors:Y. M. Borse, S. R. Shaikh Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. We consider the problem of determining the possible orders for [math]-regular, [math]-connected and bipancyclic subgraphs of the hypercube [math]. For [math] and [math] the solution to the problem is known. In this paper, we solve the problem for [math] by proving that [math] has a 4-regular, 4-connected and bipancyclic subgraph on [math] vertices if and only if [math] or [math] is an even integer such that [math] Further, by improving a result of Ramras, we prove that a [math]-regular subgraph of [math] is either isomorphic to [math] or has at least [math] vertices. We also improve a result of Mane and Waphare regarding the existence of a [math]-regular, [math]-connected and bipancyclic subgraph of [math] Some applications of our results are given. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-03-21T03:07:00Z DOI: 10.1142/S179383091750032X

Authors:Nilanjan De Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The Narumi–Katayama index of a graph was introduced in 1984 for representing the carbon skeleton of a saturated hydrocarbons and is defined as the product of degrees of all the vertices of the graph. In this paper, we examine the Narumi–Katayama index of different total transformation graphs. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-03-21T03:07:00Z DOI: 10.1142/S1793830917500331

Authors:Nathaniel Karst, Joshua Langowitz, Jessica Oehrlein, Denise Sakai Troxell Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. For a positive integer [math], a radio [math]-labeling of a graph [math] is a function [math] from its vertex set to the non-negative integers such that for all pairs of distinct vertices [math] and [math], we have [math] where [math] is the distance between the vertices [math] and [math] in [math]. The minimum span over all radio [math]-labelings of [math] is called the radio [math]-chromatic number and denoted by [math]. The most extensively studied cases are the classic vertex colorings ([math]), [math](2,1)-labelings ([math]), radio labelings ([math], the diameter of [math]), and radio antipodal labelings ([math]. Determining exact values or tight bounds for [math] is often non-trivial even within simple families of graphs. We provide general lower bounds for [math] for all cycles [math] when [math] and show that these bounds are exact values when [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-03-07T08:32:32Z DOI: 10.1142/S1793830917500318

Authors:Minghui Jiang, Yong Zhang Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. We study the parameterized complexity of several problems related to perfect domination in graphs with or without small cycles. When parameterized by the solution size, these problems are W-hard in graphs with girth at most four, but are fixed-parameter tractable in graphs with girth at least five. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-03-02T07:59:38Z DOI: 10.1142/S1793830917500306

Authors:Peter Damaschke Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Suppose that some of the [math] elements of a totally ordered structure is defective, and several repair robots are at our disposal. They can dock at a random element, move at unit speed or leave, and send each other signals if there is no defective between them. We show that, by using only two robots that obey simple rules, the defective can be localized in [math] time, which is also optimal. A variation of our strategy needs three robots but has a more predictable behavior. The model is motivated by a conjectured DNA repair mechanism, and it combines group testing with geometric search. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-24T11:40:48Z DOI: 10.1142/S179383091750029X