Discrete Mathematics, Algorithms and Applications
Number of Followers: 2 Hybrid journal (It can contain Open Access articles) ISSN (Print) 17938309  ISSN (Online) 17938317 Published by World Scientific [120 journals] 
 Average degree matrix and average degree energy

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: H. S. Sujatha
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
If [math] is a simple graph on [math] vertices [math] and [math] be the degree of [math]th vertex [math] then the average degree matrix of graph [math], [math] is of order [math] whose [math]th entry is [math] if the vertices [math] and [math] are adjacent and zero otherwise. The average degree energy of [math], [math] is the sum of all absolute value of eigenvalues of average degree matrix of a graph [math]. In this paper, bounds for average degree energy [math] and the relation between average degree energy [math] and energy [math] is discussed.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220520T07:00:00Z
DOI: 10.1142/S1793830922501014

 LCD matrix product codes with an application

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Sanjit Bhowmick, Satya Bagchi, Ramakrishna Bandi
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Matrix product (MP) codes over a finite field [math], where [math] a prime power, were first introduced by Blackmore and Norton [MP codes over [math], Appl. Algebra Engrg. Comm. Comput. 12 (2001) 477–500]. This paper investigates linear complementary dual (LCD) MP codes over finite commutative Frobenius rings. We derive a necessary and sufficient condition for an MP code to have an LCD. We provide some efficient constructions of LCD MP codes. Finally, we have shown an application on cryptography of LCD codes.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220520T07:00:00Z
DOI: 10.1142/S179383092250104X

 The adjacency spectrum and metric dimension of an induced subgraph of
comaximal graph of [math]
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Subarsha Banerjee
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a commutative ring with unity, and let [math] denote the comaximal graph of [math]. The comaximal graph [math] has vertex set as [math], and any two distinct vertices [math] of [math] are adjacent if [math]. Let [math] denote the induced subgraph of [math] on the set of all nonzero nonunit elements of [math], and any two distinct vertices [math] of [math] are adjacent if [math]. In this paper, we study the graphical structure as well the adjacency spectrum of [math], where [math] is a nonprime positive integer, and [math] is the ring of integers modulo [math]. We show that for a given nonprime positive integer [math] with [math] number of positive proper divisors, the eigenvalues of [math] are [math] with multiplicity [math], and remaining eigenvalues are contained in the spectrum of a symmetric [math] matrix. We further calculate the rank and nullity of [math]. We also determine all the eigenvalues of [math] whenever [math] is a bipartite graph. Finally, apart from determining certain structural properties of [math], we conclude the paper by determining the metric dimension of [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220513T07:00:00Z
DOI: 10.1142/S1793830922500938

 The size multipartite Ramsey numbers [math]

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yaser Rowshan, Mostafa Gholami
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Assume that [math] is a complete, and multipartite graph consisting of [math] partite sets and [math] vertices in each partite set. For given graphs [math], the multipartite Ramsey number (MRnumber) [math], is the smallest integer [math], such that for any [math]edgecoloring [math] of the edges of [math], [math] contains a monochromatic copy of [math] for at least one [math]. The size of MRnumber [math] for [math], the size of MRnumber [math] for [math] and [math], and the size of MRnumber [math] for [math] and [math] have been computed in several papers up to now. In this paper, we determine some lower bounds for the MRnumber [math] for each [math], and some values of MRnumber [math] for some [math], and each [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220513T07:00:00Z
DOI: 10.1142/S1793830922500999

 Complexity aspects of restrained Roman domination in graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Padamutham Chakradhar
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a simple, undirected graph [math], a restrained Roman dominating function (rRDF) [math] has the property that, every vertex [math] with [math] is adjacent to at least one vertex [math] for which [math] and at least one vertex [math] for which [math]. The weight of an rRDF is the sum [math]. The minimum weight of an rRDF is called the restrained Roman domination number (rRDN) and is denoted by [math]. We show that restrained Roman domination and domination problems are not equivalent in computational complexity aspects. Next, we show that the problem of deciding if [math] has an rRDF of weight at most [math] for chordal and bipartite graphs is NPcomplete. Finally, we show that rRDN is determined in linear time for bounded treewidth graphs and threshold graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220510T07:00:00Z
DOI: 10.1142/S1793830922500963

 Some results on majority bad number

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: I. Sahul Hamid, S. Anandha Prabhavathy
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A twovalued function [math] defined on the vertices of a graph [math] is a majority bad dominating function (MBDF), if the sum of its function values over at least half the closed neighborhoods is at most one. That is, for at least half the vertices [math], [math], where [math] consists of [math] and every vertex adjacent to [math]. The majority bad domination number of a graph [math], is denoted by [math], and is defined as [math]. In this paper, we determine some results on majority bad number.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220510T07:00:00Z
DOI: 10.1142/S1793830922500987

 The restrained double geodetic number of a graph

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: A. P. Santhakumaran, K. Ganesamoorthy
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a connected graph [math] of order at least two, a double geodetic set [math] of a graph [math] is a restrained double geodetic set if either [math] or the subgraph induced by [math] has no isolated vertices. The minimum cardinality of a restrained double geodetic set of [math] is the restrained double geodetic number of [math] and is denoted by [math]. The restrained double geodetic number of some standard graphs is determined. It is proved that for a nontrivial connected graph [math] [math] if and only if [math]. It is shown that for any three positive integers [math] with [math], there is a connected graph [math] with [math], [math] and [math], where [math] is the geodetic number and [math] is the restrained geodetic number of a graph [math]. It is also shown that for every pair [math], [math] of positive integers with [math], there is a connected graph [math] with [math] and [math], where [math] is the double geodetic number of a graph [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220510T07:00:00Z
DOI: 10.1142/S1793830922501002

 Maximum independent sets in a proper monograph determined through a
signature
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: S. M. Hegde, Y. M. Saumya
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a nonempty, finite graph. If the vertices of [math] can be bijectively labeled by a set [math] of positive distinct real numbers with two vertices being adjacent if and only if the positive difference of the corresponding labels is in [math], then [math] is called a proper monograph. The set [math] is called the signature of [math] and denoted as [math]. Not all proper monographs have the property that a set of idle vertices can be bijectively mapped to the maximum independent sets. As a result, in this paper, we present the proper monograph labelings of several classes of graphs that satisfy the property mentioned above. We present the proper monograph labelings of graphs such as cycles, [math], cycles with paths attached to one or more vertices, and Cycles with an irreducible tree attached to one or more vertices.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220505T07:00:00Z
DOI: 10.1142/S1793830922500926

 Linear recurrent cryptography: Goldenlike cryptography for higher order
linear recurrences
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Sergiy Koshkin, Daniel Rodriguez
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
We develop matrix cryptography based on linear recurrent sequences of any order that allows securing encryption against brute force and chosen plaintext attacks. In particular, we solve the problem of generalizing error detection and correction algorithms of golden cryptography previously known only for recurrences of a special form. They are based on proving the checking relations (inequalities satisfied by the ciphertext) under the condition that the analog of the golden [math]matrix has the strong Perron–Frobenius property. These algorithms are proved to be especially efficient when the characteristic polynomial of the recurrence is a Pisot polynomial. Finally, we outline algorithms for generating recurrences that satisfy our conditions.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220505T07:00:00Z
DOI: 10.1142/S179383092250094X

 Minimal instances with no weakly stable matching for threesided problem
with cyclic incomplete preferences
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Eduard Yu. Lerner, Regina E. Lerner
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Given [math] men, [math] women, and [math] dogs, each man has an incomplete preference list of women, each woman has an incomplete preference list of dogs, and each dog has an incomplete preference list of men. We understand a family as a triple consisting of one man, one woman, and one dog such that the dog belongs to the preference list of the woman, who, in turn, belongs to the preference list of the man, while the latter belongs to the preference list of the dog. We understand a matching as a collection of nonintersecting families (some agents, possibly, remain single). A matching is said to be nonstable, if one can find a man, a woman, and a dog who do not live together currently but each of them would become “happier” if they do. Otherwise, the matching is said to be stable (a weakly stable matching). We give an example of this problem for [math] where no stable matching exists. Moreover, we prove the absence of such an example for [math]. Such an example was known earlier only for [math] [P. Biró and E. McDermid, Threesided stable matchings with cyclic preferences, Algorithmica 58 (2010) 5–18]. The constructed examples also allow one to halve the size of the recently constructed analogous example for complete preference lists [C.K. Lam and C.G. Plaxton, On the existence of threedimensional stable matchings with cyclic preferences, in Algorithmic Game Theory, Lecture Notes in Computer Science, Vol. 11801 (Springer, 2019), pp. 329–342].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220505T07:00:00Z
DOI: 10.1142/S1793830922500951

 An instancebased algorithm for deciding the bias of a coin

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Luís Fernando Schultz Xavier da Silveira, Michiel Smid
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] and [math] be real numbers, and let [math] be a coin that comes up heads with an unknown probability [math], such that [math]. We present an algorithm that, on input [math], [math], and [math], decides, with probability at least [math], whether [math] or [math]. The expected number of coin flips made by this algorithm is [math], where [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220505T07:00:00Z
DOI: 10.1142/S1793830922500975

 Complete classification of cyclic codes of length [math] over [math]

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Brahim Boudine, Jamal Laaouine, Mohammed Elhassani Charkani
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this paper, we use a method inspired by the valuation theory to classify completely cyclic codes of length [math] over [math]. Then, we compute their separation parameters which was useful to compute the Hamming distance in [8].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220429T07:00:00Z
DOI: 10.1142/S1793830922500914

 Secure equitability in graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: L. Muthusubramanian, R. Sundareswaran, V. Swaminathan
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In secure domination [A. P. Burger, M. A. Henning and J. H. Van Vuuren, Vertex covers and secure domination in graphs, Quaest Math. 31 (2008) 163–171; E. J. Cockayne, Irredundance, secure domination and maximum degree in trees, Discrete Math. 307(1) (2007) 12–17; E. J. Cockayne, O. Favaron and C. M. Mynhardt, Secure domination, weak Roman domination and forbidden subgraph, Bull. Inst. Combin. Appl. 39 (2003) 87–100; C. M. Mynhardt, H. C. Swart and E. Ungerer, Excellent trees and secure domination, Util. Math. 67 (2005) 255–267], a vertex outside has the chance of coming inside the dominating set by replacing an element of the set without affecting domination. This idea is combined with equitability. Secure equitable dominating set is introduced and studied. Other concepts like independence and rigid security are also studied in this paper.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220427T07:00:00Z
DOI: 10.1142/S1793830922500811

 An extended study of [math]restricted edge connectivity: Another approach
to Tait’s coloring theorem
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: G Suresh Singh, Athira Chandran
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a graph [math], an edge connectivity [math] is the minimum number of edges whose removal disconnects [math]. In this paper, we define property restricted edge connectivity. Then we appraise its particular case, more precisely [math]restricted edge connectivity. Some of the basic properties of [math]restricted edge connectivity are considered. We also discuss how [math]restricted edge connectivity associates with graph coloring. In particular, we try to study how [math]restricted edge connectivity relates with Tait’s coloring theorem and thereby the famous Fourcolor conjecture.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220427T07:00:00Z
DOI: 10.1142/S1793830922500896

 Hardness of uncertain segment cover, contiguous SAT and visibility with
uncertain obstacles
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Sharareh Alipour, Salman Parsa
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this paper, we prove that the uncertain segment cover problem is NPhard. The uncertain segment cover problem, which appears in solving the question of visibility of a segment in the plane from a given point in the presence of uncertain obstacles, asks if a given interval can be covered by a collection of uncertain subintervals having two possible positions. This is done by showing that this problem is equivalent to a special version of the SAT problem that we will call contiguous SAT. In a contiguous SAT problem a CNF formula with a given ordering on its clauses is given such that any literal appears contiguously. We prove that contiguous SAT problem is NPhard and as a consequence it follows that the uncertain segment cover problem is NPhard. The approximation solution of this problem and its hardness are also studied.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220422T07:00:00Z
DOI: 10.1142/S179383092250063X

 Algorithmic aspects of domination number in nano topology induced by graph

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: V. Sutha Devi, M. Lellis Thivagar, R. Sundareswaran
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The basic intention of this paper is to impart the importance of Nano topology induced by graph. Nano topology induced by graph paves us a method to find the wellknown parameter of a graph, namely its domination number as well as all the possible dominating sets of a graph. In general, each paper, depending upon the author’s axe (or the pen), has its own point of emphasis. Accordingly, in this paper, the computational and algorithmic aspects of graph are emphasized. By experience, we know that to solve a problem using graph theory leads to a large graph virtually impossible to analyze without the aid of a computer. Hence, to simplify the problem we have used a Java program code that suits even for all graphs of finite number of vertices. We have made an attempt to find the proper location of guards and minimize the number of guards to observe all the warning lights in a nuclear power plant using such a Java program code.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220422T07:00:00Z
DOI: 10.1142/S1793830922500823

 Approaches that output infinitely many graphs with small local antimagic
chromatic number
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: GeeChoon Lau, Jianxi Li, WaiChee Shiu
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
An edge labeling of a connected graph [math] is said to be local antimagic if it is a bijection [math] such that for any pair of adjacent vertices [math] and [math], [math], where the induced vertex label [math], with [math] ranging over all the edges incident to [math]. The local antimagic chromatic number of [math], denoted by [math], is the minimum number of distinct induced vertex labels over all local antimagic labelings of [math]. In this paper, we show the existence of infinitely many bipartite and tripartite graphs with [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220418T07:00:00Z
DOI: 10.1142/S1793830922500793

 Global dominating broadcast in graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Ibrahim Boufelgha, Moussa Ahmia
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A broadcast on a graph [math] is a function [math] such that for each [math], where [math] denotes the diameter of [math] and [math] denotes the eccentricity of [math]. The cost of a broadcast is the value [math]. In this paper, we define and study a new invariant of broadcasts in graphs, which is global dominating broadcast. A dominating broadcast [math] of a graph [math] is a global dominating broadcast if [math] is also a dominating broadcast of [math] the complement of [math]. We begin by determining the global broadcast domination number of bipartite graphs, paths, cycles, grid graphs and trees. Then we establish lower and upper bounds on the global broadcast domination number of a graph. Finally, we establish relationships between the global broadcast domination number and other parameters.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220418T07:00:00Z
DOI: 10.1142/S1793830922500835

 Computing vertex resolvability of some regular planar graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Sunny Kumar Sharma, Vijay Kumar Bhat
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a connected graph of order [math]. An ordered subset [math] of vertices in [math] is said to be a resolving set for [math], if all the vertices of [math] are uniquely determined by the vector of distances to the vertices in [math]. The metric dimension of [math] is the minimum cardinality of a resolving set [math] and that resolving set is the metric basis for [math]. In this paper, we show that the metric dimension is three for a family of a threeregular convex polytope.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220418T07:00:00Z
DOI: 10.1142/S1793830922500860

 Spectrum of corona products based on splitting graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Ann Susa Thomas, Sunny Joseph Kalayathankal, Joseph Varghese Kureethara
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a simple undirected graph. Three new corona products of graphs based on splitting graph of [math] are defined. The adjacency spectra of the three new graphs based on splitting graph of [math] are determined. The number of spanning trees and the Kirchoff index of the new graphs are determined using their nonzero Laplacian eigenvalues.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220418T07:00:00Z
DOI: 10.1142/S1793830922500872

 On weak metric dimension of digraphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Min Feng, Kaishun Wang, Yuefeng Yang
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Using the twoway distance, we introduce the concept of the weak metric dimension of a strongly connected digraph [math]. We first establish lower and upper bounds for the number of arcs in [math] by using the diameter and weak metric dimension of [math], and characterize all digraphs attaining the lower or upper bound. Then we study a digraph with weak metric dimension [math] and classify all vertextransitive digraphs having weak metric dimension [math]. Finally, all digraphs of order [math] with weak metric dimension [math] or [math] are determined.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220418T07:00:00Z
DOI: 10.1142/S1793830922500884

 On the chromatic number of [math]free graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Weilun Xu, Xia Zhang
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a graph [math], [math], [math] represent the clique number and the chromatic number of [math], respectively. A hereditary family [math] of graphs is called [math]bounded with [math]binding function [math] if [math] for all [math]. A result of Schiermeyer shows that the class of [math]free graphs has a [math]binding function [math] [L. Esperet, L. Lemoine, F. Maffray and G. Morel, The chromatic number of [math]free graphs, Discrete Math. 313 (2013) 743–754]. In this paper, we prove that the class of [math]free graphs has a [math]binding function [math]. For the class of [math]free graphs, we give a [math]binding function [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220418T07:00:00Z
DOI: 10.1142/S1793830922500902

 The local complement metric dimension of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Liliek Susilowati, Siti Istikhomah, Moh. Imam Utoyo, S. Slamin
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The metric dimension of graphs has been extended in some types and variations such as local metric dimension and complement metric dimension of graphs. Merging two concepts is one way of developing the concept of graph theory as a branch of mathematics. These two variations motivated us to construct a new concept of metric dimension so called local complement metric dimension. We apply this new concept to some particular classes of graphs and the corona product of two graphs. We also characterize the local complement metric dimension of graphs with certain properties, namely, bipartite graphs and odd cycle graphs. Furthermore, we discover the local complement metric dimension of the corona product of two particular graphs as well as the corona product of two general graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220412T07:00:00Z
DOI: 10.1142/S1793830922500732

 New results on quadruple Roman domination in graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: J. Amjadi, N. Khalili
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be an integer and [math] be a simple graph with vertex set [math]. Let [math] be a function that assigns label from the set [math] to the vertices of a graph [math]. For a vertex [math], the active neighborhood of [math], denoted by [math], is the set of vertices [math] such that [math]. A [math]RDF is a function [math] satisfying the condition that for any vertex [math] with [math], [math]. The weight of a [math]RDF is [math]. The [math]Roman domination number [math] of [math] is the minimum weight of an [math]RDF on [math]. The case [math] is called quadruple Roman domination number. In this paper, we first establish an upper bound for quadruple Roman domination number of graphs with minimum degree two, and then we derive a Nordhaus–Gaddum bound on the quadruple Roman domination number of graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220412T07:00:00Z
DOI: 10.1142/S1793830922500781

 Outer independent double Italian domination: Complexity, characterization

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: R. Jalaei, D. A. Mojdeh
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
An outer independent double Italian dominating function is a double Italian dominating function [math] for which the set of vertices assigned [math] under [math] is independent. The outer independent double Italian domination number [math] is the minimum weight taken over all outer independent double Italian dominating functions of [math]. In this work, we present some contributions to the study of outer independent double Italian domination in graphs. We show that the outer independent double Italian domination number is NPcomplete even when restricted to planner graphs with maximum degree at most four. We characterize the families of all connected graphs [math] with [math]. We also investigate the families of all graphs [math] such that [math] and for [math], the graphs with this property are characterized. Finally, we characterize the families of all connected graphs [math] of order [math], for which [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220412T07:00:00Z
DOI: 10.1142/S1793830922500859

 Vertex faulttolerant spanners for weighted points in polygonal domains

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: R. Inkulu, Apurv Singh
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Given a set [math] of [math] points, a weight function [math] to associate a nonnegative weight to each point in [math], a positive integer [math], and a real number [math], we devise the following algorithms to compute a [math]vertex faulttolerant spanner network [math] for the metric space induced by the weighted points in [math]: (1). When the points in [math] are located in a simple polygon, we present an algorithm to compute [math] with multiplicative stretch [math], and the number of edges in [math] (size of [math]) is [math]. (2) When the points in [math] are located in the free space of a polygonal domain [math] with [math] number of obstacles, we present an algorithm to compute [math] with multiplicative stretch [math] and size [math]. (3) When the points in [math] are located on a polyhedral terrain, we devise an algorithm to compute [math] with multiplicative stretch [math] and size [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220411T07:00:00Z
DOI: 10.1142/S1793830922500744

 On some formulas in the problem of enumeration of finite labeled
topologies
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Kh. Sh. Al’Dzhabri, V. I. Rodionov
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Among the unsolved problems of enumeration of graphs, one of the most difficult is the problem of enumeration of transitive digraphs, which is equivalent to the problem of enumeration of finite partial orders and is equivalent to the problem of enumeration of finite labeled [math]topologies. The sequence [math], where [math] is the number of all labeled [math]topologies defined on an [math]set, has been studied from different points of view. In the previous work of the second author, a formula was obtained in which the number [math] is represented as a linear combination of numbers [math] (where the sequences [math] are compositions of the number [math]). Recurrent relations between individual numbers [math] were obtained. In this paper, new recursive formulas between separate numbers [math] are obtained.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220411T07:00:00Z
DOI: 10.1142/S1793830922500756

 Total dominator coloring number of middle graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Farshad Kazemnejad, Behnaz Pahlavsay, Elisa Palezzato, Michele Torielli
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A total dominator coloring of a graph [math] is a proper coloring of [math] in which each vertex of the graph is adjacent to every vertex of some color class. The total dominator chromatic number of a graph is the minimum number of color classes in a total dominator coloring. In this paper, we study the total dominator coloring on middle graphs by giving several bounds for the case of general graphs and trees. Moreover, we calculate explicitly the total dominator chromatic number of the middle graph of several known families of graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220411T07:00:00Z
DOI: 10.1142/S1793830922500768

 On fourth leap Zagreb index of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Ammar Alsinai, Anwar Saleh, Hanan Ahmed, Lakshmi Narayan Mishra, N. D. Soner
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this research work, we introduce a new version of leap Zagreb index called fourth leap Zagreb index. Mathematical properties and exact values for some standard classes of graphs for this new topological index are obtained. Also, the upper bounds are established. The values of this index for some graph operations containing the Cartesian product, Join and Composition are found.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220411T07:00:00Z
DOI: 10.1142/S179383092250077X

 Progress on faulttolerant locatingdominating sets

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Devin C. Jean, Suk J. Seo
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A locatingdominating set is a subset of vertices representing “detectors” in a graph [math] which can locate an “intruder” given that each detector covers its closed neighborhood and can distinguish its own location from its neighbors. We explore a faulttolerant variant of locatingdominating sets, called errordetecting locatingdominating (DET:LD) sets, which can tolerate one false negative. The concept of DET:LD sets was originally introduced in 2002, along with several properties in various classes of graphs; we extend this work by fully characterizing DET:LD sets for general graphs and establishing existence criteria. We prove that the problem of determining the minimum density of a DET:LD set in arbitrary graphs is NPcomplete. Additionally, we determine that the minimum density in cubic graphs is at least [math], and we show an infinite family of cubic graphs achieving this density.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220411T07:00:00Z
DOI: 10.1142/S179383092250080X

 2Distance coloring of planar graphs without triangles and intersecting
4cycles
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yuehua Bu, Zewei Zhang, Hongguo Zhu
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The [math]2distance coloring of graph [math] is a mapping [math] if any two vertices at distance at most two from each other get different colors. The 2distance chromatic number is the smallest integer [math] such that [math] has a [math]2distance coloring, denoted by [math]. In this paper, we prove that every planar graph [math] without 3cycles and intersecting 4cycles and [math] has [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220411T07:00:00Z
DOI: 10.1142/S1793830922500847

 [math]additive cyclic and constacyclic codes and MDSS codes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Arazgol Ghajari, Kazem Khashyarmanesh, Taher Abualrub, Irfan Siap
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this paper, we will study the structure of [math]additive codes where [math] is the wellknown ring of 4 elements and [math] is the ring given by [math], where [math], [math] and [math]. We will classify all maximum distance separable codes with respect to the Singleton bound (MDSS) over [math] Then we will focus on [math]additive cyclic and constacyclic codes. We will find a unique set of generator polynomials for these codes and determine minimum spanning sets for them. We will also find the generator polynomials for the dual of any [math]additive cyclic or constacyclic code.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220328T07:00:00Z
DOI: 10.1142/S1793830922500665

 TypeII polyadic constacyclic codes over finite fields

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Somphong Jitman, San Ling, Jareena Tharnnukhroh
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Polyadic constacyclic codes over finite fields have been of interest due to their nice algebraic structures, good parameters, and wide applications. Recently, the study of TypeI [math]adic constacyclic codes over finite fields has been established. In this paper, a family of TypeII [math]adic constacyclic codes is investigated. The existence of such codes is determined using the length of orbits in a suitable group action. A necessary condition and a sufficient condition for a positive integer [math] to be a multiplier of a TypeII [math]adic constacyclic code are determined. Subsequently, for a given positive integer [math], a necessary condition and a sufficient condition for the existence of TypeII [math]adic constacyclic codes are derived. In many cases, these conditions become both necessary and sufficient. For the other cases, determining necessary and sufficient conditions is equivalent to the discrete logarithm problem which is considered to be computationally intractable. Some special cases are investigated together with examples of TypeII polyadic constacyclic codes with good parameters.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220328T07:00:00Z
DOI: 10.1142/S1793830922500720

 On normalized Laplacian eigenvalues of power graphs associated to finite
cyclic groups
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Bilal A. Rather, S. Pirzada, T. A. Chishti, Ahmad M. Alghamdi
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a simple connected graph [math] of order [math], the normalized Laplacian is a square matrix of order [math], defined as [math], where [math] is the diagonal matrix whose [math]th diagonal entry is [math]. In this paper, we find the normalized Laplacian eigenvalues of the joined union of regular graphs in terms of the adjacency eigenvalues and the eigenvalues of quotient matrix associated with graph [math]. For a finite group [math], the power graph [math] of a group [math] is defined as the simple graph in which two distinct vertices are joined by an edge if and only if one is the power of the other. As a consequence of the joined union of graphs, we investigate the normalized Laplacian eigenvalues of the power graphs of the finite cyclic group [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220321T07:00:00Z
DOI: 10.1142/S1793830922500707

 Some results on generalized selfcomplementary graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: H. J. Gowtham, Shankar N. Upadhyay, Sabitha D’Souza, Pradeep G. Bhat
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a partition of vertex set [math] of order [math] of a graph [math]. The [math]complement of [math] denoted by [math] is defined as for all [math] and [math] in [math], [math], remove the edges between [math] and [math] in [math] and add the edges between [math] and [math] which are not in [math]. The graph [math] is called [math]selfcomplementary if [math]. For a graph [math], [math]complement of [math] denoted by [math] is defined as for each [math] remove the edges of [math] inside [math] and add the edges of [math] by joining the vertices of [math]. The graph [math] is called [math]selfcomplementary if [math] for some partition [math] of order [math]. In this paper, we determine generalized selfcomplementary graphs of forest, double star and unicyclic graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220312T08:00:00Z
DOI: 10.1142/S1793830922500653

 Wiener index of sum of shadowgraphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Shanu Goyal, Dilip Jain, Vishnu Narayan Mishra
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The Wiener index of a graph [math], denoted by [math], is defined as W(G) =∑u≠vd(u,v), where the sum is taken through all unordered pairs of vertices of [math] and [math] is distance between two vertices [math] and [math] of [math]. Let [math] and [math] be two graphs. For a graph [math], let [math] be a copy of [math] and [math]. The [math]sum [math] is a graph with the set of vertices [math] and two vertices [math] and [math] of [math] are adjacent if and only if [math] or [math], where [math] be one of the shadowgraph [math] or closed shadowgraph [math]. In this paper, we reported the Wiener index of these graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220312T08:00:00Z
DOI: 10.1142/S1793830922500689

 Indicated coloring of the Mycielskian of some families of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: P. Francis
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round, the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph [math] (regardless of Ben’s strategy) is called the indicated chromatic number of [math], denoted by [math]. In this paper, we examine whether the Mycielskian of [math], [math], is [math]indicated colorable for all [math], whenever [math] is [math]indicated colorable for all [math]. In this direction, we prove that the Mycielskian of the bipartite graphs, complete multipartite graphs, [math]free graphs, [math]free graphs, [math]free graphs and [math]free graphs are [math]indicated colorable for all [math] greater than or equal to the indicated chromatic number of the corresponding graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220312T08:00:00Z
DOI: 10.1142/S1793830922500690

 The generalized path matrix and energy

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Pengli Lu, Rui Luan
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
We define the path Laplacian matrix and the path signless Laplacian matrix of a simple connected graph [math] as [math] and [math], respectively, where [math] is the path matrix and [math] is the diagonal matrix of the vertex transmissions. The generalized path matrix is [math], for [math] and [math] are the eigenvalues of [math]. The generalized path energy can be expressed as [math], where [math] is the path Wiener index of [math]. We give basic properties of generalized path matrix [math]. Also, some upper and lower bounds of the generalized path energy of some graphs are studied.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220310T08:00:00Z
DOI: 10.1142/S1793830922500719

 The secondminimum and secondmaximum values of exponential Zagreb indices
among trees
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Lu Yang, Yan Zhu
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Exponential of the first Zagreb index and the second Zagreb index of a graph [math] are defined as [math] and [math], where [math] denotes the set of edges and [math] denotes the degree of a vertex [math]. The extremal trees of these two indices among trees have been determined in previous studies. In this paper, we give the secondminimum and the secondmaximum values of [math] and [math] among trees.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220308T08:00:00Z
DOI: 10.1142/S1793830922500641

 Embedding and the rotational dimension of a graph containing a clique

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Takumi Gomyou
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The rotational dimension is a minormonotone graph invariant related to the dimension of a Euclidean space containing a spectral embedding corresponding to the first nonzero eigenvalue of the graph Laplacian, which is introduced by Göring, Helmberg and Wappler. In this paper, we study rotational dimensions of graphs which contain large complete graphs. The complete graph is characterized by its rotational dimension. It will be obtained that a chordal graph may be made large while keeping the rotational dimension constant.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220225T08:00:00Z
DOI: 10.1142/S1793830922500616

 Corona product of signed graphs and its application to modeling signed
networks
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Bibhas Adhikari, Amrik Singh, Sandeep Kumar Yadav
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The notion of corona of two graphs was introduced by Frucht and Harary in 1970. In this paper, we generalize their definition of corona product of two graphs and introduce corona product of two signed graphs by utilizing the framework of marked graphs, which was introduced by Beineke and Harary in 1978. We study structural and spectral properties of corona product of signed graphs. Further, we define signed corona graphs by considering corona product of a fixed small signed graph with itself iteratively, and we call the small graph as the seed graph for the corresponding corona product graphs. Signed corona graphs can be employed as a signed network generative model for large growing signed networks. We study structural properties of corona graphs that include statistics of signed links, all types of signed triangles and degree distribution. Besides we analyze algebraic conflict of signed corona graphs generated by specially structured seed graphs. Finally, we show that a suitable choice of a seed graph can produce corona graphs which preserve properties of real signed networks.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220225T08:00:00Z
DOI: 10.1142/S1793830922500628

 Partially balanced incomplete block (PBIB)designs associated with
geodetic sets in graphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Medha Itagi Huilgol, M. D. Vidya
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A [math]design over regular graph [math] of degree [math] is an ordered pair [math], where [math] and [math] is the set of geodetic sets in [math] called blocks such that two vertices [math] and [math] which are [math] associates occur together in [math] blocks, the numbers [math] being independent of the choice of the pair [math] and [math]. In this paper, we obtain Partially Balanced Incomplete Block (PBIB)designs arising from geodetic sets in some classes of graphs. Also, we give a complete list of PBIBdesigns with respect to the geodetic sets for cubic graphs of order at most [math]. The discussion of nonexistence of some designs corresponding to geodetic sets from certain graphs concludes the paper.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220222T08:00:00Z
DOI: 10.1142/S1793830922500598

 A note on Hamiltonian cycles in planar graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Martin Kreh
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Unlike the problem of finding Eulerian cycles, the problem of deciding whether a given graph has a Hamiltonian cycle is NPcomplete, even when restricting to planar graphs. There are however some criteria that can be used in special cases. One of them can be derived by Grinberg’s theorem. In this note, we give some more (slightly more general) criteria derived from Grinberg’s theorem to show that a graph does not have a Hamiltonian cycle.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220217T08:00:00Z
DOI: 10.1142/S1793830922500604

 Topological indices of the wreath product of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Yongqin Zhang, Jianfeng Wang, Maurizio Brunetti
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Topological indices, i.e., numerical invariants suitably associated to graphs and only depending upon their isomorphism type, have important applications in Chemistry. Their computation constitutes an important branch of Chemical Graph Theory. In this paper, we focus on some degree and distancebased invariants related to the Zagreb indices, the Szeged index and the Wiener index, namely, the Findex, the vertex PI index and the hyperWiener index. In particular, we find the formulæ to compute these topological invariants for wreath product of graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220211T08:00:00Z
DOI: 10.1142/S1793830922500562

 Total outer connected vertexedge domination

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: B. Senthilkumar, H. Naresh Kumar, Y. B. Venkatakrishnan
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A vertex [math] of a graph is said to [math][math] dominate every edge incident with [math], as well as every edge incident to vertices adjacent to [math]. A subset [math] is a total outer connected vertexedge dominating set of a graph [math] if every edge in [math] is [math][math] dominated by a vertex in [math], the subgraph induced by [math] has no isolated vertices and the subgraph induced by [math] is connected. We initiate the study of total outer connected vertexedge domination in graphs. We show that the decision problem for total outerconnected vertexedge domination problem is [math]Complete even for bipartite graphs. We prove that for every tree of order [math] with [math] leaves, [math] and characterize the trees attaining the lower bound. We also study the effect of edge removal, edge addition and edge subdivision on total outer connected vertexedge domination number of a graph.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220211T08:00:00Z
DOI: 10.1142/S1793830922500574

 The Tutte polynomial of a class of compound graphs and its applications

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Hanlin Chen
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The Tutte polynomial, a considerable generalization of the chromatic polynomial, associated with a graph is a classical bivariate polynomial, which gives various interesting information about the graph structure. In this paper, we first present a formula for the Tutte polynomial of a class of special compound graphs. Then as applications, we obtain the Tutte polynomials of some complex network models in the context of statistical physics and the Tutte polynomials of some chemical polycyclic graphs. Moreover, explicit expressions of the number of spanning trees for these considered graphs are determined, respectively.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220211T08:00:00Z
DOI: 10.1142/S1793830922500586

 Fission: Practical algorithms for computing minimum balanced node
separators
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Johannes Blum, Ruoying Li, Sabine Storandt
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Given an undirected graph, a balanced node separator is a set of nodes whose removal splits the graph into connected components of limited size. Balanced node separators are used for graph partitioning, for the construction of graph data structures, and for measuring network reliability. It is NPhard to decide whether a graph has a balanced node separator of size at most [math]. Therefore, practical algorithms typically try to find small separators in a heuristic fashion. In this paper, we present a branching algorithm that for a given value [math] either outputs a balanced node separator of size at most [math] or certifies that [math] is a valid lower bound. Using this algorithm iteratively for growing values of [math] allows us to find a minimum balanced node separator. To make this algorithm scalable to realworld (road) networks of considerable size, we first describe pruning rules to reduce the graph size without affecting the minimum balanced separator size. In addition, we prove several structural properties of minimum balanced node separators which are then used to reduce the branching factor and search depth of our algorithm. We experimentally demonstrate the applicability of our algorithm to graphs with thousands of nodes and edges. We showcase the usefulness of having minimum balanced separators for judging the quality of existing heuristics, for improving preprocessingbased route planning techniques on road networks, and for lower bounding important graph parameters. Finally, we discuss how our ideas and methods can also be leveraged to accelerate the heuristic computation of balanced node separators.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220122T08:00:00Z
DOI: 10.1142/S1793830922500483

 On 3degree 4chordal graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Devarshi Aggarwal, R. Mahendra Kumar, N. Sadagopan
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A graph [math] is a 3degree 4chordal graph if every cycle of length at least five has a chord and the degree of each vertex is at most three. In this paper, we investigate the structure of 3degree 4chordal graphs, which is a subclass of 3degree graphs. We present a structural characterization based on minimal vertex separators and biconnected components. Many classical problems are known to be NPcomplete for 3degree graphs, and 3degree 4chordal graphs are a nontrivial subclass of 3degree graphs. Using our structural results, we present polynomialtime algorithms for many classical problems which are grouped into (i) subset problems (vertex cover and its variants, feedback vertex set, Steiner tree), (ii) Hamiltonicity and its variants, (iii) graph embedding problems (treewidth, minimum fillin), and (iv) Coloring problems(rainbow coloring).
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220122T08:00:00Z
DOI: 10.1142/S1793830922500537

 Eccentric connectivity coindex of bipartite graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Tomáš Vetrík, Mesfin Masre, Selvaraj Balachandran
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The eccentric connectivity coindex of a graph [math] is defined as [math], where [math] is the vertex set of [math], [math] is the edge set of [math], [math] is the eccentricity of [math] and [math] is the degree of [math] in [math]. We present lower bounds on the eccentric connectivity coindex for bipartite graphs of given order and vertex connectivity, order and matching number, order and odd diameter. The extremal graphs are presented as well. To the best of our knowledge, our extremal graphs of given order and vertex connectivity are not extremal graphs for any other research problem in graph theory.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220119T08:00:00Z
DOI: 10.1142/S1793830922500549

 [math]inducedpaired dominating graphs of paths and cycles

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Saharath Sanguanpong, Nantapath Trakultraipruk
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For any graph [math], a nonempty subset [math] of [math] is called an inducedpaired dominating set if every vertex in [math] is adjacent to some vertex in [math], and the induced subgraph [math] contains only independent edges. An inducedpaired dominating set of [math] with minimum number of vertices is also called a [math]set. We define the [math]induced paired dominating graph of [math], denoted by [math], to be the graph whose vertex set consists of all [math]sets, and two [math]sets are adjacent in [math] if they are different from each other by only one vertex. In this paper, we exhibit all [math]inducedpaired dominating graphs of paths and cycles.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220115T08:00:00Z
DOI: 10.1142/S1793830922500471

 Pancyclic zero divisor graph over the ring [math]

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Ravindra Kumar, Om Prakash
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be the zero divisor graph over the ring [math]. In this paper, we study pancyclic properties of [math] and [math], respectively, for different [math]. Also, we prove some results in which [math] and [math] are pancyclic for different values of [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220115T08:00:00Z
DOI: 10.1142/S1793830922500495

 [math]Efficient domination: Algorithmic perspective

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Mohsen Alambardar Meybodi
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A set [math] of a graph [math] is called an efficient dominating set of [math] if every vertex [math] has exactly one neighbor in [math], in other words, the vertex set [math] is partitioned to some circles with radius one such that the vertices in [math] are the centers of partitions. A generalization of this concept, introduced by Chellali et al. [kEfficient partitions of graphs, Commun. Comb. Optim. 4 (2019) 109–122], is called [math]efficient dominating set that briefly partitions the vertices of graph with different radiuses. It leads to a partition set [math] such that each [math] consists a center vertex [math] and all the vertices in distance [math], where [math]. In other words, there exist the dominators with various dominating powers. The problem of finding minimum set [math] is called the minimum [math]efficient domination problem. Given a positive integer [math] and a graph [math], the [math]efficient Domination Decision problem is to decide whether [math] has a [math]efficient dominating set of cardinality at most [math]. The [math]efficient Domination Decision problem is known to be NPcomplete even for bipartite graphs [M. Chellali, T. W. Haynes and S. Hedetniemi, kEfficient partitions of graphs, Commun. Comb. Optim. 4 (2019) 109–122]. Clearly, every graph has a [math]efficient dominating set but it is not correct for efficient dominating set. In this paper, we study the following: [math]efficient domination problem set is NPcomplete even in chordal graphs. A polynomialtime algorithm for [math]efficient domination in trees. [math]efficient domination on sparse graphs from the parametrized complexity perspective. In particular, we show that it is [math]hard on ddegenerate graphs while the original dominating set has Fixed Parameter Tractable (FPT) algorithm on ddegenerate graphs. [math]efficient domination on nowheredense graphs is FPT.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220112T08:00:00Z
DOI: 10.1142/S1793830922500513

 Minimum constraint removal problem for line segments is NPhard

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Bahram Sadeghi Bigham
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In the minimum constraint removal ([math]), there is no feasible path to move from a starting point towards the goal, and the minimum constraints should be removed in order to find a collisionfree path. It has been proved that [math] problem is NPhard when constraints have arbitrary shapes or even they are in shape of convex polygons. However, it has a simple linear solution when constraints are lines and the problem is open for other cases yet. In this paper, using a reduction from Subset Sum problem, in three steps, we show that the problem is NPhard for both weighted and unweighted line segments.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220112T08:00:00Z
DOI: 10.1142/S1793830922500550

 On a spanning subgraph of the annihilatingideal graph of a commutative
ring
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: S. Visweswaran
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The rings considered in this paper are commutative with identity which are not integral domains. Let [math] be a ring. Let us denote the set of all annihilating ideals of [math] by [math] and [math] by [math]. With [math], we associate an undirected graph, denoted by [math], whose vertex set is [math] and distinct vertices [math] and [math] are adjacent in this graph if and only if [math] and [math]. The aim of this paper is to study the interplay between the graphtheoretic properties of [math] and the ringtheoretic properties of [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220110T08:00:00Z
DOI: 10.1142/S1793830922500501

 On the variants of first KCD energy

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Keerthi G. Mirajkar, Akshata Morajkar
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The variants of first Karnatak College Dharwad energy, in brief, the first [math] energy, namely the first [math] hyperenergeticity, the first [math] borderenergeticity and the first [math] equienergeticity, are defined. These concepts are further studied for complement, line graph and splitting graph of a graph. Lastly, some results on first [math] equienergetic graphs are obtained.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220110T08:00:00Z
DOI: 10.1142/S1793830922500525

 On the double Roman bondage numbers of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: N. Jafari Rad, H. R. Maimani, M. Momeni, F. Rahimi Mahid
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a graph [math], a double Roman dominating function (DRDF) is a function [math] having the property that if [math] for some vertex [math], then [math] has at least two neighbors assigned [math] under [math] or one neighbor [math] with [math], and if [math] then [math] has at least one neighbor [math] with [math]. The weight of a DRDF [math] is the sum [math]. The minimum weight of a DRDF on a graph [math] is the double Roman domination number of [math] and is denoted by [math]. The double Roman bondage number of [math], denoted by [math], is the minimum cardinality among all edge subsets [math] such that [math]. In this paper, we study the double Roman bondage number in graphs. We determine the double Roman bondage number in several families of graphs, and present several bounds for the double Roman bondage number. We also study the complexity issue of the double Roman bondage number and prove that the decision problem for the double Roman bondage number is NPhard even when restricted to bipartite graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20220107T08:00:00Z
DOI: 10.1142/S179383092250046X

 Birecognition of prime graphs, and minimal prime graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Houmem Belkhechine, Cherifa Ben Salha, Pierre Ille
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Given a graph [math], a subset [math] of [math] is a module of [math] if for each [math], [math] is adjacent to all the elements of [math] or to none of them. For instance, [math], [math] and [math] ([math]) are the trivial modules of [math]. A graph [math] is prime if [math] and all its modules are trivial. Given a prime graph [math], consider [math] such that [math] is prime. Given a graph [math] such that [math] and [math], [math] and [math] are [math]similar if for each [math], [math] and [math] are both prime or not. The graph [math] is said to be [math]birecognizable if every graph, [math]similar to [math], is prime. We study the graphs [math] that are not [math]birecognizable, where [math] such that [math] is prime, by using the following notion of a minimal prime graph. Given a prime graph [math], consider [math] such that [math] is prime. Given [math], [math] is [math]minimal if for each [math] such that [math], [math] is not prime.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211228T08:00:00Z
DOI: 10.1142/S1793830922500380

 2Point set domination in separable graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Purnima Gupta, Deepti Jain
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In a graph [math], a set [math] is a [math]point set dominating set (in short 2psd set) of [math] if for every subset [math] there exists a nonempty subset [math] containing at most two vertices such that the induced subgraph [math] is connected in [math]. The [math]point set domination number of [math], denoted by [math], is the minimum cardinality of a 2psd set of [math]. The main focus of this paper is to find the value of [math] for a separable graph and thereafter computing [math] for some wellknown classes of separable graphs. Further we classify the set of all 2psd sets of a separable graph into six disjoint classes and study the existence of minimum 2psd sets in each class.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211228T08:00:00Z
DOI: 10.1142/S1793830922500446

 Injective edgecoloring of subcubic graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Baya Ferdjallah, Samia Kerdjoudj, André Raspaud
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
An injective edgecoloring [math] of a graph [math] is an edgecoloring such that if [math], [math], and [math] are three consecutive edges in [math] (they are consecutive if they form a path or a cycle of length three), then [math] and [math] receive different colors. The minimum integer [math] such that, [math] has an injective edgecoloring with [math] colors, is called the injective chromatic index of [math] ([math]). This parameter was introduced by Cardoso et al. [Injective coloring of graphs, Filomat 33(19) (2019) 6411–6423, arXiv:1510.02626] motivated by the Packet Radio Network problem. They proved that computing [math] of a graph [math] is NPhard. We give new upper bounds for this parameter and we present the relationships of the injective edgecoloring with other colorings of graphs. We study the injective edgecoloring of some classes of subcubic graphs. We prove that a subcubic bipartite graph has an injective chromatic index bounded by [math]. We also prove that if [math] is a subcubic graph with maximum average degree less than [math] (respectively, [math]), then [math] admits an injective edgecoloring with at most 4 (respectively, [math]) colors. Moreover, we establish a tight upper bound for subcubic outerplanar graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211217T08:00:00Z
DOI: 10.1142/S1793830922500409

 Strong chromatic index of generalized Jahangir graphs and generalized Helm
graphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Vikram Srinivasan Thiru, S. Balaji
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The strong edge coloring of a graph G is a proper edge coloring that assigns a different color to any two edges which are at most two edges apart. The minimum number of color classes that contribute to such a proper coloring is said to be the strong chromatic index of G. This paper defines the strong chromatic index for the generalized Jahangir graphs and the generalized Helm graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211217T08:00:00Z
DOI: 10.1142/S1793830922500458

 Edgevertex domination in trees

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Kijung Kim
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a finite simple graph. A vertex [math] is edgevertex dominated by an edge [math] if [math] is incident with [math] or [math] is incident with a vertex adjacent to [math]. An edgevertex dominating set of [math] is a subset [math] such that every vertex of [math] is edgevertex dominated by an edge of [math]. The edgevertex domination number [math] is the minimum cardinality of an edgevertex dominating set of [math]. In this paper, we prove that [math] for every tree [math] of order [math] with [math] leaves, and we characterize the trees attaining each of the bounds.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211209T08:00:00Z
DOI: 10.1142/S1793830922500434

 Computation of diameter, radius and center of permutation graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Shaoli Nandi, Sukumar Mondal, Sambhu Charan Barman
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a connected graph [math], we use the notation [math] to represent the distance between two node points [math] and [math] and it is the minimum of the lengths of all paths between them. The eccentricity [math] of a node point [math] is considered as the maximum length of all shortest paths starts from [math] to the remaining nodes, i.e., [math]. The diameter of a graph [math], we denote it by [math] and it is the length of the longest shortest path in [math], i.e., [math]. Also, the radius of a graph [math], we denote it by the symbol [math] and it is the least eccentricity of all node points in [math], i.e., [math]. The central vertex/node point [math] of a graph [math] is a node whose eccentricity is same as [math]’s radius, i.e., [math]. The collection of all central nodes of a graph [math] is considered as the center of [math] and it is symbolized by [math], i.e., [math]. A graph may have one or more central vertices. This paper develops an optimal algorithm to compute the diameter, radius and central node (s) of the permutation graph having [math] node points in [math] time. We have also established a tight relation between radius and diameter of permutation graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211206T08:00:00Z
DOI: 10.1142/S1793830922500392

 Crosscap two of class of graphs from commutative rings

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: S. Karthik, S. N. Meera, K. Selvakumar
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a commutative ring with identity and [math] be the set of all nonzero zerodivisors of [math]. The annihilator graph of commutative ring [math] is the simple undirected graph [math] with vertices [math] and two distinct vertices [math] and [math] are adjacent if and only if [math]. The essential 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] is an essential ideal. In this paper, we classify all finite commutative rings with identity whose annihilator graph and essential graph have crosscap two.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211202T08:00:00Z
DOI: 10.1142/S1793830922500410

 Online interval graphs coloring — Modification of the FirstFit
algorithm and its performance ratio
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Bartosz Bieganowski
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
We propose a modification of the FirstFit algorithm in which we forbid the use of the most frequently used color. We provide some lower bound of the performance ratio [math] on the family of interval graphs [math], where [math] denotes the number of used colors by the modified version of the FirstFit algorithm and [math] is the number of vertices in the largest complete subgraph in [math]. We also compare the modification with the usual FirstFit algorithm on some experimental data.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211202T08:00:00Z
DOI: 10.1142/S1793830922500422

 A note on nofreelunch theorem

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Lidong Wu
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The NoFreeLunch theorem is an interesting and important theoretical result in machine learning. Based on philosophy of NoFreeLunch theorem, we discuss extensively on the limitation of a datadriven approach in solving NPhard problems.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211129T08:00:00Z
DOI: 10.1142/S1793830922500276

 On the domination number of a graph and its block graph

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: E. Murugan, J. Paulraj Joseph
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a graph. A subset [math] of [math] is called a dominating set of [math] if every vertex not in [math] is adjacent to some vertex in [math] The domination number [math] of [math] is the minimum cardinality taken over all dominating sets of [math] The block graph [math] of a graph [math] is a graph whose vertex set is the set of blocks in [math] and two vertices of [math] are adjacent if and only if the corresponding blocks have a common cut vertex in [math] In this paper, we investigate the lower and upper bounds for the sum of domination number of a graph and its block graph and characterize the extremal graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211127T08:00:00Z
DOI: 10.1142/S1793830922500331

 Development of algorithm simulating spatial fold change of cell signaling
for pattern formation in zebrafish
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Bilal Gonen, Sai Nikhil Bheemanathini
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Embryos develop robust spatiotemporal patterns by encoding and interpreting biological signals in real time. Developmental patterns often scale with body or tissue size even when total cell number, cell size or growth rate are changed. A striking example of patterning is the segmentation of somites — the precursors of vertebral column. Despite decadelong efforts, how positional information for segmentation is encoded by cell signaling remained elusive. To address this fundamental question, we studied a novel zebrafish tail explant model that recapitulated the scaling of somite sizes with the length of unsegmented tissue in growing intact embryos. This paper provides an algorithm written in MATLAB as well as Python and finally finding a way to write an efficient algorithm to be able to answer the question described above. Information encoding by spatial foldchange of cell signaling is a remarkable strategy that could be utilized for engineering precisely patterned tissues or organs. We also discuss the limitations of simulations performed using MATLAB with performance decreasing with the large data sets. So, we tried to analyze the factors that impacted the performance of the algorithm. Finally, we tried to answer questions regarding the language selection in which a simulation method can be written efficiently.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211124T08:00:00Z
DOI: 10.1142/S1793830922500082

 The spectrum and metric dimension of Indu–Bala product of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Subarsha Banerjee
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Given a connected graph [math], the distance Laplacian matrix [math] is defined as [math], and the distance signless Laplacian matrix [math] is defined as [math], where [math] is the transmission matrix of [math] and [math] is the distance matrix of [math]. The Indu–Bala product of two graphs [math] and [math], denoted by [math], was introduced in (G. Indulal and R. Balakrishnan, Distance spectrum of Indu–Bala product of graphs, AKCE Int. J. Graph Comb. 13(3) (2016) 230–234). In this paper, we first obtain the distance Laplacian spectrum of [math] in terms of Laplacian spectra of [math] and [math]. We then obtain the distance signless Laplacian spectrum of [math] in terms of signless Laplacian spectra of [math] and [math]. We construct pair of graphs which are distance Laplacian cospectral as well as pair of graphs which are distance signless Laplacian cospectral. We further find the metric dimension of [math] in terms of metric dimensions of [math] and [math]. Finally, we provide a problem for future research.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211124T08:00:00Z
DOI: 10.1142/S1793830922500379

 Bounds on the Steiner–Wiener index of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: V. A. Rasila, Ambat Vijayakumar
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a set of vertices of a connected graph [math]. The Steiner distance of [math] is the minimum size among all connected subgraphs of [math] containing the vertices of [math]. The sum of all Steiner distances on sets of size [math] is called the Steiner [math]Wiener index. We obtain formulae for bounds on the Steiner–Wiener index of graphs in terms of chromatic number, vertex connectivity and independence number. Also, we obtain bounds for 4cycle free graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211118T08:00:00Z
DOI: 10.1142/S1793830922500173

 Inductive graph invariants and approximation algorithms

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: C. R. Subramanian
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
We introduce and study an inductively defined analogue [math] of any increasing graph invariant [math]. An invariant [math] is increasing if [math] whenever [math] is an induced subgraph of [math]. This inductive analogue simultaneously generalizes and unifies known notions like degeneracy, inductive independence number, etc., into a single generic notion. For any given increasing [math], this gets us several new invariants and many of which are also increasing. It is also shown that [math] is the minimum (over all orderings) of a value associated with each ordering. We also explore the possibility of computing [math] (and a corresponding optimal vertex ordering) and identify some pairs [math] for which [math] can be computed efficiently for members of [math]. In particular, it includes graphs of bounded [math] values. Some specific examples (like the class of chordal graphs) have already been studied extensively. We further extend this new notion by (i) allowing vertex weighted graphs, (ii) allowing [math] to take values from a totally ordered universe with a minimum and (iii) allowing the consideration of [math]neighborhoods for arbitrary but fixed [math]. Such a generalization is employed in designing efficient approximations of some graph optimization problems. Precisely, we obtain efficient algorithms (by generalizing the known algorithm of Ye and Borodin [Y. Ye and A. Borodin, Elimination graphs, ACM Trans. Algorithms 8(2) (2012) 1–23] for special cases) for approximating optimal weighted induced [math]subgraphs and optimal [math]colorings (for hereditary [math]’s) within multiplicative factors of (essentially) [math] and [math] respectively, where [math] denotes the inductive analogue (as defined in this work) of optimal size of an unweighted induced [math]subgraph of the input and [math] is the minimum size of a forbidden induced subgraph of [math]. Our results generalize the previous result on efficiently approximating maximum independent sets and minimum colorings on graphs of bounded inductive independence number to optimal [math]subgraphs and [math]colorings for arbitrary hereditary classes [math]. As a corollary, it is also shown that any maximal [math]subgraph approximates an optimal solution within a factor of [math] for unweighted graphs, where [math] is maximum size of any induced [math]subgraph in any local neighborhood [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211117T08:00:00Z
DOI: 10.1142/S1793830922500197

 Resolving Roman domination in graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: P. Roushini Leely Pushpam, B. Mahavir, M. Kamalam
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a graph and [math] be a Roman dominating function defined on [math]. Let [math] be some ordering of the vertices of [math]. For any [math], [math] is defined by [math]. If for all [math], [math], we have [math], that is [math], for some [math], then [math] is called a resolving Roman dominating function (RDF) on [math]. The weight of a resolving RDF [math] on [math] is [math]. The minimum weight of a resolving RDF on [math] is called the resolving Roman domination number of [math] and is denoted by [math]. A resolving RDF on [math] with weight [math] is called a [math]function on [math]. In this paper, we find the resolving Roman domination number of certain wellknown classes of graphs. We also categorize the class of graphs whose resolving Roman domination number equals their order.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211117T08:00:00Z
DOI: 10.1142/S1793830922500288

 A note on [math][math]3 conjecture for Halin graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Xiaoli Jiang, Zhengke Miao, Xiaowei Yu
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The wellknown 123 Conjecture asserts the edges of every connected graph with at least three vertices can be weighted with 1, 2 and 3 so that adjacent vertices receive distinct sums of weights. In this paper, we show this conjecture holds for Halin graph. Moreover, this bound is tight.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211117T08:00:00Z
DOI: 10.1142/S179383092250032X

 Secondstage spectrum of corona of two graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Renny P Varghese
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The derived graph of a simple graph [math], denoted by [math], is the graph having the same vertex set as [math], in which two vertices are adjacent if and only if their distance in [math] is two. The spectrum of derived graph of [math] is called the secondstage spectrum of [math]. In this paper, we will determine the secondstage spectrum (Laplace and signless Laplace spectrum) of the corona of two regular graphs with diameter less than or equal to two. The energy of the derived graph is called the secondstage energy of [math]. Here, we proved that the class of graphs [math] is integral if and only if [math] is a perfect square and the secondstage energy depends only on number of vertices. Moreover, we discuss some applications like the number of spanning trees, the Kirchhoff index and Laplacianenergylike invariant of the newly constructed graph.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211117T08:00:00Z
DOI: 10.1142/S1793830922500343

 Total vertexedge domination in graphs: Complexity and algorithms

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Nitisha Singhwal, Palagiri Venkata Subba Reddy
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a simple, undirected and connected graph. A vertex [math] of a simple, undirected graph [math]dominates all edges incident to at least one vertex in its closed neighborhood [math]. A set [math] of vertices is a vertexedge dominating set of [math], if every edge of graph [math] is [math]dominated by some vertex of [math]. A vertexedge dominating set [math] of [math] is called a total vertexedge dominating set if the induced subgraph [math] has no isolated vertices. The total vertexedge domination number [math] is the minimum cardinality of a total vertexedge dominating set of [math]. In this paper, we prove that the decision problem corresponding to [math] is NPcomplete for chordal graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs. The problem of determining [math] of a graph [math] is called the minimum total vertexedge domination problem (MTVEDP). We prove that MTVEDP is linear time solvable for chain graphs and threshold graphs. We also show that MTVEDP can be approximated within approximation ratio of [math]. It is shown that the domination and total vertexedge domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MTVEDP is presented.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211115T08:00:00Z
DOI: 10.1142/S1793830922500318

 Constacyclic codes over the ring [math], [math] [math]

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Shunhua Zhang
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be the ring [math], where [math] for any odd prime [math] and positive integer [math]. In this paper, we study constacyclic codes over the ring [math]. We define a Gray map by a matrix and decompose a constacyclic code over the ring [math] as the direct sum of constacyclic codes over [math], we also characterize selfdual constacyclic codes over the ring [math] and give necessary and sufficient conditions for constacyclic codes to be dualcontaining. As an application, we give a method to construct quantum codes from dualcontaining constacyclic codes over the ring [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211113T08:00:00Z
DOI: 10.1142/S179383092250015X

 Signed domination number of hypercubes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: B. ShekinahHenry, Y. S. Irine Sheela
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The [math]cube graph or hypercube [math] is the graph whose vertex set is the set of all [math]dimensional Boolean vectors, two vertices being joined if and only if they differ in exactly one coordinate. The purpose of the paper is to investigate the signed domination number of this hypercube graphs. In this paper, signed domination number [math]cube graph for odd [math] is found and the lower and upper bounds of hypercube for even [math] are found.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211113T08:00:00Z
DOI: 10.1142/S179383092250029X

 Graphs whose weak Roman domination number increases by the deletion of any
edge
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Rihab Hamid, Nour El Houda Bendahib, Mustapha Chellali, Nacéra Meddah
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a function on a graph [math]. A vertex [math] with [math] is said to be undefended with respect to [math] if it is not adjacent to a vertex [math] with [math]. A function [math] is called a weak Roman dominating function (WRDF) if each vertex [math] with [math] is adjacent to a vertex [math] with [math], such that the function [math] defined by [math], [math] and [math] for all [math], has no undefended vertex. The weight of a WRDF is the sum of its function values over all vertices, and the weak Roman domination number [math] is the minimum weight of a WRDF in [math]. In this paper, we consider the effects of edge deletion on the weak Roman domination number of a graph. We show that the deletion of an edge of [math] can increase the weak Roman domination number by at most 1. Then we give a necessary condition for [math]ERcritical graphs, that is, graphs [math] whose weak Roman domination number increases by the deletion of any edge. Restricted to the class of trees, we provide a constructive characterization of all [math]ERcritical trees.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211111T08:00:00Z
DOI: 10.1142/S1793830922500069

 Optimal rendezvous on a line by locationaware robots in the presence of
spies
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Huda Chuangpishit, Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A set of mobile robots is placed at arbitrary points of an infinite line. The robots are equipped with GPS devices and they may communicate their positions on the line to a central authority. The collection contains an unknown subset of “spies”, i.e., byzantine robots, which are indistinguishable from the nonfaulty ones. The set of the nonfaulty robots needs to rendezvous in the shortest possible time in order to perform some task, while the byzantine robots may try to delay their rendezvous for as long as possible. The problem facing a central authority is to determine trajectories for all robots so as to minimize the time until all the nonfaulty robots have met. The trajectories must be determined without knowledge of which robots are faulty. Our goal is to minimize the competitive ratio between the time required to achieve the first rendezvous of the nonfaulty robots and the time required for such a rendezvous to occur under the assumption that the faulty robots are known at the start. In this paper, we give rendezvous algorithms with bounded competitive ratio, where the central authority is informed only of the set of initial robot positions, without knowing which ones or how many of them are faulty. In general, regardless of the number of faults [math] it can be shown that there is an algorithm with bounded competitive ratio. Further, we are able to give a rendezvous algorithm with optimal competitive ratio provided that the number [math] of faults is strictly less than [math]. Note, however, that in general this algorithm does not give an estimate on the actual value of the competitive ratio. However, when an upper bound on the number of byzantine robots is known to the central authority, we can provide algorithms with constant competitive ratios and in some instances we are able to show that these algorithms are optimal. Moreover, in the cases where the number of faults is either [math] or [math] we are able to compute the competitive ratio of an optimal rendezvous algorithm, for a small number of robots.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211111T08:00:00Z
DOI: 10.1142/S1793830922500306

 On approximating MIS over [math]VPG graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Abhiruk Lahiri, Joydeep Mukherjee, C. R. Subramanian
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this paper, we present an approximation algorithm for the maximum independent set (MIS) problem over the class of [math]VPG graphs when the input is specified by a [math]VPG representation. We obtain a [math]approximation algorithm running in [math] time. This is an improvement over the previously best [math]approximation algorithm [J. Fox and J. Pach, Computing the independence number of intersection graphs, in Proc. TwentySecond Annual ACMSIAM Symp. Discrete Algorithms (SODA 2011), 2011, pp. 1161–1165, doi:10.1137/1.9781611973082.87] (for some fixed [math]) designed for some subclasses of string graphs, on [math]VPG graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211111T08:00:00Z
DOI: 10.1142/S1793830922500355

 On generalized adjacency Estrada index of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Maryam Baghipur, Harishchandra S. Ramane
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The Estrada index is a graphspectrumbased invariant having an important role in chemistry and physics. In this paper, we define the generalized adjacency Estrada index of a graph and obtain some lower and upper bounds for the generalized adjacency Estrada index in terms of various graph parameters associated with the structure of a graph. Further, we characterize the extremal graphs attaining these bounds. We also highlight the relationship between generalized adjacency Estrada index and generalized adjacency energy. Using these results, we obtain the improved bounds for the Estrada index based on the adjacency eigenvalues of a graph.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211110T08:00:00Z
DOI: 10.1142/S1793830922500367

 The connectivity and Hamiltonian properties of secondorder circuit graphs
of wheel cycle matroids
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Zijian Deng, Bin Liu, Bofeng Huo, Bo Deng
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be the [math]thorder circuit graph of a simple connected matroid M. The firstorder circuit graph is also called a circuit graph. There are lots of results about connectivity and Hamiltonian properties of circuit graph of matroid, while there are few related results on the secondorder circuit graph of a matroid. This paper mainly focuses on the connectivity and Hamiltonian properties of the secondorder circuit graphs of the cycle matroid of wheels. It determines the minimum degree and connectivity of these graphs, and proves that the secondorder circuit graph of the cycle matroid of a wheel is uniformly Hamiltonian.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211106T07:00:00Z
DOI: 10.1142/S1793830922500070

 Samplingbased approximate skyline calculation on big data

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Xingxing Xiao, Jianzhong Li
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Nowadays, big data is coming to the force in a lot of applications. Processing a skyline query on big data in more than linear time is by far too expensive and often even linear time may be too slow. It is obviously not possible to compute an exact solution to a skyline query in sublinear time, since an exact solution may itself have linear size. Fortunately, in many situations, a fast approximate solution is more useful than a slower exact solution. This paper proposes two samplingbased approximate algorithms for processing skyline queries. The first algorithm obtains a fixed size sample and computes the approximate skyline on it. The error of the algorithm is not only relatively small in most cases, but also is almost unaffected by the input size. The second algorithm returns an [math]approximation for the exact skyline efficiently. The running time of the algorithm has nothing to do with the input size in practical, achieving the goal of sublinearity on big data. Experiments verify the error analysis of the first algorithm, and show that the second is much faster than the existing skyline algorithms.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211106T07:00:00Z
DOI: 10.1142/S1793830922500240

 A refinement of Dyck paths: A combinatorial approach

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Rigoberto Flórez, José L. Ramírez, Fabio A. Velandia, Diego Villamizar
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Local maxima and minima of a Dyck path are called peaks and valleys, respectively. A Dyck path is called restricted[math]Dyck if the difference between any two consecutive valleys is at least [math] (righthand side minus lefthand side) or if it has at most one valley. In this paper, we use several techniques to enumerate some statistics over this new family of lattice paths. For instance, we use the symbolic method, the Chomsky–Schűtzenberger methodology, Zeilberger’s creative telescoping method, recurrence relations, and bijective relations. We count, for example, the number of paths of length [math], the number of peaks, the number of valleys, the number of peaks of a fixed height, and the area under the paths. We also give a bijection between the restricted [math]Dyck paths and a family of binary words.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211106T07:00:00Z
DOI: 10.1142/S1793830922500264

 On the local irregularity vertex coloring of volcano, broom, parachute,
double broom and complete multipartite graphs
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Arika Indah Kristiana, Nafidatun Nikmah, Dafik, Ridho Alfarisi, M. Ali Hasan, Slamin
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a simple, finite, undirected, and connected graph with vertex set [math] and edge set [math]. A bijection [math] is label function [math] if [math] and for any two adjacent vertices [math] and [math], [math] where [math] and [math] is set ofvertices adjacent to [math]. [math] is called local irregularity vertex coloring. The minimum cardinality of local irregularity vertex coloring of [math] is called chromatic number local irregular denoted by [math]. In this paper, we verify the exact values of volcano, broom, parachute, double broom and complete multipartite graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211028T07:00:00Z
DOI: 10.1142/S1793830922500227

 Twoended quasitransitive graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Babak Miraftab, Tim Rühmann
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The wellknown characterization of twoended groups says that every twoended group can be split over finite subgroups which means it is isomorphic to either by a free product with amalgamation [math] or an HNNextension [math], where [math] is a finite group and [math] and [math]. In this paper, we show that there is a way in order to spilt twoended quasitransitive graphs without dominated ends and twoended transitive graphs over finite subgraphs in the above sense. As an application of it, we characterize all groups acting with finitely many orbits almost freely on those graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211027T07:00:00Z
DOI: 10.1142/S1793830922500239

 Edge [math]choosability of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: P. Soorya, K. A. Germina
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a simple, connected graph of order [math] and size [math] Then, [math] is said to be edge [math]choosable, if there exists a collection of subsets of the edge set, [math] of cardinality [math] such that [math] whenever [math] and [math] are incident. This paper initiates a study on edge [math]choosability of certain fundamental classes of graphs and determines the maximum value of [math] for which the given graph [math] is edge [math]choosable. Also, in this paper, the relation between edge choice number and other graph theoretic parameters is discussed and we have given a conjecture on the relation between edge choice number and matching number of a graph.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211027T07:00:00Z
DOI: 10.1142/S1793830922500252

 Transitivity of trees

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Libin Chacko Samuel, Mayamma Joseph
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a graph [math], a partition [math] of the vertex set [math] is a transitive partition if [math] dominates [math] whenever [math]. The transitivity [math] of a graph [math] is the maximum order of a transitive partition of [math]. For any positive integer [math], we characterize the smallest tree with transitivity [math] and obtain an algorithm to determine the transitivity of any tree of finite order.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211022T07:00:00Z
DOI: 10.1142/S1793830922500203

 Some properties of subgroup complementary addition Cayley graphs on
abelian groups
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Naveen Palanivel, Chithra A. Velu
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this paper, we introduce subgroup complementary addition Cayley graph [math] and compute its graph invariants. Also, we prove that [math] if and only if [math] for all [math] where [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211022T07:00:00Z
DOI: 10.1142/S1793830922500215

 Structure of super strongly perfect graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: T. E. Soorya, Sunil Mathew
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Super strongly perfect graphs and their association with certain other classes of graphs are discussed in this paper. It is observed that every split graph is super strongly perfect. An existing result on super strongly perfect graphs is disproved providing a counter example. It is also established that if a graph [math] contains a cycle of odd length, then its line graph [math] is not always super strongly perfect. Complements of cycles of length six or above are proved to be nonsuper strongly perfect. If a graph is strongly perfect, then it is shown that they are super strongly perfect and hence all [math]free graphs are super strongly perfect.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20211012T07:00:00Z
DOI: 10.1142/S1793830922500185

 A remark on skew factorization and new [math]linear codes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Padmapani Seneviratne
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Nine new [math] linear codes with lengths [math] and [math] that improve previously best known parameters are constructed. By modifying these codes, another 17 new codes are obtained. It is conjectured that the complete set of factors of [math] can be derived from the factors of [math] for even values of [math] in the skew polynomial ring [math]. It is further shown that the [math] code obtained is linearly complementary dual.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210929T07:00:00Z
DOI: 10.1142/S1793830922500112

 Total double Roman domination numbers in digraphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: J. Amjadi, F. Pourhosseini
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a finite and simple digraph with vertex set [math]. A double Roman dominating function (DRDF) on digraph [math] is a function [math] such that every vertex with label 0 has an inneighbor with label 3 or two inneighbors with label 2 and every vertex with label 1 have at least one inneighbor with label at least 2. The weight of a DRDF [math] is the value [math]. A DRDF [math] on [math] with no isolated vertex is called a total double Roman dominating function if the subgraph of [math] induced by the set [math] has no isolated vertex. In this paper, we initiate the study of the total double Roman domination number in digraphs and show its relationship to other domination parameters. In particular, we present some bounds for the total double Roman domination number and we determine the total double Roman domination number of some classes of digraphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210928T07:00:00Z
DOI: 10.1142/S1793830922500148

 Movable resolving domination in graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Gerald B. Monsanto, Helen M. Rara
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a connected graph. Brigham et al., Resolving domination in graphs, Math. Bohem. 1 (2003) 25–36 defined a resolving dominating set as a set [math] of vertices of a connected graph [math] that is both resolving and dominating. A resolving dominating is a [math]movable resolving dominating set of [math] if for every [math], either [math] is a resolving dominating set or there exists a vertex [math] such that [math] is a resolving dominating set of [math]. The minimum cardinality of a [math]movable resolving dominating set of [math], denoted by [math] is the [math]movable[math]domination number of [math]. A [math]movable resolving dominating set with cardinality [math] is called a [math]set of [math]. In this paper, we characterize the [math]movable resolving dominating sets in the join and lexicographic product of two graphs and determine the bounds or exact values of the [math]movable resolving domination number of these graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210928T07:00:00Z
DOI: 10.1142/S1793830922500161

 On a conjecture of Laplacian energy of trees

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Hilal A. Ganie, Bilal A. Rather, S. Pirzada
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a simple graph with [math] vertices, [math] edges having Laplacian eigenvalues [math]. The Laplacian energy LE[math] is defined as LE[math], where [math] is the average degree of [math]. Radenković and Gutman conjectured that among all trees of order [math], the path graph [math] has the smallest Laplacian energy. Let [math] be the family of trees of order [math] having diameter [math]. In this paper, we show that Laplacian energy of any tree [math] is greater than the Laplacian energy of [math], thereby proving the conjecture for all trees of diameter [math]. We also show the truth of conjecture for all trees with number of nonpendent vertices at most [math]. Further, we give some sufficient conditions for the conjecture to hold for a tree of order [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210906T07:00:00Z
DOI: 10.1142/S1793830922500094

 On some punctured codes of [math]Simplex codes

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: J. Prabu, J. Mahalakshmi, C. Durairajan, S. Santhakumar
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this paper, we have constructed some new codes from [math]Simplex code called unit [math]Simplex code. In particular, we find the parameters of these codes and have proved that it is a [math] [math]linear code, where [math] and [math] is a smallest prime divisor of [math]. When rank [math] and [math] is a prime power, we have given the weight distribution of unit [math]Simplex code. For the rank [math] we obtain the partial weight distribution of unit [math]Simplex code when [math] is a prime power. Further, we derive the weight distribution of unit [math]Simplex code for the rank [math] [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210906T07:00:00Z
DOI: 10.1142/S1793830922500124

 Critical concepts of restrained domination in signed graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Anisha Jean Mathias, V. Sangeetha, Mukti Acharya
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A signed graph [math] is a simple undirected graph in which each edge is either positive or negative. Restrained dominating set [math] in [math] is a restrained dominating set of the underlying graph [math] where the subgraph induced by the edges across [math] and within [math] is balanced. The minimum cardinality of a restrained dominating set of [math] is called the restrained domination number, denoted by [math]. In this paper, we initiate the study on various critical concepts to investigate the effect of edge removal or edge addition on restrained domination number in signed graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210831T07:00:00Z
DOI: 10.1142/S1793830922500100

 The projective [math]annihilatingideal hypergraphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: V. Ramanathan, C. Selvaraj
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this paper, we investigate the crosscap of 3annihilatingideal hypergraph [math] of a commutative ring [math] and the topological embedding of [math] to the nonorientable compact surfaces. Furthermore, we determine all Artinian commutative nonlocal rings [math] (up to isomorphism) such that [math] is a projective graph.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210828T07:00:00Z
DOI: 10.1142/S1793830922500057

 Restrained geodetic domination of edge subdivision graph

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: John Joy Mulloor, V. Sangeetha
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a connected graph [math], a set [math] subset of [math] is said to be a geodetic set if all vertices in [math] should lie in some [math] geodesic for some [math]. The minimum cardinality of the geodetic set is the geodetic number. In this paper, the authors discussed the geodetic number, geodetic domination number, and the restrained geodetic domination of the edge subdivision graph.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210821T07:00:00Z
DOI: 10.1142/S1793830922500021

 Hamiltonian trace graph of matrices

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: M. Sivagami, T. Tamizh Chelvam
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a commutative ring with identity, [math] be a positive integer and [math] be the set of all [math] matrices over [math] For a matrix [math] Tr[math] is the trace of [math] The trace graph of the matrix ring [math] denoted by [math] is the simple undirected graph with vertex set [math][math] and two distinct vertices [math] and [math] are adjacent if and only if Tr[math] The idealbased trace graph of the matrix ring [math] with respect to an ideal [math] of [math] denoted by [math] is the simple undirected graph with vertex set [math] and two distinct vertices [math] and [math] are adjacent if and only if Tr[math] In this paper, we investigate some properties and structure of [math] Further, it is proved that both [math] and [math] are Hamiltonian.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210818T07:00:00Z
DOI: 10.1142/S179383092250001X

 Enumeration of [math]hypergroups on sets with two elements

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: M. B. Safari, B. Davvaz
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
This paper is a continuation of ideas presented in [M. B. Safari, B. Davvaz and V. LeoreanuFotea, Enumeration of 3 and 4hypergroups on sets with two elements, Eur. J. Combin. 44 (2015) 298–306]. We find the number and structure of nonisomorphism 5hypergroups on sets with two elements. Moreover, we present a general template for some special cases of [math]hypergroups by linking the last results on [math]hypergroups.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210818T07:00:00Z
DOI: 10.1142/S1793830922500033

 Algorithmic aspects of outer independent Roman domination in graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Amit Sharma, Jakkepalli Pavan Kumar, P. Venkata Subba Reddy, S. Arumugam
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a connected graph. A function [math] is called a Roman dominating function if every vertex [math] with [math] is adjacent to a vertex [math] with [math]. If further the set [math] is an independent set, then [math] is called an outer independent Roman dominating function (OIRDF). Let [math] and [math]. Then [math] is called the outer independent Roman domination number of [math]. In this paper, we prove that the decision problem for [math] is NPcomplete for chordal graphs. We also show that [math] is linear time solvable for threshold graphs and bounded tree width graphs. Moreover, we show that the domination and outer independent Roman domination problems are not equivalent in computational complexity aspects.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210818T07:00:00Z
DOI: 10.1142/S1793830922500045

 [math]Gatherings on a star and uncertain [math]gatherings on a line

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Shareef Ahmed, Shinichi Nakano, Md. Saidur Rahman
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a set of [math] customers and [math] be a set of [math] facilities. An [math]gather clustering of [math] is a partition of the customers in clusters such that each cluster contains at least [math] customers. The [math]gather clustering problem asks to find an [math]gather clustering which minimizes the maximum distance between a pair of customers in a cluster. An [math]gathering of [math] to [math] is an assignment of each customer [math] to a facility [math] such that each facility has zero or at least [math] customers. The [math]gathering problem asks to find an [math]gathering that minimizes the maximum distance between a customer and his/her facility. In this work, we consider the [math]gather clustering and [math]gathering problems when the customers and the facilities are lying on a “star”. We show that the [math]gather clustering problem and the [math]gathering problem with customers and facilities on a star with [math] rays can be solved in [math] and [math] time, respectively. Furthermore, we prove the hardness of a variant of the [math]gathering problem, called the minmaxsum [math]gathering problem, even when the customers and the facilities are on a star. We also study the [math]gathering problem when the customers and the facilities are on a line, and each customer location is uncertain. We show that the [math]gathering problem can be solved in [math] and [math] time when the customers and the facilities are on a line, and the customer locations are given by piecewise uniform functions of at most [math] pieces and “wellseparated” uniform distribution functions, respectively.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210805T07:00:00Z
DOI: 10.1142/S1793830921501603

 Algorithm to check the existence of [math] for a given [math] such that
[math] is graphical
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: K. Arathi Bhat, G. Sudhakara, M. Vinay
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A matrix with entries [math] is graphical if it is symmetric and all its diagonal entries are zero. Let [math], [math] and [math] be graphs defined on the same set of vertices. The graph [math] is said to be the matrix product of graphs [math] and [math], if [math], where [math] is the adjacency matrix of the graph [math]. In such a case, we say that [math] and [math] are companions of each other. The main purpose of this paper is to design an algorithm to check whether a given graph [math] has a companion. We derive conditions on [math] and [math] so that the generalized wheel graph, denoted by [math], has a companion and also show that the [math]th power of the path graph [math] has no companion. Finally, we indicate a possible application of the algorithm in a problem of coloring of edges of the complete graph [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210724T07:00:00Z
DOI: 10.1142/S1793830921501597

 A note on global dominator coloring of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: R. Rangarajan, David. A. Kalarkop
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Global dominator coloring of the graph [math] is the proper coloring of [math] such that every vertex of [math] dominates atleast one color class as well as antidominates atleast one color class. The minimum number of colors required for global dominator coloring of [math] is called global dominator chromatic number of [math] denoted by [math]. In this paper, we characterize trees [math] of order [math] [math] such that [math] and also establish a strict upper bound for [math] for a tree of even order [math] [math]. We construct some family of graphs [math] with [math] and prove some results on [math]partitions of [math] when [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210721T07:00:00Z
DOI: 10.1142/S1793830921501585

 On [math]irregularity strength of cycles and diamond graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Hayat Labane, Isma Bouchemakh, Andrea SemaničováFeňovčíková
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A simple graph [math] admits an [math]covering if every edge in [math] belongs to at least one subgraph of [math] isomorphic to a given graph [math]. The graph [math] admits an [math]irregular total[math]labeling [math] if [math] admits an [math]covering and for every two different subgraphs [math] and [math] isomorphic to [math], there is [math], where [math] is the associated [math]weight. The total[math]irregularity strength of [math] is [math]. In this paper, we give the exact values of [math], where [math]. For the versions edge and vertex [math]irregularity strength [math] and [math], respectively, we determine the exact values of [math], [math] and [math], where [math] is the diamond graph.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210716T07:00:00Z
DOI: 10.1142/S1793830921501573

 Deep learningbased approximation of Goldbach partition function

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Eunmi Kim
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Goldbach’s conjecture is one of the oldest and famous unproved problems in number theory. Using a deep learning model, we obtain an approximation of the Goldbach partition function, which counts the number of ways of representing an even number greater than 4 as a sum of two primes. We use residues of number modulo first 25 primes as features and archive a more accurate approximation, which reduces error rate from [math] to [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210710T07:00:00Z
DOI: 10.1142/S1793830921501524

 On generalized neighbor sum distinguishing index of planar graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Jieru Feng, Yue Wang, Jianliang Wu
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a proper [math]edge coloring [math] of a graph [math], let [math] denote the sum of the colors taken on the edges incident to the vertex [math]. Given a positive integer [math], the [math]neighbor sum distinguishing [math]edge coloring of G is [math] such that for each edge [math], [math]. We denote the smallest integer [math] in such coloring of [math] by [math]. For [math], Wang et al. proved that [math]. In this paper, we show that if G is a planar graph without isolated edges, then [math], where [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210709T07:00:00Z
DOI: 10.1142/S1793830921501470

 Sharp lower bounds on the sumconnectivity index of trees

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: S. Alyar, R. Khoeilar
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The sumconnectivity index of a graph [math] is defined as the sum of weights [math] over all edges [math] of [math], where [math] and [math] are the degrees of the vertices [math] and [math] in [math], respectively. In this paper, some extremal problems on the sumconnectivity index of trees are studied. The extremal values on the sumconnectivity index of trees with given graphic parameters, such as pendant number, matching number, domination number and diameter, are determined. The corresponding extremal graphs are characterized, respectively.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210706T11:12:37Z
DOI: 10.1142/S1793830921501536

 Planar graphs without intersecting 5cycles are signed4choosable

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: SeogJin Kim, Xiaowei Yu
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A signed graph is a pair [math], where [math] is a graph and [math] is a signature of [math]. A set [math] of integers is symmetric if [math] implies that [math]. Given a list assignment [math] of [math], an [math]coloring of a signed graph [math] is a coloring [math] of [math] such that [math] for each [math] and [math] for every edge [math]. The signed choice number [math] of a graph [math] is defined to be the minimum integer [math] such that for any [math]list assignment [math] of [math] and for any signature [math] on [math], there is a proper [math]coloring of [math]. List signed coloring is a generalization of list coloring. However, the difference between signed choice number and choice number can be arbitrarily large. Hu and Wu [Planar graphs without intersecting [math]cycles are [math]choosable, Discrete Math. 340 (2017) 1788–1792] showed that every planar graph without intersecting 5cycles is 4choosable. In this paper, we prove that [math] if [math] is a planar graph without intersecting 5cycles, which extends the main result of [D. Hu and J. Wu, Planar graphs without intersecting [math]cycles are [math]choosable, Discrete Math. 340 (2017) 1788–1792].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210706T07:00:00Z
DOI: 10.1142/S1793830921501512

 On the double total dominator chromatic number of graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Fairouz Beggas, Hamamache Kheddouci, Walid Marweni
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this paper, we introduce and study a new coloring problem of graphs called the double total dominator coloring. A double total dominator coloring of a graph [math] with minimum degree at least 2 is a proper vertex coloring of [math] such that each vertex has to dominate at least two color classes. The minimum number of colors among all double total dominator coloring of [math] is called the double total dominator chromatic number, denoted by [math]. Therefore, we establish the close relationship between the double total dominator chromatic number [math] and the double total domination number [math]. We prove the NPcompleteness of the problem. We also examine the effects on [math] when [math] is modified by some operations. Finally, we discuss the [math] number of square of trees by giving some bounds.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210706T07:00:00Z
DOI: 10.1142/S1793830921501548

 On the skew Laplacian spectral radius of a digraph

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Bilal A. Chat, Hilal A. Ganie, Altaf A. Bhat, Mohd Y. Bhat, Mehraj A. Lone
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be an orientation of a simple graph [math] with [math] vertices and [math] edges. The skew Laplacian matrix [math] of the digraph [math] is defined as [math], where [math] is the imaginary unit, [math] is the diagonal matrix with oriented degrees [math] as diagonal entries and [math] is the skew matrix of the digraph [math]. The largest eigenvalue of the matrix [math] is called skew Laplacian spectral radius of the digraph [math]. In this paper, we study the skew Laplacian spectral radius of the digraph [math]. We obtain some sharp lower and upper bounds for the skew Laplacian spectral radius of a digraph [math], in terms of different structural parameters of the digraph and the underlying graph. We characterize the extremal digraphs attaining these bounds in some cases. Further, we end the paper with some problems for the future research in this direction.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210706T07:00:00Z
DOI: 10.1142/S179383092150155X

 A secure image cryptosystem via multiple chaotic maps

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Mayada T. Wazi, Dalia S. Ali, Nadia M. G. AlSaidi, Nawras A. Alawn
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
This work focused on introducing a new twodimensional (2D) chaotic system. It is combined of some existing maps, the logistic, iterative chaotic map with infinite collapse, and Henon maps; we called it 2DLCHM. The assessment of the actual performance of 2DLCHM presents its sensitivity to a tiny change in the initial condition. Besides, its dynamics behavior is very complicated. It also has hyperchaotic properties and good ergodicity. The proposed system is occupied with designing a new image encryption system. Changing the image pixels’ locations is the primary step in the encryption process. The original image is splitting into four blocks to create four different keys based on 2DLCHM; this reduces the computation time and increases the complexity. To obtain the encryption image, we have to repeat the partitioning process several times for each block. The encryption image’s efficiency is shown through some performance analysis such as; image histogram, the number of pixels changes rate (NPCR), the unified average changing intensity (UACI), pixels correlation, and entropy. The proposed system is compared with some efficient encryption algorithms in terms of chaocity attributes and image performance; the analysis result showed consistent improvement.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210705T07:00:00Z
DOI: 10.1142/S179383092150141X

 List injective coloring of planar graphs with disjoint [math]cycles

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Wenwen Li, Jiansheng Cai
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
An injective [math]coloring of a graph [math] is called injective if any two vertices joined by a path of length two get different colors. A graph [math] is injectively [math]choosable if for any color list [math] of admissible colors on [math] of size [math] it allows an injective coloring [math] such that [math] whenever [math]. Let [math], [math] denote the injective chromatic number and injective choosability number of [math], respectively. Let [math] be a plane with disjoint [math]cycles and maximum degree [math]. We show that [math] if [math], then [math]; [math] if [math], then [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210626T07:00:00Z
DOI: 10.1142/S1793830921501482

 Notes on Latin square graphs and their domination numbers

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Sara Pouyandeh, Maryam Golriz, Mohammad Reza Sorouhesh, Maryam Khademi
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
A Latin square graph [math] is a simple graph associated with a Latin square [math]. In this paper, we consider a Latin square graph [math] in which [math] and improve the upper bound of the domination number [math] by showing that [math]. Moreover, we study certain domination numbers like medium domination, accurate domination, independent transversal domination and vertex covering transversal domination for Latin square graphs of order [math] to give useful facts.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210621T07:00:00Z
DOI: 10.1142/S1793830921501354

 Exploiting the security of [math] through approximation of [math]

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Saidu Isah Abubakar, Sadiq Shehu
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
This paper reports new techniques that exploit the security of the prime power moduli [math] using continued fraction method. Our study shows that the key equation [math] can be exploited using [math] as good approximation of [math]. This enables us to get [math] from the convergents of the continued fractions expansion of [math] where the bound of the private exponent is [math] which leads to the polynomial time factorization of the moduli [math]. We further report the polynomial time attacks that can break the security of the generalized prime power moduli [math] using generalized system of equation of the form [math] and [math] by applying simultaneous Diophantine approximations and LLL algorithm techniques where [math] and [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210621T07:00:00Z
DOI: 10.1142/S1793830921501445

 The minus total [math]domination numbers in graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Jonecis Dayap, Nasrin Dehgardi, Leila Asgharsharghi, Seyed Mahmoud Sheikholeslami
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For any integer [math], a minus total [math]dominating function is a function [math] satisfying [math] for every [math], where [math]. The minimum of the values of [math], taken over all minus total [math]dominating functions [math], is called the minus total [math]domination number and is denoted by [math]. In this paper, we initiate the study of minus total [math]domination in graphs, and we present different sharp bounds on [math]. In addition, we determine the minus total [math]domination number of some classes of graphs. Some of our results are extensions of known properties of the minus total domination number [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210621T07:00:00Z
DOI: 10.1142/S1793830921501500

 Square element graph of squaresubtract rings

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Bijon Biswas, S. Kar, M. K. Sen
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
If [math] is a ring then the square element graph [math] is the simple undirected graph whose vertex set consists of all nonzero elements of [math] and two distinct vertices [math] are adjacent if and only if [math] for some [math]. In this paper, we provide some necessary and sufficient conditions for the connectedness of [math], where [math] is a ring with identity. We mainly characterize some special class of ring [math] which we call squaresubtract ring for which the graph [math] is connected.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210618T07:00:00Z
DOI: 10.1142/S1793830921501421

 Gravitational community detection by predicting diameter

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Himansu Sekhar Pattanayak, Harsh K. Verma, Amrit Lal Sangal
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Community detection is a pivotal part of network analysis and is classified as an NPhard problem. In this paper, a novel community detection algorithm is proposed, which probabilistically predicts communities’ diameter using the local information of random seed nodes. The gravitation method is then applied to discover communities surrounding the seed nodes. The individual communities are combined to get the community structure of the whole network. The proposed algorithm, named as Local Gravitational community detection algorithm (LGCDA), can also work with overlapping communities. LGCDA algorithm is evaluated based on quality metrics and groundtruth data by comparing it with some of the widely used community detection algorithms using synthetic and realworld networks.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210618T07:00:00Z
DOI: 10.1142/S1793830921501457

 Triangulability of convex graphs and convex skewness

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Niran Abbas Ali, Gek L. Chia, Hazim Michman Trao, Adem Kilicman
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Suppose [math] is a subgraph of a convex complete graph [math] and [math] contains no boundary edge of [math] and [math]. We determine necessary and sufficient conditions on [math] such that [math] admits a triangulation. For [math], we investigate the possibility of placing [math] in [math] such that [math] admits a triangulation for certain families of graphs [math]. These results are then applied to determine the convex skewness of the convex graphs of the form [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210618T07:00:00Z
DOI: 10.1142/S1793830921501469

 Bounds and extremal graphs for Harary energy

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: A. Alhevaz, M. Baghipur, H. A. Ganie, K. C. Das
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a connected graph of order [math] and let [math] be the reciprocal distance matrix (also called Harary matrix) of the graph [math]. Let [math] be the eigenvalues of the reciprocal distance matrix [math] of the connected graph [math] called the reciprocal distance eigenvalues of [math]. The Harary energy [math] of a connected graph [math] is defined as sum of the absolute values of the reciprocal distance eigenvalues of [math], that is, [math] In this paper, we establish some new lower and upper bounds for [math] in terms of different graph parameters associated with the structure of the graph [math]. We characterize the extremal graphs attaining these bounds. We also obtain a relation between the Harary energy and the sum of [math] largest adjacency eigenvalues of a connected graph.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210618T07:00:00Z
DOI: 10.1142/S1793830921501494

 On skew cyclic codes over a mixed alphabet and their applications to DNA
codes
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Abdullah Dertli, Yasemin Cengellenmis, Nuh Aydin
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
In this paper, we introduce skew cyclic codes over the mixed alphabet [math], where [math] is the finite field with 4 elements and [math]. Our results include a description of the generator polynomials of such codes and a necessary and sufficient condition for an [math]skew cyclic code to be reversible complement.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210611T07:00:00Z
DOI: 10.1142/S1793830921501433

 On the square coloring of comparability graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Mehmet Akif Yetim
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
We find sufficient conditions for the square of a comparability graph [math] of a poset [math] to be [math]colorable when [math] lacks [math] for some [math]. Furthermore, we show that the problem of coloring the square of the comparability graph of a poset of height at least four can be reduced to the case of height three, where the height of a poset is the size of a maximum chain.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210607T07:00:00Z
DOI: 10.1142/S1793830921501391

 General sumconnectivity index of unicyclic graphs with given diameter and
girth
Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Tomáš Vetrík
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Topological indices of graphs have been studied due to their extensive applications in chemistry. We obtain lower bounds on the general sumconnectivity index [math] for unicyclic graphs [math] of given girth and diameter, and for unicyclic graphs of given diameter, where [math]. We present the extremal graphs for all the bounds. Our results generalize previously known results on the harmonic index for unicyclic graphs of given diameter.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210607T07:00:00Z
DOI: 10.1142/S1793830921501408

 Sharp lower bounds on the sumconnectivity index of quasitree graphs

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Amir Taghi Karimi
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The sumconnectivity index of a graph [math] is defined as the sum of weights [math] over all edges [math] of [math], where [math] and [math] are the degrees of the vertices [math] and [math] in [math], respectively. A graph [math] is called quasitree, if there exists [math] such that [math] is a tree. In the paper, we give a sharp lower bound on the sumconnectivity index of quasitree graphs.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210531T07:00:00Z
DOI: 10.1142/S1793830921501366

 Super domination in trees

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: B. Senthilkumar, Y. B. Venkatakrishnan, H. Naresh Kumar
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a simple graph. A set [math] is called a super dominating set if for every vertex [math], there exist [math] such that [math]. The minimum cardinality of a super dominating set of [math], denoted by [math], is called the super domination number of graph [math]. Characterization of trees with [math] is presented.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210528T07:00:00Z
DOI: 10.1142/S1793830921501378

 More on the unimodality of domination polynomial of a graph

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: GeeChoon Lau, Saeid Alikhani
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
Let [math] be a graph of order [math]. A subset [math] of [math] is a dominating set of [math] if every vertex in [math] is adjacent to at least one vertex of [math]. The domination polynomial of [math] is the polynomial [math], where [math] is the number of dominating sets of [math] of size [math], and [math] is the size of a smallest dominating set of [math], called the domination number of [math]. Motivated by a conjecture in [S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, ARS Combin. 114 (2014) 257–266] which states that the domination polynomial of any graph is unimodal, we obtain sufficient conditions for this conjecture to hold. Also we study the unimodality of graph [math] with [math], where [math] is an integer.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210528T07:00:00Z
DOI: 10.1142/S179383092150138X

 Graphs with constant adjacency dimension

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Mohsen Jannesari
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
For a set [math] of vertices and a vertex [math] in a graph [math], the [math]vector [math] is the adjacency representation of [math] with respect to [math], where [math] and [math] is the minimum of [math] and the distance between the vertices [math] and [math]. The set [math] is an adjacency resolving set for [math] if distinct vertices of [math] have distinct adjacency representations with respect to [math]. The minimum cardinality of an adjacency resolving set for [math] is its adjacency dimension. It is clear that the adjacency dimension of an [math]vertex graph [math] is between [math] and [math]. The graphs with adjacency dimension [math] and [math] are known. All graphs with adjacency dimension [math], and all [math]vertex graphs with adjacency dimension [math] are studied in this paper. In terms of the diameter and order of [math], a sharp upper bound is found for adjacency dimension of [math]. Also, a sharp lower bound for adjacency dimension of [math] is obtained in terms of order of [math]. Using these two bounds, all graphs with adjacency dimension 2, and all [math]vertex graphs with adjacency dimension [math] are characterized.
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210519T07:00:00Z
DOI: 10.1142/S1793830921501342

 On neighborhood graphs: Domination, coloring and other properties

Free preprint version: Loading...Rate this result: What is this?Please help us test our new preprint finding feature by giving the preprint link a rating.
A 5 star rating indicates the linked preprint has the exact same content as the published article.
Authors: Angsuman Das
Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print.
The neighborhood graph [math] of a graph [math] has the same vertex set as [math] and two vertices are adjacent in [math] if and only if they have a common neighbor in [math]. We study the domination number, independence number and chromatic number of [math] in terms of those of [math]. Moreover we investigate various structural similarities between [math] and [math].
Citation: Discrete Mathematics, Algorithms and Applications
PubDate: 20210517T07:00:00Z
DOI: 10.1142/S1793830921501330
