Characterization of (m, n)-Linked Planar Graphs

A graph G is ( s 1 , s 2 , … , s k ) -linked, if for any k disjoint vertex sets S 1 , S 2 , … , S k with | S i | ≤ s i , G has k vertex-disjoint connected subgraphs G 1 , G 2 , … , G k such that S i ⊆ V ( G i ) for all 1 ≤ i ≤ k . The main purpose of this paper is to characterize ( s 1 , s 2 , … , s...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2022-08, Vol.38 (4), Article 131
Main Authors: Enami, Kengo, Maezawa, Shun-ichi
Format: Article
Language:English
Subjects:
Apexes
Combinatorics
Engineering Design
Graph theory
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Vertex sets
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A graph G is ( s 1 , s 2 , … , s k ) -linked, if for any k disjoint vertex sets S 1 , S 2 , … , S k with | S i | ≤ s i , G has k vertex-disjoint connected subgraphs G 1 , G 2 , … , G k such that S i ⊆ V ( G i ) for all 1 ≤ i ≤ k . The main purpose of this paper is to characterize ( s 1 , s 2 , … , s k ) -linked planar graphs. However it is easy to solve the problem for k ≥ 3 and so we mainly study the problem for k = 2 . Throughout this paper, we use a notation ( m ,  n )-linked graphs instead of ( s 1 , s 2 ) -linked graphs. Mori (Discrete Math 308:5280–5283, 2008) proved that a planar graph G with at least six vertices is (3, 3)-linked if and only if G is 4-connected and maximal. As an extension of his result, we completely characterize ( m ,  n )-linked planar graphs for any two positive integers m and n .
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-022-02537-4