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

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

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

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

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

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:Ö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