RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sib. Èlektron. Mat. Izv.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sib. Èlektron. Mat. Izv., 2018, Volume 15, Pages 1174–1181 (Mi semr986)  

Discrete mathematics and mathematical cybernetics

All tight descriptions of $3$-paths in plane graphs with girth at least $9$

V. A. Aksenova, O. V. Borodinb, A. O. Ivanovac

a Novosibirsk National Research University, str. Pirogova, 1, 630090, Novosibirsk, Russia
b Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
c Ammosov North-Eastern Federal University, str. Kulakovskogo, 48, 677000, Yakutsk, Russia

Abstract: Lebesgue (1940) proved that every plane graph with minimum degree $\delta$ at least $3$ and girth $g$ at least $5$ has a path on three vertices ($3$-path) of degree $3$ each. A description is tight if no its parameter can be strengthened, and no triplet dropped.
Borodin et al. (2013) gave a tight description of $3$-paths in plane graphs with $\delta\ge3$ and $g\ge3$, and another tight description was given by Borodin, Ivanova and Kostochka in 2017.
Borodin and Ivanova (2015) gave seven tight descriptions of $3$-paths when $\delta\ge3$ and $g\ge4$. Furthermore, they proved that this set of tight descriptions is complete, which was a result of a new type in the structural theory of plane graphs. Also, they characterized (2018) all one-term tight descriptions if $\delta\ge3$ and $g\ge3$. The problem of producing all tight descriptions for $g\ge3$ remains widely open even for $\delta\ge3$.
Recently, several tight descriptions of $3$-paths were obtained for plane graphs with $\delta=2$ and $g\ge4$ by Jendrol', Maceková, Montassier, and Soták, four of which descriptions are for $g\ge9$.
In this paper, we prove ten new tight descriptions of $3$-paths for $\delta=2$ and $g\ge9$ and show that no other tight descriptions exist.

Keywords: plane graph, structure properties, tight description, $3$-path, minimum degree, girth.

Funding Agency Grant Number
Russian Foundation for Basic Research 18-01-00353_a
16-01-00499_a
Ministry of Education and Science of the Russian Federation 1.7217.2017/6.7
The first author was supported by the Russian Foundation for Basic Research (grant 18-01-00353). The second author was supported by the Russian Foundation for Basic Research (grant 16-01-00499). The third authors work was performed as a part of government work Leading researchers on an ongoing basis (1.7217.2017/6.7).


DOI: https://doi.org/10.17377/semi.2018.15.095

Full text: PDF file (147 kB)
References: PDF file   HTML file

Bibliographic databases:

Document Type: Article
UDC: 519.172.2
MSC: 05C75
Received September 5, 2018, published October 16, 2018
Language: English

Citation: V. A. Aksenov, O. V. Borodin, A. O. Ivanova, “All tight descriptions of $3$-paths in plane graphs with girth at least $9$”, Sib. Èlektron. Mat. Izv., 15 (2018), 1174–1181

Citation in format AMSBIB
\Bibitem{AksBorIva18}
\by V.~A.~Aksenov, O.~V.~Borodin, A.~O.~Ivanova
\paper All tight descriptions of $3$-paths in plane graphs with girth at least~$9$
\jour Sib. \`Elektron. Mat. Izv.
\yr 2018
\vol 15
\pages 1174--1181
\mathnet{http://mi.mathnet.ru/semr986}
\crossref{https://doi.org/10.17377/semi.2018.15.095}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000454860200037}


Linking options:
  • http://mi.mathnet.ru/eng/semr986
  • http://mi.mathnet.ru/eng/semr/v15/p1174

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Number of views:
    This page:24
    Full text:9
    References:3

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019