Let G = (V(G), E(G)) be a connected multigraph and let h(G) be the minimum integer k such that for every edge-colouring of G, using exactly k colours, there is at least one edge-cut of G all of whose edges receive different colours. In this note it is proved that if G has at least 2 vertices and has no bridges, then h(G) = |E(G)| -|V(G)| + 2.
A digraph D is k-transitive if the existence of a directed path (v0, v1, . . . , vk), of length k implies that (v0, vk) ∈ A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an acyclic transitive digraph. Also, strong 3 and 4-transitive digraphs have been characterized. In this work we analyze the structure of strong k-transitive digraphs having a cycle of length at least k. We show...
We present several results concerning the Laborde-Payan-Xuang conjecture stating that in every digraph there exists an independent set of vertices intersecting every longest path. The digraphs we consider are defined in terms of local semicompleteness and local transitivity. We also look at oriented graphs for which the length of a longest path does not exceed 4.
An arc-coloured digraph D = (V,A) is said to be rainbow connected if for every pair {u, v} ⊆ V there is a directed uv-path all whose arcs have different colours and a directed vu-path all whose arcs have different colours. The minimum number of colours required to make the digraph D rainbow connected is called the rainbow connection number of D, denoted rc⃗ (D). A cactus is a digraph where each arc belongs to exactly one directed cycle. In this paper we give sharp upper and lower bounds for the...
Page 1