Search Results

You are looking at 1 - 3 of 3 items for

  • Author: Juan José Montellano-Ballesteros x
Clear All Modify Search
Open access

César Hernández-Cruz and Juan José Montellano-Ballesteros

Abstract

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 that in most cases, such digraphs are complete digraphs or cycle extensions. Also, the obtained results are used to prove some particular cases of the Laborde-Payan-Xuong Conjecture.

Open access

Jesús Alva-Samos and Juan José Montellano-Ballesteros

Abstract

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 rainbow connection number of a cactus and characterize those cacti whose rainbow connection number is equal to any of those bounds. Also, we calculate the rainbow con- nection numbers of some infinite digraphs and graphs, and present, for each n ≥ 6, a tournament of order n and rainbow connection number equal to 2.

Open access

Juan José Montellano-Ballesteros and Anahy Santiago Arguello

Abstract

A variant of the Lovász Conjecture on hamiltonian paths states that every finite connected Cayley graph contains a hamiltonian cycle. Given a finite group G and a connection set S, the Cayley graph Cay(G, S) will be called normal if for every gG we have that g −1 Sg = S. In this paper we present some conditions on the connection set of a normal Cayley graph which imply the existence of a hamiltonian cycle in the graph.