A Note on Short Paths in Oriented Graphs

Authors

  • Samvel Kh. Darbinyan Institute for Informatics and Automation Problems of NAS RA
  • Iskandar A. Karapetyan Institute for Informatics and Automation Problems of NAS RA

Abstract

Let G be an oriented graph of order p ¸ 3 and minimum semi-degrees at least [p=2]-k for a positive integer k. For a subset C of vertices G, we obtain sufficient conditions implying that for any pair of distinct vertices x; y 2 V (G)-C there is a path from x to y of length less than a given integer which does not contain the vertices of C.

References

J. Bang-Jensen and G. Gutin, Digraphs. Theory. Algorithms and Applications, Springer, 2000.

J.D. Ullman, Computational Aspects of VLSI, Computer Science Press, 1984.

Downloads

Published

2021-12-10

How to Cite

Darbinyan, S. K. ., & Karapetyan, I. A. . (2021). A Note on Short Paths in Oriented Graphs. Mathematical Problems of Computer Science, 33, 35–40. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/327

Issue

Vol. 33 (2010): Mathematical Problems of Computer Science

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.