Vol. 16 no. 1 (in progress)


1. List circular backbone colouring

Havet, Frederic ; King, Andrew D..
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

Kaiser, Tomas ; Rucky, Ondrej ; Stehlik, Matej ; Skrekovski, Riste.
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 […]

3. Canonical forms for free κ-semigroups

Costa, José Carlos.
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

Stones, Rebecca, .
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 ≥1 and n ≥1, since fm,n,m+n-1 is the number of spanning trees in Km,n. In this paper, we give an algorithm […]
Section: Analysis of Algorithms

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

Leroy, Julien.
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

Tanasa, Adrian ; Duchamp, Gerard ; Foissy, Loïc ; Hoang-Nghia, Nguyen ; Manchon, Dominique.
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

Blecher, Aubrey ; Brennan, Charlotte ; Knopfmacher, Arnold.
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

Mansour, Toufik ; Shattuck, Mark ; Wilson, Mark, .
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

Gravier, Sylvain ; Janson, Svante ; Laihonen, Tero ; Ranto, Sanna.
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

Bradonjic, Milan ; Ercal, Gunes ; Meyerson, Adam ; Roytman, Alan.
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

Binkele-Raible, Daniel ; Fernau, Henning.
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

Havet, Frédéric ; King, Andrew.
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

Baudon, Olivier ; Bensmail, Julien ; Kalinowski, Rafał ; Marczyk, Antoni ; Przybyło, Jakub ; Wozniak, Mariusz.
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

Guo, Jiyun ; Yin, Jianhua.
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 of which is&nbsp;[&hellip;]
Section: Graph Theory

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

Löwenstein, Christian ; Rautenbach, Dieter ; Soták, Roman.
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 D=&#x007b;d1,d2&#x007d;⊆ℕ be such&nbsp;[&hellip;]
Section: Graph Theory

16. The Price of Connectivity for Vertex Cover

Camby, Eglantine ; Cardinal, Jean ; Fiorini, Samuel ; Schaudt, Oliver.
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&nbsp;[&hellip;]
Section: Graph Theory

17. The total irregularity of a graph

Abdo, Hosam ; Brandt, Stephan ; Dimitrov, D..
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).&nbsp;[&hellip;]
Section: Graph Theory

18. On the Meyniel condition for hamiltonicity in bipartite digraphs

Adamus, Janusz ; Adamus, Lech ; Yeo, Anders.
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 condition for&nbsp;[&hellip;]
Section: Graph Theory

19. On size, radius and minimum degree

Mukwembi, Simon.
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

Li, Xueliang ; Mao, Yaping.
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 two&nbsp;[&hellip;]
Section: Graph Theory

21. Efficient open domination in graph products

Kuziak, Dorota ; Peterin, Iztok ; Yero, Ismael Gonzalez.
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&nbsp;[&hellip;]
Section: Graph Theory

22. Computation with No Memory, and Rearrangeable Multicast Networks

Gioan, Emeric ; Burckel, Serge ; Thomé, Emmanuel.
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 papers by&nbsp;[&hellip;]

23. Strong parity vertex coloring of plane graphs

Kaiser, Tomas ; Rucky, Ondrej ; Stehlik, Matej ; Škrekovski, Riste.
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&nbsp;[&hellip;]
Section: Graph Theory