Authors:Yi Zhang, Mei Lu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A matching of a [math]-uniform hypergraph is a set of pairwise disjoint edges. A [math]-matching in a [math]-uniform hypergraph [math] is a matching of size [math]. Let [math] be a [math]-uniform hypergraph of order [math] and [math]. If [math] for any two adjacent vertices [math], and [math], then [math] contains a [math]-matching. This result is an extension of a work of Bollobás, Daykin and Erdős [Sets of independent edges of a hypergraph, Quart. J. Math. Oxford 21 (1976) 25–32]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-19T09:04:45Z DOI: 10.1142/S1793830917500720

Authors:Ishwar Baidari, Preeti Savant Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we present a new index called min–max distance degree index, [math] for molecular graphs. It appears that this index correlates well with properties of 33 and 28 nonanes like, energy of formation and density, and its correlation coefficient is 0.812 and 0.754, respectively. The basic mathematical features and graph operations are presented. In addition, the linear regression analysis of predicted and experimental boiling point of acyclic hydrocarbons is shown, where predicted boiling point is determined by implementing this index with Wiener’s model. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-19T09:04:45Z DOI: 10.1142/S1793830917500732

Authors:Muhammad Naeem, Muhammad Kamran Siddiqui Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a graph. A total labeling [math] is called totally irregular total [math]-labeling of [math] if every two distinct vertices [math] and [math] in [math] satisfy [math] and every two distinct edges [math] and [math] in [math] satisfy [math] where [math] and [math] The minimum [math] for which a graph [math] has a totally irregular total [math]-labeling is called the total irregularity strength of [math], denoted by [math] In this paper, we determined the total irregularity strength of disjoint union of [math] isomorphic copies of generalized Petersen graph. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-19T09:04:44Z DOI: 10.1142/S1793830917500719

Authors:M. Al Tahan, B. Davvaz Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Cyclic hypergroups are of great importance due to their applications to many fields in mathematics. In this paper, we classify all commutative single power cyclic hypergroups of order three and period two. Moreover, we prove some new interesting properties regarding cyclic hypergroups. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-10-10T01:55:30Z DOI: 10.1142/S1793830917500707

Authors:Gruia Calinescu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Given an edge-weighted undirected hypergraph [math] and an even-sized set of vertices [math], a T-cut is a partition of [math] into two parts [math] and [math] such that [math] is odd. A T-join in [math] for [math] is a set of hyperedges [math] such that for every T-cut [math] there is a hyperedge [math] intersecting both [math] and [math]. A directed hypergraph has for every hyperedge exactly one vertex, called the head, and several vertices, that are tails. A directed hypergraph is strongly connected if there exists at least one directed path between any two vertices of the hypergraph, where a directed path is defined to be a sequence of vertices and hyperedges for which each hyperedge has as one of its tails the vertex preceding it and as its head the vertex following it in the sequence. Orienting an undirected hypergraph means choosing a head for each hyperedge. We prove that every edge-weighted undirected hypergraph that admits a strongly connected orientation has a T-join of total weight at most 7/8 times the total weight of all the edges of the hypergraph, and sketch an improvement to 4/5. We also exhibit a series of example showing that one cannot improve the constant above to [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-28T04:13:02Z DOI: 10.1142/S1793830917500689

Authors:R. Vasanthi, K. Subramanian Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a simple and connected graph. A dominating set [math] is said to be a vertex covering transversal dominating set if it intersects every minimum vertex covering set of [math]. The vertex covering transversal domination number [math] is the minimum cardinality among all vertex covering transversal dominating sets of [math]. A vertex covering transversal dominating set of minimum cardinality [math] is called a minimum vertex covering transversal dominating set or simply a [math]-set. In this paper, we prove some general theorems on the vertex covering transversal domination number of a simple connected graph. We also provide some results about [math]-sets and try to classify those sets based on their intersection with the minimum vertex covering sets. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-28T04:13:02Z DOI: 10.1142/S1793830917500690

Authors:G. L. Chia, W. Hemakul, S. Singhun Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The square of a graph [math] is the graph obtained from [math] by adding edges joining those pairs of vertices whose distance from each other in [math] is two. If [math] is connected, then the cyclomatic number of [math] is defined as [math]. Graphs with cyclomatic number not more than [math] whose square are panconnected have been characterized, among other things, in [G. L. Chia, S. H. Ong and L. Y. Tan, On graphs whose square have strong Hamiltonian properties, Discrete Math. 309 (2009) 4608–4613, G. L. Chia, W. Hemakul and S. Singhun, Graphs with cyclomatic number two having panconnected square, Discrete Math. 311 (2011) 850–855]. Here, we show that if [math] has cyclomatic number [math] and [math] is panconnected, then [math] is one of the eight families of graphs, [math], defined in the paper. Further, we obtain necessary and sufficient conditions for three larger families of graphs (which contains [math] as special cases) whose square are panconnected. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-28T04:13:02Z DOI: 10.1142/S1793830917500677

Authors:Muhammad Imran, Shehnaz Akhter Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The topological indices are useful tools to the theoretical chemists that are provided by the graph theory. They correlate certain physicochemical properties such as boiling point, strain energy, stability, etc. of chemical compounds. For a graph [math], the double graph [math] is a graph obtained by taking two copies of graph [math] and joining each vertex in one copy with the neighbors of corresponding vertex in another copy and strong double graph SD[math] of the graph [math] is the graph obtained by taking two copies of the graph [math] and joining each vertex [math] in one copy with the closed neighborhood of the corresponding vertex in another copy. In this paper, we compute the general sum-connectivity index, general Randi[math] index, geometric–arithmetic index, general first Zagreb index, first and second multiplicative Zagreb indices for double graphs and strong double graphs and derive the exact expressions for these degree-base topological indices for double graphs and strong double graphs in terms of corresponding index of original graph [math]. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-12T03:28:08Z DOI: 10.1142/S1793830917500665

Authors:William F. Klostermeyer, Margaret-Ellen Messinger, Alejandro Angeli Ayello Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In this paper, we consider dominating sets [math] and [math] such that [math] and [math] are disjoint and there exists a perfect matching between them. Let [math] denote the cardinality of smallest such sets [math] in [math] (provided they exist, otherwise [math]). This concept was introduced in [W. F. Klostermeyer, M. E. Messinger and A. Angeli Ayello, An eternal domination problem in grids, Theory Appl. Graphs 4(1) (2017) 23pp.] in the context of studying a certain graph protection problem. We characterize the trees [math] for which [math] equals a certain graph protection parameter and for which [math], where [math] is the independence number of [math]. We also further study this parameter in graph products, e.g., by giving bounds for grid graphs, and in graphs of small independence number. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-08T02:37:59Z DOI: 10.1142/S1793830917500653

Authors:Ali Ahmad Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Graphene is an atomic scale honeycomb lattice made of the carbon atoms. Graph theory has given scientific expert an assortment of helpful apparatuses, for example, topological indices. A topological index [math] of a graph [math] is a number with the property that for each graph [math] isomorphic to [math] [math]. In this paper, we exhibit correct expressions for some topological indices for para-line graph of honeycomb networks and graphene. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-09-05T01:20:36Z DOI: 10.1142/S1793830917500641

Authors:K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner, H. C. Wauck Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Permutation sorting, one of the fundamental steps in pre-processing data for the efficient application of other algorithms, has a long history in mathematical research literature and has numerous applications. Two special-purpose sorting operations are considered in this paper: context directed swap, (cds) and context directed reversal, (cdr). These are special cases of sorting operations that were studied in prior work on permutation sorting. Moreover, cds and cdr have been postulated to model molecular sorting events that occur in the genome maintenance program of certain species of single-celled organisms called ciliates. This paper investigates mathematical aspects of these two sorting operations. The main result of this paper is a generalization of previously discovered characterizations of cds-sortability of a permutation. The combinatorial structure underlying this generalization suggests natural combinatorial two-player games. These games are the main mathematical innovation of this paper. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-25T07:18:08Z DOI: 10.1142/S179383091750063X

Authors:Blanca Isabel Niel Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. The resolutions of the different Shortest and Longest Euclidean Hamiltonian Path Problems on the vertices of simple regular [math]-Gons, by means of a geometric and arithmetic algorithm allow us to define winding indexes for Euclidean Hamiltonian cycles. New statements characterize orientation of non-necessarily regular Hamiltonian cycles on the [math]th roots of the unity embedded in the plane and deal with the existence of reflective bistarred Hamiltonian tours on vertices of coupled [math]-Gons. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-08T07:40:05Z DOI: 10.1142/S1793830917500616

Authors:Jyhmin Kuo, Hung-Lin Fu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A set of vertices of a graph whose removal leaves an acyclic graph is referred as a decycling set, or a feedback vertex set, of the graph. The minimum cardinality of a decycling set of a graph [math] is referred to as the decycling number of [math]. For [math], the generalized de Bruijn digraph [math] is defined by congruence equations as follows: [math] and [math]. In this paper, we give a systematic method to find a decycling set of [math] and give a new upper bound that improve the best known results. By counting the number of vertex-disjoint cycles with the idea of constrained necklaces, we obtain new lower bounds on the decycling number of generalized de Bruijn digraphs. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-08T07:40:05Z DOI: 10.1142/S1793830917500628

Authors:Farzad Shaveisi Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. A simple graph [math] is called [math]-bounded if for every two nonadjacent vertices [math] of [math] there exists a vertex [math] such that [math], where [math] denotes the set of neighbors of the vertex [math] in [math]. In this paper, some properties of [math]-bounded graphs are studied. It is shown that any bipartite [math]-bounded graph is a complete bipartite graph with at most two horns; in particular, any [math]-bounded tree is either a star or a two-star graph. Also, we prove that any non-end vertex of every [math]-bounded graph is contained in either a triangle or a rectangle. Among other results, it is shown that all regular [math]-bounded graphs are strongly regular graphs. Finally, we determine that how many edges can an [math]-bounded graph have' Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-08-07T03:22:01Z DOI: 10.1142/S1793830917500604

Authors:Faïçal Bouazizi, Zaineb Guetif, Sami Hidouri Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. In the present paper, we propose two new simple algorithms for computing the minimal polynomial of cos([math]) based on Galois theory. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-28T11:42:46Z DOI: 10.1142/S1793830917500598

Authors:K. Selvakumar, P. Subbulakshmi, Jafar Amjadi Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. Let [math] be a commutative ring with identity. We consider a simple graph associated with [math], denoted by [math], whose vertex set is the set of all non-trivial ideals of [math] and two distinct vertices [math] and [math] are adjacent whenever [math] or [math]. In this paper, we characterize the commutative Artinian non-local ring [math] for which [math] has genus one and crosscap one. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-19T06:43:50Z DOI: 10.1142/S1793830917500586

Authors:Tran Dan Thu Abstract: Discrete Mathematics, Algorithms and Applications, Ahead of Print. We introduce a generic identity based on the Ahlswede–Zhang (AZ) function, which can be considered as a template to establish AZ-style identities. Many AZ-style identities can be derived from the generic identity. Citation: Discrete Mathematics, Algorithms and Applications PubDate: 2017-07-17T02:56:03Z DOI: 10.1142/S1793830917500574