Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A set [math] is called a resolving set, if for each pair of distinct vertices [math] there exists [math] such that [math], where [math] is the distance between vertices [math] and [math]. The cardinality of a minimum resolving set for [math] is called the metric dimension of [math] and is denoted by [math]. A [math]-tree is a chordal graph all of whose maximal cliques are the same size [math] and all of whose minimal clique separators are also all the same size [math]. A [math]-path is a [math]-tree with maximum degree [math], where for each integer [math], [math], there exists a unique pair of vertices, [math] and [math], such that [math]. In this paper, we prove that if [math] is a [math]-path, then [math]. Moreover, we provide a characterization of all [math]-trees with metric dimension two. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-17T08:08:11Z DOI: 10.1142/S1793830917500276

Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. We study the problem of using mobile guards to defend the vertices of a graph [math] against a single attack on its vertices. A vertex cover of a graph [math] is a set [math] such that for each edge [math], at least one of [math] or [math] is in [math]. The minimum cardinality of a vertex cover is termed the vertex covering number and it is denoted by [math]. In this context, we introduce a new protection strategy called the secure vertex cover[math]SVC[math] problem, where the guards are placed at the vertices of a graph, in order to protect the graph against a single attack on its vertices. We are concerned with the protection of [math] against a single attack, using at most one guard per vertex and require the set of guarded vertices to be a vertex cover. In addition, if any guard moves along an edge to deal with an attack to an unguarded vertex, then the resulting placement of guards must also form a vertex cover. Formally, this protection strategy defends the vertices of a graph against a single attack and simultaneously protects the edges. We define a SVC to be a set [math] such that [math] is a vertex cover and for each [math], there exists a [math] such that [math] is a vertex cover. The minimum cardinality of an SVC is called the secure vertex covering number and it is denoted by [math]. In this paper, a few properties of SVC of a graph are studied and specific values of [math] for few classes of well-known graphs are evaluated. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-17T08:08:08Z DOI: 10.1142/S1793830917500264

Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a commutative ring with identity and [math] be the set of ideals with nonzero annihilator. The strongly annihilating-ideal graph of [math] is defined as the graph [math] with the vertex set [math] and two distinct vertices [math] and [math] are adjacent if and only if [math] and [math]. It is proved that [math] is connected with diameter at most two and with girth at most four, if it contains a cycle. Moreover, we characterize all rings whose strongly annihilating-ideal graphs are complete or star. Furthermore, we study the affinity between strongly annihilating-ideal graph and annihilating-ideal graph (a well-known graph with the same vertices and two distinct vertices [math] are adjacent if and only if [math]) associated with a commutative ring. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-17T08:08:07Z DOI: 10.1142/S1793830917500288

Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be the set of trees with [math] vertices. The first six trees with the maximal Estrada indices in [math] with [math] were previously reported. A new transformation for studying the Estrada index is introduced. Then, with the aid of the new transformation, we completely deduce the 7th to the 13th trees with the maximal Estrada indices in [math] with [math]. Furthermore, for the trees in [math] with [math], we obtain the relationship among three decreasing orders, namely, by their largest Estrada indices, by their largest eigenvalues, and by their largest resolvent Estrada indices, respectively. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-10T05:53:02Z DOI: 10.1142/S1793830917500252

Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a family of graphs. The anti-Ramsey number [math] for [math] in the graph [math] is the maximum number of colors in an edge coloring of [math] that does not have any rainbow copy of any graph in [math]. In this paper, we consider the anti-Ramsey number for matchings in regular bipartite graphs and determine its value under several conditions. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-10T05:53:01Z DOI: 10.1142/S1793830917500197

Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A Roman dominating function (RDF) on a graph [math] is a function [math] satisfying the condition that every vertex [math] with [math] is adjacent to at least one vertex [math] of [math] for which [math]. The weight of a RDF is the sum [math], and the minimum weight of a RDF [math] is the Roman domination number [math]. A subset [math] of [math] is a [math]-independent set of [math] if every vertex of [math] has at most one neighbor in [math] The maximum cardinality of a [math]-independent set of [math] is the [math]-independence number [math] Both parameters are incomparable in general, however, we show that if [math] is a tree, then [math]. Moreover, all extremal trees attaining equality are characterized. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-10T05:52:59Z DOI: 10.1142/S1793830917500239

Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we study the signed [math]-domination and its total version in graphs. By a simple uniform approach we give some new upper and lower bounds on these two parameters of a graph in terms of several different graph parameters. In this way, we can improve and generalize some results in literature. Moreover, we make use of the well-known theorem of Turán [On an extremal problem in graph theory, Math. Fiz. Lapok 48 (1941) 436–452] to bound the signed total [math]-domination number, [math], of a [math]-free graph [math] for [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-10T05:52:59Z DOI: 10.1142/S1793830917500240

Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The Mycielski’s construction is a well-known construction on graphs which transforms a [math]-chromatic triangle-free graph [math] into a [math]-chromatic triangle-free graph [math] which is called the Mycielski graph of [math]. In this paper, we compute the Harary index, additively weighted Harary index, and multiplicatively weighted Harary index of the Mycielski graph of any simple connected graph with girth greater than 6. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-10T05:52:57Z DOI: 10.1142/S1793830917500227

Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. There tend to be no related researches regarding the relationships between graph theory and languages ever since the concept of graph-semigroup was first proposed in 1991. In 2011, after finding out the inner co-relations among digraphs, undirected graphs and languages, we proposed certain concepts including undirected graph language and digraph language; moreover, in 2014, we proposed a broaden concept–(V,R)-language and proved: (1) both undirected graph language and digraph language are (V,R)-languages; (2) both undirected graph language and digraph language are regular languages; (3) natural languages are regular languages. In this paper, we propose a new concept–Random Graph Language and build the relationships between random graph and language, which provides researchers with the possibility to do research about languages by using random graph theory. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-02-10T05:52:56Z DOI: 10.1142/S1793830917500203

Authors:Angsuman Das Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. This paper introduces a new domination parameter called coefficient of domination of a graph, which measures the maximum possible efficiency of domination for the given graph. It is evaluated for various classes of graphs and different bounds are proposed. Finally, Nordhaus–Gaddum type inequalities are established for coefficient of domination of a graph and its complement. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-01-26T08:36:20Z DOI: 10.1142/S1793830917500185

Authors:Francesco M. Malvestuto Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. We introduce a new notion of convexity in digraphs, which we call incoming-path convexity, and prove that the incoming-path convexity space of a digraph is a convex geometry (that is, it satisfies the Minkowski–Krein–Milman property) if and only if the digraph is acyclic. Moreover, we prove that incoming-path convexity is adequate to characterize collapsibility of models generated by Bayesian networks. Based on these results, we also provide simple linear algorithms to solve two topical problems on Markov properties of a Bayesian network (that is, on conditional independences valid in a Bayesian network). Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-01-10T06:08:36Z DOI: 10.1142/S1793830917500161

Authors:P. Chella Pandian Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we give lower and upper bounds on the covering radius of codes over the ring [math] where [math] with respect to Chinese Euclidean distance and also obtain the covering radius of various Repetition codes, Simplex codes of [math]-Type code and [math]-Type code. We give bounds on the covering radius for MacDonald codes of both types over [math] Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-01-10T06:08:36Z DOI: 10.1142/S1793830917500173

Authors:Jing Jin, Yiming Wei Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A graph [math] is [math]-choosable if it has an [math]-coloring whenever [math] is a list assignment such that [math] for all [math]. We provide two sufficient conditions for 3-choosability of plane graphs. Every plane graph with [math] without cycles of length from 4 to 6 and special 7-cycles is 3-choosable. Every plane graph with [math] without cycles of length from 4 to 5 and adjacent 6-cycles is also 3-choosable. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-12-27T05:32:52Z DOI: 10.1142/S1793830917500112

Authors:Lin-Zhi Shen, Fang-Wei Fu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The [math]-incorrigible set distributions of binary linear codes over the erasure channels can be used to determine the decoding error probability of a linear code under maximum likelihood decoding and [math]-list decoding. In this short paper, we give the [math]-incorrigible set distributions of some linear codes by the finite geometry theory. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-12-27T05:32:51Z DOI: 10.1142/S1793830917500124

Authors:Taher Abualrub, N. Aydin Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Motivated by a generalization of the football pool problem, we introduce additive cyclic codes over mixed alphabets of the form [math] where [math], [math] for distinct primes [math]. We study their algebraic properties, generating sets, and duals. Additionally, we give examples of additive cyclic codes over the alphabet [math] that have best-known or optimal parameters. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-12-27T05:32:51Z DOI: 10.1142/S1793830917500100

Authors:Bu Yuehua, Zhu Hongguo Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A strong[math]-edge-coloring of a graph [math] is a mapping [math]: [math], such that [math] for every pair of distinct edges at distance at most two. The strong chromatical index of a graph [math] is the least integer [math] such that [math] has a strong-[math]-edge-coloring, denoted by [math]. In this paper, we prove [math] for any subcubic planar graph with [math] and [math]-cycles are not adjacent to [math]-cycles. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-12-27T05:32:51Z DOI: 10.1142/S1793830917500136

Authors:Johan Kok, N. K. Sudev, U. Mary Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a finite and simple undirected connected graph of order [math] and let [math] be a proper vertex coloring of [math]. Denote [math] simply, [math]. In this paper, we introduce a variation of the well-known Zagreb indices by utilizing the parameter [math] instead of the invariant [math] for all vertices of [math]. The new indices are called chromatic Zagreb indices. We study these new indices for certain classes of graphs and introduce the notion of chromatically stable graphs. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-12-27T05:32:50Z DOI: 10.1142/S1793830917500148

Authors:Ömer Eğecioğlu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Galileo sequences are generalizations of a simple sequence of integers that Galileo used in early 17th century for describing his law of falling bodies. The curious property he noted happens to be exactly what is needed to quantify his observation that the acceleration of falling bodies is uniform. Among the generalizations and extensions later given are iterated Galileo sequences. We show that these are closely related to polynomials that arise in enumerating integers by their Hamming weight. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-12-23T02:18:57Z DOI: 10.1142/S179383091750015X

Authors:Eunjeong Yi Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a graph with vertex set [math] and edge set [math]. If [math] has no isolated vertex, then a disjunctive total dominating set (DTD-set) of [math] is a vertex set [math] such that every vertex in [math] is adjacent to a vertex of [math] or has at least two vertices in [math] at distance two from it, and the disjunctive total domination number [math] of [math] is the minimum cardinality overall DTD-sets of [math]. Let [math] and [math] be two disjoint copies of a graph [math], and let [math] be a bijection. Then, a permutation graph [math] has the vertex set [math] and the edge set [math]. For any connected graph [math] of order at least three, we prove the sharp bounds [math]; we give an example showing that [math] can be arbitrarily large. We characterize permutation graphs for which [math] holds. Further, we show that [math] when [math] is a cycle, a path, and a complete [math]-partite graph, respectively. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-11-25T02:44:41Z DOI: 10.1142/S1793830917500094

Authors:Ramanjit Kumar, Surinder Pal Singh Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. We prove the Boyer’s conjecture for graphs having a perfect matching. That is, if [math] is such a graph of order [math] then [math] We also prove an upper bound for the SIG-dimension of any graph without isolated vertices, along with some other results on SIG-dimension. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-11-23T08:12:30Z DOI: 10.1142/S1793830917500082

Authors:Maryam Roozbayani, Hamid Reza Maimani Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Identifying code in graph [math] is a subset [math] of [math] such that [math] for every [math] of [math] and [math] for every [math] of [math]. The minimum size of identifying codes of graph [math] is denoted by [math]. A watching system in a graph [math] is a set [math], where [math] and [math] is a subset of closed neighborhood of [math] such that the sets [math] are nonempty and distinct, for any [math]. The minimum size of a watching system of [math] is denoted by [math]. In this paper, we show if [math], then [math] if [math] (mod 3) and [math] if [math] (mod 3). Also we show that [math]. This means that in this family of graphs the watching system is more efficient than identifying code. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-11-23T02:54:02Z DOI: 10.1142/S1793830917500070

Authors:I. Keerthi Asir, S. Athisayanathan Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we define the clique-to-vertex [math]–[math] monophonic path, the clique-to-vertex monophonic distance [math], the clique-to-vertex monophonic eccentricity [math], the clique-to-vertex monophonic radius [math], and the clique-to-vertex monophonic diameter [math], where [math] is a clique and [math] a vertex in a connected graph [math]. We determine these parameters for some standard graphs. We show the inequality among the clique-to-vertex distance, the clique-to-vertex monophonic distance, and the clique-to-vertex detour distance in graphs. Also, it is shown that the clique-to-vertex geodesic, the clique-to-vertex monophonic, and the clique-to-vertex detour are distinct in [math]. It is shown that [math] for every connected graph [math] and that every two positive integers [math] and [math] with [math] are realizable as the clique-to-vertex monophonic radius and clique-to-vertex monophonic diameter of some connected graph. Also, it is shown any three positive integers [math] with [math] are realizable as the clique-to-vertex radius, clique-to-vertex monophonic radius, and clique-to-vertex detour radius of some connected graph and also it is shown that any three positive integers [math] with [math] are realizable as the clique-to-vertex diameter, clique-to-vertex monophonic diameter, and clique-to-vertex detour diameter of some connected graph. We introduce the clique-to-vertex monophonic center [math] and the clique-to-vertex monophonic periphery [math] and it is shown that the clique-to-vertex monophonic center does not lie in a single block of [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-10-25T03:42:31Z DOI: 10.1142/S1793830917500045

Authors:Haixia Guo, You Gao Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A resolving set for an association scheme [math] is a set of points [math] such that, for all [math], the ordered list of relations [math] uniquely determines [math], where [math] denotes the relation [math] containing the pair [math] in [math]. In this paper, we determine upper bounds on class dimension for a family of association schemes in singular linear spaces, and construct their resolving sets for a special case. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-10-25T03:42:31Z DOI: 10.1142/S1793830917500057

Authors:J. John, N. Arianayagam Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. For a connected graph [math], a set [math] is called a detour dominating set of [math], if [math] is a detour set and dominating set of [math]. The detour domination number [math] of [math] is the minimum order of its detour dominating sets and any detour dominating set of order [math] is called a [math] - set of [math]. The detour domination numbers of some standard graphs are determined. Connected graph of order [math] with detour domination number [math] or [math] is characterized. For positive integers [math] and [math] with [math], there exists a connected graph with [math] and [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-10-25T03:42:30Z DOI: 10.1142/S1793830917500069

Authors:S. Balamurugan Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A set of [math] of vertices in a graph [math] is called a dominating set if every vertex of [math] is adjacent to an element of [math]. Further, if [math] has an isolated vertex, then [math] is called an isolate dominating set. The minimum cardinality of an isolate dominating set of a graph [math] is called the isolate domination number, denoted by [math]. This paper examines the effects of removal of an edge on the isolate domination number of a graph. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-10-19T10:09:27Z DOI: 10.1142/S1793830917500033

Authors:Reza Alimoradi Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Recently, by changing security requirments of computer networks, many public key schemes are introduced. One major shortcoming of identity-based cryptosystems is key screw. Certificateless public key cryptosystems were introduced to solve this problem. In this paper, a certificateless, public-key, multiple-key-agreement scheme will be offered which has some significant security properties such as perfect forward secrecy, strong security, and zero-knowledge proof. This scheme produces far more shared hidden keys per session in comparison with many existing schemes. In this paper, the security and the efficiency of the proposed scheme will be compared with some well-known current schemes. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-10-14T11:42:37Z DOI: 10.1142/S1793830917500021

Authors:Sumit Kumar Jha Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. We revisit the method of Kirschenhofer, Prodinger and Tichy to calculate the moments of number of comparisons used by the randomized quick sort algorithm. We reemphasize that this approach helps in calculating these quantities with less computation. We also point out that as observed by Knuth this method also gives moments for total path length of a binary search tree built over a random set of [math] keys. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2016-10-04T09:09:27Z DOI: 10.1142/S179383091750001X