Bipartite intrinsically knotted graphs with 23 edges

Hyoungjun Kim; Thomas Mattman; Seungsang Oh

doi:10.1016/j.disc.2022.113022

Bipartite intrinsically knotted graphs with 23 edges

Hyoungjun Kim, Thomas Mattman, Seungsang Oh

Research output: Contribution to journal › Article › peer-review

Abstract

A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that there are exactly 14 intrinsically knotted graphs with 21 edges, in which the Heawood graph is the only bipartite graph. The authors showed that there are exactly two graphs with at most 22 edges that are minor minimal bipartite intrinsically knotted: the Heawood graph and Cousin 110 of the E₉+e family. In this paper we show that there are exactly six bipartite intrinsically knotted graphs with 23 edges so that every vertex has degree 3 or more. Four among them contain the Heawood graph and the other two contain Cousin 110 of the E₉+e family. Consequently, there is no minor minimal intrinsically knotted graph with 23 edges that is bipartite.

Original language	English
Article number	113022
Journal	Discrete Mathematics
Volume	345
Issue number	11
DOIs	https://doi.org/10.1016/j.disc.2022.113022
Publication status	Published - 2022 Nov

Bibliographical note

Funding Information:
The first author was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government Ministry of Science and ICT (NRF-2018R1C1B6006692).The third author was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. NRF-2017R1A2B2007216).

Publisher Copyright:
© 2022 The Authors

Keywords

Graph embedding
Intrinsically knotted

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2022.113022

Cite this

@article{7fc37451451c423c996a2227777ae4fe,

title = "Bipartite intrinsically knotted graphs with 23 edges",

abstract = "A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that there are exactly 14 intrinsically knotted graphs with 21 edges, in which the Heawood graph is the only bipartite graph. The authors showed that there are exactly two graphs with at most 22 edges that are minor minimal bipartite intrinsically knotted: the Heawood graph and Cousin 110 of the E9+e family. In this paper we show that there are exactly six bipartite intrinsically knotted graphs with 23 edges so that every vertex has degree 3 or more. Four among them contain the Heawood graph and the other two contain Cousin 110 of the E9+e family. Consequently, there is no minor minimal intrinsically knotted graph with 23 edges that is bipartite.",

keywords = "Graph embedding, Intrinsically knotted",

author = "Hyoungjun Kim and Thomas Mattman and Seungsang Oh",

note = "Funding Information: The first author was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government Ministry of Science and ICT (NRF-2018R1C1B6006692).The third author was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. NRF-2017R1A2B2007216). Publisher Copyright: {\textcopyright} 2022 The Authors",

year = "2022",

month = nov,

doi = "10.1016/j.disc.2022.113022",

language = "English",

volume = "345",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "11",

}

TY - JOUR

T1 - Bipartite intrinsically knotted graphs with 23 edges

AU - Kim, Hyoungjun

AU - Mattman, Thomas

AU - Oh, Seungsang

N1 - Funding Information: The first author was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government Ministry of Science and ICT (NRF-2018R1C1B6006692).The third author was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) (No. NRF-2017R1A2B2007216). Publisher Copyright: © 2022 The Authors

PY - 2022/11

Y1 - 2022/11

N2 - A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that there are exactly 14 intrinsically knotted graphs with 21 edges, in which the Heawood graph is the only bipartite graph. The authors showed that there are exactly two graphs with at most 22 edges that are minor minimal bipartite intrinsically knotted: the Heawood graph and Cousin 110 of the E9+e family. In this paper we show that there are exactly six bipartite intrinsically knotted graphs with 23 edges so that every vertex has degree 3 or more. Four among them contain the Heawood graph and the other two contain Cousin 110 of the E9+e family. Consequently, there is no minor minimal intrinsically knotted graph with 23 edges that is bipartite.

AB - A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that there are exactly 14 intrinsically knotted graphs with 21 edges, in which the Heawood graph is the only bipartite graph. The authors showed that there are exactly two graphs with at most 22 edges that are minor minimal bipartite intrinsically knotted: the Heawood graph and Cousin 110 of the E9+e family. In this paper we show that there are exactly six bipartite intrinsically knotted graphs with 23 edges so that every vertex has degree 3 or more. Four among them contain the Heawood graph and the other two contain Cousin 110 of the E9+e family. Consequently, there is no minor minimal intrinsically knotted graph with 23 edges that is bipartite.

KW - Graph embedding

KW - Intrinsically knotted

UR - http://www.scopus.com/inward/record.url?scp=85132235784&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2022.113022

DO - 10.1016/j.disc.2022.113022

M3 - Article

AN - SCOPUS:85132235784

SN - 0012-365X

VL - 345

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 11

M1 - 113022

ER -

Bipartite intrinsically knotted graphs with 23 edges

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this