A graph G with at least 2k vertices is called k-subconnected if, for any 2k vertices x1,x2,⋯,x2k in G, there are k independent paths joining the 2k vertices in pairs in G. In this paper, we prove that a k-connected planar graph with at least 2k vertices is k-subconnected for k=1,2; a 4-connected planar graph is k-subconnected for each k such that 1≤k≤ν/2, where v is the number of vertices of G; and a 3-connected planar graph G with at least 2k vertices is k-subconnected for k=4,5,6. The bounds of k-subconnectedness are sharp.
Citation: Zongrong Qin, Dingjun Lou. The k-subconnectedness of planar graphs[J]. AIMS Mathematics, 2021, 6(6): 5762-5771. doi: 10.3934/math.2021340
[1] | Dingjun Lou, Zongrong Qin . The structure of minimally 2-subconnected graphs. AIMS Mathematics, 2022, 7(6): 9871-9883. doi: 10.3934/math.2022550 |
[2] | Xia Hong, Wei Feng . Completely independent spanning trees in some Cartesian product graphs. AIMS Mathematics, 2023, 8(7): 16127-16136. doi: 10.3934/math.2023823 |
[3] | Xiaoxue Hu, Jiangxu Kong . An improved upper bound for the dynamic list coloring of 1-planar graphs. AIMS Mathematics, 2022, 7(5): 7337-7348. doi: 10.3934/math.2022409 |
[4] | Hongyu Chen, Li Zhang . A smaller upper bound for the list injective chromatic number of planar graphs. AIMS Mathematics, 2025, 10(1): 289-310. doi: 10.3934/math.2025014 |
[5] | Yunfeng Tang, Huixin Yin, Miaomiao Han . Star edge coloring of K2,t-free planar graphs. AIMS Mathematics, 2023, 8(6): 13154-13161. doi: 10.3934/math.2023664 |
[6] | Yuehua Bu, Qi Jia, Hongguo Zhu, Junlei Zhu . Acyclic edge coloring of planar graphs. AIMS Mathematics, 2022, 7(6): 10828-10841. doi: 10.3934/math.2022605 |
[7] | Saba Al-Kaseasbeh, Ahmad Erfanian . A bipartite graph associated to elements and cosets of subgroups of a finite group. AIMS Mathematics, 2021, 6(10): 10395-10404. doi: 10.3934/math.2021603 |
[8] | Dijian Wang, Dongdong Gao . Laplacian integral signed graphs with few cycles. AIMS Mathematics, 2023, 8(3): 7021-7031. doi: 10.3934/math.2023354 |
[9] | Yuehua Bu, Qiang Yang, Junlei Zhu, Hongguo Zhu . Injective coloring of planar graphs with girth 5. AIMS Mathematics, 2023, 8(7): 17081-17090. doi: 10.3934/math.2023872 |
[10] | Sizhong Zhou, Jiang Xu, Lan Xu . Component factors and binding number conditions in graphs. AIMS Mathematics, 2021, 6(11): 12460-12470. doi: 10.3934/math.2021719 |
A graph G with at least 2k vertices is called k-subconnected if, for any 2k vertices x1,x2,⋯,x2k in G, there are k independent paths joining the 2k vertices in pairs in G. In this paper, we prove that a k-connected planar graph with at least 2k vertices is k-subconnected for k=1,2; a 4-connected planar graph is k-subconnected for each k such that 1≤k≤ν/2, where v is the number of vertices of G; and a 3-connected planar graph G with at least 2k vertices is k-subconnected for k=4,5,6. The bounds of k-subconnectedness are sharp.
Connectivity is an important property of graphs. It has been extensively studied (see [1]). A graph G=(V,E) is called k-connected (k≥1) (k-edge-connected) if, for any subset S⊆V(G) (S⊆E(G)) with |S|<k, G−S is connected. The connectivity κ(G) (edge connectivity λ(G)) is the order (size) of minimum cutset (edge cutset) S⊆V(G) (S⊆E(G)). When G is a complete graph Kn, we define that κ(G)=n−1.
In recent years, conditional connectivities attract researchers' attention. For example, Peroche [2] studied several sorts of connectivities, including cyclic edge (vertex) connectivity, and their relations. A cyclic edge (vertex) cutset S of G is an edge (vertex) cutset whose deletion disconnects G such that at least two of the components of G−S contain a cycle respectively. The cyclic edge (vertex) connectivity, denoted by cλ(G) (cκ(G)), is the cardinality of a minimum cyclic edge (vertex) cutset of G. Dvoŕǎk, Kára, Král and Pangrác [3] obtained the first efficient algorithm to determine the cyclic edge connectivity of cubic graphs. Lou and Wang [4] obtained the first efficient algorithm to determine the cyclic edge connectivity for k-regular graphs. Then Lou and Liang [5] improved the algorithm to have time complexity O(k9V6). Lou [6] also obtained a square time algorithm to determine the cyclic edge connectivity of planar graphs. In [7], Liang, Lou and Zhang obtained the first efficient algorithm to determine the cyclic vertex connectivity of cubic graphs. Liang and Lou [8] also showed that there is an efficient algorithm to determine the cyclic vertex connectivity for k-regular graphs with any fixed k.
Another related concept is linkage. Let G be a graph with at least 2k vertices. If, for any 2k vertices u1,u2,⋯,uk,v1,v2,⋯,vk, there are k disjoint paths Pi from ui to vi(i=1,2,⋯,k) in G, then G is called k-linked. Thomassen [9] mentioned that a necessary condition for G to be k-linked is that G is (2k−1)-connected. But this condition is not sufficient unless k=1. He also gave a complete characterization of 2-linked graphs. Bollobás and Thomason [10] proved that if κ(G)≥22k, then G is k-linked. Kawarabayashi, Kostochka and Yu [11] proved that every 2k-connected graph with average degree at least 12k is k-linked.
In [12], Qin, Lou, Zhu and Liang introduced the new concept of k-subconnected graphs. Let G be a graph with at least 2k vertices. If, for any 2k vertices v1,v2,⋯,v2k in G, there are k vertex-disjoint paths joining v1,v2,⋯,v2k in pairs, then G is called k-subconnected. If G is k-subconnected and ν(G)≥3k−1, then G is called a properly k-subconnected graph. In [12], Qin et al. showed that a properly k-subconnected graph is also a properly (k−1)-subconnected graph. But only when ν(G)≥3k−1, that G is k-subconnected implies that G is (k−1)-subconnected. Qin et al. [12] also gave a sufficient condition for a graph to be k-subconnected and a necessary and sufficient condition for a graph to be a properly k-subconnected graph (see Lemmas 1 and 2 and Corollary 3 in this paper).
If G has at least 2k vertices, that G is k-linked implies that G is k-connected, while that G is k-connected implies that G is k-subconnected (see Lemma 6 in this paper). Also in a k-connected graph G, deleting arbitrarily some edges from G, the resulting graph H is still k-subconnected. So a graph H to be k-subconnected is a spanning substructure of a k-connected graph G. To study k-subconnected graphs may help to know more properties in the structure of k-connected graphs. Notice that a k-connected graph may have a spanning substructure to be m-subconnected for m>k.
K-subconnected graphs have some background in matching theory. The proof of the necessary and sufficient condition [12] for properly k-subconnected graphs uses similar technique to matching theory.
Let S be a subset of V(G) of a graph G. We denote by G[S] the induced subetaaph of G on S. We also denote by ω(G) the number of components of G. We also use ν(G) and ε(G) to denote |V(G)| and |E(G)|. If G is a planar graph, we denote by ϕ(G) the number of faces in the planar embedding of G. Let H be a graph. A subdivision of H is a graph H′ obtained by replacing some edges by paths respectively in H. For other terminology and notation not defined in this paper, the reader is referred to [13].
In this section, we shall present some known results and some straightforward corollaries of the known results which will be used in the proof of our main theorems.
Lemma 1 (Theorem 1 of [12]). Let G be a connected graph with at least 2k vertices. Then G is k-subconnected if, for any cutset S⊆V(G) with |S|≤k−1, ω(G−S)≤|S|+1.
Lemma 2 (Theorem 2 of [12]). Let G be a connected graph with at least 3k−1 vertices. If G is a properly k-subconnected graph, then, for any cutset S⊆V(G) with |S|≤k−1, ω(G−S)≤|S|+1.
Only when v≥3k−1, that G is k-subconnected implies that G is (k-1)-subconnected. Here is an counterexample. Let S=Kk−2 be a complete graph of k−2 vertices, let H be k copies of K2, and let G be a graph with V(G)=V(S)∪V(H) and E(G)=E(S)∪E(H)∪{uv|u∈V(S),v∈V(H)}. Then v(G)=3k−2, and G is not (k-1)-subconnected since we can choose 2(k-1) vertices by taking one vertex from each copy of K2 in H and taking all vertices of S, then these 2(k-1) vertices cannot be joined by k-1 independent paths in pairs. But G is k-subconnected since when we take any 2k vertices from G, some pairs of vertices will be taken from several same K2 's in H, and then the 2k vertices can be joined by k independent paths in pairs.
Corollary 3 (Theorem 3 of [12]). Let G be a connected graph with at least 3k−1 vertices. Then G is a properly k-subconnected graph if and only if, for any cutset S⊆V(G) with |S|≤k−1, ω(G−S)≤|S|+1.
Lemma 4 ([14]). Every 4-connected planar graph is Hamiltonian.
Lemma 5. If a graph G has a Hamilton path, then G is k-subconnected for each k such that 1≤k≤ν(G)/2.
Proof. Let P be a Hamilton path in G. Let vi, i=1,2,⋯,2k, be any 2k vertices in V(G). Without loss of generality, assume that v1,v2,⋯,v2k appear on P in turn. Then there are k paths Pi on P from v2i−1 to v2i, i=1,2,⋯,k, respectively. So G is k-subconnected.
Lemma 6. A k-connected graph G with at least 2k vertices is k-subconnected.
Proof. Let G be a k-connected graph with at least 2k vertices. Then G does not have a cutset S⊆V(G) with |S|≤k−1, so the statement that, for any cutset S⊆V(G) with |S|≤k−1, ω(G−S)≤|S|+1 is true. By Lemma 1, G is k-subconnected.
In this section, we shall show the k-subconnectedness of planar graphs with different connectivities, and show the bounds of k-subconnectedness are sharp.
Corollary 7. A 1-connected planar graph G with at least 2 vertices is 1-subconnected.
Proof. By Lemma 6, the result follows.
Corollary 8. A 2-connected planar graph G with at least 4 vertices is 2-subconnected.
Proof. By Lemma 6, the result follows.
Theorem 9. A 4-connected planar graph G is k-subconnected for each k such that 1≤k≤ν(G)/2.
Proof. By Lemma 4, G has a Hamilton cycle C, and then has a Hamilton path P. By Lemma 5, the result follows.
Theorem 10. A 3-connected planar graph G with at least 2k vertices is k-subconnected for k=4,5,6.
Proof. Suppose that G is a 3-connected planar graph with at least 2k vertices which is not k-subconnected. By Lemma 1, there is a cutset S⊆V(G) with |S|≤k−1≤ such that ω(G−S)≥|S|+2. Since G is 3-connected, there is no cutset with less than 3 vertices and so |S|≥3. On the other hand, k=4,5,6, so |S|≤5. Thus let us consider three cases.
In the first case, |S|=3. By our assumption, ω(G−S)≥|S|+2, let C1,C2,⋯,C5 be different components of G−S, and S={x1,x2,x3}. Since G is 3-connected, every Ci is adjacent to each xj (1≤i≤5,1≤j≤3). Contract every Ci to a vertex C′i (i=1,2,⋯,5) to obtain a planar graph G′ as G is planar. Then G′[{x1,x2,x3}∪{C′1,C′2,C′3}] contains a K3,3, which contradicts the fact that G′ is a planar graph.
In the second case, |S|=4. By our assumption, ω(G−S)≥|S|+2, let C1,C2,⋯,C6 be different components of G−S and S={x1,x2,x3,x4}. Contract every Ci to a vertex C′i (i=1,2,⋯,6) to obtain a planar graph G′ as G is planar. Since G is 3-connected, each C′i is adjacent to at least 3 vertices in S (1≤i≤6). (In the whole proof, we shall consider that C′i is adjacent to only 3 vertices in S, and we shall neglect other vertices in S which are possibly adjacent to C′i). Since the number of 3-vertex-combinations in S is C(4,3)=4, but C′1,C′2,⋯,C′6 have 6 vertices, by the Pigeonhole Principle, there are two vertices in {C′1,C′2,⋯,C′6} which are adjacent to the same three vertices in S. Without loss of generality, assume that C′1 and C′2 are both adjacent to x1,x2,x3. If there is another C′i (3≤i≤6) adjacent to x1,x2,x3, say C′3, then G′[{x1,x2,x3}∪{C′1,C′2,C′3}] contains a K3,3, which contradicts the fact that G′ is planar (which also contradicts the assumption that G is a planar graph because G has a subetaaph which can be contracted to a K3,3). So C′i cannot be adjacent to x1,x2,x3 at the same time (i=3,4,5,6).
Suppose C′3 is adjacent to x2,x3,x4. If one of C′4,C′5,C′6 is adjacent to both x1 and x4, say C′4, then C′3 is connected to x1 by path C′3x4C′4x1, so G′[{x1,x2,x3,x4}∪{C′1,C′2,C′3,C′4}] contains a subdivision of K3,3, contradicting the fact that G′ is planar. Since C′4,C′5,C′6 are all not adjacent to x1,x2,x3 at the same time, they are all adjacent to x4. But each of them cannot be adjacent to both x1 and x4. So they are all not adjacent to x1. Hence C′4,C′5,C′6 are all adjacent to x2,x3,x4 at the same time. Then G′[{x2,x3,x4}∪{C′4,C′5,C′6}] contains a K3,3, contradicting the fact that G′ is a planar graph.
The cases that C′3 is adjacent to x1,x3,x4 or x1,x2,x4 are similar.
In the third case, |S|=5. By our assumption, ω(G−S)≥|S|+2, let C1,C2,⋯,C7 be different components of G−S and S={x1,x2,⋯,x5}. Since G is planar, contracting Ci to a vertex C′i (i=1,2,⋯,7), we obtain a planar graph G′. Also since G is 3-connected, every C′i is adjacent to at least 3 vertices in S (1≤i≤7).
Case 1. There are two of C′i (i=1,2,⋯,7) adjacent to the same three vertices in S. Without loss of generality, assume that C′1 and C′2 are both adjacent to x1,x2,x3 at the same time.
If there is another vertex C′i (3≤i≤7) adjacent to x1,x2,x3 at the same time, say C′3. Then G′[{x1,x2,x3}∪{C′1,C′2,C′3}] contains a K3,3, contradicting the fact that G′ is planar. So C′3 cannot be adjacent to x1,x2,x3 at the same time. Without loss of generality, we have two subcases.
Suppose C′3 is only adjacent to two vertices in {x1,x2,x3}, say x2 and x3. Then C′3 must be adjacent to one of x4 and x5 as G is 3-connected. Without loss of generality, assume that C′3 is also adjacent to x4. If one of C′i (i=4,5,6,7) is adjacent to both x1 and x4, say C′4. Then C′3 is connected to x1 by path C′3x4C′4x1, hence G′[{x1,x2,x3,x4}∪{C′1,C′2,C′3,C′4}] contains a subdivision of K3,3, contradicting the fact that G′ is planar. So none of C′i (i=4,5,6,7) is adjacent to both x1 and x4.
Case (1.1). Suppose that C′4 is adjacent to three vertices in {x1,x2,x3,x4} .
If C′4 is adjacent to x1,x2,x3 at the same time, then the case is similar to that C′3 is adjacent to x1,x2,x3 at the same time, and we have a contradiction. So C′4 is not adjacent to x1,x2,x3 at the same time. If C′4 is adjacent to x1, since C′4 is adjacent to three vertices in {x1,x2,x3,x4} but not x1,x2,x3, so C′4 is adjacent to x1 and x4, by the argument above, we have a contradiction. Hence C′4 can be adjacent only to x2,x3,x4.
Now x1 and x4 are symmetric, while x2 and x3 are symmetric in G′[{x1,x2,x3,x4}∪{C′1,C′2,C′3,C′4}]. Then C′i(i=5,6,7) must be adjacent to x5, we have two cases as follows.
Notice that now there are not i and j, 5≤i≠j≤7, such that C′i is adjacent to x1 and C′j is adjacent to x4, otherwise C′3 is connected to x1 by path C′3x4C′jx5C′ix1, then G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′i,C′j}] contains a subdivision of K3,3, contrary to the fact that G′ is planar.
Suppose C′5 is adjacent to x3,x4,x5. If C′6 is also adjacent to x3,x4,x5, then C′7 cannot be adjacent to x3,x4,x5, otherwise G′[{x3,x4,x5}∪{C′5,C′6,C′7}] contains a K3,3, a contradiction. So suppose C′7 is adjacent to x2,x4,x5, then C′7 is connected to x3 by path C′7x2C′2x3, and then G′[{x2,x3,x4,x5}∪{C′2,C′5,C′6,C′7}] contains a subdivision of K3,3, a contradiction. So suppose C′7 is adjacent to x2,x3,x5. But C′7 is connected to x4 by path C′7x2C′3x4, then G′[{x2,x3,x4,x5}∪{C′3,C′5,C′6,C′7}] contains a subdivision of K3,3, a contradiction again. If C′6 is adjacent to x2,x3,x5, suppose C′7 is adjacent to x3,x4,x5, then this case is similar to that C′6 is adjacent to x3,x4,x5 and C′7 is adjacent to x2,x3,x5. Then suppose C′7 is adjacent to x2,x3,x5. Now C′3 is connected to x5 by path C′3x4C′5x5, so G′[{x2,x3,x4,x5}∪{C′3,C′5,C′6,C′7}] contains a subdivision of K3,3, a contradiction. Now suppose C′7 is adjacent to x2,x4,x5. Then C′6 is connected to x4 by path C′6x5C′7x4, hence G′[{x2,x3,x4,x5}∪{C′3,C′4,C′6,C′7}] contains a subdivision of K3,3, a contradiction. The remaining case is that C′6 is adjacent to x2,x4,x5. Now the cases that C′7 is adjacent to x2,x4,x5 and that C′7 is adjacent to x3,x4,x5 are symmetric, we only discuss the former. Then C′5 is connected to x2 by path C′5x3C′4x2, so G′[{x2,x3,x4,x5}∪{C′4,C′5,C′6,C′7}] contains a subdivision of K3,3, a contradiction. The remaining case is that C′7 is adjacent to x2,x3,x5. Now C′7 is connected to x4 by path C′7x5C′6x4. Hence G′[{x2,x3,x4,x5}∪{C′3,C′4,C′6,C′7}] contains a subdivision of K3,3, a contradiction.
Suppose C′5 is adjacent to x2,x3,x5. If C′6 and C′7 are both adjacent to x2,x3,x5, then G′[{x2,x3,x5}∪{C′5,C′6,C′7}] contains a K3,3, contradicting the fact that G′ is planar. So one of C′5, C′6, C′7 is adjacent to x2,x3,x5, the other two are adjacent to x3,x4,x5; or one of C′5, C′6, C′7 is adjacent to x3,x4,x5, the other two are adjacent to x2,x3,x5; or C′5 is adjacent to x2,x3,x5, C′6 is adjacent to x3,x4,x5 and C′7 is adjacent to x2,x4,x5. These three cases are symmetric to cases discussed above. (Notice that the roles of C′5, C′6 and C′7 are symmetric.)
Case (1.2). Now suppose {x2,x3,x4} - N(C′4)≠∅.
Notice that {x2,x3,x4} - N(C′i)≠∅ for 5≤i≤7, otherwise the C′i (5≤i≤7) is similar to C′4 as discussed above, and the other three in {C′4,C′5,C′6,C′7} are similar to C′5,C′6,C′7, by the same argument as above, we obtain a contradiction. Also since C′4,C′5,C′6,C′7 each cannot be adjacent to both x1 and x4, all of C′4,C′5,C′6,C′7 must be adjacent to x5. Now x1 and x4 are not symmetric but x2 and x3 are symmetric in G′[{x1,x2,x3,x4}∪{C′1,C′2,C′3}].
First, suppose C′4 is adjacent to x4 and x3 besides x5. Then suppose C′5 is adjacent to x4 and x3. If C′6 is also adjacent to x4 and x3, then G′[{x3,x4,x5}∪{C′4,C′5,C′6}] contains K3,3, a contradiction. Then suppose C′6 is adjacent to x4,x2, now C′6 is connected to x3 by path C′6x2C′2x3, and G′[{x2,x3,x4,x5}∪{C′2,C′4,C′5,C′6}] contains a subdivision of K3,3, a contradiction. Now suppose C′6 is adjacent to x4,x1, then C′6 is connected to x3 by path C′6x1C′2x3, and G′[{x1,x3,x4,x5}∪{C′2,C′4,C′5,C′6}] contains a subdivision of K3,3 a contradiction. Then suppose C′6 is adjacent to x3,x2. Now C′6 is connected to x4 by path C′6x2C′3x4, so G′[{x2,x3,x4,x5}∪{C′3,C′4,C′5,C′6}] contains a subdivision of K3,3, a contradiction. Next we suppose C′6 is adjacent to x3,x1, then C′6 is connected to x2 by path C′6x5C′4x4C′3x2, and G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′6}] contains a subdivision of K3,3, a contradiction. Then suppose C′6 is adjacent to x2,x1, now C′6 is connected to x3 by path C′6x5C′4x3, and G′[{x1,x2,x3,x5}∪{C′1,C′2,C′4,C′6}] contains a subdivision of K3,3, a contradiction. Now we suppose C′5 is adjacent to x4,x2. By the symmetry of the roles of C′4,C′5,C′6,C′7, we only consider the cases of C′6 as follows. Suppose C′6 is adjacent to x4,x2. Then C′4 is connected to x2 by path C′4x3C′3x2, and G′[{x2,x3,x4,x5}∪{C′3,C′4,C′5,C′6}] contains a subdivision of K3,3, a contradiction. Then suppose C′6 is adjacent to x4,x1. Now C′3 is connected to x1 by path C′3x4C′6x1, and G′[{x1,x2,x3,x4}∪{C′1,C′2,C′3,C′6}] contains a subdivision of K3,3, a contradiction. Now suppose C′6 is adjacent to x3,x2. Then we consider C′7. By the symmetry of the roles of C′7 and C′6, we only consider the cases that C′7 is adjacent to {x3,x2},{x3,x1},{x2,x1} respectively. If C′7 is adjacent to x3,x2, then C′5 is connected to x3 by path C′5x4C′4x3, and G′[{x2,x3,x4,x5}∪{C′4,C′5,C′6,C′7}] contains a subdivision of K3,3, a contradiction. If C′7 is adjacent to x3,x1, then C′3 is connected to x1 by path C′3x4C′5x5C′7x1, and G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′5,C′7}] contains a subdivision of K3,3, a contradiction. If C′7 is adjacent to x2,x1, then C′7 is connected to x3 by path C′7x5C′4x3, and G′[{x1,x2,x3,x5}∪{C′1,C′2,C′4,C′7}] contains a subdivision of K3,3, a contradiction. Now suppose C′6 is adjacent to x3,x1. Then C′3 is connected to x1 by path C′3x4C′4x5C′6x1, and G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′6}] contains a subdivision of K3,3, a contradiction. Now we suppose C′6 is adjacent to x2,x1. Then C′3 is connected to x1 by path C′3x4C′4x5C′6x1, and G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′6}] contains a subdivision of K3,3, a contradiction. Now suppose C′5 is adjacent to x4,x1. Then C′3 is connected to x1 by path C′3x4C′4x5C′5x1, and G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′5}] contains a subdivision of K3,3, a contradiction. Then we suppose C′5 is adjacent to x3,x2. By symmetry of C′5 and C′6, we only need to consider the following cases. Suppose C′6 is adjacent to x3,x2. Then C′3 is connected to x5 by path C′3x4C′4x5, and G′[{x2,x3,x4,x5}∪{C′3,C′4,C′5,C′6}] contains a subdivision of K3,3, a contradiction. Now suppose C′6 is adjacent to x3,x1, then C′3 is connected to x1 by path C′3x4C′4x5C′6x1, and G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′6}] contains a subdivision of K3,3, a contradiction. Then suppose C′6 is adjacent to x2,x1, by the same argument as last case, we also obtain a contradiction. Now we suppose C′5 is adjacent to x3,x1. Then C′5 is connected to x2 by path C′5x5C′4x4C′3x2, and G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′5}] contains a subdivision of K3,3, a contradiction. So suppose C′5 is adjacent to x2,x1. Then C′5 is connected to x3 by path C′5x5C′4x3, and G′[{x1,x2,x3,x5}∪{C′1,C′2,C′4,C′5}] contains a subdivision of K3,3, a contradiction. Since the case that C′4 is adjacent to x4,x2 is symmetric to the case that C′4 is adjacent to x4,x3, we do not discuss this case. The case that C′4 is adjacent to x4,x1 is excluded by the discussion before Case (1.1). So we suppose C′4 is adjacent to x3,x2 now. By symmetry, we only need to consider the following cases. Suppose C′5 is adjacent to x3,x2, then suppose C′6 is adjacent to x3,x2. Then G′[{x2,x3,x5}∪{C′4,C′5,C′6}] contains a K3,3, a contradiction. Then suppose C′6 is adjacent to x3,x1. Now C′6 is connected to x2 by path C′6x1C′1x2, and G′[{x1,x2,x3,x5}∪{C′1,C′4,C′5,C′6}] contains a subdivision of K3,3, a contradiction. So suppose that C′6 is adjacent to x2,x1, then C′6 is connected to x3 by path C′6x1C′1x3, and G′[{x1,x2,x3,x5}∪{C′1,C′4,C′5,C′6}] contains a subdivision of K3,3, a contradiction. Now suppose C′5 is adjacent to x3,x1, then suppose C′6 is adjacent to x3,x1. Then C′4 is connected to x1 by path C′4x2C′1x1, and G′[{x1,x2,x3,x5}∪{C′1,C′4,C′5,C′6}] contains a subdivision of K3,3, a contradiction. So suppose C′6 is adjacent to x2,x1. Now C′6 is connected to x3 by path C′6x5C′4x3, and G′[{x1,x2,x3,x5}∪{C′1,C′2,C′4,C′6}] contains a subdivision of K3,3, a contradiction. Then suppose C′5 is adjacent to x2,x1, and C′6 can be adjacent only to x2,x1, by the same argument as last case, we can obtain a contradiction. Now suppose C′4 is adjacent to x3,x1, then suppose C′5 and C′6 are both adjacent to x3,x1. But G′[{x1,x3,x5}∪{C′4,C′5,C′6}] contains K3,3, a contradiction. So we suppose C′6 is adjacent to x2,x1 subject to the above assumption of C′4 and C′5. Now C′6 is connected to x3 by path C′6x5C′4x3, and G′[{x1,x2,x3,x5}∪{C′1,C′2,C′4,C′6}] contains a subdivision of K3,3, a contradiction. Then suppose C′5 is adjacent to x2,x1. Substituting C′5 for C′6 in the discussion of last case, we can obtain a contradiction. The remaining case is that C′4,C′5,C′6 are all adjacent to x2,x1. Then G′[{x1,x2,x5}∪{C′4,C′5,C′6}] contains K3,3, a contradiction.
Now we come back to the discussion of the first paragraph in Case 1. We have the second subcase as follows.
Suppose C′3 is adjacent to only one vertex in {x1,x2,x3}. By the symmetry of the roles of C′3,C′4,⋯,C′7, we can assume that each of C′3,C′4,⋯,C′7 is adjacent to only one vertex in {x1,x2,x3}. So all of C′3,C′4,⋯,C′7 are adjacent to both x4 and x5, and one of x1,x2,x3. But x1,x2,x3 have only 3 vertices and C′3,C′4,⋯,C′7 have 5 vertices, by the Pigeonhole Principle, there are C′i and C′j (3≤i≠j≤7) adjacent to x4,x5 and the same xr in {x1,x2,x3}, and there is a C′k (k≠i,j and 3≤k≤7) such that C′k is adjacent to x4,x5. We use C′i and C′j to replace C′1 and C′2, and C′k to replace C′3, then Case 1 still happens. The proof is the same as before.
Now suppose that Case 1 does not happen. Then, for any two vertices C′i and C′j (1≤i<j≤7), |N(C′i)∩N(C′j)|≤2.
Case 2. Suppose there are two vertices C′i and C′j (1≤i<j≤7) such that |N(C′i)∩N(C′j)|=2.
Without loss of generality, assume that N(C′1)={x1,x2,x3}, N(C′2)={x2,x3,x4} such that |N(C′1)∩N(C′2)|=2.
Case (2.1). C′1,C′2,C′3,C′4 are adjacent to only vertices in {x1,x2,x3,x4}.
Since G is 3-connected and Case 1 does not happen, then N(C′3)={x1,x2,x4} and N(C′4)={x1,x3,x4}. In G′[{x1,x2,x3,x4}∪{C′1,C′2,C′3,C′4}], any two of x1,x2,x3,x4 are symmetric, and any two of C′1,C′2,C′3,C′4 are symmetric. Since Case 1 does not happen, N(C′j) is not contained in {x1,x2,x3,x4} (j=5,6,7). So C′j must be adjacent to x5 (j=5,6,7). By the symmetry of any two of x1,x2,x3,x4, we can assume that C′5 is adjacent to x3,x4. Also by the assumption of Case 2, C′6 is adjacent to x1 and x2, or adjacent to x2 and x3. In the first case, {x1,x2} and {x3,x4} are symmetric, then C′1 is adjacent to x1,x2,x3, C′2 is adjacent to x2,x3, and C′2 is connected to x1 by path C′2x4C′3x1, C′6 is adjacent to x1,x2, and C′6 is connected to x3 by path C′6x5C′5x3. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′5,C′6}] contains a subdivision of K3,3, a contradiction. In the second case, C′2 is adjacent to x2,x3,x4, C′4 is adjacent to x3,x4, and is connected to x2 by path C′4x1C′1x2, C′5 is adjacent to x3,x4, and is connected to x2 by path C′5x5C′6x2. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′4,C′5,C′6}] contains a subdivision of K3,3, a contradiction.
Case (2.2). N(C′i)⊆{x1,x2,x3,x4} for i=1,2,3 but N(C′j)⊈{x1,x2,x3,x4} for 4≤j≤7.
Then N(C′3)={x1,x2,x4}. (The case that N(C′3)={x1,x3,x4} is symmetric, and the proof is similar). As the neighbourhood of C′i (i=4,5,6,7) is not contained in {x1,x2,x3,x4}, C′i is adjacent to x5 for i=4,5,6,7. In G′[{x1,x2,x3,x4}∪{C′1,C′2,C′3}], any two of x1,x3,x4 are symmetric, and any two of C′1,C′2,C′3 are symmetric. By the assumption of Case 2, we have the following four cases.
Case (2.2.1). Suppose N(C′4)={x3,x4,x5}, N(C′5)={x1,x4,x5}, and N(C′6)={x1,x3,x5}.
Notice that any two of x1,x3,x4 are symmetric, since Case (2.1) does not happen, N(C′7) is not contained in {x1,x3,x4,x5}, without loss of generality, assume that N(C′7)={x2,x3,x5}. Now C′2 is adjacent to x2,x3,x4, C′1 is adjacent to x2,x3, and is connected to x4 by path C′1x1C′3x4, C′7 is adjacent to x2,x3, and is connected to x4 by path C′7x5C′4x4. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′7}] contains a subdivision of K3,3, a contradiction.
Case (2.2.2). Suppose N(C′4)={x3,x4,x5}, N(C′5)={x1,x3,x5}.
Now x1 and x4 are symmetric. By the assumption of Case 2, as Case (2.2.1) does not hold, we have two cases: N(C′6)={x2,x4,x5}; or N(C′6)={x2,x3,x5}. Suppose N(C′6)={x2,x4,x5}. Then C′2 is adjacent to x2,x3,x4, C′1 is adjacent to x2,x3, and is connected to x4 by path C′1x1C′3x4, C′6 is adjacent to x2,x4, and is connected to x3 by path C′6x5C′5x3. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′5,C′6}] contains a subdivision of K3,3, contradicting to the fact that G′ is planar. Suppose N(C′6)={x2,x3,x5}. Then C′2 is adjacent to x2,x3,x4, C′1 is adjacent to x2,x3, and is connected to x4 by path C′1x1C′3x4, C′6 is adjacent to x2,x3, and is connected to x4 by path C′6x5C′4x4. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′6}] contains a subdivision of K3,3, a contradiction.
Case (2.2.3). Suppose N(C′4)={x3,x4,x5}.
Now x3 and x4 are symmetric. We have two cases: (1) N(C′5)={x2,x3,x5}, N(C′6)={x2,x4,x5}; (2) N(C′5)={x2,x3,x5}, N(C′6)={x1,x2,x5}.
In the first case, C′2 is adjacent to x2,x3,x4, C′1 is adjacent to x2,x3, and is connected to x4 by path C′1x1C′3x4, C′6 is adjacent to x2,x4, and is connected to x3 by path C′6x5C′5x3. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′5,C′6}] contains a subdivision of K3,3, a contradiction.
In the second case, C′1 is adjacent to x1,x2,x3, C′2 is adjacent to x2,x3, and is connected to x1 by path C′2x4C′3x1, C′6 is adjacent to x1,x2, and is connected to x3 by path C′6x5C′4x3. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′6}] contains a subdivision of K3,3, a contradiction.
There remains the last case in Case (2.2) as follows.
Case (2.2.4). Suppose N(C′4)={x2,x3,x5}, N(C′5)={x2,x4,x5}, N(C′6)={x1,x2,x5}.
Now C′1 is adjacent to x1,x2,x3, C′2 is adjacent to x2,x3, and is connected to x1 by path C′2x4C′3x1, C′6 is adjacent to x1,x2, and is connected to x3 by path C′6x5C′4x3. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′6}] contains a subdivision of K3,3, a contradiction.
Case (2.3). Suppose only C′1,C′2 are adjacent only to vertices in {x1,x2,x3,x4}.
Since N(C′i) is not contained in {x1,x2,x3,x4}, C′i is adjacent to x5 for i=3,4,⋯,7. Now x1 and x4 are symmetric, x2 and x3 are symmetric in G′[{x1,x2,x3,x4}∪{C′1,C′2}]. By the assumption of Case 2, each C′i is adjacent to exactly two vertices in {x1,x2,x3,x4} besides x5 (i=3,4,⋯,7), and C′i and C′j (3≤i<j≤7) are not adjacent to the same two vertices in {x1,x2,x3,x4}. Since the number of combinations of two vertices in {x1,x2,x3,x4} is totally C(4,2)=4×32!=6, there is exactly one combination of two vertices which are not adjacent to the same C′i (3≤i≤7), and for each of the other combinations of two vertices in {x1,x2,x3,x4}, the two vertices are both adjacent to one C′i (3≤i≤7). Considering the symmetry of the roles of C′i (i=3,4,⋯,7), there are six cases to take five combinations from the totally six combinations of two vertices in {x1,x2,x3,x4} such that the two vertices of each of the five combinations are both adjacent to a C′i (3≤i≤7). Also considering the symmetry of x1 and x4, and x2 and x3, there remains 3 cases as follows.
Case (2.3.1). No C′i (3≤i≤7) is adjacent to both x1 and x4.
Since the roles of C′3,C′4,⋯,C′7 are symmetric, without loss of generality, assume that N(C′3)={x1,x2,x5}, N(C′4)={x3,x4,x5}, N(C′5)={x2,x4,x5}, N(C′6)={x1,x3,x5}, N(C′7)={x2,x3,x5}.
Now C′7 is adjacent to x2,x3,x5, C′4 is adjacent to x3,x5, and is connected to x2 by path C′4x4C′2x2, C′3 is adjacent to x2,x5, and is connected to x3 by path C′3x1C′6x3. So G′[{x1,x2,x3,x4,x5}∪{C′2,C′3,C′4,C′6,C′7}] contains a subdivision of K3,3, a contradiction.
Case (2.3.2). No C′i (3≤i≤7) is adjacent to both x1 and x2. (For x1,x3; x2,x4; x3,x4, the discussion is similar.)
Since the roles of C′3,C′4,⋯,C′7 are symmetric, without loss of generality, assume that N(C′3)={x1,x4,x5}, N(C′4)={x1,x3,x5}, N(C′5)={x2,x4,x5}, N(C′6)={x3,x4,x5}, N(C′7)={x2,x3,x5}.
Now C′2 is adjacent to x2,x3,x4, C′1 is adjacent to x2,x3, and is connected to x4 by path C′1x1C′3x4, C′5 is adjacent to x2,x4, and is connected to x3 by path C′5x5C′7x3. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′5,C′7}] contains a subdivision of K3,3, a contradiction.
Case (2.3.3). No C′i (3≤i≤7) is adjacent to both x2 and x3.
Since the roles of C′3,C′4,⋯,C′7 are symmetric, without loss of generality, assume that N(C′3)={x1,x4,x5}, N(C′4)={x1,x2,x5}, N(C′5)={x1,x3,x5}, N(C′6)={x2,x4,x5}, N(C′7)={x3,x4,x5}.
Now C′1 is adjacent to x1,x2,x3, C′2 is adjacent to x2,x3, and is connected to x1 by path C′2x4C′3x1, C′4 is adjacent to x1,x2, and is connected to x3 by path C′4x5C′5x3. So G′[{x1,x2,x3,x4,x5}∪{C′1,C′2,C′3,C′4,C′5}] contains a subdivision of K3,3, a contradiction.
Case 3. Suppose that, for any two vertices C′i and C′j (1≤i<j≤7), |N(C′i)∩N(C′j)|≤1 and Cases 1 and 2 do not hold.
Since |N(C′i)|=|N(C′j)|=3 and |S|=5, |N(C′i)∩N(C′j)|=1 (1≤i<j≤7). Without loss of generality, assume that N(C′1)={x1,x2,x3}, and N(C′2)={x3,x4,x5}. Then N(C′1)∩N(C′2)={x3}. By the assumption of Case 3, |N(C′3)∩N(C′1)|=1, then there are two vertices of N(C′3) which are not in {x1,x2,x3}, hence |N(C′3)∩N(C′2)|≥2, which contradicts the assumption of Case 3.
In all cases discussed above, we can always obtain contradiction. So ω(G−S)≥|S|+2 does not hold. By Lemma 1, when ν(G)≥2k, G is k-subconnected for k=4,5,6.
Remark 1. Now we give some counterexamples to show the sharpness of Corollaries 7 and 8, and Theorem 10. Let H be a connected planar graph, let G1,G2,G3 be three copies of H, and let v be a vertex not in Gi (i=1,2,3). Let G be the graph such that v is joined to Gi (i=1,2,3) by an edge respectively. Then G is a 1-connected planar graph, but G is not 2-subconnected since we take a vertex vi in Gi (i=1,2,3) and let v4=v, then there are not two independent paths joining v1,v2,v3,v4 in two pairs in G. So Corollary 7 is sharp.
Let H be a planar embedding of a 2-connected planar graph, let G1,G2,G3,G4 be four copies of H, let v5 and v6 be two vertices not in Gi (i=1,2,3,4). Let G be the graph such that v5 and v6 are joined to two different vertices on the outer face of Gi (i=1,2,3,4) by edges respectively. Then G is a 2-connected planar graph, but is not 3-subconnected since we take a vertex vi in Gi (i=1,2,3,4), then there are not three independent paths joining v1,v2,v3,v4,v5,v6 in three pairs. So Corollary 8 is sharp.
Let G0 be a triangle with vertex set {v4,v5,v6}, then insert a vertex vi into a triangle inner face of Gi−1 and join vi to every vertex on the face by an edge respectively to obtain Gi for i=1,2,3. Let G=G3. Notice that ν(G)=6, ε(G0)=3, and each time when we insert a vertex, the number of edges increases by 3. So ε(G)=3+3+3+3=12. By the Euler's Formula, ϕ=ε−ν+2=12−6+2=8. Let H be a planar embedding of a 3-connected planar graph. Then put a copy of H into every face of G and join each vertex on the triangle face of G to a distinct vertex on the outer face of H to obtain a planar graph G′. Then G′ is a 3-connected planar graph with ν(G′)≥2k for k=7, but G′ is not 7-subconnected since we have a cutset S={v1,v2,v3,v4,v5,v6}, but G′−S has 8 copies of H (8 components) and ω(G′−S)=8≥|S|+2. By Lemma 1, the conclusion holds. So Theorem 10 is sharp.
Remark 2. For a 3-connected planar graph G with at least 2k vertices, by Lemma 6, G is obviously k-subconnected for k=1,2,3.
In the last section, we prove the k-subconnectivity of k′-connected planar graphs for k′=1,2,⋯,5.
Since a k-subconnected graph is a spanning substructure of a k-connected graph, in the future, we can work on the number of edges deleted from a k-connected graph such that the resulting graph is still k-subconnected.
We may also extend the k-subconnectivity of planar graphs to find the subconnectivity of general graphs with a higher genus.
[1] | O. R. Oellermann, Connectivity and edge-connectivity in graphs: A survey, Congressus Numerantium, 116 (1996), 231–252. |
[2] |
B. Peroche, On several sorts of connectivity, Discrete Math., 46 (1983), 267–277. doi: 10.1016/0012-365X(83)90121-8
![]() |
[3] | Z. Dvořák, J. Kára, D. Král, O. Pangrác, An algorithm for cyclic edge connectivity of cubic graphs, In: Algorithm Theory-SWAT 2004, Springer, Berlin, Heidelberg, 2004,236–247. |
[4] | D. Lou, W. Wang, An efficient algorithm for cyclic edge connectivity of regular graphs, Ars Combinatoria, 77 (2005), 311–318. |
[5] | D. Lou, K. Liang, An improved algorithm for cyclic edge connectivity of regular graphs, Ars Combinatoria, 115 (2014), 315–333. |
[6] | D. Lou, A square time algorithm for cyclic edge connectivity of planar graphs, Ars Combinatoria, 133 (2017), 69–92. |
[7] |
J. Liang, D. Lou, Z. Zhang, A polynomial time algorithm for cyclic vertex connectivity of cubic graphs, Int. J. Comput. Math., 94 (2017), 1501–1514. doi: 10.1080/00207160.2016.1210792
![]() |
[8] |
J. Liang, D. Lou, A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k, J. Comb. Optim., 37 (2019), 1000–1010. doi: 10.1007/s10878-018-0332-4
![]() |
[9] | C. Thomassen, 2-linked graphs, Eur. J. Combin., 1 (1980), 371–378. |
[10] | B. Bollobás, A. Thomason, Highly linked graphs, Combinatorica, 16 (1996), 313–320. |
[11] |
K. Kawarabayashi, A. Kostochka, G. Yu, On sufficient degree conditions for a graph to be k-linked, Comb. Probab. Comput., 15 (2006), 685–694. doi: 10.1017/S0963548305007479
![]() |
[12] |
Z. Qin, D. Lou, H. Zhu, J. Liang, Characterization of k-subconnected graphs, Appl. Math. Comput., 364 (2020), 124620. doi: 10.1016/j.amc.2019.124620
![]() |
[13] | J. A. Bondy, U. S. R. Murty, Graph theory with applications, MacMillan Press Ltd., 1976. |
[14] | W. T. Tutte, A theorem on planar graphs, T. Am. Math. Soc., 82 (1956), 99–116. |
1. | Dingjun Lou, Zongrong Qin, The structure of minimally 2-subconnected graphs, 2022, 7, 2473-6988, 9871, 10.3934/math.2022550 |