Geodesic
New bounds on maximal linkless graphs
Naimi, Ramin1 ; Pavelescu, Andrei2 ; Pavelescu, Elena2
1 Department of Mathematics, Occidental College, Los Angeles, CA, United States
2 Mathematics and Statistics Department, University of South Alabama, Mobile, AL, United States
Algebraic and Geometric Topology, Tome 23 (2023) no. 6, pp. 2545-2559

Voir la notice de l'article provenant de la source Mathematical Sciences Publishers

We construct a family of maximal linklessly embeddable graphs on n vertices and 3n − 5 edges for all n ≥ 10, and another family on n vertices and m < 25 12n −1 4 edges for all n ≥ 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 K6 minor studied by L Jørgensen. We give necessary and sufficient conditions for when the clique sum of two maximal linklessly embeddable graphs over K2, K3 or K4 is a maximal linklessly embeddable graph, and use these results to prove our constructions yield maximal linklessly embeddable graphs.

DOI : 10.2140/agt.2023.23.2545
Keywords: maximal linkless graphs, clique sums

Naimi, Ramin 1 ; Pavelescu, Andrei 2 ; Pavelescu, Elena 2

1 Department of Mathematics, Occidental College, Los Angeles, CA, United States
2 Mathematics and Statistics Department, University of South Alabama, Mobile, AL, United States 
@article{10_2140_agt_2023_23_2545,
     author = {Naimi, Ramin and Pavelescu, Andrei and Pavelescu, Elena},
     title = {New bounds on maximal linkless graphs},
     journal = {Algebraic and Geometric Topology},
     pages = {2545--2559},
     publisher = {mathdoc},
     volume = {23},
     number = {6},
     year = {2023},
     doi = {10.2140/agt.2023.23.2545},
     url = {http://geodesic.mathdoc.fr/articles/10.2140/agt.2023.23.2545/}
}
TY  - JOUR
AU  - Naimi, Ramin
AU  - Pavelescu, Andrei
AU  - Pavelescu, Elena
TI  - New bounds on maximal linkless graphs
JO  - Algebraic and Geometric Topology
PY  - 2023
SP  - 2545
EP  - 2559
VL  - 23
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.2140/agt.2023.23.2545/
DO  - 10.2140/agt.2023.23.2545
ID  - 10_2140_agt_2023_23_2545
ER  - 
%0 Journal Article
%A Naimi, Ramin
%A Pavelescu, Andrei
%A Pavelescu, Elena
%T New bounds on maximal linkless graphs
%J Algebraic and Geometric Topology
%D 2023
%P 2545-2559
%V 23
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.2140/agt.2023.23.2545/
%R 10.2140/agt.2023.23.2545
%F 10_2140_agt_2023_23_2545
Naimi, Ramin; Pavelescu, Andrei; Pavelescu, Elena. New bounds on maximal linkless graphs. Algebraic and Geometric Topology, Tome 23 (2023) no. 6, pp. 2545-2559. doi: 10.2140/agt.2023.23.2545

Cité par Sources :