Authors:Vinod Tyagi, Ambika Tyagi Abstract: Discrete Mathematics, Algorithms and Applications, Volume 09, Issue 04, August 2017. Byte correcting perfect codes are developed to correct burst errors within bytes. If a code is byte correcting code and we say that the code is [math]-burst correcting, meaning that it corrects a single burst of length [math] or less within a byte. A byte correcting code is such that if [math]; [math] denote the set of syndromes obtained from the [math]th-byte of the parity check matrix [math] and [math]; [math] denote the set of syndromes obtained from the [math]th-byte of the parity check matrix [math] then [math]. In an [math] code, if there are [math] bytes of size [math], then [math]. Byte correcting codes are preferred where information stored in all bytes are equally important. But there are cases where some parts of the message are more important than other parts of the message, for example, if we have to transmit a message on a border location “ Shift Battalion (Bn) from Location A to Location B” then, we will focus more on the information shift, location [math] and location [math] i.e., bytes containing these information will be more important than others. In this situation, it is needed that during transmission these bytes should have no possibility of error. In other words, these bytes should be protected absolutely against any error. Keeping this in mind, we study burst error correcting capabilities of byte oriented codes in terms of byte protection level of each byte. If there is a byte error pattern of length [math] in the transmission then all those bytes of the received pattern will be decoded correctly whose burst protection level is [math] or more even though the code word may be decoded wrongly. Taking the code length [math] to be divided into [math] bytes with burst protection level of the [math]th-byte as [math]; [math]; [math], we construct linear codes that we call byte protecting burst (BPB) codes and investigate their byte protecting capabilities in this paper. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-17T06:54:28Z DOI: 10.1142/S1793830917500513

Authors:Hiroki Izumi, Sennosuke Watanabe, Yoshihide Watanabe Abstract: Discrete Mathematics, Algorithms and Applications, Volume 09, Issue 04, August 2017. We consider the maximum 1-2 matching problem in bipartite graphs. The notion of the augmenting trail for the 1-2 matching problem, which is the extension of the notion of the augmenting path for the 1-1 matching problem is introduced. The main purpose of the present paper is to prove “the augmenting trail theorem” for the 1-2 matching problem in the bipartite graph, which is an analogue of the augmenting path theorem by Bergé for the usual 1-1 matching problems. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-17T06:54:18Z DOI: 10.1142/S1793830917500562

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

Authors:Angsuman Das Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we study the infinite graphs which admit a finite dominating set. The main contribution of the work is two folds: (i) characterization of infinite trees and hence infinite connected graphs with a finite dominating set, (ii) it is shown that apart from a family of graphs, all infinite graphs or their complements possess a finite dominating set. Moreover, some conditions of existence of finite dominating sets in product graphs are studied. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-10T10:48:55Z DOI: 10.1142/S1793830917500537

Authors:Lilian Markenzon, Christina F. E. M. Waga Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. We present in this paper a code for the class of unlabeled split–indifference graphs. This codification allows us to establish the exact number of elements of the class up to isomorphism. In order to obtain this result, structural properties of the class are explored, including a new approach for the characterization theorem. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-10T10:48:55Z DOI: 10.1142/S1793830917500550

Authors:Qirui Wang, Tianping Shuai, Wenbao Ai, Jianhua Yuan Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A graph is called [math]-equicoverable if every minimal [math]-covering of it is also its minimum [math]-covering. In this paper, we consider how to characterize a graph to be [math]-equicoverable where [math] is [math]. We obtained necessary and sufficient conditions for a graph contains a cycle with length greater than 3 but not contains any 3-cycles. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-10T10:48:54Z DOI: 10.1142/S1793830917500525

Authors:N. K. Sudev, K. P. Chithra, S. Satheesh, Johan Kok Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Coloring the vertices of a graph [math] according to certain conditions is a random experiment and a discrete random variable [math] is defined as the number of vertices having a particular color in the given type of coloring of [math] and a probability mass function for this random variable can be defined accordingly. An equitable coloring of a graph [math] is a proper coloring [math] of [math] which an assignment of colors to the vertices of [math] such that the numbers of vertices in any two color classes differ by at most one. In this paper, we extend the concepts of arithmetic mean and variance, the two major statistical parameters, to the theory of equitable graph coloring and hence determine the values of these parameters for a number of standard graphs. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-10T10:48:54Z DOI: 10.1142/S1793830917500549

Authors:J. Amjadi, S. Nazari-Moghaddam, S. M. Sheikholeslami Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A total Roman dominating function (TRDF) on a graph [math] is a function [math] satisfying the conditions (i) every vertex [math] for which [math] is adjacent at least one vertex [math] for which [math] and (ii) the subgraph of [math] induced by the set of all vertices of positive weight has no isolated vertex. The weight of a TRDF is the sum of its function values over all vertices. A total Roman dominating function [math] is called a global total Roman dominating function (GTRDF) if [math] is also a TRDF of the complement [math] of [math]. The global total Roman domination number of [math] is the minimum weight of a GTRDF on [math]. In this paper, we initiate the study of global total Roman domination number and investigate its basic properties. In particular, we relate the global total Roman domination and the total Roman domination and the global Roman domination number. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-05T07:46:43Z DOI: 10.1142/S1793830917500501

Authors:Sarika Devhare, Vinayak Joshi Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we study the non-commuting graph [math] of strictly upper triangular [math] matrices over an [math]-element chain [math]. We prove that [math] is a compact graph. From [math], we construct a poset [math]. We further prove that [math] is a dismantlable lattice and its zero-divisor graph is isomorphic to [math]. Lastly, we prove that [math] is a perfect graph. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-03T08:25:25Z DOI: 10.1142/S1793830917500495

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:Jinto James, K. A. Germina, P. Shaini Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A distance compatible set labeling (dcsl) of a connected graph [math] is an injective set assignment [math] [math] being a non-empty ground set, such that the corresponding induced function [math] given by [math] satisfies [math] for every pair of distinct vertices [math] where [math] denotes the path distance between [math] and [math] and [math] is a constant, not necessarily an integer, depending on the pair of vertices [math] chosen. A dcsl [math] of [math] is [math]-uniform if all the constants of proportionality with respect to [math] are equal to [math] and if [math] admits such a dcsl then [math] is called a [math]-uniform dcsl graph. The family [math] is well-graded family, if there is a tight path between any two of its distinct sets. A learning graph is an [math]-induced graph of a learning space. In this paper, we initiate a study on subgraphs of 1-uniform graphs which lead to the study of Knowledge Structures, Learning Spaces and Union-closed conjecture using graph theory techniques. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-06-21T09:29:23Z DOI: 10.1142/S179383091750046X

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