Linkage problem on optimal $1$-planar graphs

Abstract

Enami and Maezawa [3] give a complete characterization of $(s_{1},s_{2},\ldots,s_{k})$-linked planar graphs for any $k$-tuple of positive integers. In this paper, we investigate linkage problems for optimal 1-planar graphs. In particular, we show that every optimal 1-planar graph with connectivity $6$ is $(5,5)$-linked. Moreover, for an optimal $1$-planar graph $G$ that is not $(2,2,1)$-linked, we characterize disjoint vertex subsets $S_{1},S_{2},S_{3}$ in $G$ with $|S_{1}|=|S_{2}|=2$ and $|S_{3}|=1$ such that $G$ is not $\{S_{1},S_{2},S_{3}\}$-linked.

Keywords: linkage problem, $(s_{1},s_{2},\ldots,s_{k})$-linked, optimal $1$-planar graph.

1 Introduction

Throughout this paper, we consider only finite and simple graphs. We denote the vertex set and the edge set of a graph $G$ by $V(G)$ and $E(G)$, respectively. For a vertex subset $S\subset V(G)$, we denote the induced subgraph of $G$ on $S$ by $G[S]$. A vertex subset $S$ of a connected graph $G$ is a cut if $G-S$ is disconnected. For a cut $S$ of $G$, $S$ is a $k$-cut of $G$ if $|S|=k$. A cycle with length $k$ is a $k$-cycle. A cycle $C$ in $G$ is separating if $V(C)$ is a cut.

A graph $G$ is $k$-linked if for any distinct $2k$ vertices $a_{1},\ldots,a_{k},b_{1},\ldots,b_{k}$, $G$ has disjoint $k$ paths $P_{1},P_{2},\ldots,P_{k}$ such that $P_{i}$ joins $a_{i}$ and $b_{i}$ for all $i$. This notion has been extensively studied (see [7, 16]). Let $S_{1},S_{2},\ldots,S_{k}$ be $k$ non-empty disjoint vertex subsets of $G$. A graph $G$ is $\{S_{1},S_{2},\ldots,S_{k}\}$-linked, if $G$ contains vertex-disjoint connected subgraphs $G_{1},G_{2},\ldots,G_{k}$ such that $S_{i}\subset V(G_{i})$ for all $i$. Let $s_{1},s_{2},\ldots,s_{k}$ be $k$ positive integers. Then, $G$ is $(s_{1},s_{2},\ldots,s_{k})$-linked if $G$ has at least $\sum_{i=1}^{k}s_{i}$ vertices and for any $k$ disjoint vertex subsets $S_{1},S_{2},\ldots,S_{k}$ of $G$ with $|S_{i}|=s_{i}$ for each $i\in\{1,2,\ldots,k\}$, $G$ is $\{S_{1},S_{2},\ldots,S_{k}\}$-linked. Note that a graph $G$ with at least $2k$ vertices is $(2,2,\dots,2)$-linked, i.e., $s_{i}$ = $2$ for all $1\leq i\leq k$, if and only if $G$ is $k$-linked. This notion was introduced by Chen et al. [2] and derived from the “Graph Minor argument” related to a graph linkage problem. There are several results relating to linkages, minors, and subdivisions (see for example [1, 10]).

A graph $G$ is planar if $G$ can be drawn on the sphere $S^{2}$ (or the plane) without edge crossings. Graphs already drawn on $S^{2}$ are plane graphs. Let $G$ be a plane graph. Then a connected component of $S^{2}-G$, regarded as a topological space, is called a face of $G$. That is, “a face” in this paper is not necessarily homeomorphic to an (open) $2$-cell. In general, each boundary component of a face $f$ forms a closed walk of $G$. That is, the boundary of $f$ is the union of closed walks of $G$. In particular, if $f$ has the unique boundary component, then it is the boundary closed walk of $f$. A planar graph $G$ is $maximal$ if for any two non-adjacent vertices $x$ and $y$ of $G$, the graph obtained from $G$ by joining $x$ and $y$ by an edge is not planar. Every maximal planar graph with at least three vertices can be embedded on $S^{2}$ as a triangulation, that is, with each face bounded by a $3$-cycle. Mori [11] characterized $(3,3)$-linked planar graphs. Furthermore, as an extension of this result, Enami and Maezawa [3] give a complete characterization of $(s_{1},s_{2},\ldots,s_{k})$-linked planar graphs for any $k$-tuple of positive integers.

THEOREM 1 (Enami and Maezawa [3])

Let $G$ be a planar graph, and let $s_{1}$ and $s_{2}$ be two integers with $2\leq s_{1}\leq s_{2}\leq 4$. Then $G$ is $(s_{1},s_{2})$-linked if and only if $G$ is maximal and $(s_{2}+1)$-connected.

The result above also implies that if $k\geq 3$ and $s_{i},s_{j}\geq 2$ for two distinct indices $i,j\in\{1,2,3,\ldots,k\}$, then there is no $(s_{1},s_{2},s_{3},\ldots,s_{k})$-linked planar graph (for further details, see [3]).

A $1$-plane graph is a graph drawn on $S^{2}$ so that each edge crosses at most one other edge. An edge in a $1$-plane graph is crossing if it crosses another edge, and non-crossing otherwise. A $1$-planar graph is a graph that can be drawn on $S^{2}$ as a $1$-plane graph. The notion of $1$-planar graphs was first introduced by Ringel [15]. It is known that every $1$-planar graph $G$ with at least three vertices satisfies $|E(G)|\leq 4|V(G)|-8$ (see e.g., [4]). A $1$-planar or $1$-plane graph $G$ is optimal if it satisfies $|E(G)|=4|V(G)|-8$. Briefly, an optimal $1$-plane graph will be abbreviated as an O1PG in this paper. (In fact, there is no need to distinguish between “optimal $1$-planar” and “optimal $1$-plane”, since it was shown in [18] that every optimal $1$-planar graph admits a unique $1$-planar drawing in the unlabeled sense.) It was shown in [14] that every O1PG contains a $4$-connected triangulation as a spanning subgraph. The following proposition can be obtained from this result and Theorem 1.

PROPOSITION 2

Every O1PG is $(3,3)$-linked.

The aim of this paper is to characterize $(s_{1},s_{2},\ldots,s_{k})$-linked O1PGs for certain $k$-tuples of positive integers. In [5], Fujisawa et al. discussed connectivity of O1PGs, and showed that every O1PG has connectivity either $4$ or $6$. Observe that every O1PG with connectivity $4$ (resp. $6$) is not $(4,n)$-linked (resp. $(6,n)$-linked) for any integer $n\geq 2$.

The following is our first main result in the paper.

THEOREM 3

Every O1PG with connectivity $6$ is $(5,5)$-linked.

In [13], it was shown that every O1PG is obtained from a $3$-connected quadrangulation $H$ by adding a pair of crossing edges in each face of $H$. In other words, the spanning subgraph of an O1PG $G$, which consists of all non-crossing edges of $G$ is a $3$-connected quadrangulation. We denote such the quadrangulation $H$ in $G$ by $Q(G)(=H)$.

Let $G$ be a $1$-plane graph. Then $G$ has a graph $H$ as a subdrawing if $H$ is a subgraph of $G$, and $H$ can be obtained from $G$ on $S^{2}$ by removing all the vertices and edges that are not in $H$. The following is our second main result in the paper.

THEOREM 4

Let $G$ be an O1PG, and let $S_{1}$, $S_{2}$, and $S_{3}$ be disjoint vertex subsets of $G$ with $|S_{1}|=|S_{2}|=2$ and $|S_{3}|=1$. Then, $G$ is $\{S_{1},S_{2},S_{3}\}$-linked if and only if $Q(G)$ does not have a subdrawing $K$ such that $K$ is isomorphic to $K_{2,4}$, and $S_{1},S_{2}$, and $S_{3}$ are arranged on $K$ as shown in Fig.1.

Figure 1: A subdrawing of $Q(G)$ isomorphic to $K_{2,4}$ with specified vertices

This paper is organized as follows. In Section 2, we investigate the $(5,5)$-linkedness of O1PGs. We first establish some preliminary facts, including a general result on subtrees containing a specified set of vertices. We then prove the first main result of this paper. In Section 3, we consider the $(2,2,1)$-linkedness of O1PGs and characterize the $(2,2,1)$-linked O1PGs by determining the configurations of specified vertices that cannot be covered by three disjoint connected subgraphs. Finally, in Section 4, we discuss several related topics concerning linkages and present some open problems.

2 $(5,5)$-linkedness of O1PGs with connectivity 6

In the following discussion, we often consider the induced subgraph of $Q(G)$ by a vertex subset $S$ of an O1PG $G$, which is $Q(G)[S]$ under our definition. However, when the underlying graph $G$ is clear, we use $Q[S]$ in place of $Q(G)[S]$, to simplify the notation. The following lemma is proved in [9].

LEMMA 5 (Koizumi and Suzuki [9])

Let $G$ be an O1PG and let $S$ be a vertex subset of $G$. Then every face of $Q[S]$ contains at most one connected component of $G-S$.

Let $G$ be a connected graph. We denote the vertex subset of $G$ consisting of all vertices of degree $k$ by $V_{k}(G)$. For $S\subset V(G)$, a tree $T$ contained in $G$ as a subgraph is an $S$-subtree if $S\subset V(T)$ and all leaves of $T$ belongs to $S$. Note that $G$ contains at least one $S$-subtree for any $S\subset V(G)$; consider a spanning tree and remove vertices of degree $1$ that is not in $S$ recursively. To prove the first main theorem, we will establish the following more general statement, which may admit other applications.

PROPOSITION 6

Let $G$ be a connected graph with $|E(G)|=|V(G)|+1$, and let $S$ be a subset of $V(G)$ with $|S|\geq 2$ such that every vertex $v$ of degree $1$ belongs to $S$. If every cycle in $G$ has length at least $\max\{|S|-1,4\}$, and if for any two cycles $C_{1}$ and $C_{2}$, $|V(C_{1})\cap V(C_{2})|\leq 2$ holds, then $G$ contains an $S$-subtree $T$ with $|V(T)|<|V(G)|$.

Proof. We use induction on $|V(G)|$. Let $T$ be a spanning tree of $G$, and denote two edges of $E(G)\setminus E(T)$ by $e_{1}$ and $e_{2}$. Furthermore, let $C_{1}$ (resp. $C_{2}$) denote the unique cycle in $T+e_{1}$ (resp. $T+e_{2}$). We first consider the case when $\delta(G)\geq 2$, which is actually the base case of the induction. Let $D$ be the vertex set of $G$ consisting of all vertices of degree at least $3$. Since $G$ has exactly $|V(G)|+1$ edges and has no vertices of degree $1$, we have $2|E(G)|=2(|V_{2}(G)|+|D|+1)\geq 2|V_{2}(G)|+3|D|$, and hence $|D|\leq 2$ holds. Therefore, we have $|S|+|D|\leq|S|+2$.

If $|V(C_{1})\cup V(C_{2})|>|S|+2$, then there is a vertex $v\in(V(C_{1})\cup V(C_{2}))\setminus S$ of degree $2$. Thus, $G-v$ is connected, and hence $G-v$ contains a desired smaller tree. Thus, we assume that $|V(C_{1})\cup V(C_{2})|\leq|S|+2$. By the assumption $|C_{1}|,|C_{2}|\geq|S|-1$ and $|V(C_{1})\cap V(C_{2})|\leq 2$, we have $2|S|-4\leq|V(C_{1})\cup V(C_{2})|$, and consequently $|S|\leq 6$ holds. If $|S|\geq 5$, then $|V(C_{1})\cup V(C_{2})|\leq|S|+2<2|S|-2$ holds. On the other hand, if $|S|\leq 4$, then $|V(C_{1})\cup V(C_{2})|\leq 6$ holds by the argument above; note that $|C_{1}|,|C_{2}|\geq 4$ in this case by our assumption. That is, not depending on $|S|$, we may assume that $|V(C_{1})\cap V(C_{2})|\geq 1$. Under the condition, we have $|V(C_{1})\cup V(C_{2})|+1\leq|E(C_{1})\cup E(C_{2})|$. This implies that every component $H$ of $G-(V(C_{1})\cup V(C_{2}))$ must be a tree such that $H$ is joined by exactly one edge to $C_{1}\cup C_{2}$ by $|E(G)|=|V(G)|+1$. However, there is no such component since $\delta(G)\geq 2$. Thus, we now conclude that $G=C_{1}\cup C_{2}$.

First, we assume that $|V(C_{1})\cap V(C_{2})|=2$. Since $G$ is a two points union of two cycles, $G$ is $2$-connected . In addition, since $|V(G)|\geq\max\{6,2|S|-4\}$, we have $|V(G)|\geq|S|+1$; note that if $|S|\leq 5$, then $|V(G)|\geq 6$, and $|V(G)|\geq 2|S|-4\geq|S|+1$ otherwise. Thus, there is a vertex $v\in V(G)\setminus S$ such that $G-v$ is connected. Then, $G$ contains our desired $S$-subtree. Next, assume that $|V(C_{1})\cap V(C_{2})|=1$, that is $G$ is a one point union of $C_{1}$ and $C_{2}$. In this case, $|V(G)|\geq\max\{7,2|S|-3\}$ holds, and we similarly have $|V(G)|\geq|S|+2$. This means that $G$ has a vertex $v$ of degree $2$ that does not belong to $S$. Thus, $G-v$ contains our desired $S$-subtree.

Then, we assume that $\delta(G)=1$ below. Let $v\in V(G)$ be a vertex of degree $1$; note that $v\in S$. Let $P=v_{0}\cdots v_{k}$ $(k\geq 1)$ denote a path with $v=v_{0}$ such that (1) $v_{k}$ satisfies either $v_{k}\in S$ or $\deg_{G}(v_{k})\geq 3$, and (2) $v_{i}\notin S$ for each $\{1,\ldots,k-1\}$ (if $k\geq 2$). Then, put $P^{\prime}=P-v_{k}$, and $\tilde{G}=G-P^{\prime}$.

Now, we further put $\tilde{S}=(S\setminus\{v\})\cup\{v_{k}\}$. Then, $\tilde{G}$ and $\tilde{S}$ satisfy the conditions in the proposition. Therefore, $\tilde{G}$ contains a $\tilde{S}$-subtree $\tilde{T}$ with $|V(\tilde{T})|<|V(\tilde{G})|$ by the induction hypothesis. Then, $T=\tilde{T}\cup P$ is our desired $S$-subtree with $|V(T)|<|V(G)|$.  

Now, we prove the first main result in this paper.

Proof of Theorem 3. Let $G$ be an O1PG with connectivity $6$, and let $S_{1}$, $S_{2}$ be disjoint subsets of $V(G)$ with $|S_{1}|=|S_{2}|=5$. Let $G^{\prime}$ be the graph obtained from $G$ by removing $S_{1}$. Since $\kappa(G)=6$, $G^{\prime}$ is connected. Thus, $G^{\prime}$ contains a spanning tree. We choose a subtree $T$ of $G^{\prime}$, which is a subdrawing of $G^{\prime}$, so that it satisfies the following conditions $(i)$, $(ii)$, and $(iii)$.

• $T$ contains all vertices of $S_{2}$,

• Subject to (i), the number of crossing edges of $G$ in $T$ is minimum, and

• Subject to (i) and (ii), $|V(T)|$ is minimum.

CLAIM 1

All leaves of $T$ belong to $S_{2}$.

Proof. Suppose that there is a leaf $v$ of $T$ which does not belong to $S_{2}$. Then, $T-v$ is a tree satisfying the condition $(i)$. Let $e$ be the unique edge of $T$ that is incident to $v$. If $e$ is a crossing edge of $G$, then the tree $T-v$ has fewer crossing edges than $T$, contradicting the condition $(ii)$. If $e$ is a non-crossing edge of $G$, then this contradicts the condition $(iii)$.  

CLAIM 2

The tree $T$ is a plane graph.

Proof. Suppose that $T$ has two edges $v_{0}v_{2}$ and $v_{1}v_{3}$ that are crossing each other. Note that since $G$ is optimal, there are four non-crossing edges $v_{0}v_{1},v_{1}v_{2},v_{2}v_{3}$, and $v_{3}v_{0}$ in $G$. Since $T$ is a tree, we may assume that there exists the path joining $v_{0}$ and $v_{1}$ in $T$, up to symmetry. Then, we can obtain a new tree $T^{\prime}$ from $T$ by removing the edge $v_{1}v_{3}$ and adding the edge $v_{3}v_{0}$. The tree $T^{\prime}$ has fewer crossing edges than $T$ and satisfies the condition $(i)$. This contradicts the condition $(ii)$.  

CLAIM 3

Assume that there is an edge $e\in E(Q[V(T)])\setminus E(T)$, and let $C$ be the unique cycle contained in $T+e$. Then, every edge on $C$ is non-crossing in $G$.

Proof. Suppose that $C$ contains a crossing edge $uv$. Then, $T-uv+e$ is also a tree that satisfies the condition $(i)$ (see Fig.2). This contradicts the condition $(ii)$.  

Figure 2: $T$ and $T-uv+e$ in Claim $3$

CLAIM 4

Assume that there is an edge $e\in E(Q[V(T)])\setminus E(T)$, and let $C$ be the unique cycle contained in $T+e$. Then, $C$ has length $4$. Moreover, $|E(Q[V(T)])\setminus E(T)|\leq 1$, that is, the subgraph $Q[V(T)]$ contains at most one cycle.

Proof. Suppose that $C$ has length at least $6$. Note that since $Q(G)$ is bipartite, the length of $C$ is even. Then,

$$|V(C)\cap S_{2}|+|\{\,v\in V(C):\deg_{(T+e)}(v)\geq 3\,\}|\leq 5$$

holds by Claim $1$. Therefore, there exists a vertex $w\in V(C)\setminus S_{2}$ with $\deg_{(T+e)}(w)=2$. Then, $T+e-w$ satisfies the conditions $(i)$ and $(ii)$. This contradicts the condition $(iii)$. Thus, $C$ has length $4$.

Suppose that $|E(Q[V(T)])\setminus E(T)|\geq 2$, and let $e_{1},e_{2}\in E(Q[V(T)])\setminus E(T)$. Let $C_{1}$ (resp. $C_{2}$) be the unique $4$-cycle in $T+e_{1}$ (resp. $T+e_{2}$). Then, $T\cup\{e_{1},e_{2}\}$ has exactly $|V(T\cup\{e_{1},e_{2}\})|+1$ edges. Suppose that $|V(C_{1})\cap V(C_{2})|\geq 3$. Since $G$ is $6$-connected and $C_{1}$ and $C_{2}$ consist only of non-crossing edges of $G$, each of $C_{1}$ and $C_{2}$ bounds a face of $Q(G)$. Thus, each of $C_{1}$ and $C_{2}$ has exactly two chords corresponding to crossing edges of $G$, contradicting the simplicity of $G$. Hence $|V(C_{1})\cap V(C_{2})|\leq 2$. By Proposition 6, $T\cup\{e_{1},e_{2}\}$ contains a subtree $T^{\prime}$ such that $S_{2}\subset V(T^{\prime})$, all leaves belong to $S_{2}$, and $|V(T^{\prime})|<|V(T)|$. This contradicts the condition $(iii)$, and hence, $|E(Q[V(T)])\setminus E(T)|\leq 1$.  

Figure 3: Tree $T$ and $Q[V(T)]$

Now we consider an induced subgraph $Q[V(T)]$ of $Q(G)$. Observe that each connected component of $Q[V(T)]$ is either acyclic or, if it contains exactly one cycle, then such a cycle has length exactly $4$ by claims 3 and 4. If every connected component of $Q[V(T)]$ is acyclic, then $Q[V(T)]$ has a unique face. By Lemma 5, $G-T$ is connected, and hence we can obtain a connected subgraph in $G-T$ containing all vertices of $S_{1}$.

Therefore, we assume that there is a connected component of $Q[V(T)]$ that is not acyclic (see the left-hand side and the right-hand side of Fig.3). Then, by Claim 4, $Q[V(T)]$ has exactly two faces $F_{1}$ and $F_{2}$, one of which, say $F_{1}$, is bounded by a $4$-cycle. Since $\kappa(G)=6$, the interior of $F_{1}$ contains no vertices of $G$. Then, the interior of $F_{2}$ contains all vertices of $V(G)\setminus V(T)$. By Lemma 5, $G-T$ is connected and hence we can obtain a connected subgraph in $G-T$ containing all vertices of $S_{1}$.  

3 Characterization of $(2,2,1)$-linked O1PGs

Seymour [16], Shiloach [17], and Thomassen [20] independently characterized $(2,2)$-linked graphs. The following proposition can be obtained from the result above.

PROPOSITION 7 (Seymour [16], Shiloach [17], and Thomassen [20])

Let $G$ be a planar graph, and let $S_{1}=\{x_{1},x_{2}\}$ and $S_{2}=\{y_{1},y_{2}\}$ be disjoint vertex subsets of $G$. Then $G$ is not $\{S_{1},S_{2}\}$-linked if and only if $G$ has an embedding on $S^{2}$ that satisfies the followings:

• There is a face $f$ whose boundary closed walk $W$ has length at least $4$, and

• The boundary walk $W$ contains $x_{1},y_{1},x_{2},y_{2}$ in this order.

Let $G$ be a plane graph. Then, $G$ is a near-triangulation if it is $2$-connected and all faces, except at most one face, are triangles. A simple closed curve $\gamma$ on $S^{2}$ is a separating $k$-curve if it passes only through $k$ vertices in a plane graph $G$ and each of two regions separated by $\gamma$ contains at least one vertex of $G$.

Proof of Theorem 4. Let $G$ be an O1PG, and let $S_{1}=\{r_{1},r_{2}\}$, $S_{2}=\{b_{1},b_{2}\}$, $S_{3}=\{y\}$ be disjoint subsets of $V(G)$. The sufficiency is clear, and hence we shall prove the necessity. Assume that $G$ is not $\{S_{1},S_{2},S_{3}\}$-linked. Let $B$ and $W$ be the partite sets of $Q(G)$. We may assume that $y\in W$.

Let $N_{G}(y)=\{u_{1},u_{2},\ldots,u_{2k}\}$ with $k\geq 3$, and assume that the edges $yu_{1},yu_{2},\ldots,yu_{2k}$ appear in the clockwise order around $y$. Then, we may assume that $u_{i}\in B$ when $i$ is even, and $u_{i}\in W$ otherwise $(i\in\{1,2,\ldots,{2k}\})$. Let $G^{\prime}$ be the graph obtained from $G$ by removing $y$ (see the left-hand side of Fig. 4, where vertices in $B$ (resp. $W$) are shown in black (resp. white)). Then $G^{\prime}$ contains a spanning subgraph that is a near-triangulation whose unique non-triangular face is bounded by $C^{\prime}=u_{2}u_{4}\ldots u_{2k}$. Since $C^{\prime}$ consists only of black vertices, at most one edge in each pair of crossing edges can be a chord of $C^{\prime}$. Therefore, we can take such a near-triangulation $T$ so that $C^{\prime}$ has no chords (see the center of Fig.4). Observe that $T$ is $3$-connected. We denote by $F$ the unique non-triangular face of $T$.

Figure 4: $G^{\prime}$, $T$, and $H$

Since $G$ is not $\{S_{1},S_{2},S_{3}\}$-linked, there are no two disjoint paths joining $r_{1}$ to $r_{2}$ and $b_{1}$ to $b_{2}$ in $T$. Hence, by Proposition 7, there exists an embedding of $T$ on $S^{2}$ such that there is a face whose boundary cycle containing $r_{1},b_{1},r_{2}$, and $b_{2}$ in this order. Since $T$ is $3$-connected, such an embedding is unique. Therefore, we may assume that $r_{1},b_{1},r_{2},$ and $b_{2}$ are contained in $C^{\prime}$ in this order.

Let $H$ be the subgraph of $G$ induced by $B$ (see the right-hand side of Fig.4). Observe that $H$ is a plane graph and the face $F$ of $T$ is also a face of $H$. Since $S_{1},S_{2}\subset V(C^{\prime})$, we have $S_{1},S_{2}\subset V(H)$. Furthermore, the boundary of each face of $H$ is a cycle, and hence $H$ is $2$-connected. Let $H_{1}$ (resp. $H_{2}$) be the graph obtained from $H$ by removing the vertices $r_{1}$ and $r_{2}$ (resp. $b_{1}$ and $b_{2}$). Suppose that $H_{1}$ or $H_{2}$, say $H_{1}$ here, is connected. Then, there exists a path $P_{1}$ joining $b_{1}$ and $b_{2}$ in $H_{1}$ such that $P_{1}$ only passes through the vertices of $B-\{r_{1},r_{2}\}$. Next, let $s$ (resp. $t$) be a vertex in $W\cap N_{G^{\prime}}(r_{1})$ (resp. $W\cap N_{G^{\prime}}(r_{2})$). Note that $s,t\notin\{b_{1},b_{2}\}$, since $b_{1},b_{2}\in B$. Since the subgraph $G[W]$ of $G$ induced by $W$ is also $2$-connected, the subgraph $G[W]-y$ is connected. Then, there exists a path $P_{2}$ joining $s$ and $t$ such that $P_{2}$ only passes through the vertices of $W\setminus\{y\}$. Then, the path $P_{2}\cup\{r_{1},r_{2}\}\cup\{r_{1}s,r_{2}t\}$ and $P_{1}$ are disjoint. This contradicts the assumption. The same argument applies when $H_{2}$ is connected.

Therefore, we assume that both $H_{1}$ and $H_{2}$ are disconnected. Since $H_{1}$ is disconnected, {$r_{1},r_{2}$} is a $2$-cut of $H$. Then, there exists a separating $2$-curve $\gamma_{1}$ passing through only $r_{1}$ and $r_{2}$. Then $\gamma_{1}$ passes through the interior of a face $F_{1}$ of $H$ other than $F$ whose boundary contains $r_{1}$ and $r_{2}$. Since $H$ is the subgraph of $G$ induced by $B$, there is exactly one vertex $w\in W$ inside the face $F_{1}$. Similarly, there is a face $F_{2}$ of $H$ whose boundary contains $b_{1}$ and $b_{2}$ and whose interior contains exactly one vertex $u\in W$. Under the situation, this implies that $F_{1}=F_{2}$ whose boundary contains $r_{1},b_{1},r_{2},b_{2}$ in this order, and that $w=u$. Therefore, $\{r_{1},r_{2},b_{1},b_{2},y\}$ have the arrangement in $G$ as stated in the Theorem 4.  

Now, we can obtain the following corollary from Theorem 4.

COROLLARY 8

Every O1PG with connectivity $6$ is $(2,2,1)$-linked.

4 Concluding remarks and related topics

In the previous sections, we established the $(5,5)$-linkedness and the $(2,2,1)$-linkedness of O1PGs with connectivity $6$. A natural question is whether similar results hold for other tuples of integers. In fact, there exist infinitely many O1PGs with connectivity $6$ that are not $(2,2,2)$-linked. The following O1PG with eight vertices, shown in Fig.5, called $X\!W_{6}$, is one such example; there are no three vertex-disjoint connected subgraphs, each containing $S_{i}$ in the figure. As mentioned above, an $XW_{6}$ is a graph in an infinite series of graphs denoted by $X\!W_{2k}$ with $k\geq 3$ (see, e.g., [19] for a definition). In fact, we have already observed that none of them is $(2,2,2)$-linked; since the required case analysis is extensive, a detailed discussion will be given in a subsequent paper.

Figure 5: $X\!W_{6}$ that is not $(2,2,2)$-linked

We briefly discuss several topics related to linkages. Let $G$ be a graph and let $S$ be a vertex subset of $G$. The pair $(G,S)$ is knitted if for every partition of $S$ into non-empty subsets $S_{1},S_{2},\ldots,S_{t}$, there are disjoint connected subgraphs $G_{1},G_{2},\ldots,G_{t}$ in $G$ such that $S_{i}\subseteq V(G_{i})$ for each $i\in\{1,\ldots,t\}$. A graph $G$ is $l$-knitted if $(G,S)$ is knitted for all $S\subseteq V(G)$ with $|S|=l$. The notion of a “knitted graph” was introduced by Bollobás and Thomason [1], and was later further generalized by Kawarabayashi and Yu [8]. Observe that a graph $G$ is $l$-knitted if and only if $G$ is $(s_{1},s_{2},\ldots,s_{k})$-linked for any list $(s_{1},s_{2},\ldots,s_{k})$ with $\sum_{i=1}^{k}s_{i}=l$. In [8], the notion of a knitted graph was applied to study the connectivity of minimum counterexamples to Hadwiger’s conjecture.

By Corollary 8 and brief arguments, we can obtain the following proposition.

PROPOSITION 9

Every O1PG with connectivity $6$ is $5$-knitted.

However, there are O1PGs with connectivity $6$ that are not $6$-knitted, since there are infinitely many O1PGs with connectivity $6$ that are not $(2,2,2)$-linked as mentioned above; on the other hand, recall that every O1PG is $(3,3)$-linked.

We introduce one more related topic. A graph $G$ is $k$-ordered if for every $k$ vertices of a given order, there is a cycle containing the $k$ vertices of the given order. Note that if a graph $G$ is $k$-ordered, then $G$ is $k$-knitted. Goddard [6] showed the following theorem.

THEOREM 10 (Goddard [6])

Every $4$-connected triangulation on the sphere is $4$-ordered.

In fact, the result above has been extended to general closed surfaces by Mukae and Ozeki [12]. By Theorem 10 and the fact that every O1PG contains a $4$-connected triangulation as a spanning subgraph, we obtain the following proposition.

PROPOSITION 11

Every O1PG is $4$-ordered.

However, there exist O1PGs with connectivity $6$ that are not $5$-ordered. The following O1PG called $X\!W_{8}$ is one such example (see Fig.6). We can see that there are no cycles containing $v_{1},v_{2},v_{3},v_{4},$ and $v_{5}$ in this order.

Figure 6: $X\!W_{8}$ that is not $5$-ordered

From the discussion so far, we can see that there is a clear gap among linkage, knittedness, and orderedness. Finally, we propose several open problems.

PROBLEM 12

For a fixed integer $k$ and for any list $(s_{1},s_{2},\ldots,s_{k})$ of positive integers, characterize $(s_{1},s_{2},\ldots,s_{k})$-linked O1PGs.

PROBLEM 13

Characterize $6$-knitted O1PGs with connectivity $6$.

PROBLEM 14

Characterize $5$-ordered O1PGs with connectivity $6$.