Opuscula Math. 41, no. 4 (2021), 601-605
https://doi.org/10.7494/OpMath.2021.41.4.601

 
Opuscula Mathematica

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

Oleksiy Zelenskiy
Valentyna Darmosiuk
Illia Nalivayko

Abstract. 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\).

Keywords: graph theory, Seymour's second neighborhood conjecture, density of graph, diameter of graph.

Mathematics Subject Classification: 05C12, 05C20, 05C42.

Full text (pdf)

  1. N. Dean, B.J. Latka, Squaring the tournament - an open problem, [in:] Proceedings of the Twenty-sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995) 109 (1995), 73-80.
  2. D.C. Fisher, Squaring a tournament: A proof of Dean's conjecture, J. Graph Theory 23 (1996), no. 1, 43-48.
  3. Y. Kaneko, S.C. Locke, The minimum degree approach for Paul Seymour's distance 2 conjecture, [in:] Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001) 148 (2001), 201-206.
  • Oleksiy Zelenskiy
  • Kamyanets-Podilsky Ivan Ohienko National University, Department of Physics and Mathematics, Ohienko Str. 61, 32 300, Kamianets-Podilsky, Ukraine
  • Valentyna Darmosiuk (corresponding author)
  • ORCID iD https://orcid.org/0000-0003-3275-8249
  • V.O. Sukhomlynskyi Mykolaiv National University, Department of Physics and Mathematics, Nikolska Str. 24, Mykolaiv 54 001, Ukraine
  • Illia Nalivayko
  • Kamyanets-Podilsky Gymnasium 14, Heroes of the Heavenly Hundred Str. 17, 32 300, Kamianets-Podilsky, Ukraine
  • Communicated by Adam Paweł Wojda.
  • Received: 2020-11-03.
  • Revised: 2021-03-21.
  • Accepted: 2021-03-22.
  • Published online: 2021-07-09.
Opuscula Mathematica - cover

Cite this article as:
Oleksiy Zelenskiy, Valentyna Darmosiuk, Illia Nalivayko, A note on possible density and diameter of counterexamples to the Seymour's second neighborhood conjecture, Opuscula Math. 41, no. 4 (2021), 601-605, https://doi.org/10.7494/OpMath.2021.41.4.601

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.