Weak Diameter and Cyclic Properties in Oriented Graphs

We describe several conditions on the minimum number of arcs ensuring that any two vertices in a strong oriented graph are joining by a path of length at most a given $k$, or ensuring that they are contained in a common cycle.

Weak Diameter and Cyclic Properties in Oriented Graphs Diámetro débil y propiedades cíclicas en digrafos antisimétricos DANIEL BRITO1, OSCAR ORDAZ2, MARÍA TERESA VARELA3

1Universidad de Oriente, Cumaná, Venezuela. Email: britodaniel@cantv.net 
2Universidad Central de Venezuela, Caracas, Venezuela. Email:oscarordaz55@gmail.com 
3Universidad Simón Bolívar, Caracas, Venezuela. Email: mtvarela@usb.ve 

---

Abstract

We describe several conditions on the minimum number of arcs ensuring that any two vertices in a strong oriented graph are joining by a path of length at most a given k, or ensuring that they are contained in a common cycle.

Key words: Weak diameter, 2-Cyclic, Oriented graph.

---

2000 Mathematics Subject Classification: 05B10, 11B13.

---

Resumen

Damos varias condiciones sobre el número mínimo de arcos que implican la existencia, para todo par de vértices en un digrafo antisimétrico fuertemente conexo de un camino de longitud a lo más un k dado, que los une o de un circuito que los contiene.

Palabras clave: Diamétro débil, 2-ciclíco, digrafo antisimétrico.

---

Texto completo disponible en PDF

---

References

[1] J. Bang-Jensen, `Problems and Conjectures Concerning Connectivity, Paths, Trees and Cycles in Tournament-Like Digraphs´, Discrete Mathematics 309, 18 (2009), 5655-5667.

[2] J. Bang-Jensen and G. Gutin, Digraphs. Theory, Algorithms and Applications, Second edn, Springer Monographs in Mathematics. Springer-Verlag London, Ltd., London, United Kingdom, 2009.

[3] J. Bang-Jensen, G. Gutin, and A. Yeo, `Hamiltonian Cycles avoiding Prescribed Arcs in Tournaments´, Combin. Probab. Comput. 6, 3 (1997), 255-261.

[4] J. C. Bermond and B. Bollobás, `The Diameter of Graphs. A survey´, Congressus Numerantium 32, (1981), 3-27.

[5] J. C. Bermond and C. Thomassen, `Cycles in Digraphs. A Survey´, Journal of Graph Theory 5, (1981), 1-43.

[6] B. Bollobás and A. Scott, `Separating Systems and Oriented Graphs of Diameter Two´, J. Combinatorial Theory B 97, 2 (2007), 193-203.

[7] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan, London, United Kingdom, 1976.

[8] O. Favaron and O. Ordaz, `A Sufficient Condition for Oriented Graphs to be Hamiltonian´, Discrete Math. 58, (1986), 243-252.

[9] G. Gutin, `Cycles and Paths in Semicomplete Multipartite Digraphs, Theorems and Algorithms. A Survey´,Journal of Graphs 19, (1995), 481-508.

[10] M. C. Heydemann and D. Sotteau, `About Some Cyclic Properties in Digraphs´, J. Combinatorial Theory B38, 3 (1985), 261-278.

[11] C. Thomassen, Long Cycles in Digraphs, `Proc. London Math. Soc.´, (1981), Vol. 3, p. 231-251.

[12] C. Thomassen, Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments, `Proc. London Math. Soc.´, (1982), Vol. 3, p. 151-168.

(Recibido en julio de 2010. Aceptado en agosto de 2011)

---

Este artículo se puede citar en LaTeX utilizando la siguiente referencia bibliográfica de BibTeX:

@ARTICLE{RCMv45n2a02, 
    AUTHOR  = {Brito, Daniel and Ordaz, Oscar and Varela, María Teresa}, 
    TITLE   = {{Weak Diameter and Cyclic Properties in Oriented Graphs}}, 
    JOURNAL = {Revista Colombiana de Matemáticas}, 
    YEAR    = {2011}, 
    volume  = {45}, 
    number  = {2}, 
    pages   = {129--135}