Discrete Mathematics & Theoretical Computer Science - Latest Publications Latest papers https://dmtcs.episciences.org/img/episciences_sign_50x50.png episciences.org https://dmtcs.episciences.org Tue, 04 Oct 2022 07:44:17 +0000 episciences.org https://dmtcs.episciences.org Discrete Mathematics & Theoretical Computer Science Discrete Mathematics & Theoretical Computer Science On the Boolean dimension of a graph and other related parameters Fri, 23 Sep 2022 09:22:20 +0000 https://doi.org/10.46298/dmtcs.7437 https://doi.org/10.46298/dmtcs.7437 Pouzet, Maurice Si Kaddour, Hamza Thatte, Bhalchandra, Pouzet, Maurice Si Kaddour, Hamza Thatte, Bhalchandra, 0 Induced betweenness in order-theoretic trees Sat, 17 Sep 2022 14:51:24 +0000 https://doi.org/10.46298/dmtcs.7288 https://doi.org/10.46298/dmtcs.7288 Courcelle, Bruno Courcelle, Bruno 0 On the monophonic rank of a graph Thu, 15 Sep 2022 14:27:11 +0000 https://doi.org/10.46298/dmtcs.6835 https://doi.org/10.46298/dmtcs.6835 Dourado, Mitre C. Ponciano, Vitor S. da Silva, Rômulo L. O. Dourado, Mitre C. Ponciano, Vitor S. da Silva, Rômulo L. O. 0 On the domination number of $t$-constrained de Bruijn graphs Mon, 22 Aug 2022 10:02:18 +0000 https://doi.org/10.46298/dmtcs.8879 https://doi.org/10.46298/dmtcs.8879 Calamoneri, Tiziana Monti, Angelo Sinaimeri, Blerina Calamoneri, Tiziana Monti, Angelo Sinaimeri, Blerina 0 Further results on Hendry's Conjecture Mon, 22 Aug 2022 09:57:22 +0000 https://doi.org/10.46298/dmtcs.6700 https://doi.org/10.46298/dmtcs.6700 Lafond, Manuel Seamone, Ben Sherkati, Rezvan Lafond, Manuel Seamone, Ben Sherkati, Rezvan 0 Tuza's Conjecture for Threshold Graphs Sun, 14 Aug 2022 19:17:06 +0000 https://doi.org/10.46298/dmtcs.7660 https://doi.org/10.46298/dmtcs.7660 Bonamy, Marthe Bożyk, Łukasz Grzesik, Andrzej Hatzel, Meike Masařík, Tomáš Novotná, Jana Okrasa, Karolina Bonamy, Marthe Bożyk, Łukasz Grzesik, Andrzej Hatzel, Meike Masařík, Tomáš Novotná, Jana Okrasa, Karolina 0 Positional Marked Patterns in Permutations Mon, 08 Aug 2022 16:03:27 +0000 https://doi.org/10.46298/dmtcs.7171 https://doi.org/10.46298/dmtcs.7171 Thamrongpairoj, Sittipong Remmel, Jeffrey B. Thamrongpairoj, Sittipong Remmel, Jeffrey B. 0 Automatic sequences: from rational bases to trees Tue, 19 Jul 2022 12:30:07 +0000 https://doi.org/10.46298/dmtcs.8455 https://doi.org/10.46298/dmtcs.8455 Rigo, Michel Stipulanti, Manon Rigo, Michel Stipulanti, Manon 0 Asymptotically sharpening the $s$-Hamiltonian index bound Mon, 13 Jun 2022 13:34:01 +0000 https://doi.org/10.46298/dmtcs.8484 https://doi.org/10.46298/dmtcs.8484 Song, Sulin Lei, Lan Shao, Yehong Lai, Hong-Jian Song, Sulin Lei, Lan Shao, Yehong Lai, Hong-Jian 0 Maker-Breaker total domination game on cubic graphs Thu, 02 Jun 2022 08:36:32 +0000 https://doi.org/10.46298/dmtcs.8529 https://doi.org/10.46298/dmtcs.8529 Forcan, Jovana Mikalački, Mirjana Forcan, Jovana Mikalački, Mirjana 0 Down-step statistics in generalized Dyck paths Tue, 24 May 2022 14:31:23 +0000 https://doi.org/10.46298/dmtcs.7163 https://doi.org/10.46298/dmtcs.7163 Asinowski, Andrei Hackl, Benjamin Selkirk, Sarah J. Asinowski, Andrei Hackl, Benjamin Selkirk, Sarah J. 0 Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree Fri, 13 May 2022 12:38:55 +0000 https://doi.org/10.46298/dmtcs.6844 https://doi.org/10.46298/dmtcs.6844 Baste, Julien Ehard, Stefan Rautenbach, Dieter Baste, Julien Ehard, Stefan Rautenbach, Dieter 0 Separating layered treewidth and row treewidth Fri, 13 May 2022 12:35:08 +0000 https://doi.org/10.46298/dmtcs.7458 https://doi.org/10.46298/dmtcs.7458 Bose, Prosenjit Dujmović, Vida Javarsineh, Mehrnoosh Morin, Pat Wood, David R. Bose, Prosenjit Dujmović, Vida Javarsineh, Mehrnoosh Morin, Pat Wood, David R. 0 The Neighborhood Polynomial of Chordal Graphs Fri, 06 May 2022 13:09:43 +0000 https://doi.org/10.46298/dmtcs.8388 https://doi.org/10.46298/dmtcs.8388 Bergold, Helena Hochstättler, Winfried Mayer, Uwe Bergold, Helena Hochstättler, Winfried Mayer, Uwe 0 Domination in Knödel Graphs Fri, 06 May 2022 13:06:07 +0000 https://doi.org/10.46298/dmtcs.7158 https://doi.org/10.46298/dmtcs.7158 Racicot, Jesse Rosso, Giovanni Racicot, Jesse Rosso, Giovanni 0 On the connectivity of the disjointness graph of segments of point sets in general position in the plane Fri, 06 May 2022 13:01:53 +0000 https://doi.org/10.46298/dmtcs.6678 https://doi.org/10.46298/dmtcs.6678 Leaños, J. Ndjatchi, Christophe Ríos-Castro, L. M. Leaños, J. Ndjatchi, Christophe Ríos-Castro, L. M. 0 Universal Horn Sentences and the Joint Embedding Property Fri, 06 May 2022 12:58:29 +0000 https://doi.org/10.46298/dmtcs.7435 https://doi.org/10.46298/dmtcs.7435 Bodirsky, Manuel Rydval, Jakub Schrottenloher, André Bodirsky, Manuel Rydval, Jakub Schrottenloher, André 0 On the Erdős-Pósa property for immersions and topological minors in tournaments Tue, 05 Apr 2022 16:05:27 +0000 https://doi.org/10.46298/dmtcs.7099 https://doi.org/10.46298/dmtcs.7099 Bożyk, Łukasz Pilipczuk, Michał Bożyk, Łukasz Pilipczuk, Michał 0 Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs Thu, 31 Mar 2022 14:27:13 +0000 https://doi.org/10.46298/dmtcs.8719 https://doi.org/10.46298/dmtcs.8719 Takazawa, Kenjiro Takazawa, Kenjiro 0 Constant Congestion Brambles Thu, 31 Mar 2022 14:15:06 +0000 https://doi.org/10.46298/dmtcs.6699 https://doi.org/10.46298/dmtcs.6699 Hatzel, Meike Komosa, Pawel Pilipczuk, Marcin Sorge, Manuel Hatzel, Meike Komosa, Pawel Pilipczuk, Marcin Sorge, Manuel 0 Determining Number of Kneser Graphs: Exact Values and Improved Bounds Wed, 30 Mar 2022 09:24:23 +0000 https://doi.org/10.46298/dmtcs.7627 https://doi.org/10.46298/dmtcs.7627 Das, Angsuman Dey, Hiranya Kishore Das, Angsuman Dey, Hiranya Kishore 0 On the Connectivity of Token Graphs of Trees Wed, 30 Mar 2022 09:20:29 +0000 https://doi.org/10.46298/dmtcs.7538 https://doi.org/10.46298/dmtcs.7538 Fabila-Monroy, Ruy Leaños, Jesús Trujillo-Negrete, Ana Laura Fabila-Monroy, Ruy Leaños, Jesús Trujillo-Negrete, Ana Laura 0 Leaf multiplicity in a Bienaymé-Galton-Watson tree Wed, 30 Mar 2022 09:17:27 +0000 https://doi.org/10.46298/dmtcs.7515 https://doi.org/10.46298/dmtcs.7515 Brandenberger, Anna M. Devroye, Luc Goh, Marcel K. Zhao, Rosie Y. Brandenberger, Anna M. Devroye, Luc Goh, Marcel K. Zhao, Rosie Y. 0 Restricted generating trees for weak orderings Mon, 21 Mar 2022 14:59:04 +0000 https://doi.org/10.46298/dmtcs.8350 https://doi.org/10.46298/dmtcs.8350 Birmajer, Daniel Gil, Juan B. Kenepp, David S. Weiner, Michael D. Birmajer, Daniel Gil, Juan B. Kenepp, David S. Weiner, Michael D. 0 Polymorphism-homogeneity and universal algebraic geometry Mon, 21 Mar 2022 14:54:14 +0000 https://doi.org/10.46298/dmtcs.6904 https://doi.org/10.46298/dmtcs.6904 Tóth, Endre Waldhauser, Tamás Tóth, Endre Waldhauser, Tamás 0 Efficient recurrence for the enumeration of permutations with fixed pinnacle set Fri, 11 Mar 2022 13:00:56 +0000 https://doi.org/10.46298/dmtcs.8321 https://doi.org/10.46298/dmtcs.8321 Fang, Wenjie Fang, Wenjie 0 Graphs containing finite induced paths of unbounded length Tue, 08 Mar 2022 16:07:01 +0000 https://doi.org/10.46298/dmtcs.6915 https://doi.org/10.46298/dmtcs.6915 Pouzet, Maurice Zaguia, Imed Pouzet, Maurice Zaguia, Imed 0 Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs Mon, 07 Feb 2022 10:59:48 +0000 https://doi.org/10.46298/dmtcs.8440 https://doi.org/10.46298/dmtcs.8440 Cappelle, Márcia R. Coelho, Erika Foulds, Les R. Longo, Humberto J. Cappelle, Márcia R. Coelho, Erika Foulds, Les R. Longo, Humberto J. 0 Further enumeration results concerning a recent equivalence of restricted inversion sequences )$ is the same as that of $n-1-\text{asc}$ on the class $I_n(>,\neq,\geq)$, which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on $I_n(\geq,\neq,>)$ of asc and desc along with two other parameters, and do the same for $n-1-\text{asc}$ and desc on $I_n(>,\neq,\geq)$. By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result $|I_n(\geq,\neq,>)|=|I_n(>,\neq,\geq)|$. In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents.]]> Mon, 07 Feb 2022 10:56:51 +0000 https://doi.org/10.46298/dmtcs.8330 https://doi.org/10.46298/dmtcs.8330 Mansour, Toufik Shattuck, Mark Mansour, Toufik Shattuck, Mark )$ is the same as that of $n-1-\text{asc}$ on the class $I_n(>,\neq,\geq)$, which confirmed an earlier conjecture of Lin. In this paper, we consider some further enumerative aspects related to this equivalence and, as a consequence, provide an alternative proof of the conjecture. In particular, we find recurrence relations for the joint distribution on $I_n(\geq,\neq,>)$ of asc and desc along with two other parameters, and do the same for $n-1-\text{asc}$ and desc on $I_n(>,\neq,\geq)$. By employing a functional equation approach together with the kernel method, we are able to compute explicitly the generating function for both of the aforementioned joint distributions, which extends (and provides a new proof of) the recent result $|I_n(\geq,\neq,>)|=|I_n(>,\neq,\geq)|$. In both cases, an algorithm is formulated for computing the generating function of the asc distribution on members of each respective class having a fixed number of descents.]]> 0 An explicit construction of graphs of bounded degree that are far from being Hamiltonian Mon, 31 Jan 2022 08:47:41 +0000 https://doi.org/10.46298/dmtcs.7109 https://doi.org/10.46298/dmtcs.7109 Adler, Isolde Köhler, Noleen Adler, Isolde Köhler, Noleen 0 Freezing, Bounded-Change and Convergent Cellular Automata Mon, 31 Jan 2022 08:44:09 +0000 https://doi.org/10.46298/dmtcs.5734 https://doi.org/10.46298/dmtcs.5734 Ollinger, Nicolas Theyssier, Guillaume Ollinger, Nicolas Theyssier, Guillaume 0 Upward-closed hereditary families in the dominance order Thu, 20 Jan 2022 16:56:54 +0000 https://doi.org/10.46298/dmtcs.5666 https://doi.org/10.46298/dmtcs.5666 Barrus, Michael D. Guillaume, Jean A. Barrus, Michael D. Guillaume, Jean A. 0 Extremal digraphs on Meyniel-type condition for hamiltonian cycles in balanced bipartite digraphs Thu, 20 Jan 2022 16:52:09 +0000 https://doi.org/10.46298/dmtcs.5851 https://doi.org/10.46298/dmtcs.5851 Wang, Ruixia Wu, Linxin Meng, Wei Wang, Ruixia Wu, Linxin Meng, Wei 0 Defective Coloring on Classes of Perfect Graphs Thu, 20 Jan 2022 16:47:09 +0000 https://doi.org/10.46298/dmtcs.4926 https://doi.org/10.46298/dmtcs.4926 Belmonte, Rémy Lampis, Michael Mitsou, Valia Belmonte, Rémy Lampis, Michael Mitsou, Valia 0 Upper paired domination versus upper domination Thu, 16 Dec 2021 13:15:54 +0000 https://doi.org/10.46298/dmtcs.7331 https://doi.org/10.46298/dmtcs.7331 Alizadeh, Hadi Gözüpek, Didem Alizadeh, Hadi Gözüpek, Didem 0 The treewidth of 2-section of hypergraphs Thu, 09 Dec 2021 15:59:54 +0000 https://doi.org/10.46298/dmtcs.6499 https://doi.org/10.46298/dmtcs.6499 Liu, Ke Lu, Mei Liu, Ke Lu, Mei 0 Antipowers in Uniform Morphic Words and the Fibonacci Word Thu, 09 Dec 2021 15:53:04 +0000 https://doi.org/10.46298/dmtcs.7134 https://doi.org/10.46298/dmtcs.7134 Garg, Swapnil Garg, Swapnil 0 List-antimagic labeling of vertex-weighted graphs Thu, 02 Dec 2021 15:23:48 +0000 https://doi.org/10.46298/dmtcs.5631 https://doi.org/10.46298/dmtcs.5631 Berikkyzy, Zhanar Brandt, Axel Jahanbekam, Sogol Larsen, Victor Rorabaugh, Danny Berikkyzy, Zhanar Brandt, Axel Jahanbekam, Sogol Larsen, Victor Rorabaugh, Danny 0 On non-adaptive majority problems of large query size Fri, 26 Nov 2021 10:00:41 +0000 https://doi.org/10.46298/dmtcs.7084 https://doi.org/10.46298/dmtcs.7084 Gerbner, Dániel Vizer, Máté Gerbner, Dániel Vizer, Máté 0 Certificate complexity and symmetry of nested canalizing functions Fri, 26 Nov 2021 09:50:34 +0000 https://doi.org/10.46298/dmtcs.6191 https://doi.org/10.46298/dmtcs.6191 Li, Yuan Ingram, Frank Zhang, Huaming Li, Yuan Ingram, Frank Zhang, Huaming 0 Fast Diameter Computation within Split Graphs Mon, 15 Nov 2021 10:16:07 +0000 https://doi.org/10.46298/dmtcs.6422 https://doi.org/10.46298/dmtcs.6422 Ducoffe, Guillaume Habib, Michel Viennot, Laurent Ducoffe, Guillaume Habib, Michel Viennot, Laurent 0 Five results on maximizing topological indices in graphs Mon, 15 Nov 2021 10:10:33 +0000 https://doi.org/10.46298/dmtcs.6896 https://doi.org/10.46298/dmtcs.6896 Cambie, Stijn Cambie, Stijn 0 On the genera of polyhedral embeddings of cubic graph Fri, 05 Nov 2021 15:40:54 +0000 https://doi.org/10.46298/dmtcs.6729 https://doi.org/10.46298/dmtcs.6729 Brinkmann, Gunnar Tucker, Thomas Van Cleemput, Nico Brinkmann, Gunnar Tucker, Thomas Van Cleemput, Nico 0 The algebra of binary trees is affine complete Thu, 04 Nov 2021 08:44:33 +0000 https://doi.org/10.46298/dmtcs.6890 https://doi.org/10.46298/dmtcs.6890 Arnold, Andre Cegielski, Patrick Grigorieff, Serge Guessarian, Irene Arnold, Andre Cegielski, Patrick Grigorieff, Serge Guessarian, Irene 0 Introduction to local certification Wed, 15 Sep 2021 12:18:21 +0000 https://doi.org/10.46298/dmtcs.6280 https://doi.org/10.46298/dmtcs.6280 Feuilloley, Laurent Feuilloley, Laurent 0 The undecidability of joint embedding for 3-dimensional permutation classes Tue, 14 Sep 2021 08:40:59 +0000 https://doi.org/10.46298/dmtcs.6165 https://doi.org/10.46298/dmtcs.6165 Braunfeld, Samuel Braunfeld, Samuel 0 A tight lower bound for the online bounded space hypercube bin packing problem Tue, 14 Sep 2021 08:37:20 +0000 https://doi.org/10.46298/dmtcs.8325 https://doi.org/10.46298/dmtcs.8325 Kohayakawa, Yoshiharu Miyazawa, Flávio Keidi Wakabayashi, Yoshiko Kohayakawa, Yoshiharu Miyazawa, Flávio Keidi Wakabayashi, Yoshiko 0 On the density of sets of the Euclidean plane avoiding distance 1 Tue, 31 Aug 2021 16:35:13 +0000 https://doi.org/10.46298/dmtcs.5153 https://doi.org/10.46298/dmtcs.5153 Bellitto, Thomas Pêcher, Arnaud Sédillot, Antoine Bellitto, Thomas Pêcher, Arnaud Sédillot, Antoine 0 Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations Tue, 31 Aug 2021 07:30:13 +0000 https://doi.org/10.46298/dmtcs.6494 https://doi.org/10.46298/dmtcs.6494 Mularczyk, Hanna Mularczyk, Hanna 0 Binary patterns in the Prouhet-Thue-Morse sequence Mon, 30 Aug 2021 12:58:00 +0000 https://doi.org/10.46298/dmtcs.5460 https://doi.org/10.46298/dmtcs.5460 Almeida, Jorge Klíma, Ondřej Almeida, Jorge Klíma, Ondřej 0 The structure and the list 3-dynamic coloring of outer-1-planar graphs Fri, 27 Aug 2021 06:57:03 +0000 https://doi.org/10.46298/dmtcs.5860 https://doi.org/10.46298/dmtcs.5860 Li, Yan Zhang, Xin Li, Yan Zhang, Xin 0 Determining the Hausdorff Distance Between Trees in Polynomial Time Thu, 19 Aug 2021 15:29:10 +0000 https://doi.org/10.46298/dmtcs.6952 https://doi.org/10.46298/dmtcs.6952 Kelenc, Aleksander Kelenc, Aleksander 0 On the VC-dimension of half-spaces with respect to convex sets 2. We focus on, possibly intersecting, segments in the plane and determine that the VC-dimension is always at most 5. And this is tight, as we construct a set of five segments that can be shattered. We give two exemplary applications. One for a geometric set cover problem and one for a range-query data structure problem, to motivate our findings.]]> Thu, 19 Aug 2021 15:24:12 +0000 https://doi.org/10.46298/dmtcs.6631 https://doi.org/10.46298/dmtcs.6631 Grelier, Nicolas Ilchi, Saeed Gh. Miltzow, Tillmann Smorodinsky, Shakhar Grelier, Nicolas Ilchi, Saeed Gh. Miltzow, Tillmann Smorodinsky, Shakhar 2. We focus on, possibly intersecting, segments in the plane and determine that the VC-dimension is always at most 5. And this is tight, as we construct a set of five segments that can be shattered. We give two exemplary applications. One for a geometric set cover problem and one for a range-query data structure problem, to motivate our findings.]]> 0 Two examples of Wilf-collapse Thu, 19 Aug 2021 15:18:29 +0000 https://doi.org/10.46298/dmtcs.5986 https://doi.org/10.46298/dmtcs.5986 Albert, Michael Jelínek, Vít Opler, Michal Albert, Michael Jelínek, Vít Opler, Michal 0 A birational lifting of the Stanley-Thomas word on products of two chains Wed, 18 Aug 2021 07:18:26 +0000 https://doi.org/10.46298/dmtcs.6633 https://doi.org/10.46298/dmtcs.6633 Joseph, Michael Roby, Tom Joseph, Michael Roby, Tom 0 Enumeration of Dumont permutations avoiding certain four-letter patterns Tue, 06 Jul 2021 12:35:41 +0000 https://doi.org/10.46298/dmtcs.6174 https://doi.org/10.46298/dmtcs.6174 Burstein, Alexander Jones, Opel Burstein, Alexander Jones, Opel 0 Semipaired Domination in Some Subclasses of Chordal Graphs Tue, 06 Jul 2021 12:30:51 +0000 https://doi.org/10.46298/dmtcs.6782 https://doi.org/10.46298/dmtcs.6782 Henning, Michael A. Pandey, Arti Tripathi, Vikash Henning, Michael A. Pandey, Arti Tripathi, Vikash 0 Fillings of skew shapes avoiding diagonal patterns Fri, 18 Jun 2021 12:31:44 +0000 https://doi.org/10.46298/dmtcs.6171 https://doi.org/10.46298/dmtcs.6171 Jelínek, Vít Karpilovskij, Mark Jelínek, Vít Karpilovskij, Mark 0 Crisp-determinization of weighted tree automata over strong bimonoids Tue, 15 Jun 2021 07:40:34 +0000 https://doi.org/10.46298/dmtcs.5943 https://doi.org/10.46298/dmtcs.5943 Fülöp, Zoltán Kószó, Dávid Vogler, Heiko Fülöp, Zoltán Kószó, Dávid Vogler, Heiko 0 A note on tight cuts in matching-covered graphs Mon, 14 Jun 2021 09:51:56 +0000 https://doi.org/10.46298/dmtcs.6013 https://doi.org/10.46298/dmtcs.6013 Zhao, Xiao Chen, Sheng Zhao, Xiao Chen, Sheng 0 Destroying Bicolored $P_3$s by Deleting Few Edges Tue, 08 Jun 2021 08:23:01 +0000 https://doi.org/10.46298/dmtcs.6108 https://doi.org/10.46298/dmtcs.6108 Grüttemeier, Niels Komusiewicz, Christian Schestag, Jannik Sommer, Frank Grüttemeier, Niels Komusiewicz, Christian Schestag, Jannik Sommer, Frank 0 The Elser nuclei sum revisited Thu, 03 Jun 2021 09:41:13 +0000 https://doi.org/10.46298/dmtcs.7012 https://doi.org/10.46298/dmtcs.7012 Grinberg, Darij Grinberg, Darij 0 Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees Thu, 03 Jun 2021 09:37:26 +0000 https://doi.org/10.46298/dmtcs.6040 https://doi.org/10.46298/dmtcs.6040 Hellmuth, Marc Seemann, Carsten R. Stadler, Peter F. Hellmuth, Marc Seemann, Carsten R. Stadler, Peter F. 0 Wiener index in graphs with given minimum degree and maximum degree Thu, 03 Jun 2021 09:31:33 +0000 https://doi.org/10.46298/dmtcs.6956 https://doi.org/10.46298/dmtcs.6956 Dankelmann, Peter Alochukwu, Alex Dankelmann, Peter Alochukwu, Alex 0 Weak equivalence of higher-dimensional automata Tue, 18 May 2021 09:47:50 +0000 https://doi.org/10.46298/dmtcs.5884 https://doi.org/10.46298/dmtcs.5884 Kahl, Thomas Kahl, Thomas 0 Flip-sort and combinatorial aspects of pop-stack sorting Fri, 30 Apr 2021 08:26:14 +0000 https://doi.org/10.46298/dmtcs.6196 https://doi.org/10.46298/dmtcs.6196 Asinowski, Andrei Banderier, Cyril Hackl, Benjamin Asinowski, Andrei Banderier, Cyril Hackl, Benjamin 0 New Algorithms for Mixed Dominating Set Fri, 30 Apr 2021 08:23:11 +0000 https://doi.org/10.46298/dmtcs.6824 https://doi.org/10.46298/dmtcs.6824 Dublois, Louis Lampis, Michael Paschos, Vangelis Th. Dublois, Louis Lampis, Michael Paschos, Vangelis Th. 0 Row bounds needed to justifiably express flagged Schur functions with Gessel-Viennot determinants Fri, 23 Apr 2021 09:42:21 +0000 https://doi.org/10.46298/dmtcs.6632 https://doi.org/10.46298/dmtcs.6632 Proctor, Robert A. Willis, Matthew J. Proctor, Robert A. Willis, Matthew J. 0 Catalan words avoiding pairs of length three patterns Fri, 16 Apr 2021 07:43:30 +0000 https://doi.org/10.46298/dmtcs.6002 https://doi.org/10.46298/dmtcs.6002 Baril, Jean-Luc Khalil, Carine Vajnovszki, Vincent Baril, Jean-Luc Khalil, Carine Vajnovszki, Vincent 0 Enumeration of Stack-Sorting Preimages via a Decomposition Lemma Fri, 09 Apr 2021 15:03:26 +0000 https://doi.org/10.46298/dmtcs.6709 https://doi.org/10.46298/dmtcs.6709 Defant, Colin Defant, Colin 0 Enumeration of Permutation Classes and Weighted Labelled Independent Sets Mon, 29 Mar 2021 09:02:41 +0000 https://doi.org/10.46298/dmtcs.5995 https://doi.org/10.46298/dmtcs.5995 Bean, Christian Nadeau, Émile Ulfarsson, Henning Bean, Christian Nadeau, Émile Ulfarsson, Henning 0 Bounded affine permutations I. Pattern avoidance and enumeration Mon, 29 Mar 2021 08:57:54 +0000 https://doi.org/10.46298/dmtcs.6178 https://doi.org/10.46298/dmtcs.6178 Madras, Neal Troyka, Justin M. Madras, Neal Troyka, Justin M. 0 On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets Mon, 29 Mar 2021 08:53:54 +0000 https://doi.org/10.46298/dmtcs.6773 https://doi.org/10.46298/dmtcs.6773 Duffy, Christopher Shan, Sonja Linghui Duffy, Christopher Shan, Sonja Linghui 0 Exponential multivalued forbidden configurations 3$. We also prove a stability result for the $2\times 2$ identity matrix. Along the way, we expose some interesting qualitative differences between the cases $r=2$, $r = 3$, and $r > 3$.]]> Tue, 23 Mar 2021 09:42:29 +0000 https://doi.org/10.46298/dmtcs.6613 https://doi.org/10.46298/dmtcs.6613 Dillon, Travis Sali, Attila Dillon, Travis Sali, Attila 3$. We also prove a stability result for the $2\times 2$ identity matrix. Along the way, we expose some interesting qualitative differences between the cases $r=2$, $r = 3$, and $r > 3$.]]> 0 Wiener Index and Remoteness in Triangulations and Quadrangulations Mon, 08 Mar 2021 08:48:59 +0000 https://doi.org/10.46298/dmtcs.6473 https://doi.org/10.46298/dmtcs.6473 Czabarka, Éva Dankelmann, Peter Olsen, Trevor Székely, László A. Czabarka, Éva Dankelmann, Peter Olsen, Trevor Székely, László A. 0 Efficient enumeration of non-isomorphic interval graphs Mon, 08 Mar 2021 08:45:41 +0000 https://doi.org/10.46298/dmtcs.6164 https://doi.org/10.46298/dmtcs.6164 Mikos, Patryk Mikos, Patryk 0 Anti-power $j$-fixes of the Thue-Morse word Thu, 25 Feb 2021 09:28:02 +0000 https://doi.org/10.46298/dmtcs.5483 https://doi.org/10.46298/dmtcs.5483 Gaetz, Marisa Gaetz, Marisa 0 On BMRN*-colouring of planar digraphs Thu, 25 Feb 2021 09:24:16 +0000 https://doi.org/10.46298/dmtcs.5798 https://doi.org/10.46298/dmtcs.5798 Bensmail, Julien Fioravantes, Foivos Bensmail, Julien Fioravantes, Foivos 0 Unary profile of lambda terms with restricted De Bruijn indices Fri, 12 Feb 2021 09:04:37 +0000 https://doi.org/10.46298/dmtcs.5836 https://doi.org/10.46298/dmtcs.5836 Grygiel, Katarzyna Larcher, Isabella Grygiel, Katarzyna Larcher, Isabella 0 The number of distinct adjacent pairs in geometrically distributed words Thu, 28 Jan 2021 14:22:47 +0000 https://doi.org/10.23638/DMTCS-22-4-10 https://doi.org/10.23638/DMTCS-22-4-10 Archibald, Margaret Blecher, Aubrey Brennan, Charlotte Knopfmacher, Arnold Wagner, Stephan Ward, Mark Archibald, Margaret Blecher, Aubrey Brennan, Charlotte Knopfmacher, Arnold Wagner, Stephan Ward, Mark 0 Quantitative and Algorithmic aspects of Barrier Synchronization in Concurrency Mon, 25 Jan 2021 13:58:42 +0000 https://doi.org/10.46298/dmtcs.5820 https://doi.org/10.46298/dmtcs.5820 Bodini, OLivier Dien, Matthieu Genitrini, Antoine Peschanski, Frédéric Bodini, OLivier Dien, Matthieu Genitrini, Antoine Peschanski, Frédéric 0 A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture Mon, 18 Jan 2021 12:23:33 +0000 https://doi.org/10.23638/DMTCS-22-4-12 https://doi.org/10.23638/DMTCS-22-4-12 Darbinyan, Samvel Kh. Darbinyan, Samvel Kh. 0 Determining Genus From Sandpile Torsor Algorithms Thu, 07 Jan 2021 09:16:32 +0000 https://doi.org/10.46298/dmtcs.6176 https://doi.org/10.46298/dmtcs.6176 McDonough, Alex McDonough, Alex 0 A Note on Graphs of Dichromatic Number 2 Tue, 05 Jan 2021 08:49:23 +0000 https://doi.org/10.23638/DMTCS-22-4-11 https://doi.org/10.23638/DMTCS-22-4-11 Steiner, Raphael Steiner, Raphael 0 The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs Mon, 28 Dec 2020 09:08:45 +0000 https://doi.org/10.23638/DMTCS-22-4-13 https://doi.org/10.23638/DMTCS-22-4-13 Gao, Xiao-Lu Xu, Shou-Jun Gao, Xiao-Lu Xu, Shou-Jun 0 Two lower bounds for $p$-centered colorings Wed, 11 Nov 2020 09:20:55 +0000 https://doi.org/10.23638/DMTCS-22-4-9 https://doi.org/10.23638/DMTCS-22-4-9 Dubois, Loïc Joret, Gwenaël Perarnau, Guillem Pilipczuk, Marcin Pitois, François Dubois, Loïc Joret, Gwenaël Perarnau, Guillem Pilipczuk, Marcin Pitois, François 0 Even cycles and perfect matchings in claw-free plane graphs Mon, 12 Oct 2020 07:36:00 +0000 https://doi.org/10.23638/DMTCS-22-4-6 https://doi.org/10.23638/DMTCS-22-4-6 Zhang, Shanshan Wang, Xiumei Yuan, Jinjiang Zhang, Shanshan Wang, Xiumei Yuan, Jinjiang 0 Extension Complexity, MSO Logic, and Treewidth Thu, 01 Oct 2020 15:42:02 +0000 https://doi.org/10.23638/DMTCS-22-4-8 https://doi.org/10.23638/DMTCS-22-4-8 Kolman, Petr Koutecký, Martin Tiwary, Hans Raj Kolman, Petr Koutecký, Martin Tiwary, Hans Raj 0 Taking-and-merging games as rewrite games epsilon. We give sufficient conditions for a game to be such that the losing positions (resp. the positions with a given Grundy value) form a regular language or a context-free language. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games. Finally we show that more general rewrite games quickly lead to undecidable problems. Namely, it is undecidable whether there exists a winning position in a given regular language, even if we restrict to games where each move strictly reduces the length of the current position. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games.]]> Wed, 23 Sep 2020 11:47:19 +0000 https://doi.org/10.23638/DMTCS-22-4-5 https://doi.org/10.23638/DMTCS-22-4-5 Duchêne, Eric Marsault, Victor Parreau, Aline Rigo, Michel Duchêne, Eric Marsault, Victor Parreau, Aline Rigo, Michel epsilon. We give sufficient conditions for a game to be such that the losing positions (resp. the positions with a given Grundy value) form a regular language or a context-free language. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games. Finally we show that more general rewrite games quickly lead to undecidable problems. Namely, it is undecidable whether there exists a winning position in a given regular language, even if we restrict to games where each move strictly reduces the length of the current position. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games.]]> 0 A Double Exponential Lower Bound for the Distinct Vectors Problem Fri, 18 Sep 2020 13:34:05 +0000 https://doi.org/10.23638/DMTCS-22-4-7 https://doi.org/10.23638/DMTCS-22-4-7 Pilipczuk, Marcin Sorge, Manuel Pilipczuk, Marcin Sorge, Manuel 0 (Open) packing number of some graph products Thu, 27 Aug 2020 07:18:21 +0000 https://doi.org/10.23638/DMTCS-22-4-1 https://doi.org/10.23638/DMTCS-22-4-1 Mojdeh, Doost Ali Peterin, Iztok Samadi, Babak Yero, Ismael G. Mojdeh, Doost Ali Peterin, Iztok Samadi, Babak Yero, Ismael G. 0 Evacuating Robots from a Disk Using Face-to-Face Communication Thu, 27 Aug 2020 07:13:53 +0000 https://doi.org/10.23638/DMTCS-22-4-4 https://doi.org/10.23638/DMTCS-22-4-4 Czyzowicz, Jurek Georgiou, Konstantinos Kranakis, Evangelos Narayanan, Lata Opatrny, Jarda Vogtenhuber, Birgit Czyzowicz, Jurek Georgiou, Konstantinos Kranakis, Evangelos Narayanan, Lata Opatrny, Jarda Vogtenhuber, Birgit 0 A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage Thu, 27 Aug 2020 07:12:06 +0000 https://doi.org/10.23638/DMTCS-22-4-3 https://doi.org/10.23638/DMTCS-22-4-3 Engelfriet, Joost Vogler, Heiko Engelfriet, Joost Vogler, Heiko 0 A Type System Describing Unboundedness Tue, 18 Aug 2020 07:20:48 +0000 https://doi.org/10.23638/DMTCS-22-4-2 https://doi.org/10.23638/DMTCS-22-4-2 Parys, Paweł Parys, Paweł 0 On an alternative sequence comparison statistic of Steele Fri, 10 Jul 2020 10:03:55 +0000 https://doi.org/10.23638/DMTCS-22-1-18 https://doi.org/10.23638/DMTCS-22-1-18 Işlak, Ümit Özdemir, Alperen Y. Işlak, Ümit Özdemir, Alperen Y. 0 The agreement distance of unrooted phylogenetic networks Thu, 09 Jul 2020 08:30:40 +0000 https://doi.org/10.23638/DMTCS-22-1-22 https://doi.org/10.23638/DMTCS-22-1-22 Klawitter, Jonathan Klawitter, Jonathan 0 Inversion sequences avoiding pairs of patterns Mon, 29 Jun 2020 13:38:31 +0000 https://doi.org/10.23638/DMTCS-22-1-23 https://doi.org/10.23638/DMTCS-22-1-23 Yan, Chunyan Lin, Zhicong Yan, Chunyan Lin, Zhicong 0 Dissecting a square into congruent polygons Mon, 29 Jun 2020 13:34:40 +0000 https://doi.org/10.23638/DMTCS-22-1-21 https://doi.org/10.23638/DMTCS-22-1-21 Rao, Hui Ren, Lei Wang, Yang Rao, Hui Ren, Lei Wang, Yang 0 On the heapability of finite partial orders Mon, 29 Jun 2020 13:29:19 +0000 https://doi.org/10.23638/DMTCS-22-1-17 https://doi.org/10.23638/DMTCS-22-1-17 Balogh, János Bonchiş, Cosmin Diniş, Diana Istrate, Gabriel Todinca, Ioan Balogh, János Bonchiş, Cosmin Diniş, Diana Istrate, Gabriel Todinca, Ioan 0 Complementary symmetric Rote sequences: the critical exponent and the recurrence function Sat, 06 Jun 2020 11:59:49 +0000 https://doi.org/10.23638/DMTCS-22-1-20 https://doi.org/10.23638/DMTCS-22-1-20 Dvořáková, Lubomíra Medková, Kateřina Pelantová, Edita Dvořáková, Lubomíra Medková, Kateřina Pelantová, Edita 0 The Complexity of Helly-$B_{1}$ EPG Graph Recognition Thu, 04 Jun 2020 14:56:38 +0000 https://doi.org/10.23638/DMTCS-22-1-19 https://doi.org/10.23638/DMTCS-22-1-19 Bornstein, Claudson F. Golumbic, Martin Charles Santos, Tanilson D. Souza, Uéverton S. Szwarcfiter, Jayme L. Bornstein, Claudson F. Golumbic, Martin Charles Santos, Tanilson D. Souza, Uéverton S. Szwarcfiter, Jayme L. 0 New schemes for simplifying binary constraint satisfaction problems Thu, 04 Jun 2020 14:38:55 +0000 https://doi.org/10.23638/DMTCS-22-1-10 https://doi.org/10.23638/DMTCS-22-1-10 Naanaa, Wady Naanaa, Wady 0 Antifactors of regular bipartite graphs Thu, 04 Jun 2020 14:33:38 +0000 https://doi.org/10.23638/DMTCS-22-1-16 https://doi.org/10.23638/DMTCS-22-1-16 Lu, Hongliang Wang, Wei Yan, Juan Lu, Hongliang Wang, Wei Yan, Juan 0 Formal inverses of the generalized Thue-Morse sequences and variations of the Rudin-Shapiro sequence Mon, 25 May 2020 08:03:35 +0000 https://doi.org/10.23638/DMTCS-22-1-15 https://doi.org/10.23638/DMTCS-22-1-15 Merta, Łukasz Merta, Łukasz 0 Complexity of Leading Digit Sequences 0$ that are not integral powers of $b$. In particular, we show that, for all such pairs $(a,b)$, the complexity function $p_{a,b}(n)$ is \emph{affine}, i.e., satisfies $p_{a,b}(n)=c_{a,b} n + d_{a,b}$ for all $n\ge1$, with coefficients $c_{a,b}\ge1$ and $d_{a,b}\ge0$, given explicitly in terms of $a$ and $b$. We also show that the requirement that $b$ be squarefree cannot be dropped: If $b$ is not squarefree, then there exist integers $a$ with $1 Thu, 30 Apr 2020 09:13:09 +0000 https://doi.org/10.23638/DMTCS-22-1-14 https://doi.org/10.23638/DMTCS-22-1-14 He, Xinwei Hildebrand, A. J. Li, Yuchen Zhang, Yunyi He, Xinwei Hildebrand, A. J. Li, Yuchen Zhang, Yunyi 0$ that are not integral powers of $b$. In particular, we show that, for all such pairs $(a,b)$, the complexity function $p_{a,b}(n)$ is \emph{affine}, i.e., satisfies $p_{a,b}(n)=c_{a,b} n + d_{a,b}$ for all $n\ge1$, with coefficients $c_{a,b}\ge1$ and $d_{a,b}\ge0$, given explicitly in terms of $a$ and $b$. We also show that the requirement that $b$ be squarefree cannot be dropped: If $b$ is not squarefree, then there exist integers $a$ with $1 0 The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints Thu, 30 Apr 2020 08:51:36 +0000 https://doi.org/10.23638/DMTCS-22-1-13 https://doi.org/10.23638/DMTCS-22-1-13 Naumovs, Aleksejs Dimitrijevs, Maksims Yakaryılmaz, Abuzer Naumovs, Aleksejs Dimitrijevs, Maksims Yakaryılmaz, Abuzer 0 From generalized Tamari intervals to non-separable planar maps Wed, 22 Apr 2020 21:33:39 +0000 https://doi.org/10.46298/dmtcs.6421 https://doi.org/10.46298/dmtcs.6421 Fang, Wenjie Préville-Ratelle, Louis-François Fang, Wenjie Préville-Ratelle, Louis-François 0 Matrix product and sum rule for Macdonald polynomials Wed, 22 Apr 2020 21:33:38 +0000 https://doi.org/10.46298/dmtcs.6419 https://doi.org/10.46298/dmtcs.6419 Cantini, Luigi De Gier, Jan Wheeler, Michael Cantini, Luigi De Gier, Jan Wheeler, Michael 0 The number of corner polyhedra graphs Wed, 22 Apr 2020 21:33:38 +0000 https://doi.org/10.46298/dmtcs.6420 https://doi.org/10.46298/dmtcs.6420 Dervieux, Clement Poulalhon, Dominique Schaeffer, Gilles Dervieux, Clement Poulalhon, Dominique Schaeffer, Gilles 0 An equivalence of multistatistics on permutations Wed, 22 Apr 2020 21:33:37 +0000 https://doi.org/10.46298/dmtcs.6418 https://doi.org/10.46298/dmtcs.6418 Nunge, Arthur Nunge, Arthur 0 Counting quadrant walks via Tutte's invariant method (extended abstract) Wed, 22 Apr 2020 21:33:36 +0000 https://doi.org/10.46298/dmtcs.6416 https://doi.org/10.46298/dmtcs.6416 Bernardi, Olivier Bousquet-Mélou, Mireille Raschel, Kilian Bernardi, Olivier Bousquet-Mélou, Mireille Raschel, Kilian 0 Rectangular Young tableaux and the Jacobi ensemble Wed, 22 Apr 2020 21:33:36 +0000 https://doi.org/10.46298/dmtcs.6417 https://doi.org/10.46298/dmtcs.6417 Marchal, Philippe Marchal, Philippe 0 Continued Classification of 3D Lattice Models in the Positive Octant Wed, 22 Apr 2020 21:33:35 +0000 https://doi.org/10.46298/dmtcs.6415 https://doi.org/10.46298/dmtcs.6415 Bacher, Axel Kauers, Manuel Yatchak, Rika Bacher, Axel Kauers, Manuel Yatchak, Rika 0 On q-integrals over order polytopes (extended abstract) Wed, 22 Apr 2020 21:33:34 +0000 https://doi.org/10.46298/dmtcs.6413 https://doi.org/10.46298/dmtcs.6413 Kim, Jang Soo Kim, Jang Soo 0 Non-ambiguous trees: new results and generalization Wed, 22 Apr 2020 21:33:34 +0000 https://doi.org/10.46298/dmtcs.6414 https://doi.org/10.46298/dmtcs.6414 Aval, Jean-Christophe Boussicault, Adrien Delcroix-Oger, Bérénice Hivert, Florent Laborde-Zubieta, Patxi Aval, Jean-Christophe Boussicault, Adrien Delcroix-Oger, Bérénice Hivert, Florent Laborde-Zubieta, Patxi 0 A bijective proof of Macdonald's reduced word formula Wed, 22 Apr 2020 21:33:33 +0000 https://doi.org/10.46298/dmtcs.6412 https://doi.org/10.46298/dmtcs.6412 Billey, Sara, Holroyd, Alexander Young, Benjamin, Billey, Sara, Holroyd, Alexander Young, Benjamin, 0 Staircase diagrams and the enumeration of smooth Schubert varieties Wed, 22 Apr 2020 21:33:32 +0000 https://doi.org/10.46298/dmtcs.6411 https://doi.org/10.46298/dmtcs.6411 Richmond, Edward Slofstra, William Richmond, Edward Slofstra, William 0 Dual Immaculate Quasisymmetric Functions Expand Positively into Young Quasisymmetric Schur Functions Wed, 22 Apr 2020 21:33:31 +0000 https://doi.org/10.46298/dmtcs.6410 https://doi.org/10.46298/dmtcs.6410 Allen, Edward, Hallam, Joshua Mason, Sarah, Allen, Edward, Hallam, Joshua Mason, Sarah, 0 Schur polynomials and matrix positivity preservers Wed, 22 Apr 2020 21:33:29 +0000 https://doi.org/10.46298/dmtcs.6408 https://doi.org/10.46298/dmtcs.6408 Belton, Alexander Guillot, Dominique Khare, Apoorva Putinar, Mihai Belton, Alexander Guillot, Dominique Khare, Apoorva Putinar, Mihai 0 Extending the weak order on Coxeter groups Wed, 22 Apr 2020 21:33:29 +0000 https://doi.org/10.46298/dmtcs.6409 https://doi.org/10.46298/dmtcs.6409 Viard, Francois Viard, Francois 0 The Mixing Time for a Random Walk on the Symmetric Group Generated by Random Involutions Wed, 22 Apr 2020 21:33:28 +0000 https://doi.org/10.46298/dmtcs.6407 https://doi.org/10.46298/dmtcs.6407 Bernstein, Megan Bernstein, Megan 0 Toric matrix Schubert varieties and root polytopes (extended abstract) Wed, 22 Apr 2020 21:33:27 +0000 https://doi.org/10.46298/dmtcs.6405 https://doi.org/10.46298/dmtcs.6405 Escobar, Laura Mészáros, Karola Escobar, Laura Mészáros, Karola 0 The generalized Gelfand–Graev characters of GLn(Fq) Wed, 22 Apr 2020 21:33:27 +0000 https://doi.org/10.46298/dmtcs.6406 https://doi.org/10.46298/dmtcs.6406 Andrews, Scott Thiem, Nathaniel Andrews, Scott Thiem, Nathaniel 0 Order Filter Model for Minuscule Plücker Relations Wed, 22 Apr 2020 21:33:26 +0000 https://doi.org/10.46298/dmtcs.6404 https://doi.org/10.46298/dmtcs.6404 Lax, David C Lax, David C 0 The configuration space of a robotic arm in a tunnel of width 2 Wed, 22 Apr 2020 21:33:25 +0000 https://doi.org/10.46298/dmtcs.6402 https://doi.org/10.46298/dmtcs.6402 Ardila, Federico Bastidas, Hanner Ceballos, Cesar Guo, John Ardila, Federico Bastidas, Hanner Ceballos, Cesar Guo, John 0 The twist for positroids Wed, 22 Apr 2020 21:33:25 +0000 https://doi.org/10.46298/dmtcs.6403 https://doi.org/10.46298/dmtcs.6403 Muller, Greg Speyer, David E. Muller, Greg Speyer, David E. 0 Brick polytopes, lattices and Hopf algebras Wed, 22 Apr 2020 21:33:24 +0000 https://doi.org/10.46298/dmtcs.6401 https://doi.org/10.46298/dmtcs.6401 Pilaud, Vincent Pilaud, Vincent 0 Compatibility fans realizing graphical nested complexes Wed, 22 Apr 2020 21:33:23 +0000 https://doi.org/10.46298/dmtcs.6400 https://doi.org/10.46298/dmtcs.6400 Manneville, Thibault Pilaud, Vincent Manneville, Thibault Pilaud, Vincent 0 The facial weak order in finite Coxeter groups Wed, 22 Apr 2020 21:33:23 +0000 https://doi.org/10.46298/dmtcs.6399 https://doi.org/10.46298/dmtcs.6399 Dermenjian, Aram Hohlweg, Christophe Pilaud, Vincent Dermenjian, Aram Hohlweg, Christophe Pilaud, Vincent 0 Normal Supercharacter Theory Wed, 22 Apr 2020 21:33:22 +0000 https://doi.org/10.46298/dmtcs.6397 https://doi.org/10.46298/dmtcs.6397 Aliniaeifard, Farid Aliniaeifard, Farid 0 A bijection for nonorientable general maps Wed, 22 Apr 2020 21:33:22 +0000 https://doi.org/10.46298/dmtcs.6398 https://doi.org/10.46298/dmtcs.6398 Bettinelli, Jérémie Bettinelli, Jérémie 0 Matrix-Ball Construction of affine Robinson-Schensted correspondence Wed, 22 Apr 2020 21:33:21 +0000 https://doi.org/10.46298/dmtcs.6396 https://doi.org/10.46298/dmtcs.6396 Chmutov, Michael Pylyavskyy, Pavlo Yudovina, Elena Chmutov, Michael Pylyavskyy, Pavlo Yudovina, Elena 0 Quasi-isomorphisms of cluster algebras and the combinatorics of webs (extended abstract) Wed, 22 Apr 2020 21:33:20 +0000 https://doi.org/10.46298/dmtcs.6395 https://doi.org/10.46298/dmtcs.6395 Fraser, Chris Fraser, Chris 0 Affine type A geometric crystal structure on the Grassmannian Wed, 22 Apr 2020 21:33:19 +0000 https://doi.org/10.46298/dmtcs.6393 https://doi.org/10.46298/dmtcs.6393 Frieden, Gabriel Frieden, Gabriel 0 Resonance in orbits of plane partitions Wed, 22 Apr 2020 21:33:19 +0000 https://doi.org/10.46298/dmtcs.6394 https://doi.org/10.46298/dmtcs.6394 Dilks, Kevin Pechenik, Oliver Striker, Jessica Dilks, Kevin Pechenik, Oliver Striker, Jessica 0 Total positivity for the Lagrangian Grassmannian Wed, 22 Apr 2020 21:33:18 +0000 https://doi.org/10.46298/dmtcs.6392 https://doi.org/10.46298/dmtcs.6392 Karpman, Rachel Karpman, Rachel 0 New hook-content formulas for strict partitions Wed, 22 Apr 2020 21:33:17 +0000 https://doi.org/10.46298/dmtcs.6391 https://doi.org/10.46298/dmtcs.6391 Han, Guo-Niu Xiong, Huan Han, Guo-Niu Xiong, Huan 0 Links in the complex of weakly separated collections Wed, 22 Apr 2020 21:33:16 +0000 https://doi.org/10.46298/dmtcs.6389 https://doi.org/10.46298/dmtcs.6389 Oh, Suho Speyer, David Oh, Suho Speyer, David 0 Asymptotics of lattice walks via analytic combinatorics in several variables Wed, 22 Apr 2020 21:33:16 +0000 https://doi.org/10.46298/dmtcs.6390 https://doi.org/10.46298/dmtcs.6390 Melczer, Stephen Wilson, Mark C. Melczer, Stephen Wilson, Mark C. 0 Categorifying the tensor product of the Kirillov-Reshetikhin crystal B1,1 and a fundamental crystal Wed, 22 Apr 2020 21:33:15 +0000 https://doi.org/10.46298/dmtcs.6388 https://doi.org/10.46298/dmtcs.6388 Kvinge, Henry Vazirani, Monica Kvinge, Henry Vazirani, Monica 0 Rational Dyck Paths in the Non Relatively Prime Case Wed, 22 Apr 2020 21:33:14 +0000 https://doi.org/10.46298/dmtcs.6387 https://doi.org/10.46298/dmtcs.6387 Gorsky, Eugene Mazin, Mikhail Vazirani, Monica Gorsky, Eugene Mazin, Mikhail Vazirani, Monica 0 A combinatorial analysis of Severi degrees Wed, 22 Apr 2020 21:33:13 +0000 https://doi.org/10.46298/dmtcs.6385 https://doi.org/10.46298/dmtcs.6385 Liu, Fu Liu, Fu 0 The Prism tableau model for Schubert polynomials Wed, 22 Apr 2020 21:33:13 +0000 https://doi.org/10.46298/dmtcs.6386 https://doi.org/10.46298/dmtcs.6386 Weigandt, Anna Yong, Alexander Weigandt, Anna Yong, Alexander 0 The Delta Conjecture Wed, 22 Apr 2020 21:33:12 +0000 https://doi.org/10.46298/dmtcs.6384 https://doi.org/10.46298/dmtcs.6384 Haglund, James Remmel, Jeffrey B. Wilson, Andrew Timothy Haglund, James Remmel, Jeffrey B. Wilson, Andrew Timothy 0 Maximal green sequences for arbitrary triangulations of marked surfaces (Extended Abstract) Wed, 22 Apr 2020 21:33:11 +0000 https://doi.org/10.46298/dmtcs.6383 https://doi.org/10.46298/dmtcs.6383 Mills, Matthew R. Mills, Matthew R. 0 GL(n, q)-analogues of factorization problems in the symmetric group Wed, 22 Apr 2020 21:33:10 +0000 https://doi.org/10.46298/dmtcs.6382 https://doi.org/10.46298/dmtcs.6382 Lewis, Joel Brewster Morales, Alejandro H. Lewis, Joel Brewster Morales, Alejandro H. 0 On intervals of the consecutive pattern poset Wed, 22 Apr 2020 21:33:09 +0000 https://doi.org/10.46298/dmtcs.6380 https://doi.org/10.46298/dmtcs.6380 Elizalde, Sergi McNamara, Peter R. W. Elizalde, Sergi McNamara, Peter R. W. 0 Monodromy and K-theory of Schubert curves via generalized jeu de taquin Wed, 22 Apr 2020 21:33:09 +0000 https://doi.org/10.46298/dmtcs.6381 https://doi.org/10.46298/dmtcs.6381 Gillespie, Maria Monks Levinson, Jake Gillespie, Maria Monks Levinson, Jake 0 Oriented Flip Graphs and Noncrossing Tree Partitions Wed, 22 Apr 2020 21:33:08 +0000 https://doi.org/10.46298/dmtcs.6379 https://doi.org/10.46298/dmtcs.6379 Garver, Alexander McConville, Thomas Garver, Alexander McConville, Thomas 0 Noncrossing partitions, toggles, and homomesy Wed, 22 Apr 2020 21:33:06 +0000 https://doi.org/10.46298/dmtcs.6378 https://doi.org/10.46298/dmtcs.6378 Einstein, David Farber, Miriam Gunawan, Emily Joseph, Michael Macauley, Matthew Propp, James Rubinstein-Salzedo, Simon Einstein, David Farber, Miriam Gunawan, Emily Joseph, Michael Macauley, Matthew Propp, James Rubinstein-Salzedo, Simon 0 A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition Wed, 22 Apr 2020 21:33:05 +0000 https://doi.org/10.46298/dmtcs.6376 https://doi.org/10.46298/dmtcs.6376 Smith, Jason P Smith, Jason P 0 Combinatorial descriptions of the crystal structure on certain PBW bases Wed, 22 Apr 2020 21:33:05 +0000 https://doi.org/10.46298/dmtcs.6377 https://doi.org/10.46298/dmtcs.6377 Salisbury, Ben Schultze, Adam Tingley, Peter Salisbury, Ben Schultze, Adam Tingley, Peter 0 Intersections of Amoebas Wed, 22 Apr 2020 21:33:04 +0000 https://doi.org/10.46298/dmtcs.6375 https://doi.org/10.46298/dmtcs.6375 Juhnke-Kubitzke, Martina De Wolff, Timo Juhnke-Kubitzke, Martina De Wolff, Timo 0 Refined dual stable Grothendieck polynomials and generalized Bender-Knuth involutions Wed, 22 Apr 2020 21:33:03 +0000 https://doi.org/10.46298/dmtcs.6374 https://doi.org/10.46298/dmtcs.6374 Galashin, Pavel Grinberg, Darij Liu, Gaku Galashin, Pavel Grinberg, Darij Liu, Gaku 0 Schur-positivity via products of grid classes Wed, 22 Apr 2020 21:33:02 +0000 https://doi.org/10.46298/dmtcs.6373 https://doi.org/10.46298/dmtcs.6373 Elizalde, Sergi Roichman, Yuval Elizalde, Sergi Roichman, Yuval 0 Separation of Variables and the Computation of Fourier Transforms on Finite Groups, II Wed, 22 Apr 2020 21:33:01 +0000 https://doi.org/10.46298/dmtcs.6372 https://doi.org/10.46298/dmtcs.6372 Maslan, David Rockmore, Daniel N. Wolff, Sarah Maslan, David Rockmore, Daniel N. Wolff, Sarah 0 Some results on counting roots of polynomials and the Sylvester resultant. Wed, 22 Apr 2020 21:33:00 +0000 https://doi.org/10.46298/dmtcs.6371 https://doi.org/10.46298/dmtcs.6371 Monagan, Michael Tuncer, Baris Monagan, Michael Tuncer, Baris 0 Yang-Baxter basis of Hecke algebra and Casselman's problem (extended abstract) Wed, 22 Apr 2020 21:32:59 +0000 https://doi.org/10.46298/dmtcs.6370 https://doi.org/10.46298/dmtcs.6370 Nakasuji, Maki Naruse, Hiroshi Nakasuji, Maki Naruse, Hiroshi 0 Almost simplicial polytopes: the lower and upper bound theorems Wed, 22 Apr 2020 21:32:58 +0000 https://doi.org/10.46298/dmtcs.6369 https://doi.org/10.46298/dmtcs.6369 Nevo, Eran Pineda-Villavicencio, Guillermo Ugon, Julien Yost, David Nevo, Eran Pineda-Villavicencio, Guillermo Ugon, Julien Yost, David 0 Counting connected graphs with large excess Wed, 22 Apr 2020 21:32:57 +0000 https://doi.org/10.46298/dmtcs.6368 https://doi.org/10.46298/dmtcs.6368 De Panafieu, Élie De Panafieu, Élie 0 A noncommutative geometric LR rule Wed, 22 Apr 2020 21:32:56 +0000 https://doi.org/10.46298/dmtcs.6367 https://doi.org/10.46298/dmtcs.6367 Richmond, Edward Tewari, Vasu Van Willigenburg, Stephanie Richmond, Edward Tewari, Vasu Van Willigenburg, Stephanie 0 Relaxations of the matroid axioms I: Independence, Exchange and Circuits Wed, 22 Apr 2020 21:32:55 +0000 https://doi.org/10.46298/dmtcs.6365 https://doi.org/10.46298/dmtcs.6365 Samper, Jose ́ Alejandro Samper, Jose ́ Alejandro 0 Symmetric Fundamental Expansions to Schur Positivity Wed, 22 Apr 2020 21:32:55 +0000 https://doi.org/10.46298/dmtcs.6366 https://doi.org/10.46298/dmtcs.6366 Roberts, Austin Roberts, Austin 0 Strange Expectations and Simultaneous Cores Wed, 22 Apr 2020 21:32:54 +0000 https://doi.org/10.46298/dmtcs.6364 https://doi.org/10.46298/dmtcs.6364 Thiel, Marko Williams, Nathan Thiel, Marko Williams, Nathan 0 Elliptic rook and file numbers Wed, 22 Apr 2020 21:32:53 +0000 https://doi.org/10.46298/dmtcs.6362 https://doi.org/10.46298/dmtcs.6362 Schlosser, Michael J. Yoo, Meesue Schlosser, Michael J. Yoo, Meesue 0 Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices Wed, 22 Apr 2020 21:32:53 +0000 https://doi.org/10.46298/dmtcs.6363 https://doi.org/10.46298/dmtcs.6363 Mühle, Henri Mühle, Henri 0 A dual approach to structure constants for K-theory of Grassmannians Wed, 22 Apr 2020 21:32:52 +0000 https://doi.org/10.46298/dmtcs.6361 https://doi.org/10.46298/dmtcs.6361 Li, Huilan Morse, Jennifer Shields, Pat Li, Huilan Morse, Jennifer Shields, Pat 0 A Hopf algebra of subword complexes (Extended abstract) Wed, 22 Apr 2020 21:32:51 +0000 https://doi.org/10.46298/dmtcs.6359 https://doi.org/10.46298/dmtcs.6359 Bergeron, Nantel Ceballos, Cesar Bergeron, Nantel Ceballos, Cesar 0 McKay Centralizer Algebras Wed, 22 Apr 2020 21:32:51 +0000 https://doi.org/10.46298/dmtcs.6360 https://doi.org/10.46298/dmtcs.6360 Benkart, Georgia Halverson, Tom Benkart, Georgia Halverson, Tom 0 Tropical Ideals Wed, 22 Apr 2020 21:32:50 +0000 https://doi.org/10.46298/dmtcs.6358 https://doi.org/10.46298/dmtcs.6358 Maclagan, Diane Rincón, Felipe Maclagan, Diane Rincón, Felipe 0 Defining amplituhedra and Grassmann polytopes Wed, 22 Apr 2020 21:32:49 +0000 https://doi.org/10.46298/dmtcs.6356 https://doi.org/10.46298/dmtcs.6356 Karp, Steven N. Karp, Steven N. 0 Slicings of parallelogram polyominoes, or how Baxter and Schröder can be reconciled Wed, 22 Apr 2020 21:32:49 +0000 https://doi.org/10.46298/dmtcs.6357 https://doi.org/10.46298/dmtcs.6357 Bouvel, Mathilde Guerrini, Veronica Rinaldi, Simone Bouvel, Mathilde Guerrini, Veronica Rinaldi, Simone 0 Hook formulas for skew shapes Wed, 22 Apr 2020 21:32:48 +0000 https://doi.org/10.46298/dmtcs.6354 https://doi.org/10.46298/dmtcs.6354 Morales, Alejandro H. Pak, Igor Panova, Greta Morales, Alejandro H. Pak, Igor Panova, Greta 0 The topology of the external activity complex of a matroid Wed, 22 Apr 2020 21:32:48 +0000 https://doi.org/10.46298/dmtcs.6355 https://doi.org/10.46298/dmtcs.6355 Ardila, Federico Castillo, Federico Samper, Jose, Ardila, Federico Castillo, Federico Samper, Jose, 0 A two-sided analogue of the Coxeter complex Wed, 22 Apr 2020 21:32:47 +0000 https://doi.org/10.46298/dmtcs.6353 https://doi.org/10.46298/dmtcs.6353 Petersen, T. Kyle Petersen, T. Kyle 0 The Smith normal form distribution of a random integer matrix Wed, 22 Apr 2020 21:32:46 +0000 https://doi.org/10.46298/dmtcs.6352 https://doi.org/10.46298/dmtcs.6352 Wang, Yinghui Stanley, Richard P. Wang, Yinghui Stanley, Richard P. 0 On (non-) freeness of some tridendriform algebras Wed, 22 Apr 2020 21:32:45 +0000 https://doi.org/10.46298/dmtcs.6350 https://doi.org/10.46298/dmtcs.6350 Vong, Vincent Vong, Vincent 0 Cataland: Why the Fuss? Wed, 22 Apr 2020 21:32:45 +0000 https://doi.org/10.46298/dmtcs.6351 https://doi.org/10.46298/dmtcs.6351 Stump, Christian Thomas, Hugh Williams, Nathan Stump, Christian Thomas, Hugh Williams, Nathan 0 Rational Shi tableaux and the skew length statistic Wed, 22 Apr 2020 21:32:44 +0000 https://doi.org/10.46298/dmtcs.6349 https://doi.org/10.46298/dmtcs.6349 Sulzgruber, Robin Sulzgruber, Robin 0 On trees, tanglegrams, and tangled chains Wed, 22 Apr 2020 21:32:43 +0000 https://doi.org/10.46298/dmtcs.6348 https://doi.org/10.46298/dmtcs.6348 Billey, Sara, Konvalinka, Matjaz Matsen IV, Frderick, Billey, Sara, Konvalinka, Matjaz Matsen IV, Frderick, 0 Diagonally and antidiagonally symmetric alternating sign matrices of odd order Wed, 22 Apr 2020 21:32:42 +0000 https://doi.org/10.46298/dmtcs.6346 https://doi.org/10.46298/dmtcs.6346 Behrend, Roger, Fischer, Ilse Konvalinka, Matjaz Behrend, Roger, Fischer, Ilse Konvalinka, Matjaz 0 Parabolic double cosets in Coxeter groups Wed, 22 Apr 2020 21:32:42 +0000 https://doi.org/10.46298/dmtcs.6347 https://doi.org/10.46298/dmtcs.6347 Billey, Sara, Konvalinka, Matjaz Petersen, T. Kyle Slofstra, William Tenner, Bridget, Billey, Sara, Konvalinka, Matjaz Petersen, T. Kyle Slofstra, William Tenner, Bridget, 0 Cyclic inclusion-exclusion and the kernel of P -partitions Wed, 22 Apr 2020 21:32:41 +0000 https://doi.org/10.46298/dmtcs.6344 https://doi.org/10.46298/dmtcs.6344 Féray, Valentin Féray, Valentin 0 Plane partitions and the combinatorics of some families of reduced Kronecker coefficients. Wed, 22 Apr 2020 21:32:41 +0000 https://doi.org/10.46298/dmtcs.6345 https://doi.org/10.46298/dmtcs.6345 Colmenarejo, Laura Colmenarejo, Laura 0 Weak Separation, Pure Domains and Cluster Distance Wed, 22 Apr 2020 21:32:40 +0000 https://doi.org/10.46298/dmtcs.6343 https://doi.org/10.46298/dmtcs.6343 Farber, Miriam Galashin, Pavel Farber, Miriam Galashin, Pavel 0 The colored symmetric and exterior algebras Wed, 22 Apr 2020 21:32:39 +0000 https://doi.org/10.46298/dmtcs.6342 https://doi.org/10.46298/dmtcs.6342 Gonzalez D'Leon, Rafael S. Gonzalez D'Leon, Rafael S. 0 Parking functions, tree depth and factorizations of the full cycle into transpositions Wed, 22 Apr 2020 21:32:38 +0000 https://doi.org/10.46298/dmtcs.6340 https://doi.org/10.46298/dmtcs.6340 Irving, John Rattan, Amarpreet Irving, John Rattan, Amarpreet 0 Fully packed loop configurations : polynomiality and nested arches Wed, 22 Apr 2020 21:32:38 +0000 https://doi.org/10.46298/dmtcs.6341 https://doi.org/10.46298/dmtcs.6341 Aigner, Florian Aigner, Florian 0 Asymptotics of Bivariate Analytic Functions with Algebraic Singularities Wed, 22 Apr 2020 21:32:37 +0000 https://doi.org/10.46298/dmtcs.6339 https://doi.org/10.46298/dmtcs.6339 Greenwood, Torin Greenwood, Torin 0 Factorial Characters and Tokuyama's Identity for Classical Groups Wed, 22 Apr 2020 21:32:36 +0000 https://doi.org/10.46298/dmtcs.6338 https://doi.org/10.46298/dmtcs.6338 Hamel, Angèle M. King, Ronald C. Hamel, Angèle M. King, Ronald C. 0 Scheduling Problems and Generalized Graph Coloring Wed, 22 Apr 2020 21:32:35 +0000 https://doi.org/10.46298/dmtcs.6336 https://doi.org/10.46298/dmtcs.6336 Machacek, John Machacek, John 0 Symmetric matrices, Catalan paths, and correlations Wed, 22 Apr 2020 21:32:35 +0000 https://doi.org/10.46298/dmtcs.6337 https://doi.org/10.46298/dmtcs.6337 Tsukerman, Emmanuel Williams, Lauren Sturmfels, Bernd Tsukerman, Emmanuel Williams, Lauren Sturmfels, Bernd 0 The flag upper bound theorem for 3- and 5-manifolds Wed, 22 Apr 2020 21:32:34 +0000 https://doi.org/10.46298/dmtcs.6335 https://doi.org/10.46298/dmtcs.6335 Zheng, Hailun Zheng, Hailun 0 Quasisymmetric functions from combinatorial Hopf monoids and Ehrhart Theory Wed, 22 Apr 2020 21:32:33 +0000 https://doi.org/10.46298/dmtcs.6334 https://doi.org/10.46298/dmtcs.6334 White, Jacob, White, Jacob, 0 DHD-puzzles Wed, 22 Apr 2020 21:32:32 +0000 https://doi.org/10.46298/dmtcs.6332 https://doi.org/10.46298/dmtcs.6332 Beil, Sabine Beil, Sabine 0 A triple product formula for plane partitions derived from biorthogonal polynomials Wed, 22 Apr 2020 21:32:32 +0000 https://doi.org/10.46298/dmtcs.6333 https://doi.org/10.46298/dmtcs.6333 Kamioka, Shuhei Kamioka, Shuhei 0 A lattice point counting generalisation of the Tutte polynomial Wed, 22 Apr 2020 21:32:31 +0000 https://doi.org/10.46298/dmtcs.6331 https://doi.org/10.46298/dmtcs.6331 Cameron, Amanda Fink, Alex Cameron, Amanda Fink, Alex 0 Asymptotic laws for knot diagrams Wed, 22 Apr 2020 21:32:30 +0000 https://doi.org/10.46298/dmtcs.6329 https://doi.org/10.46298/dmtcs.6329 Chapman, Harrison Chapman, Harrison 0 Asymptotics of polygons in restricted geometries subject to a force 0 the force stretches the polygons, while when f < 0 the force is compressive. In this extended abstract we obtain and prove the asymptotic form of the free energy in the limit f → −∞. We conjecture that the f → −∞ asymptote is the same as the free energy of Hamiltonian polygons, which visit every vertex in a L × M × N box.]]> Wed, 22 Apr 2020 21:32:30 +0000 https://doi.org/10.46298/dmtcs.6330 https://doi.org/10.46298/dmtcs.6330 Beaton, Nicholas, Eng, Jeremy Soteros, Christine Beaton, Nicholas, Eng, Jeremy Soteros, Christine 0 the force stretches the polygons, while when f < 0 the force is compressive. In this extended abstract we obtain and prove the asymptotic form of the free energy in the limit f → −∞. We conjecture that the f → −∞ asymptote is the same as the free energy of Hamiltonian polygons, which visit every vertex in a L × M × N box.]]> 0 Non-representable hyperbolic matroids Wed, 22 Apr 2020 21:32:29 +0000 https://doi.org/10.46298/dmtcs.6328 https://doi.org/10.46298/dmtcs.6328 Amini, Nima Branden, Petter Amini, Nima Branden, Petter 0 A type B analog of the Lie representation Wed, 22 Apr 2020 21:32:28 +0000 https://doi.org/10.46298/dmtcs.6327 https://doi.org/10.46298/dmtcs.6327 Berget, Andrew Berget, Andrew 0 Combinatorial description of the cohomology of the affine flag variety Wed, 22 Apr 2020 21:32:27 +0000 https://doi.org/10.46298/dmtcs.6326 https://doi.org/10.46298/dmtcs.6326 Lee, Seung Jin Lee, Seung Jin 0 A non-partitionable Cohen–Macaulay simplicial complex Wed, 22 Apr 2020 21:32:26 +0000 https://doi.org/10.46298/dmtcs.6325 https://doi.org/10.46298/dmtcs.6325 Duval, Art M. Goeckner, Bennet Klivans, Caroline J. Martin, Jeremy Duval, Art M. Goeckner, Bennet Klivans, Caroline J. Martin, Jeremy 0 Decomposition of the product of a monomial and a Demazure atom Wed, 22 Apr 2020 21:32:25 +0000 https://doi.org/10.46298/dmtcs.6323 https://doi.org/10.46298/dmtcs.6323 Ying Pun, Anna Ying Pun, Anna 0 Fourientation activities and the Tutte polynomial Wed, 22 Apr 2020 21:32:25 +0000 https://doi.org/10.46298/dmtcs.6324 https://doi.org/10.46298/dmtcs.6324 Backman, Spencer Hopkins, Sam Traldi, Lorenzo Backman, Spencer Hopkins, Sam Traldi, Lorenzo 0 Kraskiewicz-Pragacz modules and Pieri and dual Pieri rules for Schubert polynomials Wed, 22 Apr 2020 21:32:24 +0000 https://doi.org/10.46298/dmtcs.6321 https://doi.org/10.46298/dmtcs.6321 Watanabe, Masaki Watanabe, Masaki 0 Cumulants of Jack symmetric functions and b-conjecture (extended abstract) Wed, 22 Apr 2020 21:32:24 +0000 https://doi.org/10.46298/dmtcs.6322 https://doi.org/10.46298/dmtcs.6322 Dolega, Maciej Féray, Valentin Dolega, Maciej Féray, Valentin 0 Rhombic alternative tableaux, assemblees of permutations, and the ASEP Wed, 22 Apr 2020 21:32:23 +0000 https://doi.org/10.46298/dmtcs.6320 https://doi.org/10.46298/dmtcs.6320 Mandelshtam, Olya Viennot, Xavier Mandelshtam, Olya Viennot, Xavier 0 Minimal factorizations of a cycle: a multivariate generating function Wed, 22 Apr 2020 21:32:22 +0000 https://doi.org/10.46298/dmtcs.6318 https://doi.org/10.46298/dmtcs.6318 Biane, Philippe Josuat-Vergès, Matthieu Biane, Philippe Josuat-Vergès, Matthieu 0 A combinatorial approach to Macdonald q, t-symmetry via the Carlitz bijection Wed, 22 Apr 2020 21:32:22 +0000 https://doi.org/10.46298/dmtcs.6319 https://doi.org/10.46298/dmtcs.6319 Gillespie, Maria Monks Gillespie, Maria Monks 0 Cayley graphs of basic algebraic structures Mon, 20 Apr 2020 07:16:02 +0000 https://doi.org/10.23638/DMTCS-21-1-16 https://doi.org/10.23638/DMTCS-21-1-16 Caucal, Didier Caucal, Didier 0 The super-connectivity of Johnson graphs Tue, 14 Apr 2020 09:13:25 +0000 https://doi.org/10.23638/DMTCS-22-1-12 https://doi.org/10.23638/DMTCS-22-1-12 Ekinci, Gülnaz Boruzanlı Gauci, John Baptist Ekinci, Gülnaz Boruzanlı Gauci, John Baptist 0 The Chromatic Number of the Disjointness Graph of the Double Chain Sun, 22 Mar 2020 08:58:41 +0000 https://doi.org/10.23638/DMTCS-22-1-11 https://doi.org/10.23638/DMTCS-22-1-11 Fabila-Monroy, Ruy Hidalgo-Toscano, Carlos Leaños, Jesús Lomelí-Haro, Mario Fabila-Monroy, Ruy Hidalgo-Toscano, Carlos Leaños, Jesús Lomelí-Haro, Mario 0 New tools for state complexity Mon, 16 Mar 2020 09:28:28 +0000 https://doi.org/10.23638/DMTCS-22-1-9 https://doi.org/10.23638/DMTCS-22-1-9 Caron, Pascal court, Edwin Hamel-De le Luque, Jean-Gabriel Patrou, Bruno Caron, Pascal court, Edwin Hamel-De le Luque, Jean-Gabriel Patrou, Bruno 0 A method for eternally dominating strong grids Mon, 16 Mar 2020 09:21:39 +0000 https://doi.org/10.23638/DMTCS-22-1-8 https://doi.org/10.23638/DMTCS-22-1-8 Gagnon, Alizée Hassler, Alexander Huang, Jerry Krim-Yee, Aaron Mc Inerney, Fionn Zacarías, Andrés, Seamone, Ben Virgile, Virgélot Gagnon, Alizée Hassler, Alexander Huang, Jerry Krim-Yee, Aaron Mc Inerney, Fionn Zacarías, Andrés, Seamone, Ben Virgile, Virgélot 0 The 3-way flower intersection problem for Steiner triple systems Mon, 16 Mar 2020 09:15:00 +0000 https://doi.org/10.23638/DMTCS-22-1-5 https://doi.org/10.23638/DMTCS-22-1-5 Amjadi, H. Soltankhah, N. Amjadi, H. Soltankhah, N. 0 The repetition threshold for binary rich words Mon, 24 Feb 2020 14:05:19 +0000 https://doi.org/10.23638/DMTCS-22-1-6 https://doi.org/10.23638/DMTCS-22-1-6 Currie, James D. Mol, Lucas Rampersad, Narad Currie, James D. Mol, Lucas Rampersad, Narad 0 Analysis of a Model for Generating Weakly Scale-free Networks k_{min} > 0$. Preferential attachment is the mechanism that has been considered responsible for such organization of these networks. In many real networks, degree distribution before the $k_{min}$ varies very slowly to the extent of being uniform as compared with the degree distribution for $k > k_{min}$ . In this paper, we proposed a model that describe this particular degree distribution for the whole range of $k>0$. We adopt a two step approach. In the first step, at every time stamp we add a new node to the network and attach it with an existing node using preferential attachment method. In the second step, we add edges between existing pairs of nodes with the node selection based on the uniform probability distribution. Our approach generates weakly scale-free networks that closely follow the degree distribution of real-world networks. We perform comprehensive mathematical analysis of the model in the discrete domain and compare the degree distribution generated by these models with that of real-world networks.]]> Mon, 24 Feb 2020 14:02:25 +0000 https://doi.org/10.23638/DMTCS-22-1-7 https://doi.org/10.23638/DMTCS-22-1-7 Anwar, Raheel Yousuf, Muhammad Irfan Abid, Muhammad Anwar, Raheel Yousuf, Muhammad Irfan Abid, Muhammad k_{min} > 0$. Preferential attachment is the mechanism that has been considered responsible for such organization of these networks. In many real networks, degree distribution before the $k_{min}$ varies very slowly to the extent of being uniform as compared with the degree distribution for $k > k_{min}$ . In this paper, we proposed a model that describe this particular degree distribution for the whole range of $k>0$. We adopt a two step approach. In the first step, at every time stamp we add a new node to the network and attach it with an existing node using preferential attachment method. In the second step, we add edges between existing pairs of nodes with the node selection based on the uniform probability distribution. Our approach generates weakly scale-free networks that closely follow the degree distribution of real-world networks. We perform comprehensive mathematical analysis of the model in the discrete domain and compare the degree distribution generated by these models with that of real-world networks.]]> 0 A Characterization of Morphic Words with Polynomial Growth Thu, 06 Feb 2020 16:00:08 +0000 https://doi.org/10.23638/DMTCS-22-1-3 https://doi.org/10.23638/DMTCS-22-1-3 Smith, Tim Smith, Tim 0 Statistics on Linear Chord Diagrams Thu, 23 Jan 2020 16:56:22 +0000 https://doi.org/10.23638/DMTCS-21-2-11 https://doi.org/10.23638/DMTCS-21-2-11 Cameron, Naiomi T. Killpatrick, Kendra Cameron, Naiomi T. Killpatrick, Kendra 0 On the Complexity of Digraph Colourings and Vertex Arboricity 1$. In this paper, we consider the complexity of corresponding decision problems for related notions of fractional colourings for digraphs and graphs, including the star dichromatic number, the fractional dichromatic number and the circular vertex arboricity. We prove the following results: Deciding if the star dichromatic number of a digraph is at most $p$ is NP-complete for every rational $p>1$. Deciding if the fractional dichromatic number of a digraph is at most $p$ is NP-complete for every $p>1, p \neq 2$. Deciding if the circular vertex arboricity of a graph is at most $p$ is NP-complete for every rational $p>1$. To show these results, different techniques are required in each case. In order to prove the first result, we relate the star dichromatic number to a new notion of homomorphisms between digraphs, called circular homomorphisms, which might be of independent interest. We provide a classification of the computational complexities of the corresponding homomorphism colouring problems similar to the one derived by Feder et al. for acyclic homomorphisms.]]> Tue, 21 Jan 2020 14:55:24 +0000 https://doi.org/10.23638/DMTCS-22-1-4 https://doi.org/10.23638/DMTCS-22-1-4 Hochstättler, Winfried Schröder, Felix Steiner, Raphael Hochstättler, Winfried Schröder, Felix Steiner, Raphael 1$. In this paper, we consider the complexity of corresponding decision problems for related notions of fractional colourings for digraphs and graphs, including the star dichromatic number, the fractional dichromatic number and the circular vertex arboricity. We prove the following results: Deciding if the star dichromatic number of a digraph is at most $p$ is NP-complete for every rational $p>1$. Deciding if the fractional dichromatic number of a digraph is at most $p$ is NP-complete for every $p>1, p \neq 2$. Deciding if the circular vertex arboricity of a graph is at most $p$ is NP-complete for every rational $p>1$. To show these results, different techniques are required in each case. In order to prove the first result, we relate the star dichromatic number to a new notion of homomorphisms between digraphs, called circular homomorphisms, which might be of independent interest. We provide a classification of the computational complexities of the corresponding homomorphism colouring problems similar to the one derived by Feder et al. for acyclic homomorphisms.]]> 0 From light edges to strong edge-colouring of 1-planar graphs Thu, 09 Jan 2020 09:24:43 +0000 https://doi.org/10.23638/DMTCS-22-1-2 https://doi.org/10.23638/DMTCS-22-1-2 Bensmail, Julien Dross, François Hocquard, Hervé Sopena, Eric Bensmail, Julien Dross, François Hocquard, Hervé Sopena, Eric 0 Vertex order with optimal number of adjacent predecessors Thu, 09 Jan 2020 09:13:29 +0000 https://doi.org/10.23638/DMTCS-22-1-1 https://doi.org/10.23638/DMTCS-22-1-1 Omer, Jérémy Migot, Tangi Omer, Jérémy Migot, Tangi 0 A code for square permutations and convex permutominoes Mon, 30 Dec 2019 12:31:35 +0000 https://doi.org/10.23638/DMTCS-21-2-2 https://doi.org/10.23638/DMTCS-21-2-2 Duchi, Enrica Duchi, Enrica 0 The undecidability of joint embedding and joint homomorphism for hereditary graph classes Fri, 13 Dec 2019 17:05:17 +0000 https://doi.org/10.23638/DMTCS-21-2-9 https://doi.org/10.23638/DMTCS-21-2-9 Braunfeld, Samuel Braunfeld, Samuel 0 Power domination in maximal planar graphs Fri, 13 Dec 2019 15:01:55 +0000 https://doi.org/10.23638/DMTCS-21-4-18 https://doi.org/10.23638/DMTCS-21-4-18 Dorbec, Paul González, Antonio Pennarun, Claire Dorbec, Paul González, Antonio Pennarun, Claire 0 Prolific Compositions Fri, 13 Dec 2019 14:57:51 +0000 https://doi.org/10.23638/DMTCS-21-2-10 https://doi.org/10.23638/DMTCS-21-2-10 Tannock, Murray Albert, Michael Tannock, Murray Albert, Michael 0 Cyclic permutations avoiding pairs of patterns of length three Tue, 26 Nov 2019 13:45:09 +0000 https://doi.org/10.23638/DMTCS-21-2-8 https://doi.org/10.23638/DMTCS-21-2-8 Bona, Miklos Cory, Michael Bona, Miklos Cory, Michael 0 Symmetry Properties of Nested Canalyzing Functions Tue, 26 Nov 2019 13:39:22 +0000 https://doi.org/10.23638/DMTCS-21-4-19 https://doi.org/10.23638/DMTCS-21-4-19 Rosenkrantz, Daniel J. Marathe, Madhav V. Ravi, S. S. Stearns, Richard E. Rosenkrantz, Daniel J. Marathe, Madhav V. Ravi, S. S. Stearns, Richard E. 0 Enumeration of super-strong Wilf equivalence classes of permutations in the generalized factor order Mon, 11 Nov 2019 11:12:23 +0000 https://doi.org/10.23638/DMTCS-21-2-3 https://doi.org/10.23638/DMTCS-21-2-3 Michos, Ioannis Savvidou, Christina Michos, Ioannis Savvidou, Christina 0 Generalized Petersen graphs and Kronecker covers Mon, 11 Nov 2019 10:41:35 +0000 https://doi.org/10.23638/DMTCS-21-4-15 https://doi.org/10.23638/DMTCS-21-4-15 Krnc, Matjaž Pisanski, Tomaž Krnc, Matjaž Pisanski, Tomaž 0 Equitable Coloring and Equitable Choosability of Planar Graphs without chordal 4- and 6-Cycles Mon, 11 Nov 2019 10:31:41 +0000 https://doi.org/10.23638/DMTCS-21-3-16 https://doi.org/10.23638/DMTCS-21-3-16 Dong, Aijun Wu, Jianliang Dong, Aijun Wu, Jianliang 0 Uniquely-Wilf classes Mon, 04 Nov 2019 12:58:27 +0000 https://doi.org/10.23638/DMTCS-21-2-7 https://doi.org/10.23638/DMTCS-21-2-7 Albert, Michael Li, Jinge Albert, Michael Li, Jinge 0 Consecutive Patterns in Inversion Sequences Mon, 04 Nov 2019 12:54:33 +0000 https://doi.org/10.23638/DMTCS-21-2-6 https://doi.org/10.23638/DMTCS-21-2-6 Auli, Juan S. Elizalde, Sergi Auli, Juan S. Elizalde, Sergi 0 On the number of pancake stacks requiring four flips to be sorted Mon, 04 Nov 2019 12:50:08 +0000 https://doi.org/10.23638/DMTCS-21-2-5 https://doi.org/10.23638/DMTCS-21-2-5 Blanco, Saúl A. Buehrle, Charles Patidar, Akshay Blanco, Saúl A. Buehrle, Charles Patidar, Akshay 0 Classical pattern distributions in $\mathcal{S}_{n}(132)$ and $\mathcal{S}_{n}(123)$ Mon, 04 Nov 2019 12:44:15 +0000 https://doi.org/10.23638/DMTCS-21-2-4 https://doi.org/10.23638/DMTCS-21-2-4 Qiu, Dun Remmel, Jeffrey Qiu, Dun Remmel, Jeffrey 0 An improved algorithm for the vertex cover $P_3$ problem on graphs of bounded treewidth Mon, 04 Nov 2019 12:32:49 +0000 https://doi.org/10.23638/DMTCS-21-4-17 https://doi.org/10.23638/DMTCS-21-4-17 Bai, Zongwen Tu, Jianhua Shi, Yongtang Bai, Zongwen Tu, Jianhua Shi, Yongtang 0 On the inducibility of small trees Thu, 17 Oct 2019 13:50:52 +0000 https://doi.org/10.23638/DMTCS-21-4-13 https://doi.org/10.23638/DMTCS-21-4-13 Dossou-Olory, Audace A. V. Wagner, Stephan Dossou-Olory, Audace A. V. Wagner, Stephan 0 Proofs of Conjectures about Pattern-Avoiding Linear Extensions Wed, 02 Oct 2019 07:52:20 +0000 https://doi.org/10.23638/DMTCS-21-4-16 https://doi.org/10.23638/DMTCS-21-4-16 Defant, Colin Defant, Colin 0 Monochromatic loose paths in multicolored $k$-uniform cliques 0$ such that for all $k\ge 2$, $\ell\ge3$, $2\le r\le k-1$, and $n\ge k(\ell+1)r(1+\ln(r))$, there is an algorithm such that for every $r$-edge-coloring of the edges of $K_n^{(k)}$, it finds a monochromatic copy of $P_\ell^{(k)}$ in time at most $cn^k$. We also prove a non-constructive upper bound $R(P_\ell^{(k)};r)\le(k-1)\ell r$.]]> Wed, 02 Oct 2019 07:45:10 +0000 https://doi.org/10.23638/DMTCS-21-4-7 https://doi.org/10.23638/DMTCS-21-4-7 Dudek, Andrzej Ruciński, Andrzej Dudek, Andrzej Ruciński, Andrzej 0$ such that for all $k\ge 2$, $\ell\ge3$, $2\le r\le k-1$, and $n\ge k(\ell+1)r(1+\ln(r))$, there is an algorithm such that for every $r$-edge-coloring of the edges of $K_n^{(k)}$, it finds a monochromatic copy of $P_\ell^{(k)}$ in time at most $cn^k$. We also prove a non-constructive upper bound $R(P_\ell^{(k)};r)\le(k-1)\ell r$.]]> 0 Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic Fri, 27 Sep 2019 12:13:40 +0000 https://doi.org/10.23638/DMTCS-21-4-14 https://doi.org/10.23638/DMTCS-21-4-14 Enami, Kengo Enami, Kengo 0 New results on classical and quantum counter automata Fri, 27 Sep 2019 11:34:14 +0000 https://doi.org/10.23638/DMTCS-21-4-12 https://doi.org/10.23638/DMTCS-21-4-12 Nakanishi, Masaki Yakaryılmaz, Abuzer Gainutdinova, Aida Nakanishi, Masaki Yakaryılmaz, Abuzer Gainutdinova, Aida 0 Expected size of a tree in the fixed point forest Fri, 27 Sep 2019 09:53:22 +0000 https://doi.org/10.23638/DMTCS-21-2-1 https://doi.org/10.23638/DMTCS-21-2-1 Regan, Samuel Slivken, Erik Regan, Samuel Slivken, Erik 0 Structure of conflict graphs in constraint alignment problems and algorithms Wed, 11 Sep 2019 07:18:44 +0000 https://doi.org/10.23638/DMTCS-21-4-10 https://doi.org/10.23638/DMTCS-21-4-10 Alkan, Ferhat Bıyıkoğlu, Türker Demange, Marc Erten, Cesim Alkan, Ferhat Bıyıkoğlu, Türker Demange, Marc Erten, Cesim 0 Constrained ear decompositions in graphs and digraphs Mon, 02 Sep 2019 09:47:42 +0000 https://doi.org/10.23638/DMTCS-21-4-3 https://doi.org/10.23638/DMTCS-21-4-3 Havet, Frédéric Nisse, Nicolas Havet, Frédéric Nisse, Nicolas 0 Clustered Spanning Tree - Conditions for Feasibility be a hypergraph, where V is a set of vertices and S is a set of not necessarily disjoint clusters Si ⊆ V. The Clustered Spanning Tree problem is to find a spanning tree of G which satisfies that each cluster induces a subtree, when it exists. We provide an efficient and unique algorithm which finds a feasible solution tree for H when it exists, or states that no feasible solution exists. The paper also uses special structures of the intersection graph of H to construct a feasible solution more efficiently. For cases when the hypergraph does not have a feasible solution tree, we consider adding vertices to exactly one cluster in order to gain feasibility. We characterize when such addition can gain feasibility, find the appropriate cluster and a possible set of vertices to be added.]]> Tue, 27 Aug 2019 13:55:09 +0000 https://doi.org/10.23638/DMTCS-21-1-15 https://doi.org/10.23638/DMTCS-21-1-15 Guttmann-Beck, Nili Sorek, Zeev Stern, Michal Guttmann-Beck, Nili Sorek, Zeev Stern, Michal be a hypergraph, where V is a set of vertices and S is a set of not necessarily disjoint clusters Si ⊆ V. The Clustered Spanning Tree problem is to find a spanning tree of G which satisfies that each cluster induces a subtree, when it exists. We provide an efficient and unique algorithm which finds a feasible solution tree for H when it exists, or states that no feasible solution exists. The paper also uses special structures of the intersection graph of H to construct a feasible solution more efficiently. For cases when the hypergraph does not have a feasible solution tree, we consider adding vertices to exactly one cluster in order to gain feasibility. We characterize when such addition can gain feasibility, find the appropriate cluster and a possible set of vertices to be added.]]> 0 On the centroid of increasing trees Tue, 27 Aug 2019 13:49:59 +0000 https://doi.org/10.23638/DMTCS-21-4-8 https://doi.org/10.23638/DMTCS-21-4-8 Durant, Kevin Wagner, Stephan Durant, Kevin Wagner, Stephan 0 Fractional matching preclusion for generalized augmented cubes Tue, 13 Aug 2019 06:56:59 +0000 https://doi.org/10.23638/DMTCS-21-4-6 https://doi.org/10.23638/DMTCS-21-4-6 Ma, Tianlong Mao, Yaping Cheng, Eddie Melekian, Christopher Ma, Tianlong Mao, Yaping Cheng, Eddie Melekian, Christopher 0 $(2/2/3)$-SAT problem and its applications in dominating set problems Mon, 12 Aug 2019 09:38:12 +0000 https://doi.org/10.23638/DMTCS-21-4-9 https://doi.org/10.23638/DMTCS-21-4-9 Ahadi, Arash Dehghan, Ali Ahadi, Arash Dehghan, Ali 0 On cordial labeling of hypertrees Wed, 07 Aug 2019 07:18:23 +0000 https://doi.org/10.23638/DMTCS-21-4-1 https://doi.org/10.23638/DMTCS-21-4-1 Tuczyński, Michał Wenus, Przemysław Węsek, Krzysztof Tuczyński, Michał Wenus, Przemysław Węsek, Krzysztof 0 Super edge-connectivity and matching preclusion of data center networks Tue, 30 Jul 2019 15:50:15 +0000 https://doi.org/10.23638/DMTCS-21-4-2 https://doi.org/10.23638/DMTCS-21-4-2 Lü, Huazhong Wu, Tingzeng Lü, Huazhong Wu, Tingzeng 0 Extremal properties of flood-filling games Tue, 30 Jul 2019 11:43:03 +0000 https://doi.org/10.23638/DMTCS-21-4-11 https://doi.org/10.23638/DMTCS-21-4-11 Meeks, Kitty Vu, Dominik K. Meeks, Kitty Vu, Dominik K. 0 On almost hypohamiltonian graphs Tue, 30 Jul 2019 11:39:03 +0000 https://doi.org/10.23638/DMTCS-21-4-5 https://doi.org/10.23638/DMTCS-21-4-5 Goedgebeur, Jan Zamfirescu, Carol T. Goedgebeur, Jan Zamfirescu, Carol T. 0 A note on the convexity number for complementary prisms Tue, 30 Jul 2019 11:30:12 +0000 https://doi.org/10.23638/DMTCS-21-4-4 https://doi.org/10.23638/DMTCS-21-4-4 Castonguay, Diane Coelho, Erika M. M. Coelho, Hebert Nascimento, Julliano R. Castonguay, Diane Coelho, Erika M. M. Coelho, Hebert Nascimento, Julliano R. 0 Backbone colouring and algorithms for TDMA scheduling Sat, 13 Jul 2019 12:04:12 +0000 https://doi.org/10.23638/DMTCS-21-3-24 https://doi.org/10.23638/DMTCS-21-3-24 Bensmail, Julien Blanc, Thibaut Cohen, Nathann Havet, Frédéric Rocha, Leonardo Bensmail, Julien Blanc, Thibaut Cohen, Nathann Havet, Frédéric Rocha, Leonardo 0 The maximum number of $P_\ell$ copies in $P_k$-free graphs Sat, 13 Jul 2019 08:02:11 +0000 https://doi.org/10.23638/DMTCS-21-1-14 https://doi.org/10.23638/DMTCS-21-1-14 Győri, Ervin Salia, Nika Tompkins, Casey Zamora, Oscar Győri, Ervin Salia, Nika Tompkins, Casey Zamora, Oscar 0 The Adaptive sampling revisited Tue, 25 Jun 2019 07:35:08 +0000 https://doi.org/10.23638/DMTCS-21-3-13 https://doi.org/10.23638/DMTCS-21-3-13 Drescher, Matthew Louchard, Guy Swan, Yvik Drescher, Matthew Louchard, Guy Swan, Yvik 0 On the multipacking number of grid graphs Thu, 20 Jun 2019 08:33:55 +0000 https://doi.org/10.23638/DMTCS-21-3-23 https://doi.org/10.23638/DMTCS-21-3-23 Beaudou, Laurent Brewster, Richard C. Beaudou, Laurent Brewster, Richard C. 0 On-line algorithms for multiplication and division in real and complex numeration systems 1$, and the digit set $A$ is a finite set of digits including $0$. Thus a number can be seen as a finite or infinite string of digits. An on-line algorithm processes the input piece-by-piece in a serial fashion. On-line arithmetic, introduced by Trivedi and Ercegovac, is a mode of computation where operands and results flow through arithmetic units in a digit serial manner, starting with the most significant digit. In this paper, we first formulate a generalized version of the on-line algorithms for multiplication and division of Trivedi and Ercegovac for the cases that $\beta$ is any real or complex number, and digits are real or complex. We then define the so-called OL Property, and show that if $(\beta, A)$ has the OL Property, then on-line multiplication and division are feasible by the Trivedi-Ercegovac algorithms. For a real base $\beta$ and a digit set $A$ of contiguous integers, the system $(\beta, A)$ has the OL Property if $\# A > |\beta|$. For a complex base $\beta$ and symmetric digit set $A$ of contiguous integers, the system $(\beta, A)$ has the OL Property if $\# A > \beta\overline{\beta} + |\beta + \overline{\beta}|$. Provided that addition and subtraction are realizable in parallel in the system $(\beta, A)$ and that preprocessing of the denominator is possible, our on-line algorithms for multiplication and division have linear time complexity. Three examples are presented in detail: base $\beta=\frac{3+\sqrt{5}}{2}$ with digits $A=\{-1,0,1\}$; base $\beta=2i$ with digits $A = \{-2,-1, 0,1,2\}$; and base $\beta = -\frac{3}{2} + i \frac{\sqrt{3}}{2} = -1 + \omega$, where $\omega = \exp{\frac{2i\pi}{3}}$, with digits $A = \{0, \pm 1, \pm \omega, \pm \omega^2 \}$.]]> Thu, 20 Jun 2019 08:29:32 +0000 https://doi.org/10.23638/DMTCS-21-3-14 https://doi.org/10.23638/DMTCS-21-3-14 Frougny, Christiane Pavelka, Marta Pelantova, Edita Svobodova, Milena Frougny, Christiane Pavelka, Marta Pelantova, Edita Svobodova, Milena 1$, and the digit set $A$ is a finite set of digits including $0$. Thus a number can be seen as a finite or infinite string of digits. An on-line algorithm processes the input piece-by-piece in a serial fashion. On-line arithmetic, introduced by Trivedi and Ercegovac, is a mode of computation where operands and results flow through arithmetic units in a digit serial manner, starting with the most significant digit. In this paper, we first formulate a generalized version of the on-line algorithms for multiplication and division of Trivedi and Ercegovac for the cases that $\beta$ is any real or complex number, and digits are real or complex. We then define the so-called OL Property, and show that if $(\beta, A)$ has the OL Property, then on-line multiplication and division are feasible by the Trivedi-Ercegovac algorithms. For a real base $\beta$ and a digit set $A$ of contiguous integers, the system $(\beta, A)$ has the OL Property if $\# A > |\beta|$. For a complex base $\beta$ and symmetric digit set $A$ of contiguous integers, the system $(\beta, A)$ has the OL Property if $\# A > \beta\overline{\beta} + |\beta + \overline{\beta}|$. Provided that addition and subtraction are realizable in parallel in the system $(\beta, A)$ and that preprocessing of the denominator is possible, our on-line algorithms for multiplication and division have linear time complexity. Three examples are presented in detail: base $\beta=\frac{3+\sqrt{5}}{2}$ with digits $A=\{-1,0,1\}$; base $\beta=2i$ with digits $A = \{-2,-1, 0,1,2\}$; and base $\beta = -\frac{3}{2} + i \frac{\sqrt{3}}{2} = -1 + \omega$, where $\omega = \exp{\frac{2i\pi}{3}}$, with digits $A = \{0, \pm 1, \pm \omega, \pm \omega^2 \}$.]]> 0 Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models Thu, 13 Jun 2019 13:58:53 +0000 https://doi.org/10.23638/DMTCS-21-3-20 https://doi.org/10.23638/DMTCS-21-3-20 Georgiou, Konstantinos Karakostas, George Kranakis, Evangelos Georgiou, Konstantinos Karakostas, George Kranakis, Evangelos 0 On the End-Vertex Problem of Graph Searches Thu, 13 Jun 2019 13:40:15 +0000 https://doi.org/10.23638/DMTCS-21-1-13 https://doi.org/10.23638/DMTCS-21-1-13 Beisegel, Jesse Denkert, Carolin Köhler, Ekkehard Krnc, Matjaž Pivač, Nevena Scheffler, Robert Strehler, Martin Beisegel, Jesse Denkert, Carolin Köhler, Ekkehard Krnc, Matjaž Pivač, Nevena Scheffler, Robert Strehler, Martin 0 Alternating Hamiltonian cycles in $2$-edge-colored multigraphs Thu, 13 Jun 2019 13:33:15 +0000 https://doi.org/10.23638/DMTCS-21-1-12 https://doi.org/10.23638/DMTCS-21-1-12 Contreras-Balbuena, Alejandro Galeana-Sánchez, Hortensia Goldfeder, Ilan A. Contreras-Balbuena, Alejandro Galeana-Sánchez, Hortensia Goldfeder, Ilan A. 0 Stable gonality is computable Thu, 13 Jun 2019 13:28:19 +0000 https://doi.org/10.23638/DMTCS-21-1-10 https://doi.org/10.23638/DMTCS-21-1-10 Koerkamp, Ragnar Groot van der Wegen, Marieke Koerkamp, Ragnar Groot van der Wegen, Marieke 0 Efficient enumeration of solutions produced by closure operations Thu, 13 Jun 2019 13:23:30 +0000 https://doi.org/10.23638/DMTCS-21-3-22 https://doi.org/10.23638/DMTCS-21-3-22 Mary, Arnaud Strozecki, Yann Mary, Arnaud Strozecki, Yann 0 Consecutive patterns in restricted permutations and involutions Wed, 05 Jun 2019 09:23:05 +0000 https://doi.org/10.23638/DMTCS-21-3-21 https://doi.org/10.23638/DMTCS-21-3-21 Barnabei, M. Bonetti, F. Castronuovo, N. Silimbani, M. Barnabei, M. Bonetti, F. Castronuovo, N. Silimbani, M. 0 Planar 3-SAT with a Clause/Variable Cycle Wed, 05 Jun 2019 09:16:09 +0000 https://doi.org/10.23638/DMTCS-21-3-18 https://doi.org/10.23638/DMTCS-21-3-18 Pilz, Alexander Pilz, Alexander 0 Bisplit graphs satisfy the Chen-Chvátal conjecture Wed, 29 May 2019 07:26:16 +0000 https://doi.org/10.23638/DMTCS-21-1-5 https://doi.org/10.23638/DMTCS-21-1-5 Beaudou, Laurent Kahn, Giacomo Rosenfeld, Matthieu Beaudou, Laurent Kahn, Giacomo Rosenfeld, Matthieu 0 New Bounds for the Dichromatic Number of a Digraph Thu, 23 May 2019 15:34:39 +0000 https://doi.org/10.23638/DMTCS-21-1-7 https://doi.org/10.23638/DMTCS-21-1-7 Cordero-Michel, Narda Galeana-Sánchez, Hortensia Cordero-Michel, Narda Galeana-Sánchez, Hortensia 0 Computing metric hulls in graphs Thu, 23 May 2019 13:14:19 +0000 https://doi.org/10.23638/DMTCS-21-1-11 https://doi.org/10.23638/DMTCS-21-1-11 Knauer, Kolja Nisse, Nicolas Knauer, Kolja Nisse, Nicolas 0 Characterising and recognising game-perfect graphs Thu, 23 May 2019 09:54:49 +0000 https://doi.org/10.23638/DMTCS-21-1-6 https://doi.org/10.23638/DMTCS-21-1-6 Andres, Dominique Lock, Edwin Andres, Dominique Lock, Edwin 0 The agreement distance of rooted phylogenetic networks Thu, 23 May 2019 09:16:07 +0000 https://doi.org/10.23638/DMTCS-21-3-19 https://doi.org/10.23638/DMTCS-21-3-19 Klawitter, Jonathan Klawitter, Jonathan 0 Non-crossing paths with geographic constraints Thu, 23 May 2019 09:12:53 +0000 https://doi.org/10.23638/DMTCS-21-3-15 https://doi.org/10.23638/DMTCS-21-3-15 Silveira, Rodrigo I. Speckmann, Bettina Verbeek, Kevin Silveira, Rodrigo I. Speckmann, Bettina Verbeek, Kevin 0 The 2-domination and Roman domination numbers of grid graphs Thu, 23 May 2019 09:08:17 +0000 https://doi.org/10.23638/DMTCS-21-1-9 https://doi.org/10.23638/DMTCS-21-1-9 Rao, Michaël Talon, Alexandre Rao, Michaël Talon, Alexandre 0 Parameterized Complexity of Equitable Coloring Thu, 16 May 2019 11:24:04 +0000 https://doi.org/10.23638/DMTCS-21-1-8 https://doi.org/10.23638/DMTCS-21-1-8 Gomes, Guilherme de C. M. Lima, Carlos V. G. C. Santos, Vinícius F. dos Gomes, Guilherme de C. M. Lima, Carlos V. G. C. Santos, Vinícius F. dos 0 Number of orbits of Discrete Interval Exchanges Thu, 16 May 2019 11:19:54 +0000 https://doi.org/10.23638/DMTCS-21-3-17 https://doi.org/10.23638/DMTCS-21-3-17 Lapointe, Mélodie Lapointe, Mélodie 0 Exact values for three domination-like problems in circular and infinite grid graphs of small height Thu, 16 May 2019 11:15:52 +0000 https://doi.org/10.23638/DMTCS-21-3-12 https://doi.org/10.23638/DMTCS-21-3-12 Bouznif, Marwane Darlay, Julien Moncel, Julien Preissmann, Myriam Bouznif, Marwane Darlay, Julien Moncel, Julien Preissmann, Myriam 0 On Stronger Types of Locating-dominating Codes Sat, 11 May 2019 10:10:31 +0000 https://doi.org/10.23638/DMTCS-21-1-1 https://doi.org/10.23638/DMTCS-21-1-1 Junnila, Ville Laihonen, Tero Lehtilä, Tuomo Puertas, María Luz Junnila, Ville Laihonen, Tero Lehtilä, Tuomo Puertas, María Luz 0 Some results on the palette index of graphs Sat, 11 May 2019 10:03:15 +0000 https://doi.org/10.23638/DMTCS-21-3-11 https://doi.org/10.23638/DMTCS-21-3-11 Casselgren, C. J. Petrosyan, Petros A. Casselgren, C. J. Petrosyan, Petros A. 0 FPT algorithms to recognize well covered graphs Tue, 02 Apr 2019 12:20:11 +0000 https://doi.org/10.23638/DMTCS-21-1-3 https://doi.org/10.23638/DMTCS-21-1-3 Araujo, Rafael Costa, Eurinardo Klein, Sulamita Sampaio, Rudini Souza, Ueverton S. Araujo, Rafael Costa, Eurinardo Klein, Sulamita Sampaio, Rudini Souza, Ueverton S. 0 On Weakly Distinguishing Graph Polynomials Tue, 02 Apr 2019 09:34:53 +0000 https://doi.org/10.23638/DMTCS-21-1-4 https://doi.org/10.23638/DMTCS-21-1-4 Makowsky, Johann A. Rakita, Vsevolod Makowsky, Johann A. Rakita, Vsevolod 0 A general decomposition theory for the 1-2-3 Conjecture and locally irregular decompositions Tue, 02 Apr 2019 09:27:40 +0000 https://doi.org/10.23638/DMTCS-21-1-2 https://doi.org/10.23638/DMTCS-21-1-2 Baudon, Olivier Bensmail, Julien Davot, Tom Hocquard, Hervé Przybyło, Jakub Senhaji, Mohammed Sopena, Eric Woźniak, Mariusz Baudon, Olivier Bensmail, Julien Davot, Tom Hocquard, Hervé Przybyło, Jakub Senhaji, Mohammed Sopena, Eric Woźniak, Mariusz 0 Bounds for the smallest $k$-chromatic graphs of given girth 5$. In particular, the new bounds include: $n_4(7) \leq 77$, $26 \leq n_6(4) \leq 66$, $30 \leq n_7(4) \leq 171$.]]> Mon, 11 Mar 2019 15:08:17 +0000 https://doi.org/10.23638/DMTCS-21-3-9 https://doi.org/10.23638/DMTCS-21-3-9 Exoo, Geoffrey Goedgebeur, Jan Exoo, Geoffrey Goedgebeur, Jan 5$. In particular, the new bounds include: $n_4(7) \leq 77$, $26 \leq n_6(4) \leq 66$, $30 \leq n_7(4) \leq 171$.]]> 0 Slimness of graphs Mon, 04 Mar 2019 15:04:50 +0000 https://doi.org/10.23638/DMTCS-21-3-10 https://doi.org/10.23638/DMTCS-21-3-10 Dragan, Feodor F. Mohammed, Abdulhakeem Dragan, Feodor F. Mohammed, Abdulhakeem 0 Packing chromatic vertex-critical graphs Mon, 18 Feb 2019 14:45:17 +0000 https://doi.org/10.23638/DMTCS-21-3-8 https://doi.org/10.23638/DMTCS-21-3-8 Klavžar, Sandi Rall, Douglas F. Klavžar, Sandi Rall, Douglas F. 0 Packing coloring of generalized Sierpinski graphs Fri, 08 Feb 2019 10:36:37 +0000 https://doi.org/10.23638/DMTCS-21-3-7 https://doi.org/10.23638/DMTCS-21-3-7 Korze, Danilo Vesel, Aleksander Korze, Danilo Vesel, Aleksander 0 On the insertion of n-powers Tue, 05 Feb 2019 15:08:07 +0000 https://doi.org/10.23638/DMTCS-21-3-5 https://doi.org/10.23638/DMTCS-21-3-5 Almeida, J. Klíma, O. Almeida, J. Klíma, O. 0 $K_{1,3}$-covering red and blue points in the plane 3b$, there are too many red points and at least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering. Furthermore, in all the cases we provide efficient algorithms to compute the corresponding coverings.]]> Thu, 31 Jan 2019 16:01:00 +0000 https://doi.org/10.23638/DMTCS-21-3-6 https://doi.org/10.23638/DMTCS-21-3-6 Ábrego, Bernardo M. Fernández-Merchant, Silvia Kano, Mikio Orden, David Pérez-Lantero, Pablo Seara, Carlos Tejel, Javier Ábrego, Bernardo M. Fernández-Merchant, Silvia Kano, Mikio Orden, David Pérez-Lantero, Pablo Seara, Carlos Tejel, Javier 3b$, there are too many red points and at least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering. Furthermore, in all the cases we provide efficient algorithms to compute the corresponding coverings.]]> 0 Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words Thu, 31 Jan 2019 15:49:43 +0000 https://doi.org/10.23638/DMTCS-21-3-4 https://doi.org/10.23638/DMTCS-21-3-4 Löding, Christof Spinrath, Christopher Löding, Christof Spinrath, Christopher 0 An output-sensitive Algorithm to partition a Sequence of Integers into Subsets with equal Sums Thu, 24 Jan 2019 15:36:20 +0000 https://doi.org/10.23638/DMTCS-20-2-18 https://doi.org/10.23638/DMTCS-20-2-18 Büchel, Alexander Gilleßen, Ulrich Witt, Kurt-Ulrich Büchel, Alexander Gilleßen, Ulrich Witt, Kurt-Ulrich 0 On the maximum number of minimum total dominating sets in forests Wed, 23 Jan 2019 10:30:07 +0000 https://doi.org/10.23638/DMTCS-21-3-3 https://doi.org/10.23638/DMTCS-21-3-3 Henning, Michael A. Mohr, Elena Rautenbach, Dieter Henning, Michael A. Mohr, Elena Rautenbach, Dieter 0 Binding Number, Toughness and General Matching Extendability in Graphs Thu, 17 Jan 2019 12:37:26 +0000 https://doi.org/10.23638/DMTCS-21-3-1 https://doi.org/10.23638/DMTCS-21-3-1 Lu, Hongliang Yu, Qinglin Lu, Hongliang Yu, Qinglin 0 Solving Two Conjectures regarding Codes for Location in Circulant Graphs Tue, 08 Jan 2019 15:00:19 +0000 https://doi.org/10.23638/DMTCS-21-3-2 https://doi.org/10.23638/DMTCS-21-3-2 Junnila, Ville Laihonen, Tero Paris, Gabrielle Junnila, Ville Laihonen, Tero Paris, Gabrielle 0 Sigma Partitioning: Complexity and Random Graphs Mon, 17 Dec 2018 14:39:19 +0000 https://doi.org/10.23638/DMTCS-20-2-19 https://doi.org/10.23638/DMTCS-20-2-19 Dehghan, Ali Sadeghi, Mohammad-Reza Ahadi, Arash Dehghan, Ali Sadeghi, Mohammad-Reza Ahadi, Arash 0 Solving the kernel perfect problem by (simple) forbidden subdigraphs for digraphs in some families of generalized tournaments and generalized bipartite tournaments Tue, 11 Dec 2018 09:24:21 +0000 https://doi.org/10.23638/DMTCS-20-2-16 https://doi.org/10.23638/DMTCS-20-2-16 Galeana-Sánchez, H. Olsen, M. Galeana-Sánchez, H. Olsen, M. 0 Pattern Avoidance for Random Permutations Tue, 04 Dec 2018 14:42:38 +0000 https://doi.org/10.23638/DMTCS-19-2-13 https://doi.org/10.23638/DMTCS-19-2-13 Crane, Harry DeSalvo, Stephen Crane, Harry DeSalvo, Stephen 0 Complexity of locally-injective homomorphisms to tournaments Fri, 30 Nov 2018 10:33:11 +0000 https://doi.org/10.23638/DMTCS-20-2-4 https://doi.org/10.23638/DMTCS-20-2-4 Bard, Stefan Bellitto, Thomas Duffy, Christopher MacGillivray, Gary Yang, Feiran Bard, Stefan Bellitto, Thomas Duffy, Christopher MacGillivray, Gary Yang, Feiran 0 Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs Tue, 20 Nov 2018 10:33:15 +0000 https://doi.org/10.23638/DMTCS-20-2-15 https://doi.org/10.23638/DMTCS-20-2-15 Protti, Fábio Souza, Uéverton S. Protti, Fábio Souza, Uéverton S. 0 On Almost Well-Covered Graphs of Girth at Least 6 Tue, 20 Nov 2018 10:28:34 +0000 https://doi.org/10.23638/DMTCS-20-2-17 https://doi.org/10.23638/DMTCS-20-2-17 Ekim, Tınaz Gözüpek, Didem Hujdurović, Ademir Milanič, Martin Ekim, Tınaz Gözüpek, Didem Hujdurović, Ademir Milanič, Martin 0 A Note on Flips in Diagonal Rectangulations Fri, 09 Nov 2018 14:34:53 +0000 https://doi.org/10.23638/DMTCS-20-2-14 https://doi.org/10.23638/DMTCS-20-2-14 Cardinal, Jean Sacristán, Vera Silveira, Rodrigo I. Cardinal, Jean Sacristán, Vera Silveira, Rodrigo I. 0 General bounds on limited broadcast domination Mon, 29 Oct 2018 16:37:28 +0000 https://doi.org/10.23638/DMTCS-20-2-13 https://doi.org/10.23638/DMTCS-20-2-13 Cáceres, José Hernando, Carmen Mora, Mercè Pelayo, Ignacio M. Puertas, María Luz Cáceres, José Hernando, Carmen Mora, Mercè Pelayo, Ignacio M. Puertas, María Luz 0 IMP with exceptions over decorated logic Mon, 29 Oct 2018 16:18:58 +0000 https://doi.org/10.23638/DMTCS-20-2-11 https://doi.org/10.23638/DMTCS-20-2-11 Ekici , Burak Ekici , Burak 0 Pattern Avoidance in Reverse Double Lists Mon, 29 Oct 2018 16:10:26 +0000 https://doi.org/10.23638/DMTCS-19-2-14 https://doi.org/10.23638/DMTCS-19-2-14 Anderson, Monica Diepenbroek, Marika Pudwell, Lara Stoll, Alex Anderson, Monica Diepenbroek, Marika Pudwell, Lara Stoll, Alex 0 The 26 Wilf-equivalence classes of length five quasi-consecutive patterns Wed, 24 Oct 2018 09:21:40 +0000 https://doi.org/10.23638/DMTCS-20-2-12 https://doi.org/10.23638/DMTCS-20-2-12 Chen, Evan Narayanan, Shyam Chen, Evan Narayanan, Shyam 0 Steiner Distance in Product Networks Tue, 23 Oct 2018 09:14:34 +0000 https://doi.org/10.23638/DMTCS-20-2-8 https://doi.org/10.23638/DMTCS-20-2-8 Mao, Yaping Cheng, Eddie Wang, Zhao Mao, Yaping Cheng, Eddie Wang, Zhao 0 Summation formulas for Fox-Wright function Mon, 22 Oct 2018 12:29:30 +0000 https://doi.org/10.23638/DMTCS-20-2-9 https://doi.org/10.23638/DMTCS-20-2-9 Wei, Chuanan Liu, Lily Li Gong, Dianxuan Wei, Chuanan Liu, Lily Li Gong, Dianxuan 0 Parameterized Power Vertex Cover Mon, 08 Oct 2018 13:44:44 +0000 https://doi.org/10.23638/DMTCS-20-2-10 https://doi.org/10.23638/DMTCS-20-2-10 Angel, Eric Bampis, Evripidis Escoffier, Bruno Lampis, Michael Angel, Eric Bampis, Evripidis Escoffier, Bruno Lampis, Michael 0 Fast strategies in biased Maker--Breaker games Mon, 08 Oct 2018 13:37:12 +0000 https://doi.org/10.23638/DMTCS-20-2-6 https://doi.org/10.23638/DMTCS-20-2-6 Mikalački, Mirjana Stojaković, Miloš Mikalački, Mirjana Stojaković, Miloš 0 On locally irregular decompositions and the 1-2 Conjecture in digraphs Mon, 01 Oct 2018 12:11:10 +0000 https://doi.org/10.23638/DMTCS-20-2-7 https://doi.org/10.23638/DMTCS-20-2-7 Baudon , Olivier Bensmail , Julien Przybyło , Jakub Woźniak , Mariusz Baudon , Olivier Bensmail , Julien Przybyło , Jakub Woźniak , Mariusz 0 Semitotal domination in trees Fri, 28 Sep 2018 15:11:41 +0000 https://doi.org/10.23638/DMTCS-20-2-5 https://doi.org/10.23638/DMTCS-20-2-5 Wei, Zhuang Guoliang, Hao Wei, Zhuang Guoliang, Hao 0 Convexity of tableau sets for type A Demazure characters (key polynomials), parabolic Catalan numbers Thu, 16 Aug 2018 08:27:14 +0000 https://doi.org/10.23638/DMTCS-20-2-3 https://doi.org/10.23638/DMTCS-20-2-3 Proctor, Robert A. Willis, Matthew J. Proctor, Robert A. Willis, Matthew J. 0 Quadrant marked mesh patterns in 123-avoiding permutations Fri, 03 Aug 2018 09:38:59 +0000 https://doi.org/10.23638/DMTCS-19-2-12 https://doi.org/10.23638/DMTCS-19-2-12 Qiu, Dun Remmel, Jeffrey B. Qiu, Dun Remmel, Jeffrey B. 0 Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent Tue, 31 Jul 2018 10:03:57 +0000 https://doi.org/10.23638/DMTCS-20-2-1 https://doi.org/10.23638/DMTCS-20-2-1 Highley, Timothy Le, Hoang Highley, Timothy Le, Hoang 0 On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width Tue, 31 Jul 2018 09:58:49 +0000 https://doi.org/10.23638/DMTCS-20-2-2 https://doi.org/10.23638/DMTCS-20-2-2 Rajaati, M. Hooshmandasl, M. R. Dinneen, M. J. Shakiba, A. Rajaati, M. Hooshmandasl, M. R. Dinneen, M. J. Shakiba, A. 0 Weighted Regular Tree Grammars with Storage Tue, 03 Jul 2018 14:54:58 +0000 https://doi.org/10.23638/DMTCS-20-1-26 https://doi.org/10.23638/DMTCS-20-1-26 Fülöp, Zoltán Herrmann, Luisa Vogler, Heiko Fülöp, Zoltán Herrmann, Luisa Vogler, Heiko 0 Group twin coloring of graphs Tue, 26 Jun 2018 15:14:31 +0000 https://doi.org/10.23638/DMTCS-20-1-24 https://doi.org/10.23638/DMTCS-20-1-24 Cichacz, Sylwia Przybyło, Jakub Cichacz, Sylwia Przybyło, Jakub 0 Expected Number of Distinct Subsequences in Randomly Generated Binary Strings Tue, 26 Jun 2018 09:19:47 +0000 https://doi.org/10.23638/DMTCS-19-2-10 https://doi.org/10.23638/DMTCS-19-2-10 Biers-Ariel, Yonah Godbole, Anant Kelley, Elizabeth Biers-Ariel, Yonah Godbole, Anant Kelley, Elizabeth 0 Continued fractions for permutation statistics Mon, 25 Jun 2018 09:08:15 +0000 https://doi.org/10.23638/DMTCS-19-2-11 https://doi.org/10.23638/DMTCS-19-2-11 Elizalde, Sergi Elizalde, Sergi 0 A Sufficient Condition for Graphic Sequences with Given Largest and Smallest Entries, Length, and Sum Mon, 25 Jun 2018 09:02:23 +0000 https://doi.org/10.23638/DMTCS-20-1-25 https://doi.org/10.23638/DMTCS-20-1-25 Cloteaux, Brian Cloteaux, Brian 0 On a Class of Graphs with Large Total Domination Number Mon, 04 Jun 2018 08:37:11 +0000 https://doi.org/10.23638/DMTCS-20-1-23 https://doi.org/10.23638/DMTCS-20-1-23 Bahadır, Selim Gözüpek, Didem Bahadır, Selim Gözüpek, Didem 0 Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs 0$ unless P = NP. We then turn our attention to block graphs, which also form a subclass of chordal graphs. We determine the strong rainbow connection number of block graphs, and show it can be computed in linear time. Finally, we provide a polynomial-time characterization of bridgeless block graphs with rainbow connection number at most 4.]]> Mon, 04 Jun 2018 08:30:35 +0000 https://doi.org/10.23638/DMTCS-20-1-22 https://doi.org/10.23638/DMTCS-20-1-22 Keranen, Melissa Lauri, Juho Keranen, Melissa Lauri, Juho 0$ unless P = NP. We then turn our attention to block graphs, which also form a subclass of chordal graphs. We determine the strong rainbow connection number of block graphs, and show it can be computed in linear time. Finally, we provide a polynomial-time characterization of bridgeless block graphs with rainbow connection number at most 4.]]> 0 On neighbour sum-distinguishing $\{0,1\}$-edge-weightings of bipartite graphs Mon, 04 Jun 2018 08:27:12 +0000 https://doi.org/10.23638/DMTCS-20-1-21 https://doi.org/10.23638/DMTCS-20-1-21 Lyngsie, Kasper Szabo Lyngsie, Kasper Szabo 0 Permutation complexity of images of Sturmian words by marked morphisms Mon, 04 Jun 2018 08:22:33 +0000 https://doi.org/10.23638/DMTCS-20-1-20 https://doi.org/10.23638/DMTCS-20-1-20 Borchert, Adam Rampersad, Narad Borchert, Adam Rampersad, Narad 0 Forbidden subgraphs for constant domination number Mon, 04 Jun 2018 08:19:22 +0000 https://doi.org/10.23638/DMTCS-20-1-19 https://doi.org/10.23638/DMTCS-20-1-19 Furuya, Michitaka Furuya, Michitaka 0 Proof of a local antimagic conjecture Mon, 04 Jun 2018 08:15:49 +0000 https://doi.org/10.23638/DMTCS-20-1-18 https://doi.org/10.23638/DMTCS-20-1-18 Haslegrave, John Haslegrave, John 0 Weakly threshold graphs 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 of the weakly threshold sequences. The weakly threshold graphs properly include the threshold graphs and satisfy pleasing extensions of many properties of threshold graphs. We demonstrate a majorization property of weakly threshold sequences and an iterative construction algorithm for weakly threshold graphs, as well as a forbidden induced subgraph characterization. We conclude by exactly enumerating weakly threshold sequences and graphs.]]> Mon, 04 Jun 2018 08:08:17 +0000 https://doi.org/10.23638/DMTCS-20-1-15 https://doi.org/10.23638/DMTCS-20-1-15 Barrus, Michael D. Barrus, Michael D. 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 of the weakly threshold sequences. The weakly threshold graphs properly include the threshold graphs and satisfy pleasing extensions of many properties of threshold graphs. We demonstrate a majorization property of weakly threshold sequences and an iterative construction algorithm for weakly threshold graphs, as well as a forbidden induced subgraph characterization. We conclude by exactly enumerating weakly threshold sequences and graphs.]]> 0 Rowmotion and generalized toggle groups Fri, 25 May 2018 15:04:47 +0000 https://doi.org/10.23638/DMTCS-20-1-17 https://doi.org/10.23638/DMTCS-20-1-17 Striker, Jessica Striker, Jessica 0 Annular and pants thrackles Fri, 25 May 2018 14:59:37 +0000 https://doi.org/10.23638/DMTCS-20-1-16 https://doi.org/10.23638/DMTCS-20-1-16 Misereh, Grace Nikolayevsky, Yuri Misereh, Grace Nikolayevsky, Yuri 0 A Linear Kernel for Planar Total Dominating Set Wed, 16 May 2018 14:19:58 +0000 https://doi.org/10.23638/DMTCS-20-1-14 https://doi.org/10.23638/DMTCS-20-1-14 Garnero, Valentin Sau, Ignasi Garnero, Valentin Sau, Ignasi 0 On interval number in cycle convexity Mon, 07 May 2018 08:26:53 +0000 https://doi.org/10.23638/DMTCS-20-1-13 https://doi.org/10.23638/DMTCS-20-1-13 Araujo , Julio Ducoffe , Guillaume Nisse , Nicolas Suchan , Karol Araujo , Julio Ducoffe , Guillaume Nisse , Nicolas Suchan , Karol 0 A Central Limit Theorem for Vincular Permutation Patterns Mon, 26 Mar 2018 09:21:09 +0000 https://doi.org/10.23638/DMTCS-19-2-9 https://doi.org/10.23638/DMTCS-19-2-9 Hofer, Lisa Hofer, Lisa 0 Non-adaptive Group Testing on Graphs Mon, 26 Mar 2018 09:13:44 +0000 https://doi.org/10.23638/DMTCS-20-1-9 https://doi.org/10.23638/DMTCS-20-1-9 Kameli, Hamid Kameli, Hamid 0 Protected node profile of Tries Mon, 26 Mar 2018 09:04:02 +0000 https://doi.org/10.23638/DMTCS-20-1-12 https://doi.org/10.23638/DMTCS-20-1-12 Javanian, Mehri Javanian, Mehri 0 Asymptotic results on Klazar set partition avoidance Mon, 19 Mar 2018 10:02:07 +0000 https://doi.org/10.23638/DMTCS-19-2-7 https://doi.org/10.23638/DMTCS-19-2-7 Alweiss, Ryan Alweiss, Ryan 0 On subtrees of the representation tree in rational base numeration systems Mon, 05 Mar 2018 08:53:22 +0000 https://doi.org/10.23638/DMTCS-20-1-10 https://doi.org/10.23638/DMTCS-20-1-10 Akiyama, Shigeki Marsault, Victor Sakarovitch, Jacques Akiyama, Shigeki Marsault, Victor Sakarovitch, Jacques 0 Finding Hamilton cycles in random intersection graphs Mon, 05 Mar 2018 08:48:23 +0000 https://doi.org/10.23638/DMTCS-20-1-8 https://doi.org/10.23638/DMTCS-20-1-8 Rybarczyk, Katarzyna Rybarczyk, Katarzyna 0 Growing and Destroying Catalan-Stanley Trees Wed, 28 Feb 2018 15:37:21 +0000 https://doi.org/10.23638/DMTCS-20-1-11 https://doi.org/10.23638/DMTCS-20-1-11 Hackl, Benjamin Prodinger, Helmut Hackl, Benjamin Prodinger, Helmut 0 On consecutive pattern-avoiding permutations of length 4, 5 and beyond Mon, 26 Feb 2018 09:53:53 +0000 https://doi.org/10.23638/DMTCS-19-2-8 https://doi.org/10.23638/DMTCS-19-2-8 Beaton, Nicholas R Conway, Andrew R Guttmann, Anthony J Beaton, Nicholas R Conway, Andrew R Guttmann, Anthony J 0 Equivalence classes of mesh patterns with a dominating pattern Fri, 09 Feb 2018 09:58:50 +0000 https://doi.org/10.23638/DMTCS-19-2-6 https://doi.org/10.23638/DMTCS-19-2-6 Tannock, Murray Ulfarsson, Henning Tannock, Murray Ulfarsson, Henning 0 Improving bounds on packing densities of 4-point permutations Tue, 06 Feb 2018 16:39:16 +0000 https://doi.org/10.23638/DMTCS-19-2-3 https://doi.org/10.23638/DMTCS-19-2-3 Sliacan, Jakub Stromquist, Walter Sliacan, Jakub Stromquist, Walter 0 A Study of $k$-dipath Colourings of Oriented Graphs Thu, 01 Feb 2018 13:42:05 +0000 https://doi.org/10.23638/DMTCS-20-1-6 https://doi.org/10.23638/DMTCS-20-1-6 Duffy, Christopher MacGillivray, Gary Sopena, Éric Duffy, Christopher MacGillivray, Gary Sopena, Éric 0 Weak embeddings of posets to the Boolean lattice Wed, 24 Jan 2018 13:06:55 +0000 https://doi.org/10.23638/DMTCS-20-1-7 https://doi.org/10.23638/DMTCS-20-1-7 Pálvölgyi, Dömötör Pálvölgyi, Dömötör 0 A bijection between the set of nesting-similarity classes and L & P matchings Mon, 22 Jan 2018 07:55:56 +0000 https://doi.org/10.23638/DMTCS-19-2-1 https://doi.org/10.23638/DMTCS-19-2-1 Martinez, Megan A. Riehl, Manda Martinez, Megan A. Riehl, Manda 0 Hitting minors, subdivisions, and immersions in tournaments Wed, 17 Jan 2018 08:38:58 +0000 https://doi.org/10.23638/DMTCS-20-1-5 https://doi.org/10.23638/DMTCS-20-1-5 Raymond, Jean-Florent Raymond, Jean-Florent 0 A Variation on Chip-Firing: the diffusion game Wed, 17 Jan 2018 08:30:10 +0000 https://doi.org/10.23638/DMTCS-20-1-4 https://doi.org/10.23638/DMTCS-20-1-4 Duffy, C. Lidbetter, T. F. Messinger, M. E. Nowakowski, R. J. Duffy, C. Lidbetter, T. F. Messinger, M. E. Nowakowski, R. J. 0 Three matching intersection property for matching covered graphs Mon, 15 Jan 2018 10:43:15 +0000 https://doi.org/10.23638/DMTCS-19-3-16 https://doi.org/10.23638/DMTCS-19-3-16 Lin, Hao Wang, Xiumei Lin, Hao Wang, Xiumei 0 On Minimum Maximal Distance-k Matchings Thu, 11 Jan 2018 13:10:17 +0000 https://doi.org/10.23638/DMTCS-20-1-3 https://doi.org/10.23638/DMTCS-20-1-3 Kartynnik, Yury Ryzhikov, Andrew Kartynnik, Yury Ryzhikov, Andrew 0 Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II is a 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 by the 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, we define two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterize the representations of ENPT holes that satisfy (P1), (P2), (P3). In this work, we continue our work by relaxing these three assumptions one by one. We characterize the representations of ENPT holes satisfying (P3) by providing a polynomial-time algorithm to solve P3-HamiltonianPairRec. We also show that there does not exist a polynomial-time algorithm to solve HamiltonianPairRec, unless P=NP.]]> Thu, 11 Jan 2018 12:36:58 +0000 https://doi.org/10.23638/DMTCS-20-1-2 https://doi.org/10.23638/DMTCS-20-1-2 Boyacı, Arman Ekim, Tınaz Shalom, Mordechai Zaks, Shmuel Boyacı, Arman Ekim, Tınaz Shalom, Mordechai Zaks, Shmuel is a 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 by the 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, we define two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterize the representations of ENPT holes that satisfy (P1), (P2), (P3). In this work, we continue our work by relaxing these three assumptions one by one. We characterize the representations of ENPT holes satisfying (P3) by providing a polynomial-time algorithm to solve P3-HamiltonianPairRec. We also show that there does not exist a polynomial-time algorithm to solve HamiltonianPairRec, unless P=NP.]]> 0 Monotone Simultaneous Paths Embeddings in $\mathbb{R}^d$ Fri, 05 Jan 2018 10:41:38 +0000 https://doi.org/10.23638/DMTCS-20-1-1 https://doi.org/10.23638/DMTCS-20-1-1 Bremner, David Devillers, Olivier Glisse, Marc Lazard, Sylvain Liotta, Giuseppe Mchedlidze, Tamara Moroz, Guillaume Whitesides, Sue Wismath, Stephen Bremner, David Devillers, Olivier Glisse, Marc Lazard, Sylvain Liotta, Giuseppe Mchedlidze, Tamara Moroz, Guillaume Whitesides, Sue Wismath, Stephen 0 Best and worst case permutations for random online domination of the path Wed, 20 Dec 2017 10:48:15 +0000 https://doi.org/10.23638/DMTCS-19-2-2 https://doi.org/10.23638/DMTCS-19-2-2 Coscia, Christopher DeWitt, Jonathan Yang, Fan Zhang, Yiguang Coscia, Christopher DeWitt, Jonathan Yang, Fan Zhang, Yiguang 0 Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts Wed, 20 Dec 2017 10:43:45 +0000 https://doi.org/10.23638/DMTCS-19-3-17 https://doi.org/10.23638/DMTCS-19-3-17 Cornet, Alexis Laforest, Christian Cornet, Alexis Laforest, Christian 0 Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations Wed, 20 Dec 2017 10:33:20 +0000 https://doi.org/10.23638/DMTCS-19-4-3 https://doi.org/10.23638/DMTCS-19-4-3 Bougeret, Marin Duvillié, Guillerme Giroudeau, Rodolphe Watrigant, Rémi Bougeret, Marin Duvillié, Guillerme Giroudeau, Rodolphe Watrigant, Rémi 0 Asymptotic distribution of fixed points of pattern-avoiding involutions Mon, 11 Dec 2017 12:37:42 +0000 https://doi.org/10.23638/DMTCS-19-2-5 https://doi.org/10.23638/DMTCS-19-2-5 Miner, Samuel Rizzolo, Douglas Slivken, Erik Miner, Samuel Rizzolo, Douglas Slivken, Erik 0 A Characterization for Decidable Separability by Piecewise Testable Languages Mon, 11 Dec 2017 10:46:30 +0000 https://doi.org/10.23638/DMTCS-19-4-1 https://doi.org/10.23638/DMTCS-19-4-1 Czerwiński, Wojciech Martens, Wim van Rooijen, Lorijn Zeitoun, Marc Zetzsche, Georg Czerwiński, Wojciech Martens, Wim van Rooijen, Lorijn Zeitoun, Marc Zetzsche, Georg 0 Splittability and 1-amalgamability of permutation classes Tue, 05 Dec 2017 09:56:28 +0000 https://doi.org/10.23638/DMTCS-19-2-4 https://doi.org/10.23638/DMTCS-19-2-4 Jelínek, Vít Opler, Michal Jelínek, Vít Opler, Michal 0 Parabolic Catalan numbers count flagged Schur functions and their appearances as type A Demazure characters (key polynomials) Tue, 05 Dec 2017 09:50:02 +0000 https://doi.org/10.23638/DMTCS-19-3-15 https://doi.org/10.23638/DMTCS-19-3-15 Proctor, Robert A. Willis, Matthew J. Proctor, Robert A. Willis, Matthew J. 0 Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps Thu, 30 Nov 2017 16:05:03 +0000 https://doi.org/10.23638/DMTCS-19-3-14 https://doi.org/10.23638/DMTCS-19-3-14 Devismes, Stéphane Ilcinkas, David Johnen, Colette Devismes, Stéphane Ilcinkas, David Johnen, Colette 0 Periodic balanced binary triangles Tue, 28 Nov 2017 19:32:42 +0000 https://doi.org/10.23638/DMTCS-19-3-13 https://doi.org/10.23638/DMTCS-19-3-13 Chappelon, Jonathan Chappelon, Jonathan 0 Witness structures and immediate snapshot complexes Tue, 28 Nov 2017 10:19:21 +0000 https://doi.org/10.23638/DMTCS-19-3-12 https://doi.org/10.23638/DMTCS-19-3-12 Kozlov, Dmitry N. Kozlov, Dmitry N. 0 A sufficient condition for a balanced bipartite digraph to be hamiltonian Fri, 10 Nov 2017 12:31:54 +0000 https://doi.org/10.23638/DMTCS-19-3-11 https://doi.org/10.23638/DMTCS-19-3-11 Wang, Ruixia Wang, Ruixia 0 Circular Separation Dimension of a Subclass of Planar Graphs Fri, 03 Nov 2017 12:57:46 +0000 https://doi.org/10.23638/DMTCS-19-3-8 https://doi.org/10.23638/DMTCS-19-3-8 Bharathi, Arpitha P. De, Minati Lahiri, Abhiruk Bharathi, Arpitha P. De, Minati Lahiri, Abhiruk 0 Depth, Highness and DNR degrees Thu, 26 Oct 2017 08:22:26 +0000 https://doi.org/10.23638/DMTCS-19-4-2 https://doi.org/10.23638/DMTCS-19-4-2 Moser, Philippe Stephan, Frank Moser, Philippe Stephan, Frank 0 On path-cycle decompositions of triangle-free graphs Thu, 26 Oct 2017 08:17:39 +0000 https://doi.org/10.23638/DMTCS-19-3-7 https://doi.org/10.23638/DMTCS-19-3-7 Jiménez, Andrea Wakabayashi, Yoshiko Jiménez, Andrea Wakabayashi, Yoshiko 0 Tight upper bound on the maximum anti-forcing numbers of graphs Tue, 17 Oct 2017 09:07:09 +0000 https://doi.org/10.23638/DMTCS-19-3-9 https://doi.org/10.23638/DMTCS-19-3-9 Shi, Lingjuan Zhang, Heping Shi, Lingjuan Zhang, Heping 0 Longest Gapped Repeats and Palindromes Fri, 13 Oct 2017 12:32:21 +0000 https://doi.org/10.23638/DMTCS-19-4-4 https://doi.org/10.23638/DMTCS-19-4-4 Dumitran, Marius Gawrychowski, Paweł Manea, Florin Dumitran, Marius Gawrychowski, Paweł Manea, Florin 0 On rank-width of even-hole-free graphs Thu, 05 Oct 2017 11:39:06 +0000 https://doi.org/10.23638/DMTCS-19-1-24 https://doi.org/10.23638/DMTCS-19-1-24 Adler, Isolde Le, Ngoc Khang Müller, Haiko Radovanović, Marko Trotignon, Nicolas Vušković, Kristina Adler, Isolde Le, Ngoc Khang Müller, Haiko Radovanović, Marko Trotignon, Nicolas Vušković, Kristina 0 Binary Codes and Period-2 Orbits of Sequential Dynamical Systems Tue, 03 Oct 2017 09:40:34 +0000 https://doi.org/10.23638/DMTCS-19-3-10 https://doi.org/10.23638/DMTCS-19-3-10 Defant, Colin Defant, Colin 0 Lattice paths with catastrophes Fri, 29 Sep 2017 14:58:21 +0000 https://doi.org/10.23638/DMTCS-19-1-23 https://doi.org/10.23638/DMTCS-19-1-23 Banderier, Cyril Wallner, Michael Banderier, Cyril Wallner, Michael 0 Irreversible 2-conversion set in graphs of bounded degree Tue, 26 Sep 2017 11:54:32 +0000 https://doi.org/10.23638/DMTCS-19-3-5 https://doi.org/10.23638/DMTCS-19-3-5 Kynčl, Jan Lidický, Bernard Vyskočil, Tomáš Kynčl, Jan Lidický, Bernard Vyskočil, Tomáš 0 Inkdots as advice for finite automata Tue, 26 Sep 2017 11:50:45 +0000 https://doi.org/10.23638/DMTCS-19-3-1 https://doi.org/10.23638/DMTCS-19-3-1 Küçük, Uğur Say, A. C. Cem Yakaryılmaz, Abuzer Küçük, Uğur Say, A. C. Cem Yakaryılmaz, Abuzer 0 Refined Enumeration of Corners in Tree-like Tableaux Tue, 26 Sep 2017 11:47:44 +0000 https://doi.org/10.23638/DMTCS-19-3-6 https://doi.org/10.23638/DMTCS-19-3-6 Yan, Sherry H. F. Zhou, Robin D. P. Yan, Sherry H. F. Zhou, Robin D. P. 0 Tight Euler tours in uniform hypergraphs - computational aspects Tue, 26 Sep 2017 11:43:07 +0000 https://doi.org/10.23638/DMTCS-19-3-2 https://doi.org/10.23638/DMTCS-19-3-2 Lonc, Zbigniew Naroski, Paweł Rzążewski, Paweł Lonc, Zbigniew Naroski, Paweł Rzążewski, Paweł 0 Stammering tableaux Fri, 15 Sep 2017 11:36:00 +0000 https://doi.org/10.23638/DMTCS-19-3-3 https://doi.org/10.23638/DMTCS-19-3-3 Josuat-Vergès, Matthieu Josuat-Vergès, Matthieu 0 Post-surjectivity and balancedness of cellular automata over groups Fri, 15 Sep 2017 11:30:58 +0000 https://doi.org/10.23638/DMTCS-19-3-4 https://doi.org/10.23638/DMTCS-19-3-4 Capobianco, Silvio Kari, Jarkko Taati, Siamak Capobianco, Silvio Kari, Jarkko Taati, Siamak 0 Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs Wed, 30 Aug 2017 13:49:35 +0000 https://doi.org/10.23638/DMTCS-19-1-25 https://doi.org/10.23638/DMTCS-19-1-25 Gözüpek, Didem Hujdurović, Ademir Milanič, Martin Gözüpek, Didem Hujdurović, Ademir Milanič, Martin 0 On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture Tue, 08 Aug 2017 10:14:00 +0000 https://doi.org/10.23638/DMTCS-19-1-21 https://doi.org/10.23638/DMTCS-19-1-21 Bensmail, Julien Senhaji, Mohammed Szabo Lyngsie, Kasper Bensmail, Julien Senhaji, Mohammed Szabo Lyngsie, Kasper 0 Asymptotics of the occupancy scheme in a random environment and its applications to tries Fri, 04 Aug 2017 18:31:07 +0000 https://doi.org/10.23638/DMTCS-19-1-22 https://doi.org/10.23638/DMTCS-19-1-22 Businger, Silvia Businger, Silvia 0 Rises in forests of binary shrubs Wed, 19 Jul 2017 09:55:50 +0000 https://doi.org/10.23638/DMTCS-19-1-15 https://doi.org/10.23638/DMTCS-19-1-15 Remmel, Jeffrey Zheng, Sai-nan Remmel, Jeffrey Zheng, Sai-nan 0 A Bijection on Classes Enumerated by the Schröder Numbers Wed, 19 Jul 2017 09:46:44 +0000 https://doi.org/10.46298/dmtcs.1326 https://doi.org/10.46298/dmtcs.1326 Schroeder, Michael W. Smith, Rebecca Schroeder, Michael W. Smith, Rebecca 0 Evaluations of series of the $q$-Watson, $q$-Dixon, and $q$-Whipple type Tue, 27 Jun 2017 08:30:43 +0000 https://doi.org/10.23638/DMTCS-19-1-19 https://doi.org/10.23638/DMTCS-19-1-19 Wei, Chuanan Wang, Xiaoxia Wei, Chuanan Wang, Xiaoxia 0 Nonrepetitive edge-colorings of trees Tue, 27 Jun 2017 08:27:45 +0000 https://doi.org/10.23638/DMTCS-19-1-18 https://doi.org/10.23638/DMTCS-19-1-18 Kündgen, A. Talbot, T. Kündgen, A. Talbot, T. 0 Equivalence of the filament and overlap graphs of subtrees of limited trees Tue, 20 Jun 2017 09:37:51 +0000 https://doi.org/10.23638/DMTCS-19-1-20 https://doi.org/10.23638/DMTCS-19-1-20 Enright, Jessica Stewart, Lorna Enright, Jessica Stewart, Lorna 0 Composing short 3-compressing words on a 2-letter alphabet Tue, 20 Jun 2017 09:34:52 +0000 https://doi.org/10.23638/DMTCS-19-1-17 https://doi.org/10.23638/DMTCS-19-1-17 Cherubini, Alessandra Frigeri, Achille Liu, Zuhua Cherubini, Alessandra Frigeri, Achille Liu, Zuhua 0 Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid Mon, 12 Jun 2017 11:18:19 +0000 https://doi.org/10.23638/DMTCS-19-1-13 https://doi.org/10.23638/DMTCS-19-1-13 Boyacı, Arman Ekim, Tınaz Shalom, Mordechai Zaks, Shmuel Boyacı, Arman Ekim, Tınaz Shalom, Mordechai Zaks, Shmuel 0 Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs Wed, 07 Jun 2017 09:25:02 +0000 https://doi.org/10.23638/DMTCS-19-1-14 https://doi.org/10.23638/DMTCS-19-1-14 Faria, Luerbio Klein, Sulamita Sau, Ignasi Sucupira, Rubens Faria, Luerbio Klein, Sulamita Sau, Ignasi Sucupira, Rubens 0 On universal partial words Wed, 31 May 2017 09:00:18 +0000 https://doi.org/10.23638/DMTCS-19-1-16 https://doi.org/10.23638/DMTCS-19-1-16 Chen, Herman Z. Q. Kitaev, Sergey Mütze, Torsten Sun, Brian Y. Chen, Herman Z. Q. Kitaev, Sergey Mütze, Torsten Sun, Brian Y. 0 The quotients between the (revised) Szeged index and Wiener index of graphs Tue, 09 May 2017 08:48:50 +0000 https://doi.org/10.23638/DMTCS-19-1-12 https://doi.org/10.23638/DMTCS-19-1-12 Zhang, Huihui Chen, Jing Li, Shuchao Zhang, Huihui Chen, Jing Li, Shuchao 0 Decidability of multiset, set and numerically decipherable directed figure codes Wed, 03 May 2017 08:17:40 +0000 https://doi.org/10.23638/DMTCS-19-1-11 https://doi.org/10.23638/DMTCS-19-1-11 Moczurad, Włodzimierz Moczurad, Włodzimierz 0 Pairwise Stability in Two Sided Market with Strictly Increasing Valuation Functions Wed, 12 Apr 2017 12:50:47 +0000 https://doi.org/10.23638/DMTCS-19-1-10 https://doi.org/10.23638/DMTCS-19-1-10 Ali, Yasir Javaid, Asma Ali, Yasir Javaid, Asma 0 The permutation class Av(4213,2143) Tue, 04 Apr 2017 14:33:15 +0000 https://doi.org/10.46298/dmtcs.1309 https://doi.org/10.46298/dmtcs.1309 Bevan, David Bevan, David 0 S-Restricted Compositions Revisited Tue, 28 Mar 2017 08:24:04 +0000 https://doi.org/10.23638/DMTCS-19-1-9 https://doi.org/10.23638/DMTCS-19-1-9 Zolfaghari, Behrouz Fallah, Mehran S. Sedighi, Mehdi Zolfaghari, Behrouz Fallah, Mehran S. Sedighi, Mehdi 0 On the shelling antimatroids of split graphs Fri, 24 Mar 2017 16:07:54 +0000 https://doi.org/10.23638/DMTCS-19-1-7 https://doi.org/10.23638/DMTCS-19-1-7 Cardinal, Jean Doignon, Jean-Paul Merckx, Keno Cardinal, Jean Doignon, Jean-Paul Merckx, Keno 0 Wilf classification of triples of 4-letter patterns II Fri, 24 Mar 2017 15:40:12 +0000 https://doi.org/10.23638/DMTCS-19-1-6 https://doi.org/10.23638/DMTCS-19-1-6 Callan, David Mansour, Toufik Shattuck, Mark Callan, David Mansour, Toufik Shattuck, Mark 0 Wilf classification of triples of 4-letter patterns I Fri, 24 Mar 2017 15:37:57 +0000 https://doi.org/10.23638/DMTCS-19-1-5 https://doi.org/10.23638/DMTCS-19-1-5 Callan, David Mansour, Toufik Shattuck, Mark Callan, David Mansour, Toufik Shattuck, Mark 0 A class of symmetric difference-closed sets related to commuting involutions Thu, 23 Mar 2017 10:33:33 +0000 https://doi.org/10.23638/DMTCS-19-1-8 https://doi.org/10.23638/DMTCS-19-1-8 Campbell, John Campbell, John 0 Permutation Pattern matching in (213, 231)-avoiding permutations Wed, 22 Mar 2017 10:10:58 +0000 https://doi.org/10.46298/dmtcs.1329 https://doi.org/10.46298/dmtcs.1329 Neou, Both, Rizzi, Romeo Vialette, Stéphane Neou, Both, Rizzi, Romeo Vialette, Stéphane 0 The Existence of Planar Hypotraceable Oriented Graphs Thu, 16 Mar 2017 13:27:09 +0000 https://doi.org/10.23638/DMTCS-19-1-4 https://doi.org/10.23638/DMTCS-19-1-4 van Aardt, Susan, Burger, Alewyn Petrus Frick, Marietjie van Aardt, Susan, Burger, Alewyn Petrus Frick, Marietjie 0 A characterization of trees with equal 2-domination and 2-independence numbers Thu, 09 Mar 2017 07:53:33 +0000 https://doi.org/10.23638/DMTCS-19-1-1 https://doi.org/10.23638/DMTCS-19-1-1 Brause, Christoph Henning, Michael A. Krzywkowski, Marcin Brause, Christoph Henning, Michael A. Krzywkowski, Marcin 0 A New Game Invariant of Graphs: the Game Distinguishing Number Thu, 02 Mar 2017 14:48:34 +0000 https://doi.org/10.23638/DMTCS-19-1-2 https://doi.org/10.23638/DMTCS-19-1-2 Gravier, Sylvain Meslem, Kahina Schmidt, Simon Slimani, Souad Gravier, Sylvain Meslem, Kahina Schmidt, Simon Slimani, Souad 0 Descent c-Wilf Equivalence Thu, 02 Mar 2017 14:13:07 +0000 https://doi.org/10.46298/dmtcs.1312 https://doi.org/10.46298/dmtcs.1312 Bach, Quang T. Remmel, Jeffrey B. Bach, Quang T. Remmel, Jeffrey B. 0 Right-jumps and pattern avoiding permutations Fri, 10 Feb 2017 08:11:59 +0000 https://doi.org/10.46298/dmtcs.1344 https://doi.org/10.46298/dmtcs.1344 Banderier, Cyril Baril, Jean-Luc Santos, Céline Moreira Dos Banderier, Cyril Baril, Jean-Luc Santos, Céline Moreira Dos 0 Postorder Preimages Mon, 06 Feb 2017 16:17:25 +0000 https://doi.org/10.23638/DMTCS-19-1-3 https://doi.org/10.23638/DMTCS-19-1-3 Defant, Colin Defant, Colin 0 Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs Fri, 03 Feb 2017 10:43:52 +0000 https://doi.org/10.46298/dmtcs.1376 https://doi.org/10.46298/dmtcs.1376 Felsner, Stefan Heldt, Daniel Felsner, Stefan Heldt, Daniel 0 The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations Wed, 21 Dec 2016 14:02:07 +0000 https://doi.org/10.46298/dmtcs.1308 https://doi.org/10.46298/dmtcs.1308 Albert, Michael H. Lackner, Marie-Louise Lackner, Martin Vatter, Vincent Albert, Michael H. Lackner, Marie-Louise Lackner, Martin Vatter, Vincent 0 Enumeration of Corners in Tree-like Tableaux Fri, 02 Dec 2016 13:27:20 +0000 https://doi.org/10.46298/dmtcs.1408 https://doi.org/10.46298/dmtcs.1408 Gao, Alice L. L. Gao, Emily X. L. Laborde-Zubieta, Patxi Sun, Brian Y. Gao, Alice L. L. Gao, Emily X. L. Laborde-Zubieta, Patxi Sun, Brian Y. 0 Stokes posets and serpent nests Fri, 02 Dec 2016 13:12:07 +0000 https://doi.org/10.46298/dmtcs.1382 https://doi.org/10.46298/dmtcs.1382 Chapoton, Frédéric Chapoton, Frédéric 0 Constructions of words rich in palindromes and pseudopalindromes Tue, 22 Nov 2016 14:00:59 +0000 https://doi.org/10.46298/dmtcs.655 https://doi.org/10.46298/dmtcs.655 Pelantová, Edita Starosta, Štěpán Pelantová, Edita Starosta, Štěpán 0 Sequential selection of the k best out of nrankable objects infinity and in the corresponding asymptotic performance of the threshold algorithm.]]> Fri, 28 Oct 2016 10:01:41 +0000 https://doi.org/10.46298/dmtcs.1291 https://doi.org/10.46298/dmtcs.1291 Bruss, F. Thomas Louchard, Guy Bruss, F. Thomas Louchard, Guy infinity and in the corresponding asymptotic performance of the threshold algorithm.]]> 0 Most Complex Regular Ideal Languages Mon, 17 Oct 2016 09:42:14 +0000 https://doi.org/10.46298/dmtcs.1343 https://doi.org/10.46298/dmtcs.1343 Brzozowski, Janusz Davies, Sylvie Liu, Bo Yang Victor Brzozowski, Janusz Davies, Sylvie Liu, Bo Yang Victor 0 Ramsey-type theorems for lines in 3-space Mon, 19 Sep 2016 08:08:44 +0000 https://doi.org/10.46298/dmtcs.1367 https://doi.org/10.46298/dmtcs.1367 Cardinal, Jean Payne, Michael S. Solomon, Noam Cardinal, Jean Payne, Michael S. Solomon, Noam 0 Pattern avoidance for set partitions à la Klazar k$ and all partitions $\tau_1$ of $[k]$ with exactly two blocks. We conjecture that this result holds for all partitions $\tau_1$ of $[k]$. Finally, we enumerate $\Pi_n(\tau)$ for all partitions $\tau$ of $[4]$.]]> Wed, 07 Sep 2016 07:52:25 +0000 https://doi.org/10.46298/dmtcs.1327 https://doi.org/10.46298/dmtcs.1327 Bloom, Jonathan Saracino, Dan Bloom, Jonathan Saracino, Dan k$ and all partitions $\tau_1$ of $[k]$ with exactly two blocks. We conjecture that this result holds for all partitions $\tau_1$ of $[k]$. Finally, we enumerate $\Pi_n(\tau)$ for all partitions $\tau$ of $[4]$.]]> 0 Linear recognition of generalized Fibonacci cubes $Q_h(111)$ Fri, 02 Sep 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2165 https://doi.org/10.46298/dmtcs.2165 Rho, Yoomi Vesel, Aleksander Rho, Yoomi Vesel, Aleksander 0 Matchings of quadratic size extend to long cycles in hypercubes Thu, 01 Sep 2016 15:18:52 +0000 https://doi.org/10.46298/dmtcs.1336 https://doi.org/10.46298/dmtcs.1336 Dvořák, Tomáš Dvořák, Tomáš 0 Connected Tropical Subgraphs in Vertex-Colored Graphs Sat, 06 Aug 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2151 https://doi.org/10.46298/dmtcs.2151 Anglès d'Auriac, Jean-Alexandre Cohen, Nathann El Mafthoui, Hakim Harutyunyan, Ararat Legay, Sylvain Manoussakis, Yannis Anglès d'Auriac, Jean-Alexandre Cohen, Nathann El Mafthoui, Hakim Harutyunyan, Ararat Legay, Sylvain Manoussakis, Yannis 0 An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size -tree if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795–802) proved that if $k \geq 2$, $n \geq \frac{9}{2}k^2 + \frac{19}{2}k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > (k-2)n$, then $\pi$ has a realization containing every tree on $k$ vertices as a subgraph. Moreover, the lower bound $(k-2)n$ is the best possible. This is a variation of a conjecture due to Erdős and Sós. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if $k \geq 3$, $n \geq 2k^2-k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > \frac{4kn}{3} - \frac{5n}{3}$ then $\pi$ has a realization containing every 2-tree on $k$ vertices as a subgraph. We also show that the lower bound $\frac{4kn}{3} - \frac{5n}{3}$ is almost the best possible.]]> Fri, 05 Aug 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2152 https://doi.org/10.46298/dmtcs.2152 Zeng, De-Yan Yin, Jian-Hua Zeng, De-Yan Yin, Jian-Hua -tree if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795–802) proved that if $k \geq 2$, $n \geq \frac{9}{2}k^2 + \frac{19}{2}k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > (k-2)n$, then $\pi$ has a realization containing every tree on $k$ vertices as a subgraph. Moreover, the lower bound $(k-2)n$ is the best possible. This is a variation of a conjecture due to Erdős and Sós. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if $k \geq 3$, $n \geq 2k^2-k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > \frac{4kn}{3} - \frac{5n}{3}$ then $\pi$ has a realization containing every 2-tree on $k$ vertices as a subgraph. We also show that the lower bound $\frac{4kn}{3} - \frac{5n}{3}$ is almost the best possible.]]> 0 A Context free language associated with interval maps Fri, 05 Aug 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.3197 https://doi.org/10.46298/dmtcs.3197 Archana, M Kannan, V Archana, M Kannan, V 0 On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, or $k$-vertex fault Hamiltonian-connected if $G-F$ remains traceable, Hamiltonian, and Hamiltonian-connected for all $F$ with $0 \leq |F| \leq k$, respectively. The notations $h_1(n, \delta ,k)$, $h_2(n, \delta ,k)$, and $h_3(n, \delta ,k)$ denote the minimum number of edges required to guarantee an $n$-vertex graph with minimum degree $\delta (G) \geq \delta$ to be $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, and $k$-vertex fault Hamiltonian-connected, respectively. In this paper, we establish a theorem which uses the degree sequence of a given graph to characterize the $k$-vertex fault traceability/hamiltonicity/Hamiltonian-connectivity, respectively. Then we use this theorem to obtain the formulas for $h_i(n, \delta ,k)$ for $1 \leq i \leq 3$, which improves and extends the known results for $k=0$.]]> Mon, 01 Aug 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2149 https://doi.org/10.46298/dmtcs.2149 Chen, Shih-Yan Kao, Shin-Shin Su, Hsun Chen, Shih-Yan Kao, Shin-Shin Su, Hsun $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, or $k$-vertex fault Hamiltonian-connected if $G-F$ remains traceable, Hamiltonian, and Hamiltonian-connected for all $F$ with $0 \leq |F| \leq k$, respectively. The notations $h_1(n, \delta ,k)$, $h_2(n, \delta ,k)$, and $h_3(n, \delta ,k)$ denote the minimum number of edges required to guarantee an $n$-vertex graph with minimum degree $\delta (G) \geq \delta$ to be $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, and $k$-vertex fault Hamiltonian-connected, respectively. In this paper, we establish a theorem which uses the degree sequence of a given graph to characterize the $k$-vertex fault traceability/hamiltonicity/Hamiltonian-connectivity, respectively. Then we use this theorem to obtain the formulas for $h_i(n, \delta ,k)$ for $1 \leq i \leq 3$, which improves and extends the known results for $k=0$.]]> 0 Energy-optimal algorithms for computing aggregative functions in random networks Sun, 24 Jul 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2160 https://doi.org/10.46298/dmtcs.2160 Klonowski, Marek Sulkowska, Małgorzata Klonowski, Marek Sulkowska, Małgorzata 0 Edge Disjoint Hamilton Cycles in Knödel Graphs Thu, 21 Jul 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2148 https://doi.org/10.46298/dmtcs.2148 Paulraja, Palanivel Subramania Nadar Sampath Kumar, S Paulraja, Palanivel Subramania Nadar Sampath Kumar, S 0 Pattern avoidance in forests of binary shrubs Thu, 21 Jul 2016 10:09:41 +0000 https://doi.org/10.46298/dmtcs.1322 https://doi.org/10.46298/dmtcs.1322 Bevan, David Levin, Derek Nugent, Peter Pantone, Jay Pudwell, Lara Riehl, Manda Tlachac, ML Bevan, David Levin, Derek Nugent, Peter Pantone, Jay Pudwell, Lara Riehl, Manda Tlachac, ML 0 Traceability of locally hamiltonian and locally traceable graphs locally $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the open neighbourhood of the vertex $v$. Pareek and Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions. Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph? Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph? We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.]]> Thu, 30 Jun 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2144 https://doi.org/10.46298/dmtcs.2144 De Wet, Johan Van Aardt, Susan De Wet, Johan Van Aardt, Susan locally $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the open neighbourhood of the vertex $v$. Pareek and Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions. Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph? Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph? We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.]]> 0 On the complexity of edge-colored subgraph partitioning problems in network optimization monochromatic if all its edges have the same color, and called multicolored if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph $G$ is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln $|V(G)|+1$.]]> Thu, 30 Jun 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2159 https://doi.org/10.46298/dmtcs.2159 Zhang, Xiaoyan Zhang, Zan-Bo Broersma, Hajo Wen, Xuelian Zhang, Xiaoyan Zhang, Zan-Bo Broersma, Hajo Wen, Xuelian monochromatic if all its edges have the same color, and called multicolored if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph $G$ is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln $|V(G)|+1$.]]> 0 Pattern Avoidance in Task-Precedence Posets Fri, 24 Jun 2016 13:02:33 +0000 https://doi.org/10.46298/dmtcs.1324 https://doi.org/10.46298/dmtcs.1324 Paukner, Mitchell Pepin, Lucy Riehl, Manda Wieser, Jarred Paukner, Mitchell Pepin, Lucy Riehl, Manda Wieser, Jarred 0 Packing densities of layered permutations and the minimum number of monotone sequences in layered permutations Thu, 23 Jun 2016 11:06:48 +0000 https://doi.org/10.46298/dmtcs.1313 https://doi.org/10.46298/dmtcs.1313 Bastos, Josefran de Oliveira Coregliano, Leonardo Nagami Bastos, Josefran de Oliveira Coregliano, Leonardo Nagami 0 Variance and Covariance of Several Simultaneous Outputs of a Markov Chain Thu, 23 Jun 2016 10:59:03 +0000 https://doi.org/10.46298/dmtcs.1341 https://doi.org/10.46298/dmtcs.1341 Kropf, Sara Kropf, Sara 0 The inapproximability for the $(0,1)$-additive number additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$ ($x \sim y$ means that $x$ is joined to $y$). The additive number of $G$, denoted by $\eta (G)$, is the minimum number $k$ such that $G$ has a additive labeling $\ell : V(G) \rightarrow \mathbb{N}_k$. The additive choosability of a graph $G$, denoted by $\eta_\ell (G)$, is the smallest number $k$ such that $G$ has an additive labeling for any assignment of lists of size $k$ to the vertices of $G$, such that the label of each vertex belongs to its own list. Seamone in his PhD thesis conjectured that for every graph $G$, $\eta(G)= \eta_\ell (G)$. We give a negative answer to this conjecture and we show that for every $k$ there is a graph $G$ such that $\eta_\ell (G) - \eta(G) \geq k$. A $(0,1)$-additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \{0,1 \}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$. A graph may lack any $(0,1)$-additive labeling. We show that it is NP-complete to decide whether a $(0,1)$-additive labeling exists for some families of graphs such as perfect graphs and planar triangle-free graphs. For a graph $G$ with some $(0,1)$-additive labelings, the $(0,1)$-additive number of $G$ is defined as $\sigma_1 (G) = \mathrm{min}_{\ell \in \Gamma} \Sigma_{v \in V (G)} \ell (v)$ where $\Gamma$ is the set of $(0,1)$-additive labelings of $G$. We prove that given a planar graph that admits a $(0,1)$-additive labeling, for all $\epsilon > 0$ , approximating the $(0,1)$-additive number within $n^{1-\epsilon}$ is NP-hard.]]> Thu, 16 Jun 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2145 https://doi.org/10.46298/dmtcs.2145 Ahadi, Arash Dehghan, Ali Ahadi, Arash Dehghan, Ali additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$ ($x \sim y$ means that $x$ is joined to $y$). The additive number of $G$, denoted by $\eta (G)$, is the minimum number $k$ such that $G$ has a additive labeling $\ell : V(G) \rightarrow \mathbb{N}_k$. The additive choosability of a graph $G$, denoted by $\eta_\ell (G)$, is the smallest number $k$ such that $G$ has an additive labeling for any assignment of lists of size $k$ to the vertices of $G$, such that the label of each vertex belongs to its own list. Seamone in his PhD thesis conjectured that for every graph $G$, $\eta(G)= \eta_\ell (G)$. We give a negative answer to this conjecture and we show that for every $k$ there is a graph $G$ such that $\eta_\ell (G) - \eta(G) \geq k$. A $(0,1)$-additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \{0,1 \}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$. A graph may lack any $(0,1)$-additive labeling. We show that it is NP-complete to decide whether a $(0,1)$-additive labeling exists for some families of graphs such as perfect graphs and planar triangle-free graphs. For a graph $G$ with some $(0,1)$-additive labelings, the $(0,1)$-additive number of $G$ is defined as $\sigma_1 (G) = \mathrm{min}_{\ell \in \Gamma} \Sigma_{v \in V (G)} \ell (v)$ where $\Gamma$ is the set of $(0,1)$-additive labelings of $G$. We prove that given a planar graph that admits a $(0,1)$-additive labeling, for all $\epsilon > 0$ , approximating the $(0,1)$-additive number within $n^{1-\epsilon}$ is NP-hard.]]> 0 The irregularity of two types of trees Tue, 07 Jun 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2146 https://doi.org/10.46298/dmtcs.2146 Jianxi, Li Liu, Yang Shiu, Wai Jianxi, Li Liu, Yang Shiu, Wai 0 A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups Mon, 06 Jun 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2155 https://doi.org/10.46298/dmtcs.2155 Mikhaylova, Inna Mikhaylova, Inna 0 Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient open domination graph Thu, 02 Jun 2016 14:21:12 +0000 https://doi.org/10.46298/dmtcs.1277 https://doi.org/10.46298/dmtcs.1277 Šumenjak, Tadeja Kraner Peterin, Iztok Rall, Douglas F. Tepeh, Aleksandra Šumenjak, Tadeja Kraner Peterin, Iztok Rall, Douglas F. Tepeh, Aleksandra 0 Snow Leopard Permutations and Their Even and Odd Threads Wed, 01 Jun 2016 07:43:53 +0000 https://doi.org/10.46298/dmtcs.1279 https://doi.org/10.46298/dmtcs.1279 Egge, Eric S. Rubin, Kailee Egge, Eric S. Rubin, Kailee 0 Statistics for 3-letter patterns with repetitions in compositions Mon, 30 May 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2156 https://doi.org/10.46298/dmtcs.2156 Shabani, Armend Gjergji, Rexhep Shabani, Armend Gjergji, Rexhep 0 Permutations of context-free, ET0L and indexed languages Mon, 30 May 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2164 https://doi.org/10.46298/dmtcs.2164 Brough, Tara Ciobanu, Laura Elder, Murray Zetzsche, Georg Brough, Tara Ciobanu, Laura Elder, Murray Zetzsche, Georg 0 Asymptotics for minimal overlapping patterns for generalized Euler permutations, standard tableaux of rectangular shape, and column strict arrays Fri, 20 May 2016 16:16:41 +0000 https://doi.org/10.46298/dmtcs.1315 https://doi.org/10.46298/dmtcs.1315 Pan, Ran Remmel, Jeffrey B. Pan, Ran Remmel, Jeffrey B. 0 Planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable list edge coloring and list total coloring. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the edges and the vertices while ensuring that two edges that are adjacent, two vertices that are adjacent, or a vertex and an edge that are incident receive different colors. In their list extensions, instead of having the same set of colors for the whole graph, every vertex or edge is assigned some set of colors and has to be colored from it. A graph is minimally edge or total choosable if it is list $\Delta$-edge-colorable or list $(\Delta +1)$-total-colorable, respectively, where $\Delta$ is the maximum degree in the graph. It is already known that planar graphs with $\Delta \geq 8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $\Delta \geq 7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k (\forall 3 \leq k \leq 6)$ are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.]]> Wed, 11 May 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2147 https://doi.org/10.46298/dmtcs.2147 Bonamy, Marthe Lévêque, Benjamin Pinlou, Alexandre Bonamy, Marthe Lévêque, Benjamin Pinlou, Alexandre list edge coloring and list total coloring. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the edges and the vertices while ensuring that two edges that are adjacent, two vertices that are adjacent, or a vertex and an edge that are incident receive different colors. In their list extensions, instead of having the same set of colors for the whole graph, every vertex or edge is assigned some set of colors and has to be colored from it. A graph is minimally edge or total choosable if it is list $\Delta$-edge-colorable or list $(\Delta +1)$-total-colorable, respectively, where $\Delta$ is the maximum degree in the graph. It is already known that planar graphs with $\Delta \geq 8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $\Delta \geq 7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k (\forall 3 \leq k \leq 6)$ are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.]]> 0 Automata in SageMath---Combinatorics meet Theoretical Computer Science Tue, 10 May 2016 08:00:47 +0000 https://doi.org/10.46298/dmtcs.1352 https://doi.org/10.46298/dmtcs.1352 Heuberger, Clemens Krenn, Daniel Kropf, Sara Heuberger, Clemens Krenn, Daniel Kropf, Sara 0 Combinatorial optimization in networks with Shared Risk Link Groups Tue, 03 May 2016 09:30:11 +0000 https://doi.org/10.46298/dmtcs.1297 https://doi.org/10.46298/dmtcs.1297 Coudert, David Pérennes, Stéphane Rivano, Hervé Voge, Marie-Emilie Coudert, David Pérennes, Stéphane Rivano, Hervé Voge, Marie-Emilie 0 Rainbow eulerian multidigraphs and the product of cycles Wed, 20 Apr 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2153 https://doi.org/10.46298/dmtcs.2153 López, Susana Muntaner-Batle, Francesc-Antoni López, Susana Muntaner-Batle, Francesc-Antoni 0 Robust Wireless Sensor Network Deployment Wed, 20 Apr 2016 22:00:00 +0000 https://doi.org/10.46298/dmtcs.2163 https://doi.org/10.46298/dmtcs.2163 Erdelj, Milan Mitton, Nathalie Razafindralambo, Tahiry Erdelj, Milan Mitton, Nathalie Razafindralambo, Tahiry 0 On the number of vertices of each rank in phylogenetic trees and their generalizations Mon, 11 Apr 2016 19:55:16 +0000 https://doi.org/10.46298/dmtcs.653 https://doi.org/10.46298/dmtcs.653 Bóna, Miklós Bóna, Miklós 0 Heredity for generalized power domination Sun, 03 Apr 2016 21:25:50 +0000 https://doi.org/10.46298/dmtcs.1290 https://doi.org/10.46298/dmtcs.1290 Dorbec, Paul Varghese, Seethu Vijayakumar, Ambat Dorbec, Paul Varghese, Seethu Vijayakumar, Ambat 0 Patterns in Inversion Sequences I \pi_i \}|$. This correspondence makes it a natural extension to study patterns in inversion sequences much in the same way that patterns have been studied in permutations. This paper, the first of two on patterns in inversion sequences, focuses on the enumeration of inversion sequences that avoid words of length three. Our results connect patterns in inversion sequences to a number of well-known numerical sequences including Fibonacci numbers, Bell numbers, Schr\"oder numbers, and Euler up/down numbers.]]> Thu, 31 Mar 2016 09:47:19 +0000 https://doi.org/10.46298/dmtcs.1323 https://doi.org/10.46298/dmtcs.1323 Corteel, Sylvie Martinez, Megan A. Savage, Carla D. Weselcouch, Michael Corteel, Sylvie Martinez, Megan A. Savage, Carla D. Weselcouch, Michael \pi_i \}|$. This correspondence makes it a natural extension to study patterns in inversion sequences much in the same way that patterns have been studied in permutations. This paper, the first of two on patterns in inversion sequences, focuses on the enumeration of inversion sequences that avoid words of length three. Our results connect patterns in inversion sequences to a number of well-known numerical sequences including Fibonacci numbers, Bell numbers, Schr\"oder numbers, and Euler up/down numbers.]]> 0 Open k-monopolies in graphs: complexity and related concepts Tue, 29 Mar 2016 19:20:25 +0000 https://doi.org/10.46298/dmtcs.654 https://doi.org/10.46298/dmtcs.654 Kuziak, Dorota Peterin, Iztok Yero, Ismael G. Kuziak, Dorota Peterin, Iztok Yero, Ismael G. 0 An Erdős--Hajnal analogue for permutation classes Thu, 24 Mar 2016 16:45:14 +0000 https://doi.org/10.46298/dmtcs.1328 https://doi.org/10.46298/dmtcs.1328 Vatter, Vincent Vatter, Vincent 0 Sticky Seeding in Discrete-Time Reversible-Threshold Networks Thu, 17 Mar 2016 10:49:04 +0000 https://doi.org/10.46298/dmtcs.1241 https://doi.org/10.46298/dmtcs.1241 Spencer, Gwen Spencer, Gwen 0 The Flip Diameter of Rectangulations and Convex Subdivisions Thu, 17 Mar 2016 09:57:41 +0000 https://doi.org/10.46298/dmtcs.646 https://doi.org/10.46298/dmtcs.646 Ackerman, Eyal Allen, Michelle M. Barequet, Gill Löffler, Maarten Mermelstein, Joshua Souvaine, Diane L. Tóth, Csaba D. Ackerman, Eyal Allen, Michelle M. Barequet, Gill Löffler, Maarten Mermelstein, Joshua Souvaine, Diane L. Tóth, Csaba D. 0 Asymptotic Density of Zimin Words Thu, 17 Mar 2016 08:46:11 +0000 https://doi.org/10.46298/dmtcs.1302 https://doi.org/10.46298/dmtcs.1302 Cooper, Joshua Rorabaugh, Danny Cooper, Joshua Rorabaugh, Danny 0 Factoriality and the Pin-Reutenauer procedure Tue, 15 Mar 2016 13:04:03 +0000 https://doi.org/10.46298/dmtcs.650 https://doi.org/10.46298/dmtcs.650 Almeida, J. Costa, J. C. Zeitoun, M. Almeida, J. Costa, J. C. Zeitoun, M. 0 Arithmetic completely regular codes Fri, 26 Feb 2016 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2150 https://doi.org/10.46298/dmtcs.2150 Koolen, Jacobus Sun Lee, Woo Martin, William Tanaka, Hajime Koolen, Jacobus Sun Lee, Woo Martin, William Tanaka, Hajime 0 Dendriform structures for restriction-deletion and restriction-contraction matroid Hopf algebras Thu, 25 Feb 2016 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2157 https://doi.org/10.46298/dmtcs.2157 Hoang-Nghia, Nguyen Tanasa, Adrian Tollu, Christophe Hoang-Nghia, Nguyen Tanasa, Adrian Tollu, Christophe 0 Edge-partitioning graphs into regular and locally irregular components Tue, 16 Feb 2016 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2154 https://doi.org/10.46298/dmtcs.2154 Bensmail, Julien Stevens, Brett Bensmail, Julien Stevens, Brett 0 The complexity of deciding whether a graph admits an orientation with fixed weak diameter Tue, 16 Feb 2016 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2161 https://doi.org/10.46298/dmtcs.2161 Bensmail, Julien Duvignau, Romaric Kirgizov, Sergey Bensmail, Julien Duvignau, Romaric Kirgizov, Sergey 0 $2\times 2$ monotone grid classes are finitely based Thu, 11 Feb 2016 10:31:02 +0000 https://doi.org/10.46298/dmtcs.1325 https://doi.org/10.46298/dmtcs.1325 Albert, Michael Brignall, Robert Albert, Michael Brignall, Robert 0 Avoiding patterns in irreducible permutations i.e., those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{132,213,321\}$. This induces two new bijections between the set of Dyck paths and some restricted sets of permutations.]]> Sun, 17 Jan 2016 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2158 https://doi.org/10.46298/dmtcs.2158 Baril, Jean-Luc Baril, Jean-Luc i.e., those in which there is no index $i$ such that $\sigma (i+1) - \sigma (i)=1$. The problem is addressed completely in the case of avoiding one or two patterns of length three, and several well known sequences are encountered in the process, such as Catalan, Motzkin, Fibonacci, Tribonacci, Padovan and Binary numbers. Also, we present constructive bijections between the set of Motzkin paths of length $n-1$ and the sets of irreducible permutations of length $n$ (respectively fixed point free irreducible involutions of length $2n$) avoiding a pattern $\alpha$ for $\alpha \in \{132,213,321\}$. This induces two new bijections between the set of Dyck paths and some restricted sets of permutations.]]> 0 Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights Mon, 04 Jan 2016 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2162 https://doi.org/10.46298/dmtcs.2162 Lu, Hongliang Lu, Hongliang 0 The double competition multigraph of a digraph Wed, 30 Dec 2015 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2133 https://doi.org/10.46298/dmtcs.2133 Sano, Yoshio Park, Jeongmi Sano, Yoshio Park, Jeongmi 0 A relation on 132-avoiding permutation patterns avoiding if it does not contain the permutation $τ$. For any $n$, the popularity of a permutation $τ$, denoted $A$$n$($τ$), is the number of copies of $τ$ contained in the set of all 132-avoiding permutations of length $n$. Rudolph conjectures that for permutations $τ$ and $μ$ of the same length, $A$$n$($τ$) ≤ $A$$n$($μ$) for all $n$ if and only if the spine structure of $τ$ is less than or equal to the spine structure of $μ$ in refinement order. We prove one direction of this conjecture, by showing that if the spine structure of $τ$ is less than or equal to the spine structure of $μ$, then $A$$n$($τ$) ≤ $A$$n$($μ$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture.]]> Mon, 14 Dec 2015 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2141 https://doi.org/10.46298/dmtcs.2141 Aisbett, Natalie Aisbett, Natalie avoiding if it does not contain the permutation $τ$. For any $n$, the popularity of a permutation $τ$, denoted $A$$n$($τ$), is the number of copies of $τ$ contained in the set of all 132-avoiding permutations of length $n$. Rudolph conjectures that for permutations $τ$ and $μ$ of the same length, $A$$n$($τ$) ≤ $A$$n$($μ$) for all $n$ if and only if the spine structure of $τ$ is less than or equal to the spine structure of $μ$ in refinement order. We prove one direction of this conjecture, by showing that if the spine structure of $τ$ is less than or equal to the spine structure of $μ$, then $A$$n$($τ$) ≤ $A$$n$($μ$) for all $n$. We disprove the opposite direction by giving a counterexample, and hence disprove the conjecture.]]> 0 Some undecidable problems about the trace-subshift associated to a Turing machine Tue, 01 Dec 2015 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2137 https://doi.org/10.46298/dmtcs.2137 Gajardo, Anahí Ollinger, Nicolas Torres-Avilés, Rodrigo Gajardo, Anahí Ollinger, Nicolas Torres-Avilés, Rodrigo 0 The game colouring number of powers of forests Tue, 24 Nov 2015 19:53:58 +0000 https://doi.org/10.46298/dmtcs.648 https://doi.org/10.46298/dmtcs.648 Andres, Stephan Dominique Hochstättler, Winfried Andres, Stephan Dominique Hochstättler, Winfried 0 Spanning connectedness and Hamiltonian thickness of graphs and interval graphs Sun, 22 Nov 2015 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2082 https://doi.org/10.46298/dmtcs.2082 Li, Peng Wu, Yaokun Li, Peng Wu, Yaokun 0 Cubical coloring — fractional covering by cuts and semidefinite programming Tue, 17 Nov 2015 23:00:00 +0000 https://doi.org/10.46298/dmtcs.2134 https://doi.org/10.46298/dmtcs.2134 Šámal, Robert Šámal, Robert