for Journals by Title or ISSN
for Articles by Keywords
help
  Subjects -> MATHEMATICS (Total: 1030 journals)
    - APPLIED MATHEMATICS (83 journals)
    - GEOMETRY AND TOPOLOGY (21 journals)
    - MATHEMATICS (765 journals)
    - MATHEMATICS (GENERAL) (43 journals)
    - NUMERICAL ANALYSIS (22 journals)
    - PROBABILITIES AND MATH STATISTICS (96 journals)

MATHEMATICS (765 journals)                  1 2 3 4 | Last

Showing 1 - 200 of 538 Journals sorted alphabetically
Abakós     Open Access   (Followers: 4)
Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg     Hybrid Journal   (Followers: 4)
Academic Voices : A Multidisciplinary Journal     Open Access   (Followers: 2)
Accounting Perspectives     Full-text available via subscription   (Followers: 7)
ACM Transactions on Algorithms (TALG)     Hybrid Journal   (Followers: 15)
ACM Transactions on Computational Logic (TOCL)     Hybrid Journal   (Followers: 3)
ACM Transactions on Mathematical Software (TOMS)     Hybrid Journal   (Followers: 6)
ACS Applied Materials & Interfaces     Hybrid Journal   (Followers: 38)
Acta Applicandae Mathematicae     Hybrid Journal   (Followers: 1)
Acta Mathematica     Hybrid Journal   (Followers: 12)
Acta Mathematica Hungarica     Hybrid Journal   (Followers: 2)
Acta Mathematica Scientia     Full-text available via subscription   (Followers: 5)
Acta Mathematica Sinica, English Series     Hybrid Journal   (Followers: 6)
Acta Mathematica Vietnamica     Hybrid Journal  
Acta Mathematicae Applicatae Sinica, English Series     Hybrid Journal  
Advanced Science Letters     Full-text available via subscription   (Followers: 12)
Advances in Applied Clifford Algebras     Hybrid Journal   (Followers: 4)
Advances in Calculus of Variations     Hybrid Journal   (Followers: 6)
Advances in Catalysis     Full-text available via subscription   (Followers: 5)
Advances in Complex Systems     Hybrid Journal   (Followers: 9)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 21)
Advances in Decision Sciences     Open Access   (Followers: 3)
Advances in Difference Equations     Open Access   (Followers: 3)
Advances in Fixed Point Theory     Open Access   (Followers: 6)
Advances in Geosciences (ADGEO)     Open Access   (Followers: 17)
Advances in Linear Algebra & Matrix Theory     Open Access   (Followers: 10)
Advances in Materials Science     Open Access   (Followers: 17)
Advances in Mathematical Physics     Open Access   (Followers: 7)
Advances in Mathematics     Full-text available via subscription   (Followers: 14)
Advances in Nonlinear Analysis     Open Access  
Advances in Numerical Analysis     Open Access   (Followers: 7)
Advances in Operations Research     Open Access   (Followers: 12)
Advances in Porous Media     Full-text available via subscription   (Followers: 5)
Advances in Pure and Applied Mathematics     Hybrid Journal   (Followers: 8)
Advances in Pure Mathematics     Open Access   (Followers: 9)
Advances in Science and Research (ASR)     Open Access   (Followers: 6)
Aequationes Mathematicae     Hybrid Journal   (Followers: 2)
African Journal of Educational Studies in Mathematics and Sciences     Full-text available via subscription   (Followers: 7)
African Journal of Mathematics and Computer Science Research     Open Access   (Followers: 5)
Afrika Matematika     Hybrid Journal   (Followers: 1)
Air, Soil & Water Research     Open Access   (Followers: 14)
AKSIOMA Journal of Mathematics Education     Open Access   (Followers: 2)
Al-Jabar : Jurnal Pendidikan Matematika     Open Access   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 7)
Algebra Colloquium     Hybrid Journal   (Followers: 4)
Algebra Universalis     Hybrid Journal   (Followers: 2)
Algorithmic Operations Research     Open Access   (Followers: 5)
Algorithms     Open Access   (Followers: 11)
Algorithms Research     Open Access   (Followers: 1)
American Journal of Computational and Applied Mathematics     Open Access   (Followers: 8)
American Journal of Mathematical Analysis     Open Access  
American Journal of Mathematics     Full-text available via subscription   (Followers: 6)
American Journal of Operations Research     Open Access   (Followers: 6)
An International Journal of Optimization and Control: Theories & Applications     Open Access   (Followers: 11)
Anadol University Journal of Science and Technology B : Theoritical Sciences     Open Access  
Analele Universitatii Ovidius Constanta - Seria Matematica     Open Access  
Analysis and Applications     Hybrid Journal   (Followers: 1)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 6)
Analysis Mathematica     Full-text available via subscription  
Analysis. International mathematical journal of analysis and its applications     Hybrid Journal   (Followers: 3)
Annales Mathematicae Silesianae     Open Access   (Followers: 2)
Annales mathématiques du Québec     Hybrid Journal   (Followers: 4)
Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica     Open Access   (Followers: 1)
Annales Universitatis Paedagogicae Cracoviensis. Studia Mathematica     Open Access  
Annali di Matematica Pura ed Applicata     Hybrid Journal   (Followers: 1)
Annals of Combinatorics     Hybrid Journal   (Followers: 4)
Annals of Data Science     Hybrid Journal   (Followers: 13)
Annals of Discrete Mathematics     Full-text available via subscription   (Followers: 7)
Annals of Mathematics     Full-text available via subscription   (Followers: 2)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 12)
Annals of PDE     Hybrid Journal  
Annals of Pure and Applied Logic     Open Access   (Followers: 4)
Annals of the Alexandru Ioan Cuza University - Mathematics     Open Access  
Annals of the Institute of Statistical Mathematics     Hybrid Journal   (Followers: 1)
Annals of West University of Timisoara - Mathematics     Open Access  
Annals of West University of Timisoara - Mathematics and Computer Science     Open Access   (Followers: 1)
Annuaire du Collège de France     Open Access   (Followers: 6)
ANZIAM Journal     Open Access   (Followers: 1)
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2)
Applications of Mathematics     Hybrid Journal   (Followers: 3)
Applied Categorical Structures     Hybrid Journal   (Followers: 4)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 14)
Applied Mathematics     Open Access   (Followers: 4)
Applied Mathematics     Open Access   (Followers: 8)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 10)
Applied Mathematics - A Journal of Chinese Universities     Hybrid Journal   (Followers: 1)
Applied Mathematics and Nonlinear Sciences     Open Access  
Applied Mathematics Letters     Full-text available via subscription   (Followers: 3)
Applied Mathematics Research eXpress     Hybrid Journal   (Followers: 1)
Applied Network Science     Open Access   (Followers: 3)
Applied Numerical Mathematics     Hybrid Journal   (Followers: 5)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 6)
Arab Journal of Mathematical Sciences     Open Access   (Followers: 4)
Arabian Journal of Mathematics     Open Access   (Followers: 2)
Archive for Mathematical Logic     Hybrid Journal   (Followers: 3)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 6)
Archive of Numerical Software     Open Access  
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 6)
Arkiv för Matematik     Hybrid Journal   (Followers: 1)
Armenian Journal of Mathematics     Open Access   (Followers: 1)
Arnold Mathematical Journal     Hybrid Journal   (Followers: 1)
Artificial Satellites     Open Access   (Followers: 25)
Asia-Pacific Journal of Operational Research     Hybrid Journal   (Followers: 3)
Asian Journal of Algebra     Open Access   (Followers: 1)
Asian-European Journal of Mathematics     Hybrid Journal   (Followers: 3)
Australian Mathematics Teacher, The     Full-text available via subscription   (Followers: 7)
Australian Primary Mathematics Classroom     Full-text available via subscription   (Followers: 5)
Australian Senior Mathematics Journal     Full-text available via subscription   (Followers: 2)
Automatic Documentation and Mathematical Linguistics     Hybrid Journal   (Followers: 5)
Axioms     Open Access   (Followers: 1)
Baltic International Yearbook of Cognition, Logic and Communication     Open Access   (Followers: 1)
Basin Research     Hybrid Journal   (Followers: 5)
BIBECHANA     Open Access   (Followers: 2)
Biomath     Open Access  
BIT Numerical Mathematics     Hybrid Journal   (Followers: 1)
Boletim Cearense de Educação e História da Matemática     Open Access  
Boletim de Educação Matemática     Open Access  
Boletín de la Sociedad Matemática Mexicana     Hybrid Journal  
Bollettino dell'Unione Matematica Italiana     Full-text available via subscription   (Followers: 2)
British Journal of Mathematical and Statistical Psychology     Full-text available via subscription   (Followers: 20)
Bruno Pini Mathematical Analysis Seminar     Open Access  
Buletinul Academiei de Stiinte a Republicii Moldova. Matematica     Open Access   (Followers: 13)
Bulletin des Sciences Mathamatiques     Full-text available via subscription   (Followers: 4)
Bulletin of Dnipropetrovsk University. Series : Communications in Mathematical Modeling and Differential Equations Theory     Open Access   (Followers: 3)
Bulletin of Mathematical Sciences     Open Access   (Followers: 1)
Bulletin of Symbolic Logic     Full-text available via subscription   (Followers: 2)
Bulletin of the Australian Mathematical Society     Full-text available via subscription   (Followers: 1)
Bulletin of the Brazilian Mathematical Society, New Series     Hybrid Journal  
Bulletin of the Iranian Mathematical Society     Hybrid Journal  
Bulletin of the London Mathematical Society     Hybrid Journal   (Followers: 3)
Bulletin of the Malaysian Mathematical Sciences Society     Hybrid Journal  
Calculus of Variations and Partial Differential Equations     Hybrid Journal  
Canadian Journal of Mathematics / Journal canadien de mathématiques     Hybrid Journal  
Canadian Journal of Science, Mathematics and Technology Education     Hybrid Journal   (Followers: 20)
Canadian Mathematical Bulletin     Hybrid Journal  
Carpathian Mathematical Publications     Open Access   (Followers: 1)
Catalysis in Industry     Hybrid Journal   (Followers: 1)
CEAS Space Journal     Hybrid Journal   (Followers: 2)
CHANCE     Hybrid Journal   (Followers: 5)
Chaos, Solitons & Fractals     Hybrid Journal   (Followers: 3)
Chaos, Solitons & Fractals : X     Open Access  
ChemSusChem     Hybrid Journal   (Followers: 8)
Chinese Annals of Mathematics, Series B     Hybrid Journal  
Chinese Journal of Catalysis     Full-text available via subscription   (Followers: 2)
Chinese Journal of Mathematics     Open Access  
Clean Air Journal     Full-text available via subscription   (Followers: 1)
Cogent Mathematics     Open Access   (Followers: 2)
Cognitive Computation     Hybrid Journal   (Followers: 3)
Collectanea Mathematica     Hybrid Journal  
COMBINATORICA     Hybrid Journal  
Combinatorics, Probability and Computing     Hybrid Journal   (Followers: 4)
Combustion Theory and Modelling     Hybrid Journal   (Followers: 15)
Commentarii Mathematici Helvetici     Hybrid Journal  
Communications in Advanced Mathematical Sciences     Open Access  
Communications in Combinatorics and Optimization     Open Access  
Communications in Contemporary Mathematics     Hybrid Journal  
Communications in Mathematical Physics     Hybrid Journal   (Followers: 4)
Communications On Pure & Applied Mathematics     Hybrid Journal   (Followers: 3)
Complex Analysis and its Synergies     Open Access   (Followers: 3)
Complex Variables and Elliptic Equations: An International Journal     Hybrid Journal  
Composite Materials Series     Full-text available via subscription   (Followers: 9)
Compositio Mathematica     Full-text available via subscription  
Comptes Rendus Mathematique     Full-text available via subscription  
Computational and Applied Mathematics     Hybrid Journal   (Followers: 4)
Computational and Mathematical Methods in Medicine     Open Access   (Followers: 2)
Computational and Mathematical Organization Theory     Hybrid Journal   (Followers: 2)
Computational Complexity     Hybrid Journal   (Followers: 4)
Computational Mathematics and Modeling     Hybrid Journal   (Followers: 10)
Computational Mechanics     Hybrid Journal   (Followers: 5)
Computational Methods and Function Theory     Hybrid Journal  
Computational Optimization and Applications     Hybrid Journal   (Followers: 8)
Computers & Mathematics with Applications     Full-text available via subscription   (Followers: 10)
Concrete Operators     Open Access   (Followers: 5)
Confluentes Mathematici     Hybrid Journal  
Contributions to Game Theory and Management     Open Access  
COSMOS     Hybrid Journal  
Cryptography and Communications     Hybrid Journal   (Followers: 13)
Cuadernos de Investigación y Formación en Educación Matemática     Open Access  
Cubo. A Mathematical Journal     Open Access  
Current Research in Biostatistics     Open Access   (Followers: 8)
Czechoslovak Mathematical Journal     Hybrid Journal   (Followers: 1)
Demographic Research     Open Access   (Followers: 15)
Demonstratio Mathematica     Open Access  
Dependence Modeling     Open Access  
Design Journal : An International Journal for All Aspects of Design     Hybrid Journal   (Followers: 31)
Developments in Clay Science     Full-text available via subscription   (Followers: 1)
Developments in Mineral Processing     Full-text available via subscription   (Followers: 3)
Dhaka University Journal of Science     Open Access  
Differential Equations and Dynamical Systems     Hybrid Journal   (Followers: 4)
Differentsial'nye Uravneniya     Open Access  
Digital Experiences in Mathematics Education     Hybrid Journal  
Discrete Mathematics     Hybrid Journal   (Followers: 8)
Discrete Mathematics & Theoretical Computer Science     Open Access  
Discrete Mathematics, Algorithms and Applications     Hybrid Journal   (Followers: 2)
Discussiones Mathematicae - General Algebra and Applications     Open Access  
Discussiones Mathematicae Graph Theory     Open Access   (Followers: 2)
Diskretnaya Matematika     Full-text available via subscription  
Dnipropetrovsk University Mathematics Bulletin     Open Access  
Doklady Akademii Nauk     Open Access  
Doklady Mathematics     Hybrid Journal  

        1 2 3 4 | Last

Similar Journals
Journal Cover
Discrete Mathematics & Theoretical Computer Science
Journal Prestige (SJR): 0.593
Citation Impact (citeScore): 1
Number of Followers: 0  

  This is an Open Access Journal Open Access journal
ISSN (Online) 1365-8050
Published by DMTCS Homepage  [1 journal]
  • On a Class of Graphs with Large Total Domination Number

    • Abstract: Let $\gamma(G)$ and $\gamma_t(G)$ denote the domination number and the totaldomination number, respectively, of a graph $G$ with no isolated vertices. Itis well-known that $\gamma_t(G) \leq 2\gamma(G)$. We provide a characterizationof a large family of graphs (including chordal graphs) satisfying $\gamma_t(G)=2\gamma(G)$, strictly generalizing the results of Henning (2001) and Hou et al.(2010), and partially answering an open question of Henning (2009).
      PubDate: Mon, 04 Jun 2018 10:37:11 +020
       
  • Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs

    • Abstract: A path in an edge-colored graph $G$ is rainbow if no two edges of it arecolored the same. The graph $G$ is rainbow-connected if there is a rainbow pathbetween every pair of vertices. If there is a rainbow shortest path betweenevery pair of vertices, the graph $G$ is strongly rainbow-connected. Theminimum number of colors needed to make $G$ rainbow-connected is known as therainbow connection number of $G$, and is denoted by $\text{rc}(G)$. Similarly,the minimum number of colors needed to make $G$ strongly rainbow-connected isknown as the strong rainbow connection number of $G$, and is denoted by$\text{src}(G)$. We prove that for every $k \geq 3$, deciding whether$\text{src}(G) \leq k$ is NP-complete for split graphs, which form a subclassof chordal graphs. Furthermore, there exists no polynomial-time algorithm forapproximating the strong rainbow connection number of an $n$-vertex split graphwith a factor of $n^{1/2-\epsilon}$ for any $\epsilon> 0$ unless P = NP. Wethen turn our attention to block graphs, which also form a subclass of chordalgraphs. We determine the strong rainbow connection number of block graphs, andshow it can be computed in linear time. Finally, we provide a polynomial-timecharacterization of bridgeless block graphs with rainbow connection number atmost 4.
      PubDate: Mon, 04 Jun 2018 10:30:35 +020
       
  • On neighbour sum-distinguishing $\{0,1\}$-edge-weightings of bipartite
           graphs

    • Abstract: Let $S$ be a set of integers. A graph G is said to have the S-property ifthere exists an S-edge-weighting $w : E(G) \rightarrow S$ such that any twoadjacent vertices have different sums of incident edge-weights. In this paperwe characterise all bridgeless bipartite graphs and all trees without the$\{0,1\}$-property. In particular this problem belongs to P for these graphswhile it is NP-complete for all graphs.
      PubDate: Mon, 04 Jun 2018 10:27:12 +020
       
  • Permutation complexity of images of Sturmian words by marked morphisms

    • Abstract: We show that the permutation complexity of the image of a Sturmian word by abinary marked morphism is $n+k$ for some constant $k$ and all lengths $n$sufficiently large.
      PubDate: Mon, 04 Jun 2018 10:22:33 +020
       
  • Forbidden subgraphs for constant domination number

    • Abstract: In this paper, we characterize the sets $\mathcal{H}$ of connected graphssuch that there exists a constant $c=c(\mathcal{H})$ satisfying $\gamma (G)\leqc$ for every connected $\mathcal{H}$-free graph $G$, where $\gamma (G)$ is thedomination number of $G$.
      PubDate: Mon, 04 Jun 2018 10:19:22 +020
       
  • Proof of a local antimagic conjecture

    • Abstract: An antimagic labelling of a graph $G$ is a bijection$f:E(G)\to\{1,\ldots,E(G)\}$ such that the sums $S_v=\sum_{e\ni v}f(e)$distinguish all vertices. A well-known conjecture of Hartsfield and Ringel(1994) is that every connected graph other than $K_2$ admits an antimagiclabelling. Recently, two sets of authors (Arumugam, Premalatha, Ba\v{c}a \&Semani\v{c}ov\'a-Fe\v{n}ov\v{c}\'ikov\'a (2017), and Bensmail, Senhaji \&Lyngsie (2017)) independently introduced the weaker notion of a local antimagiclabelling, where only adjacent vertices must be distinguished. Both sets ofauthors conjectured that any connected graph other than $K_2$ admits a localantimagic labelling. We prove this latter conjecture using the probabilisticmethod. Thus the parameter of local antimagic chromatic number, introduced byArumugam et al., is well-defined for every connected graph other than $K_2$ .
      PubDate: Mon, 04 Jun 2018 10:15:49 +020
       
  • Weakly threshold graphs

    • Abstract: We define a weakly threshold sequence to be a degree sequence$d=(d_1,\dots,d_n)$ of a graph having the property that $\sum_{i \leq k} d_i\geq k(k-1)+\sum_{i> k} \min\{k,d_i\} - 1$ for all positive $k \leq\max\{i:d_i \geq i-1\}$. The weakly threshold graphs are the realizations ofthe weakly threshold sequences. The weakly threshold graphs properly includethe threshold graphs and satisfy pleasing extensions of many properties ofthreshold graphs. We demonstrate a majorization property of weakly thresholdsequences and an iterative construction algorithm for weakly threshold graphs,as well as a forbidden induced subgraph characterization. We conclude byexactly enumerating weakly threshold sequences and graphs.
      PubDate: Mon, 04 Jun 2018 10:08:17 +020
       
  • Rowmotion and generalized toggle groups

    • Abstract: We generalize the notion of the toggle group, as defined in [P. Cameron-D.Fon-der-Flaass '95] and further explored in [J. Striker-N. Williams '12], fromthe set of order ideals of a poset to any family of subsets of a finite set. Weprove structure theorems for certain finite generalized toggle groups, similarto the theorem of Cameron and Fon-der-Flaass in the case of order ideals. Weapply these theorems and find other results on generalized toggle groups in thefollowing settings: chains, antichains, and interval-closed sets of a poset;independent sets, vertex covers, acyclic subgraphs, and spanning subgraphs of agraph; matroids and convex geometries. We generalize rowmotion, an actionstudied on order ideals in [P. Cameron-D. Fon-der-Flaass '95] and [J.Striker-N. Williams '12], to a map we call cover-closure on closed sets of aclosure operator. We show that cover-closure is bijective if and only if theset of closed sets is isomorphic to the set of order ideals of a poset, whichimplies rowmotion is the only bijective cover-closure map.
      PubDate: Fri, 25 May 2018 17:04:47 +020
       
  • Annular and pants thrackles

    • Abstract: A thrackle is a drawing of a graph in which each pair of edges meetsprecisely once. Conway's Thrackle Conjecture asserts that a thrackle drawing ofa graph on the plane cannot have more edges than vertices. We prove theConjecture for thrackle drawings all of whose vertices lie on the boundaries of$d \le 3$ connected domains in the complement of the drawing. We also give adetailed description of thrackle drawings corresponding to the cases when $d=2$(annular thrackles) and $d=3$ (pants thrackles).
      PubDate: Fri, 25 May 2018 16:59:37 +020
       
  • A Linear Kernel for Planar Total Dominating Set

    • Abstract: A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ suchthat every vertex in $V$ is adjacent to some vertex in $D$. Finding a totaldominating set of minimum size is NP-hard on planar graphs and W[2]-complete ongeneral graphs when parameterized by the solution size. By the meta-theorem ofBodlaender et al. [J. ACM, 2016], there exists a linear kernel for TotalDominating Set on graphs of bounded genus. Nevertheless, it is not clear howsuch a kernel can be effectively constructed, and how to obtain explicitreduction rules with reasonably small constants. Following the approach ofAlber et al. [J. ACM, 2004], we provide an explicit kernel for Total DominatingSet on planar graphs with at most $410k$ vertices, where $k$ is the size of thesolution. This result complements several known constructive linear kernels onplanar graphs for other domination problems such as Dominating Set, EdgeDominating Set, Efficient Dominating Set, Connected Dominating Set, or Red-BlueDominating Set.
      PubDate: Wed, 16 May 2018 16:19:58 +020
       
  • On interval number in cycle convexity

    • Abstract: Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by $in_{cc} (G)$, is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S.In this work, first we provide bounds on $in_{cc} (G)$ and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether $in_{cc} (G)$ ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtainthat $in_{cc} (G)$ cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = N P ).On the positive side, we present polynomial-time algorithms to compute $in_{cc} (G)$ for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q − 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G.Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems.
      PubDate: Mon, 07 May 2018 10:26:53 +020
       
  • A Central Limit Theorem for Vincular Permutation Patterns

    • Abstract: We study the number of occurrences of any fixed vincular permutation pattern.We show that this statistics on uniform random permutations is asymptoticallynormal and describe the speed of convergence. To prove this central limittheorem, we use the method of dependency graphs. The main difficulty is then toestimate the variance of our statistics. We need a lower bound on the variance,for which we introduce a recursive technique based on the law of totalvariance.
      PubDate: Mon, 26 Mar 2018 11:21:09 +020
       
  • Non-adaptive Group Testing on Graphs

    • Abstract: Grebinski and Kucherov (1998) and Alon et al. (2004-2005) study the problemof learning a hidden graph for some especial cases, such as hamiltonian cycle,cliques, stars, and matchings. This problem is motivated by problems inchemical reactions, molecular biology and genome sequencing. In this paper, we present a generalization of this problem. Precisely, weconsider a graph G and a subgraph H of G and we assume that G contains exactlyone defective subgraph isomorphic to H. The goal is to find the defectivesubgraph by testing whether an induced subgraph contains an edge of thedefective subgraph, with the minimum number of tests. We present an upper boundfor the number of tests to find the defective subgraph by using the symmetricand high probability variation of Lov\'asz Local Lemma.
      PubDate: Mon, 26 Mar 2018 11:13:44 +020
       
  • Protected node profile of Tries

    • Abstract: In a rooted tree, protected nodes are neither leaves nor parents of any leaves. They have some practical motivations, e.g., in organizational schemes, security models and social-network models. Protected node profile measures the number of protected nodes with the same distance from the root in rooted trees. For no rooted tree, protected node profile has been investigated so far. Here, we present the asymptotic expectations, variances, covariance and limiting bivariate distribution of protected node profile and non-protected internal node profile in random tries, an important data structure on words in computer science. Also we investigate the fraction of these expectations asymptotically. These results are derived by the methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization and depoissonization, saddle point method and singularity analysis.
      PubDate: Mon, 26 Mar 2018 11:04:02 +020
       
  • Asymptotic results on Klazar set partition avoidance

    • Abstract: We establish asymptotic bounds for the number of partitions of $[n]$ avoidinga given partition in Klazar's sense, obtaining the correct answer to within anexponential for the block case. This technique also enables us to establish ageneral lower bound. Additionally, we consider a graph theoretic restatement ofpartition avoidance problems, and propose several conjectures.
      PubDate: Mon, 19 Mar 2018 11:02:07 +010
       
  • On subtrees of the representation tree in rational base numeration systems
           

    • Abstract: Every rational number p/q defines a rational base numeration system in whichevery integer has a unique finite representation, up to leading zeroes. Thiswork is a contribution to the study of the set of the representations ofintegers. This prefix-closed subset of the free monoid is naturally representedas a highly non-regular tree. Its nodes are the integers, its edges bear labelstaken in {0,1,...,p-1}, and its subtrees are all distinct. We associate with each subtree (or with its root n) three infinite words. Thebottom word of n is the lexicographically smallest word that is the label of abranch of the subtree. The top word of n is defined similarly. The span-word ofn is the digitwise difference between the latter and the former. First, we show that the set of all the span-words is accepted by an infiniteautomaton whose underlying graph is essentially the same as the tree itself.Second, we study the function that computes for all n the bottom wordassociated with n+1 from the one associated with n, and show that it isrealised by an infinite sequential transducer whose underlying graph is onceagain essentially the same as the tree itself. An infinite word may be interpreted as an expansion in base p/q after theradix point, hence evaluated to a real number. If T is a subtree whose root isn, then the evaluations of the labels of the branches of T form an interval of$\mathbb{R}$. The length of this interval is called the span of n and is equalto the evaluation of the span-word of n. The set of all spans is then a subsetof R and we use the preceding construction to study its topological closure. Weshow that it is an interval when p is greater than or equal to 2q-1, and aCantor set of measure zero otherwise.
      PubDate: Mon, 05 Mar 2018 09:53:22 +010
       
  • Finding Hamilton cycles in random intersection graphs

    • Abstract: The construction of the random intersection graph model is based on a randomfamily of sets. Such structures, which are derived from intersections of sets,appear in a natural manner in many applications. In this article we study theproblem of finding a Hamilton cycle in a random intersection graph. To this endwe analyse a classical algorithm for finding Hamilton cycles in random graphs(algorithm HAM) and study its efficiency on graphs from a family of randomintersection graphs (denoted here by G(n,m,p)). We prove that the thresholdfunction for the property of HAM constructing a Hamilton cycle in G(n,m,p) isthe same as the threshold function for the minimum degree at least two. Untilnow, known algorithms for finding Hamilton cycles in G(n,m,p) were designed towork in very small ranges of parameters and, unlike HAM, used the structure ofthe family of random sets.
      PubDate: Mon, 05 Mar 2018 09:48:23 +010
       
  • Growing and Destroying Catalan-Stanley Trees

    • Abstract: Stanley lists the class of Dyck paths where all returns to the axis are ofodd length as one of the many objects enumerated by (shifted) Catalan numbers.By the standard bijection in this context, these special Dyck paths correspondto a class of rooted plane trees, so-called Catalan-Stanley trees. This paper investigates a deterministic growth procedure for these trees bywhich any Catalan-Stanley tree can be grown from the tree of size one aftersome number of rounds; a parameter that will be referred to as the age of thetree. Asymptotic analyses are carried out for the age of a randomCatalan-Stanley tree of given size as well as for the "speed" of the growthprocess by comparing the size of a given tree to the size of its ancestors.
      PubDate: Wed, 28 Feb 2018 16:37:21 +010
       
  • On consecutive pattern-avoiding permutations of length 4, 5 and beyond

    • Abstract: We review and extend what is known about the generating functions forconsecutive pattern-avoiding permutations of length 4, 5 and beyond, and theirasymptotic behaviour. There are respectively, seven length-4 and twenty-fivelength-5 consecutive-Wilf classes. D-finite differential equations are knownfor the reciprocal of the exponential generating functions for four of thelength-4 and eight of the length-5 classes. We give the solutions of some ofthese ODEs. An unsolved functional equation is known for one more class oflength-4, length-5 and beyond. We give the solution of this functionalequation, and use it to show that the solution is not D-finite. For threefurther length-5 c-Wilf classes we give recurrences for two and adifferential-functional equation for a third. For a fourth class we find a newalgebraic solution. We give a polynomial-time algorithm to generate thecoefficients of the generating functions which is faster than existingalgorithms, and use this to (a) calculate the asymptotics for all classes oflength 4 and length 5 to significantly greater precision than previously, and(b) use these extended series to search, unsuccessfully, for D-finite solutionsfor the unsolved classes, leading us to conjecture that the solutions are notD-finite. We have also searched, unsuccessfully, for differentially algebraicsolutions.
      PubDate: Mon, 26 Feb 2018 10:53:53 +010
       
  • Equivalence classes of mesh patterns with a dominating pattern

    • Abstract: Two mesh patterns are coincident if they are avoided by the same set ofpermutations, and are Wilf-equivalent if they have the same number of avoidersof each length. We provide sufficient conditions for coincidence of meshpatterns, when only permutations also avoiding a longer classical pattern areconsidered. Using these conditions we completely classify coincidences betweenfamilies containing a mesh pattern of length 2 and a classical pattern oflength 3. Furthermore, we completely Wilf-classify mesh patterns of length 2inside the class of 231-avoiding permutations.
      PubDate: Fri, 09 Feb 2018 10:58:50 +010
       
  • Improving bounds on packing densities of 4-point permutations

    • Abstract: We consolidate what is currently known about packing densities of 4-pointpermutations and in the process improve the lower bounds for the packingdensities of 1324 and 1342. We also provide rigorous upper bounds for thepacking densities of 1324, 1342, and 2413. All our bounds are within $10^{-4}$of the true packing densities. Together with the known bounds, this gives us afairly complete picture of all 4-point packing densities. We also provide newupper bounds for several small permutations of length at least five. Our maintool for the upper bounds is the framework of flag algebras introduced byRazborov in 2007.
      PubDate: Tue, 06 Feb 2018 17:39:16 +010
       
  • A Study of $k$-dipath Colourings of Oriented Graphs

    • Abstract: We examine $t$-colourings of oriented graphs in which, for a fixed integer $k\geq 1$, vertices joined by a directed path of length at most $k$ must beassigned different colours. A homomorphism model that extends the ideas ofSherk for the case $k=2$ is described. Dichotomy theorems for the complexity ofthe problem of deciding, for fixed $k$ and $t$, whether there exists such a$t$-colouring are proved.
      PubDate: Thu, 01 Feb 2018 14:42:05 +010
       
  • Weak embeddings of posets to the Boolean lattice

    • Abstract: The goal of this paper is to prove that several variants of deciding whethera poset can be (weakly) embedded into a small Boolean lattice, or to a fewconsecutive levels of a Boolean lattice, are NP-complete, answering a questionof Griggs and of Patkos. As an equivalent reformulation of one of theseproblems, we also derive that it is NP-complete to decide whether a given graphcan be embedded to the two middle levels of some hypercube.
      PubDate: Wed, 24 Jan 2018 14:06:55 +010
       
  • A bijection between the set of nesting-similarity classes and L & P
           matchings

    • Abstract: Matchings are frequently used to model RNA secondary structures; however, notall matchings can be realized as RNA motifs. One class of matchings, called theL $\&$ P matchings, is the most restrictive model for RNA secondary structuresin the Largest Hairpin Family (LHF). The L $\&$ P matchings were enumerated in$2015$ by Jefferson, and they are equinumerous with the set ofnesting-similarity classes of matchings, enumerated by Klazar. We provide abijection between these two sets. This bijection preserves noncrossingmatchings, and preserves the sequence obtained reading left to right of whetheran edge begins or ends at that vertex.
      PubDate: Mon, 22 Jan 2018 08:55:56 +010
       
  • Hitting minors, subdivisions, and immersions in tournaments

    • Abstract: The Erd\H{o}s-P\'osa property relates parameters of covering and packing ofcombinatorial structures and has been mostly studied in the setting ofundirected graphs. In this note, we use results of Chudnovsky, Fradkin, Kim,and Seymour to show that, for every directed graph $H$ (resp.strongly-connected directed graph $H$), the class of directed graphs thatcontain $H$ as a strong minor (resp. butterfly minor, topological minor) hasthe vertex-Erd\H{o}s-P\'osa property in the class of tournaments. We also provethat if $H$ is a strongly-connected directed graph, the class of directedgraphs containing $H$ as an immersion has the edge-Erd\H{o}s-P\'osa property inthe class of tournaments.
      PubDate: Wed, 17 Jan 2018 09:38:58 +010
       
  • A Variation on Chip-Firing: the diffusion game

    • Abstract: We introduce a natural variant of the parallel chip-firing game, called thediffusion game. Chips are initially assigned to vertices of a graph. At everystep, all vertices simultaneously send one chip to each neighbour with fewerchips. As the dynamics of the parallel chip-firing game occur on a finite setthe process is inherently periodic. However the diffusion game is not obviouslyperiodic: even if $2 E(G) $ chips are assigned to vertices of graph G, theremay exist time steps where some vertices have a negative number of chips. Weinvestigate the process, prove periodicity for a number of graph classes, andpose some questions for future research.
      PubDate: Wed, 17 Jan 2018 09:30:10 +010
       
  • Three matching intersection property for matching covered graphs

    • Abstract: In connection with Fulkerson's conjecture on cycle covers, Fan and Raspaudproposed a weaker conjecture: For every bridgeless cubic graph $G$, there arethree perfect matchings $M_1$, $M_2$, and $M_3$ such that $M_1\cap M_2 \capM_3=\emptyset$. We call the property specified in this conjecture the threematching intersection property (and 3PM property for short). We study thisproperty on matching covered graphs. The main results are a necessary andsufficient condition and its applications to characterization of specialgraphs, such as the Halin graphs and 4-regular graphs.
      PubDate: Mon, 15 Jan 2018 11:43:15 +010
       
  • On Minimum Maximal Distance-k Matchings

    • Abstract: We study the computational complexity of several problems connected withfinding a maximal distance-$k$ matching of minimum cardinality or minimumweight in a given graph. We introduce the class of $k$-equimatchable graphswhich is an edge analogue of $k$-equipackable graphs. We prove that therecognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k \ge2$. We provide a simple characterization for the class of strongly chordalgraphs with equal $k$-packing and $k$-domination numbers. We also prove thatfor any fixed integer $\ell \ge 1$ the problem of finding a minimum weightmaximal distance-$2\ell$ matching and the problem of finding a minimum weight$(2 \ell - 1)$-independent dominating set cannot be approximated in polynomialtime in chordal graphs within a factor of $\delta \ln V(G) $ unless$\mathrm{P} = \mathrm{NP}$, where $\delta$ is a fixed constant (therebyimproving the NP-hardness result of Chang for the independent domination case).Finally, we show the NP-hardness of the minimum maximal induced matching andindependent dominating set problems in large-girth planar graphs.
      PubDate: Thu, 11 Jan 2018 14:10:17 +010
       
  • Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations
           of Holes-Part II

    • Abstract: Given a tree and a set P of non-trivial simple paths on it, VPT(P) is the VPTgraph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is theEPT graph (i.e. the edge intersection graph) of P. These graphs have beenextensively studied in the literature. Given two (edge) intersecting paths in agraph, their split vertices is the set of vertices having degree at least 3 intheir union. A pair of (edge) intersecting paths is termed non-splitting ifthey do not have split vertices (namely if their union is a path). We definethe graph ENPT(P) of edge intersecting non-splitting paths of a tree, termedthe ENPT graph, as the graph having a vertex for each path in P, and an edgebetween every pair of vertices representing two paths that are bothedge-intersecting and non-splitting. A graph G is an ENPT graph if there is atree T and a set of paths P of T such that G=ENPT(P), and we say that isa representation of G. Our goal is to characterize the representation of chordless ENPT cycles(holes). To achieve this goal, we first assume that the EPT graph induced bythe vertices of an ENPT hole is given. In [2] we introduce three assumptions(P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. In the same study, wedefine two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterizethe representations of ENPT holes that satisfy (P1), (P2), (P3). In this work, we continue our work by relaxing these three assumptions one byone. We characterize the representations of ENPT holes satisfying (P3) byproviding a polynomial-time algorithm to solve P3-HamiltonianPairRec. We alsoshow that there does not exist a polynomial-time algorithm to solveHamiltonianPairRec, unless P=NP.
      PubDate: Thu, 11 Jan 2018 13:36:58 +010
       
  • Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$

    • Abstract: We study the following problem: Given $k$ paths that share the same vertex set, is there a simultaneous geometric embedding of these paths such that each individual drawing is monotone in some direction' We prove that for any dimension $d\geq 2$, there is a set of $d + 1$ paths that does not admit a monotone simultaneous geometric embedding.
      PubDate: Fri, 05 Jan 2018 11:41:38 +010
       
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
 
Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs
Your IP address: 18.208.159.25
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-