Օբյեկտ

Վերնագիր: A new sufficient condition for a digraph to be Hamiltonian−A proof of Manoussakis conjecture

Հեղինակ:

Darbinyan Samvel Kh.

Տեսակ:

article

Ամփոփում:

In this paper, we confirm this conjecture. Moreover, we prove that if a digraph D satisfies the conditions of this conjecture and has a pair of non-adjacent vertices {x, y} such that d(x) + d(y)  2n − 4, then D contains cycles of all lengths 3, 4, . . . , n.

Հրատարակիչ:

DMTCS

Հանձնման ամսաթիվը:

2020-02-11

Ընդունման ամսաթիվը:

2020-11-05

Փոփոխման ամսաթիվը:

2020-07-21, 2020-11-05,

Հրատարակման ամսաթիվ:

2021-01-18

Նույնականացուցիչ:

oai:noad.sci.am:136199

DOI:

10.23638/DMTCS-22-4-12

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Discrete Mathematics & Theoretical Computer Science

Հատոր:

22

Համար:

4

URL:


լրացուցիչ տեղեկատվություն:

The author would like to thank the anonymous referees for thoroughly review and many helpful commentsand suggestions which improved substantially the rewriting of this paper. We also thank PhD P. Hakobyanfor formatting the manuscript of this paper.

Կազմակերպության անվանում:

Institute for Informatics and Automation Problems of NAS RA

Տարի:

2021

Հիշատակումներ:

J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London,2000. ; A. Benhocine. Pancyclism and Meyniel’s conditions. Discrete Math., 58:113–120, 1986. ; J.-C. Bermond and C. Thomassen. Cycles in digraphs − a survey. J. Graph Theory, 5(1):1–43, 1981. ; J. Bondy and C. Thomassen. A short proof of Meyniel’s theorem. Discrete Math., 19:195–197, 1977. ; S. Darbinyan. On Hamiltonian bypasses in digraphs with the condition of Y. Manoussakis. In Proc-ceedings Conference Computer Science and Information Tecnologies, (CSIT 2015). Yerevan, 2015, pp.53-63. doi: 10.1109/CSITechnol.2015.7358250. ; S. Darbinyan. On pancyclic digraphs. Preprint of the Computing Center of Akademy of Sciences ofArmenia, 1979. ; S. Darbinyan. Disproof of a conjecture of Thomassen. Akad. Nauk Armyan. SSR Dokl., 76(2):51–54,1983. ; S. Darbinyan. Pancyclicity of digraphs with the Meyniel condition. Studia Sci. Math. Hungar., (Ph.D.Thesis, Institute Mathematici Akad. Nauk BSSR, Minsk, 1981), 20(1-4):95–117, 1985. ; S. Darbinyan. Hamiltonian and strongly Hamilton-connected digraphs. Akad. Nauk Armyan. SSR Dokl.,(for a detailed proof see arXiv: 1801.05166v1, 16 Jan. 2018), 91(1):3–6, 1990. ; S. Darbinyan. On cyclability of digraphs with a Manoussakis’-type condition. Transactions of IIAP NASRA, Mathematical Problems of Computer Science, 47:15–29, 2017. ; S. Darbinyan. Some remarks on Manoussakis conjecture for a digraph to be hamiltonian. Emil ArtinInternational Conference, Yerevan, Armenia, May 27-June 2, pages 39–40, 2018. ; S. Darbinyan. On the Manoussakis conjecture for a digraph to be hamiltonian. Transactions of IIAP NASRA, Mathematical Problems of Computer Science, 51:21–38, 2019. ; S. Darbinyan and I. Karapetyan. On pre-Hamiltonian cycles in Hamiltonian digraphs. Transactions ofIIAP NAS RA, Mathematical Problems of Computer Science, 43:5–25, 2015. ; A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit hamiltonien. C. R. Acad. Sci. ParisSer. A-B, 251:495–497, 1960. ; R. Häggkvist and C. Thomassen. On pancyclic digraphs. J. Combin. Theory Ser.B, 20:20–40, 1976. ; F. Harary and L.Moser. The theory of round robin tournaments. Amer.Math.Monthly, 73:231–246, 1966. ; D. Kühn and D. Osthus. A survey on Hamilton cycles in directed graphs. European J. Combin., 33:750–766, 2012. ; H. Li, E. Flandrin, and J. Shu. A sufficient condition for cyclability of directed graphs. Discrete math.,307:1291–1297, 2007. ; Y. Manoussakis. Directed hamiltonian graphs. J. Graph Theory, 16(1):51–59, 1992. ; M. Meyniel. Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe oriente. J.Combin. Theory Ser.B, 14:137–147, 1973. ; C. S. J. A. Nash-Williams. Hamilton circuits in graphs and digraphs, the many facets of graph theory.Springer Verlag Lecture Notes, 110:237–243, 1969. ; B. Ning. Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs. InformationProcessing Letters, 115:221–224, 2015. ; O. Ore. Note on Hamilton circuits. Amer. Math. Monthly, 67:55, 1960. ; D. Woodall. Sufficient condition for circuits in graphs. Proc. London Math. Soc., 24:739–755, 1972. ; A. Yeo. How close to regular must a semicomplete multipartite digraph to be secure hamiltonicity?Graphs Combin., 15:481–493, 1999.

Ինդեքսավորում:

DBLP ; DOAJ ; MathSciNet ; Research Gate ; Scimago ; ZentralBlatt

Օբյեկտի հավաքածուներ:

Վերջին անգամ ձևափոխված:

Apr 23, 2021

Մեր գրադարանում է սկսած:

Apr 23, 2021

Օբյեկտի բովանդակության հարվածների քանակ:

9

Օբյեկտի բոլոր հասանելի տարբերակները:

https://noad.sci.am/publication/149764

Ցույց տալ նկարագրությունը RDF ձևաչափով:

RDF

Ցույց տալ նկարագրությունը OAI-PMH ձևաչափով։

OAI-PMH

Հրատարակության անուն Ամսաթիվ
A new sufficient condition for a digraph to be Hamiltonian − A proof of Manoussakis conjecture Apr 23, 2021

Այս էջը օգտագործում է 'cookie-ներ'։ Ավելի տեղեկատվություն