Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

A note on possible density and diameter of counterexamples to the Seymour's second neighborhood conjecture

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
  • معلومة اضافية
    • بيانات النشر:
      AGH Univeristy of Science and Technology Press, 2021.
    • الموضوع:
      2021
    • نبذة مختصرة :
      Seymour's second neighborhood conjecture states that every simple digraph without loops or 2-cycles contains a vertex whose second neighborhood is at least as large as its first. In this paper we show, that from falsity of Seymour's second neighborhood conjecture it follows that there exist strongly-connected counterexamples with both low and high density (dense and sparse graph). Moreover, we show that if there is a counterexample to conjecture, then it is possible to construct counterexample with any diameter \(k\geq 3\).
    • ISSN:
      1232-9274
    • Rights:
      OPEN
    • الرقم المعرف:
      edsair.doi.dedup.....511e023d611d9c9743e3f47c4bf13c09