# Vol. 16 no. 1 (in progress)

### 1. List circular backbone colouring

A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, […]

### 2. Strong parity vertex coloring of plane graphs

A strong parity vertex coloring of a 2-connected plane graph is a coloring of the vertices such that every face is incident with zero or an odd number of vertices of each color. We prove that every 2-connected loopless plane graph has a strong parity vertex coloring with 97 colors. Moreover the […]

The implicit signature κ consists of the multiplication and the (ω-1)-power. We describe a procedure to transform each κ-term over a finite alphabet A into a certain canonical form and show that different canonical forms have different interpretations over some finite semigroup. The procedure of […]
Section: Automata, Logic and Semantics

### 4. Computing the number of h-edge spanning forests in complete bipartite graphs

Let fm,n,h be the number of spanning forests with h edges in the complete bipartite graph Km,n. Kirchhoff\textquoterights Matrix Tree Theorem implies fm,n,m+n-1=mn-1 nm-1 when m &#x2265;1 and n &#x2265;1, since fm,n,m+n-1 is the number of spanning trees in Km,n. In this paper, we give an […]
Section: Analysis of Algorithms

### 5. An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n+1) - p(n) ≤ 2

An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n + 1) − p(n) ≤ 2 S. Ferenczi proved that any minimal subshift with first difference of complexity bounded by 2 is S-adic with Card(S) ≤ 3 27. In this paper, we improve this result by giving an S-adic […]
Section: Automata, Logic and Semantics

### 6. A combinatorial non-commutative Hopf algebra of graphs

A non-commutative, planar, Hopf algebra of planar rooted trees was defined independently by one of the authors in Foissy (2002) and by R. Holtkamp in Holtkamp (2003). In this paper we propose such a non-commutative Hopf algebra for graphs. In order to define a non-commutative product we use a […]
Section: Combinatorics

### 7. Descents after maxima in compositions

We consider compositions of n, i.e., sequences of positive integers (or parts) (σi)i=1k where σ1+σ2+...+σk=n. We define a maximum to be any part which is not less than any other part. The variable of interest is the size of the descent immediately following the first and the last maximum. Using […]
Section: Combinatorics

### 8. Congruence successions in compositions

A composition is a sequence of positive integers, called parts, having a fixed sum. By an m-congruence succession, we will mean a pair of adjacent parts x and y within a composition such that x=y(modm). Here, we consider the problem of counting the compositions of size n according to the number of […]
Section: Combinatorics

### 9. Graphs where every k-subset of vertices is an identifying set

Let $G=(V,E)$ be an undirected graph without loops and multiple edges. A subset $C\subseteq V$ is called \emph{identifying} if for every vertex $x\in V$ the intersection of $C$ and the closed neighbourhood of $x$ is nonempty, and these intersections are different for different vertices $x$. Let $k$ […]
Section: Combinatorics

### 10. The Price of Mediation

We study the relationship between correlated equilibria and Nash equilibria. In contrast to previous work focusing on the possible benefits of a benevolent mediator, we define and bound the Price of Mediation (PoM): the ratio of the social cost (or utility) of the worst correlated equilibrium to the […]
Section: Discrete Algorithms

### 11. A Parameterized Measure-and-ConquerAnalysis for Finding a k-Leaf Spanning Treein an Undirected Graph

The problem of finding a spanning tree in an undirected graph with a maximum number of leaves is known to be NP-hard. We present an algorithm which finds a spanning tree with at least k leaves in time O*(3.4575k) which improves the currently best algorithm. The estimation of the running time is done […]
Section: Discrete Algorithms

### 12. List circular backbone colouring

A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, […]
Section: Graph Theory

### 13. On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph

A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence τ=(n1,\textellipsis,nk) of positive integers that sum up to n, there exists a partition (V1,\textellipsis,Vk) of the vertex set V(G) such that each set Vi induces a connected subgraph of order ni. A graph […]
Section: Graph Theory

### 14. A variant of Niessen’s problem on degreesequences of graphs

Let (a1,a2,\textellipsis,an) and (b1,b2,\textellipsis,bn) be two sequences of nonnegative integers satisfying the condition that b1>=b2>=...>=bn, ai<= bi for i=1,2,\textellipsis,n and ai+bi>=ai+1+bi+1 for i=1,2,\textellipsis, n-1. In this paper, we give two different conditions, one […]
Section: Graph Theory

### 15. On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs

For a positive integer n∈ℕ and a set D⊆ ℕ, the distance graph GnD has vertex set &#x007b; 0,1,\textellipsis,n-1&#x007d; and two vertices i and j of GnD are adjacent exactly if |j-i|∈D. The condition gcd(D)=1 is necessary for a distance graph GnD being connected. Let […]
Section: Graph Theory

### 16. The Price of Connectivity for Vertex Cover

The vertex cover number of a graph is the minimum number of vertices that are needed to cover all edges. When those vertices are further required to induce a connected subgraph, the corresponding number is called the connected vertex cover number, and is always greater or equal to the vertex cover […]
Section: Graph Theory

### 17. The total irregularity of a graph

In this note a new measure of irregularity of a graph G is introduced. It is named the total irregularity of a graph and is defined as irr(t)(G) - 1/2 Sigma(u, v is an element of V(G)) vertical bar d(G)(u) - d(G)(v)vertical bar, where d(G)(u) denotes the degree of a vertex u is an element of V(G). […]
Section: Graph Theory

### 18. On the Meyniel condition for hamiltonicity in bipartite digraphs

We prove a sharp Meyniel-type criterion for hamiltonicity of a balanced bipartite digraph: For a&#x2265;2, a strongly connected balanced bipartite digraph D on 2a vertices is hamiltonian if d(u)+d(v)&#x2265;3a whenever uv∉A(D) and vu∉A(D). As a consequence, we obtain a sharp sufficient […]
Section: Graph Theory

### 19. On size, radius and minimum degree

Let G be a finite connected graph. We give an asymptotically tight upper bound on the size of G in terms of order, radius and minimum degree. Our result is a strengthening of an old classical theorem of Vizing (1967) if minimum degree is prescribed.
Section: Graph Theory

### 20. The generalized 3-connectivity of Lexicographic product graphs

The generalized k-connectivity κk(G) of a graph G, first introduced by Hager, is a natural generalization of the concept of (vertex-)connectivity. Denote by G^H and G&Box;H the lexicographic product and Cartesian product of two graphs G and H, respectively. In this paper, we prove that for any […]
Section: Graph Theory

### 21. Efficient open domination in graph products

A graph G is an efficient open domination graph if there exists a subset D of V(G) for which the open neighborhoods centered in vertices of D form a partition of V(G). We completely describe efficient open domination graphs among lexicographic, strong, and disjunctive products of graphs. For the […]
Section: Graph Theory

### 22. Computation with No Memory, and Rearrangeable Multicast Networks

We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one component at a time, hence using no extra memory. In this paper, we survey this problem introduced in previous […]

### 23. Strong parity vertex coloring of plane graphs

A strong parity vertex coloring of a 2-connected plane graph is a coloring of the vertices such that every face is incident with zero or an odd number of vertices of each color. We prove that every 2-connected loopless plane graph has a strong parity vertex coloring with 97 colors. Moreover the […]
Section: Graph Theory