Vol. 14 no. 1


1. Vertex-colouring edge-weightings with two edge weights

Khatirinejad, Mahdad ; Naserasr, Reza ; Newman, Mike ; Seamone, Ben ; Stevens, Brett.
An edge-weighting vertex colouring of a graph is an edge-weight assignment such that the accumulated weights at the vertices yields a proper vertex colouring. If such an assignment from a set S exists, we say the graph is S-weight colourable. It is conjectured that every graph with no isolated edge […]
Section: Graph and Algorithms

2. On hamiltonian chain saturated uniform hypergraphs

Dudek, Aneta ; Zak, Andrzej.
We say that a hypergraph H is hamiltonian chain saturated if H does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H. In this paper we ask about the smallest size of a k-uniform hamiltonian chain saturated hypergraph. We present a construction of a family […]
Section: Graph and Algorithms

3. A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set

Gaspers, Serge ; Liedloff, Mathieu.
An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas […]
Section: Graph and Algorithms

4. The generalized 3-connectivity of Cartesian product graphs

Li, Hengzhe ; Li, Xueliang ; Sun, Yuefang.
The generalized connectivity of a graph, which was introduced by Chartrand et al. in 1984, is a generalization of the concept of vertex connectivity. Let S be a nonempty set of vertices of G, a collection \T-1, T (2), ... , T-r\ of trees in G is said to be internally disjoint trees connecting S if […]
Section: Graph Theory

5. Optimal Computer Crash Performance Precaution

Laksman, Efraim ; Lennerstad, Hakan ; Lundberg, Lars.
For a parallel computer system with m identical computers, we study optimal performance precaution for one possible computer crash. We want to calculate the cost of crash precaution in the case of no crash. We thus define a tolerance level r meaning that we only tolerate that the completion time of […]
Section: Distributed Computing and Networking

6. Adaptive Identification of Sets of Vertices in Graphs

Junnila, Ville.
In this paper, we consider a concept of adaptive identification of vertices and sets of vertices in different graphs, which was recently introduced by Ben-Haim, Gravier, Lobstein and Moncel (2008). The motivation for adaptive identification comes from applications such as sensor networks and fault […]
Section: Combinatorics

7. Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law

Bell, Jason P. ; Burris, Stanley N. ; Yeats, Karen A..
Let T be a monadic-second order class of finite trees, and let T(x) be its (ordinary) generating function, with radius of convergence rho. If rho >= 1 then T has an explicit specification (without using recursion) in terms of the operations of union, sum, stack, and the multiset operators n and […]
Section: Automata, Logic and Semantics

8. Bounds for the minimum oriented diameter

Kurz, Sascha ; Laetsch, Martin.
We consider the problem of determining an orientation with minimum diameter MOD(G) of a connected and bridge-less graph G. In 2001 Fomin et al. discovered the relation MOD(G) <= 9 gamma(G) - 5 between the minimum oriented diameter and the size gamma(G) of a minimum dominating set. We improve […]
Section: Graph and Algorithms

9. A linear time algorithm for finding an Euler walk in a strongly connected 3-uniform hypergraph

Lonc, Zbigniew ; Naroski, Pawel.
By an Euler walk in a 3-uniform hypergraph H we mean an alternating sequence v(0), epsilon(1), v(1), epsilon(2), v(2), ... , v(m-1), epsilon(m), v(m) of vertices and edges in H such that each edge of H appears in this sequence exactly once and v(i-1); v(i) is an element of epsilon(i), v(i-1) not […]
Section: Discrete Algorithms

10. alpha-Labelings and the Structure of Trees with Nonzero alpha-Deficit

Brinkmann, Gunnar ; Crevals, Simon ; Melot, Hadrien ; Rylands, Leanne ; Steffen, Eckhard.
We present theoretical and computational results on alpha-labelings of trees. The theorems proved in this paper were inspired by the results of a computer investigation of alpha-labelings of all trees with up to 26 vertices, all trees with maximum degree 3 and up to 36 vertices, all trees with […]
Section: Graph Theory

11. The Join of the Varieties of R-trivial and L-trivial Monoids via Combinatorics on Words

Kufleitner, Manfred ; Lauser, Alexander.
The join of two varieties is the smallest variety containing both. In finite semigroup theory, the varieties of R-trivial and L-trivial monoids are two of the most prominent classes of finite monoids. Their join is known to be decidable due to a result of Almeida and Azevedo. In this paper, we give […]
Section: Automata, Logic and Semantics