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