Vol 19 no. 1


1. A characterization of trees with equal 2-domination and 2-independence numbers

Brause, Christoph ; Henning, Michael A. ; Krzywkowski, Marcin.
A set $S$ of vertices in a graph $G$ is a $2$-dominating set if every vertex of $G$ not in $S$ is adjacent to at least two vertices in $S$, and $S$ is a $2$-independent set if every vertex in $S$ is adjacent to at most one vertex of $S$. The $2$-domination number $\gamma_2(G)$ is the minimum […]
Section: Graph Theory

2. A New Game Invariant of Graphs: the Game Distinguishing Number

Gravier, Sylvain ; Meslem, Kahina ; Schmidt, Simon ; Slimani, Souad.
The distinguishing number of a graph $G$ is a symmetry related graph invariant whose study started two decades ago. The distinguishing number $D(G)$ is the least integer $d$ such that $G$ has a $d$-distinguishing coloring. A distinguishing $d$-coloring is a coloring […]
Section: Graph Theory

3. Postorder Preimages

Defant, Colin.
Given a set $Y$ of decreasing plane trees and a permutation $\pi$, how many trees in $Y$ have $\pi$ as their postorder? Using combinatorial and geometric constructions, we provide a method for answering this question for certain sets $Y$ and all permutations $\pi$. We then provide applications of […]
Section: Combinatorics

4. The Existence of Planar Hypotraceable Oriented Graphs

van Aardt, Susan,  ; Burger, Alewyn Petrus ; Frick, Marietjie.
A digraph is \emph{traceable} if it has a path that visits every vertex. A digraph $D$ is \emph{hypotraceable} if $D$ is not traceable but $D-v$ is traceable for every vertex $v\in V(D)$. It is known that there exists a planar hypotraceable digraph of order $n$ for every $n\geq 7$, but no examples […]
Section: Graph Theory

5. Wilf classification of triples of 4-letter patterns I

Callan, David ; Mansour, Toufik ; Shattuck, Mark.
This is the first of two papers in which we determine all 242 Wilf classes of triples of 4-letter patterns by showing that there are 32 non-singleton Wilf classes. There are 317 symmetry classes of triples of 4-letter patterns and after computer calculation of initial terms, the problem reduces to […]
Section: Combinatorics

6. Wilf classification of triples of 4-letter patterns II

Callan, David ; Mansour, Toufik ; Shattuck, Mark.
This is the second of two papers in which we determine all 242 Wilf classes of triples of 4-letter patterns by showing that there are 32 non-singleton Wilf classes. There are 317 symmetry classes of triples of 4-letter patterns and after computer calculation of initial terms, the problem reduces to […]
Section: Combinatorics

7. On the shelling antimatroids of split graphs

Cardinal, Jean ; Doignon, Jean-Paul ; Merckx, Keno.
Chordal graph shelling antimatroids have received little attention with regard to their combinatorial properties and related optimization problems, as compared to the case of poset shelling antimatroids. Here we consider a special case of these antimatroids, namely the split graph shelling […]
Section: Combinatorics

8. A class of symmetric difference-closed sets related to commuting involutions

Campbell, John.
Recent research on the combinatorics of finite sets has explored the structure of symmetric difference-closed sets, and recent research in combinatorial group theory has concerned the enumeration of commuting involutions in $S_{n}$ and $A_{n}$. In this article, we consider an interesting combination […]
Section: Combinatorics

9. S-Restricted Compositions Revisited

Zolfaghari, Behrouz ; Fallah, Mehran S. ; Sedighi, Mehdi.
An S-restricted composition of a positive integer n is an ordered partition of n where each summand is drawn from a given subset S of positive integers. There are various problems regarding such compositions which have received attention in recent years. This paper is an attempt at finding a closed- […]
Section: Combinatorics

10. Pairwise Stability in Two Sided Market with Strictly Increasing Valuation Functions

Ali, Yasir ; Javaid, Asma.
This paper deals with two-sided matching market with two disjoint sets, i.e. the set of buyers and the set of sellers. Each seller can trade with at most with one buyer and vice versa. Money is transferred from sellers to buyers for an indivisible goods that buyers own. Valuation functions, for […]
Section: Discrete Algorithms

11. Decidability of multiset, set and numerically decipherable directed figure codes

Moczurad, Włodzimierz.
Codes with various kinds of decipherability, weaker than the usual unique decipherability, have been studied since multiset decipherability was introduced in mid-1980s. We consider decipherability of directed figure codes, where directed figures are defined as labelled polyominoes with […]
Section: Automata, Logic and Semantics

12. The quotients between the (revised) Szeged index and Wiener index of graphs

Zhang, Huihui ; Chen, Jing ; Li, Shuchao.
Let $Sz(G),Sz^*(G)$ and $W(G)$ be the Szeged index, revised Szeged index and Wiener index of a graph $G.$ In this paper, the graphs with the fourth, fifth, sixth and seventh largest Wiener indices among all unicyclic graphs of order $n\geqslant 10$ are characterized; as well the graphs with the […]
Section: Graph Theory

13. Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid

Boyacı, Arman ; Ekim, Tınaz ; Shalom, Mordechai ; Zaks, Shmuel.
The families EPT (resp. EPG) Edge Intersection Graphs of Paths in a tree (resp. in a grid) are well studied graph classes. Recently we introduced the graph classes Edge-Intersecting and Non-Splitting Paths in a Tree ENPT, and in a Grid (ENPG). It was shown that ENPG contains an infinite hierarchy […]
Section: Graph Theory

14. Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs

Faria, Luerbio ; Klein, Sulamita ; Sau, Ignasi ; Sucupira, Rubens.
A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph is balanced if there is a bipartition of its vertex set such that an edge has sign $-$ if and only if its endpoints are in different parts. The Edwards-Erd\"os bound states that every graph with $n$ vertices and $m$ edges […]
Section: Discrete Algorithms

15. Rises in forests of binary shrubs

Remmel, Jeffrey ; Zheng, Sai-nan.
The study of patterns in permutations associated with forests of binary shrubs was initiated by D. Bevan et al.. In this paper, we study five different types of rise statistics that can be associated with such permutations and find the generating functions for the distribution of such rise […]
Section: Combinatorics

16. On universal partial words

Chen, Herman Z. Q. ; Kitaev, Sergey ; Mütze, Torsten ; Sun, Brian Y..
A universal word for a finite alphabet $A$ and some integer $n\geq 1$ is a word over $A$ such that every word in $A^n$ appears exactly once as a subword (cyclically or linearly). It is well-known and easy to prove that universal words exist for any $A$ and $n$. In this work we initiate the […]
Section: Combinatorics

17. Composing short 3-compressing words on a 2-letter alphabet

Cherubini, Alessandra ; Frigeri, Achille ; Liu, Zuhua.
A finite deterministic (semi)automaton A = (Q, Σ, δ) is k-compressible if there is some word w ∈ Σ + such that theimage of its state set Q under the natural action of w is reduced by at least k states. Such word w, if it exists, is calleda k-compressing word for A and A is said to be k-compressed by […]
Section: Automata, Logic and Semantics

18. Nonrepetitive edge-colorings of trees

Kündgen, A. ; Talbot, T..
A repetition is a sequence of symbols in which the first half is the same as the second half. An edge-coloring of a graph is repetition-free or nonrepetitive if there is no path with a color pattern that is a repetition. The minimum number of colors so that a graph has a nonrepetitive […]
Section: Graph Theory

19. Evaluations of series of the $q$-Watson, $q$-Dixon, and $q$-Whipple type

Wei, Chuanan ; Wang, Xiaoxia.
Using $q$-series identities and series rearrangement, we establish several extensions of $q$-Watson formulas with two extra integer parameters. Then they and Sears' transformation formula are utilized to derive some generalizations of $q$-Dixon formulas and $q$-Whipple formulas with two extra […]
Section: Combinatorics

20. Equivalence of the filament and overlap graphs of subtrees of limited trees

Enright, Jessica ; Stewart, Lorna.
The overlap graphs of subtrees of a tree are equivalent to subtree filament graphs, the overlap graphs of subtrees of a star are cocomparability graphs, and the overlap graphs of subtrees of a caterpillar are interval filament graphs. In this paper, we show the equivalence of many more classes of […]
Section: Graph Theory

21. On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture

Bensmail, Julien ; Senhaji, Mohammed ; Szabo Lyngsie, Kasper.
This paper is dedicated to studying the following question: Is it always possible to injectively assign the weights 1, ..., |E(G)| to the edges of any given graph G (with no component isomorphic to K2) so that every two adjacent vertices of G get distinguished by their sums of incident weights? One […]
Section: Graph Theory

22. Asymptotics of the occupancy scheme in a random environment and its applications to tries

Businger, Silvia.
Consider $ m $ copies of an irreducible, aperiodic Markov chain $ Y $ taking values in a finite state space. The asymptotics as $ m $ tends to infinity, of the first time from which on the trajectories of the $ m $ copies differ, have been studied by Szpankowski (1991) in the setting of tries. We […]
Section: Analysis of Algorithms

23. Lattice paths with catastrophes

Banderier, Cyril ; Wallner, Michael.
In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is like having the possibility of jumping from any altitude to zero. These objects have the interesting feature that they do not have the same intuitive probabilistic behaviour as […]
Section: Analysis of Algorithms

24. Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs

Gözüpek, Didem ; Hujdurović, Ademir ; Milanič, Martin.
A graph is said to be well-dominated if all its minimal dominating sets are of the same size. The class of well-dominated graphs forms a subclass of the well studied class of well-covered graphs. While the recognition problem for the class of well-covered graphs is known to be co-NP-complete, the […]
Section: Graph Theory