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. 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

14. 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

15. 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

16. 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

17. 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