Vol. 17 no.2


1. The complexity of $P$<sub>4</sub>-decomposition of regular graphs and multigraphs

Diwan, Ajit ; Dion, Justine ; Mendell, David ; Plantholt, Michael ; Tipnis, Shailesh.
Let G denote a multigraph with edge set E(G), let &micro;(G) denote the maximum edge multiplicity in G, and let Pk denote the path on k vertices. Heinrich et al.(1999) showed that P4 decomposes a connected 4-regular graph G if and only if |E(G)| is divisible by 3. We show that P4 decomposes a […]
Section: Graph Theory

2. On graphs double-critical with respect to the colouring number

Kriesell, Matthias ; Pedersen, Anders.
The colouring number col($G$) of a graph $G$ is the smallest integer $k$ for which there is an ordering of the vertices of $G$ such that when removing the vertices of $G$ in the specified order no vertex of degree more than $k-1$ in the remaining graph is removed at any step. An edge $e$ of a graph […]
Section: Graph Theory

3. The game chromatic number of trees and forests

Dunn, Charles ; Larsen, Victor ; Lindke, Kira ; Retter, Troy ; Toci, Dustin.
While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests […]
Section: Graph Theory

4. Disimplicial arcs, transitive vertices, and disimplicial eliminations

Eguia, Martiniano ; Soulignac, Francisco, .
In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A <i>diclique</i> of a digraph is a pair $V$ &rarr; $W$ of sets of vertices such that $v$ &rarr; $w$ is an arc for […]
Section: Graph Theory

5. Packing Plane Perfect Matchings into a Point Set

Biniaz, Ahmad ; Bose, Prosenjit ; Maheshwari, Anil ; Smid, Michiel.
Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$? For points in general position we prove the lower bound of &#x230A;log<sub>2</sub>$n$&#x230B;$-1$. For some special […]
Section: Graph Theory

6. The double competition multigraph of a digraph

Sano, Yoshio ; Park, Jeongmi.
In this article, we introduce the notion of the double competition multigraph of a digraph. We give characterizations of the double competition multigraphs of arbitrary digraphs, loopless digraphs, reflexive digraphs, and acyclic digraphs in terms of edge clique partitions of the multigraphs.
Section: Graph Theory

7. Cubical coloring — fractional covering by cuts and semidefinite programming

Šámal, Robert.
We introduce a new graph parameter that measures fractional covering of a graph by cuts. Besides being interesting in its own right, it is useful for study of homomorphisms and tension-continuous mappings. We study the relations with chromatic number, bipartite density, and other graph parameters. […]
Section: Graph Theory

8. Reducing the rank of a matroid

Joret, Gwenaël ; Vetta, Adrian.
We consider the <i>rank reduction problem</i> for matroids: Given a matroid $M$ and an integer $k$, find a minimum size subset of elements of $M$ whose removal reduces the rank of $M$ by at least $k$. When $M$ is a graphical matroid this problem is the minimum $k$-cut problem, which […]
Section: Discrete Algorithms

9. Improving Vertex Cover as a Graph Parameter

Ganian, Robert.
Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with graph problems which are hard to solve even when parameterized by tree-width; however, the drawback of vertex cover is that bounding […]
Section: Discrete Algorithms

10. Some undecidable problems about the trace-subshift associated to a Turing machine

Gajardo, Anahí ; Ollinger, Nicolas ; Torres-Avilés, Rodrigo.
We consider three problems related to dynamics of one-tape Turing machines: Existence of blocking configurations, surjectivity in the trace, and entropy positiveness. In order to address them, a reversible two-counter machine is simulated by a reversible Turing machine on the right side of its tape. […]
Section: Automata, Logic and Semantics

11. Classical Automata on Promise Problems

Geffert, Viliam ; Yakaryilmaz, Abuzer.
Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required […]
Section: Automata, Logic and Semantics

12. Minimum Number of Colors: the Turk’s Head Knots Case Study

Lopes, Pedro ; Matias, João.
An $r$-coloring of a knot diagram is an assignment of integers modulo $r$ to the arcs of the diagram such that at each crossing, twice the the number assigned to the over-arc equals the sum of the numbers assigned to the under-arcs, modulo $r$. The number of $r$-colorings is a knot invariant i.e., […]
Section: Combinatorics

13. On avoidance of patterns of the form σ-τ by words over a finite alphabet

Mansour, Toufik ; Shattuck, Mark.
Vincular or dashed patterns resemble classical patterns except that some of the letters within an occurrence are required to be adjacent. We prove several infinite families of Wilf-equivalences for $k$-ary words involving vincular patterns containing a single dash, which explain the majority of the […]
Section: Combinatorics

14. A relation on 132-avoiding permutation patterns

Aisbett, Natalie.
A permutation $&sigma;$ contains the permutation $&tau;$ if there is a subsequence of $&sigma;$ order isomorphic to $&tau;$. A permutation $&sigma;$ is $&tau;$-<i>avoiding</i> if it does not contain the permutation $&tau;$. For any $n$, the […]
Section: Combinatorics

15. Symmetries of Monocoronal Tilings

Frettlöh, Dirk ; Garber, Alexey.
The vertex corona of a vertex of some tiling is the vertex together with the adjacent tiles. A tiling where all vertex coronae are congruent is called monocoronal. We provide a classification of monocoronal tilings in the Euclidean plane and derive a list of all possible symmetry groups of […]
Section: Combinatorics

16. On the Dynamics of Systems of Urns

Klonowski, Marek ; Cichoń, Jacek ; Kapelko, Rafał.
In this paper we present an analysis of some generalization of the classic urn and balls model. In our model each urn has a fixed capacity and initially is filled with white balls. Black balls are added to the system of connected urns and gradually displace white balls. We show a general form of […]
Section: Analysis of Algorithms