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

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

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

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

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

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

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

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

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

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

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