New bounds on maximal linkless graphs

Naimi, Ramin; Pavelescu, Andrei; Pavelescu, Elena

doi:10.2140/agt.2023.23.2545

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the Journal

Editorial Board

Subscriptions

Submission Guidelines

Submission Page

Policies for Authors

Ethics Statement

ISSN 1472-2739 (online)

ISSN 1472-2747 (print)

Author Index

To Appear

Other MSP Journals

New bounds on maximal linkless graphs

Ramin Naimi, Andrei Pavelescu and Elena Pavelescu

Algebraic & Geometric Topology 23 (2023) 2545–2559

DOI: 10.2140/agt.2023.23.2545

Abstract

We construct a family of maximal linklessly embeddable graphs on $n$ vertices and $3 n - 5$ edges for all $n \geq 10$ , and another family on $n$ vertices and $m < \frac{25}{12} n - \frac{1}{4}$ edges for all $n \geq 13$ . The latter significantly improves the lowest edge-to-vertex ratio for any previously known infinite family. We construct a family of graphs showing that the class of maximal linklessly embeddable graphs differs from the class of graphs that are maximal without a $K_{6}$ minor studied by L Jørgensen. We give necessary and sufficient conditions for when the clique sum of two maximal linklessly embeddable graphs over $K_{2}$ , $K_{3}$ or $K_{4}$ is a maximal linklessly embeddable graph, and use these results to prove our constructions yield maximal linklessly embeddable graphs.

Keywords

maximal linkless graphs, clique sums

Mathematical Subject Classification

Primary: 57M15

Secondary: 05C10

References

Publication

Received: 19 September 2020

Revised: 28 December 2021

Accepted: 18 January 2022

Published: 7 September 2023

Authors

Ramin Naimi
Department of Mathematics Occidental College Los Angeles, CA United States

Andrei Pavelescu
Mathematics and Statistics Department University of South Alabama Mobile, AL United States

Elena Pavelescu
Mathematics and Statistics Department University of South Alabama Mobile, AL United States

Open Access made possible by participating institutions via Subscribe to Open.

Volume 23, issue 6 (2023)