math.CO

# Title:Edge-maximal graphs on orientable and some non-orientable surfaces

Abstract: We study edge-maximal, non-complete graphs on surfaces that do not triangulate the surface. We prove that there is no such graph on the projective plane $\mathbb{N}_1$, $K_7-e$ is the unique such graph on the Klein bottle $\mathbb{N}_2$ and $K_8-E(C_5)$ is the unique such graph on the torus $\mathbb{S}_1$. In contrast to this for each $g\ge 2$ we construct an infinite family of such graphs on the orientable surface $\mathbb{S}_g$ of genus $g$, that are $\lfloor \frac{g}{2} \rfloor$ edges short of a triangulation.
 Comments: 18 pages, 19 figures Subjects: Combinatorics (math.CO) MSC classes: 05C35, 05C62 Cite as: arXiv:1911.02666 [math.CO] (or arXiv:1911.02666v1 [math.CO] for this version)

## Submission history

From: James Davies [view email]
[v1] Wed, 6 Nov 2019 22:59:00 UTC (25 KB)
{"ft_lang_label":"__label__en","ft_lang_prob":0.77098477,"math_prob":0.9834323,"size":807,"snap":"2019-43-2019-47","text_gpt3_token_len":236,"char_repetition_ratio":0.12826899,"word_repetition_ratio":0.051282052,"special_character_ratio":0.2812887,"punctuation_ratio":0.08974359,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9927763,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-11-19T06:01:22Z\",\"WARC-Record-ID\":\"<urn:uuid:59bee177-c3ab-469f-9615-ced3ef9648e8>\",\"Content-Length\":\"18155\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b4268e8c-14b0-48bd-b392-aade546b0c41>\",\"WARC-Concurrent-To\":\"<urn:uuid:7b16f9ed-96ca-455a-a0b0-3b0d48836769>\",\"WARC-IP-Address\":\"128.84.21.199\",\"WARC-Target-URI\":\"https://arxiv.org/abs/1911.02666\",\"WARC-Payload-Digest\":\"sha1:NK45NSQV32L4IOBTK7ZMGZ2H5SKWG43W\",\"WARC-Block-Digest\":\"sha1:HHUVDKEONCOBLOSUH37VN63MYJX2ROFX\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-47/CC-MAIN-2019-47_segments_1573496670006.89_warc_CC-MAIN-20191119042928-20191119070928-00064.warc.gz\"}"}