Geodesic
On the maximum degree of path-pairable planar graphs
António Girão1 ; Gábor Mészáros2 ; Kamil Popielarz2 ; Richard Snyder2
1University of Cambridge
2University of Memphis
The electronic journal of combinatorics, Tome 26 (2019) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A graph is path-pairable if for any pairing of its vertices there exist edge-disjoint paths joining the vertices in each pair. We investigate the behaviour of the maximum degree in path-pairable planar graphs. We show that any $n$-vertex path-pairable planar graph must contain a vertex of degree linear in $n$. Our result generalizes to graphs embeddable on a surface of finite genus.
DOI : 10.37236/7291
Classification : 05C07, 05C10, 05C35, 05C40, 05C38

António Girão  1   ; Gábor Mészáros  2   ; Kamil Popielarz  2   ; Richard Snyder  2

1 University of Cambridge
2 University of Memphis 
@article{10_37236_7291,
     author = {Ant\'onio Gir\~ao and G\'abor M\'esz\'aros and Kamil Popielarz and Richard Snyder},
     title = {On the maximum degree of path-pairable planar graphs},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {2},
     doi = {10.37236/7291},
     zbl = {1410.05024},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7291/}
}
TY  - JOUR
AU  - António Girão
AU  - Gábor Mészáros
AU  - Kamil Popielarz
AU  - Richard Snyder
TI  - On the maximum degree of path-pairable planar graphs
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7291/
DO  - 10.37236/7291
ID  - 10_37236_7291
ER  - 
%0 Journal Article
%A António Girão
%A Gábor Mészáros
%A Kamil Popielarz
%A Richard Snyder
%T On the maximum degree of path-pairable planar graphs
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7291/
%R 10.37236/7291
%F 10_37236_7291
António Girão; Gábor Mészáros; Kamil Popielarz; Richard Snyder. On the maximum degree of path-pairable planar graphs. The electronic journal of combinatorics, Tome 26 (2019) no. 2. doi: 10.37236/7291

Cité par Sources :