# Closure Results for Arbitrarily Partitionable Graphs

Julien Bensmail

► To cite this version:

Julien Bensmail. Closure Results for Arbitrarily Partitionable Graphs. Opuscula Mathematica, 2024, 44 (6), pp.773-788. 10.7494/OpMath.2024.44.6.773. hal-04370225v2

HAL Id: hal-04370225

https://hal.science/hal-04370225v2

Submitted on 29 Jul 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
1

# Closure Results for Arbitrarily Partitionable Graphs

2

Julien Bensmailª

3

ªUniversité Côte d'Azur, CNRS, Inria, I3S, France

4

## Abstract

A well-known result of Bondy and Chvátal establishes that a graph of order $n$ is Hamiltonian if and only if its $n$-closure (obtained through repeatedly adding an edge joining any two non-adjacent vertices with degree sum at least $n$) also is. In this work, we investigate such closure results for arbitrarily partitionable graphs, a weakening of Hamiltonian graphs being those graphs that can be partitioned into arbitrarily many connected graphs of arbitrary orders. Among other results, we establish closure results for arbitrary partitions into connected graphs of order at most 3, for arbitrary partitions into connected graphs of order exactly any $\lambda$, and for the property of being arbitrarily partitionable in full.

5

**Keywords:** connected partition; arbitrarily partitionable graph; closure; traceability.

6

## 1. Introduction

7

8

9

10

11

12

13

14

15

16

17

Let $n \ge 1$ be a positive integer. An $n$-graph $G$ is a graph of order $n$, while an $n$-partition $\pi = (\lambda_1, \dots, \lambda_p)$ is a partition of $n$ (i.e., $\lambda_1 + \dots + \lambda_p = n$). A partition $(S_1, \dots, S_p)$ of the vertex set $V(G)$ of $G$ is called a *realisation* of $\pi$ in $G$ if each part $S_i$ is *connected* and has cardinality $\lambda_i$, that is, if, for every $i \in \{1, \dots, p\}$, the graph $G[S_i]$ is a connected graph of order $\lambda_i$. We now say $G$ is *arbitrarily partitionable* (AP) if every $n$-partition is realisable in $G$, or, in other words, if $G$ can be partitioned into arbitrarily many connected graphs with arbitrary orders. All these notions have been introduced and considered independently by Barth, Baudon, and Puech in [1], and by Horňák and Woźniak in [13], in connection, in particular, with a practical network sharing problem. Since then, quite some interesting aspects of AP graphs have been introduced and investigated in literature, see e.g. the latest references [3, 4, 5, 6, 8, 10, 15] on the topic for further information.

18

19

20

21

22

23

24

25

26

One of the main sources of motivation behind the investigations in the current work, is the fact that APness can be perceived both as a strengthening of *perfect matchings* (sets of $[n/2]$ pairwise disjoint edges<fnref n="1" />) and a weakening of *Hamiltonian paths* (paths going through all $n$ vertices exactly once). Indeed, note that an AP $n$-graph, depending on the parity of $n$, admits realisations of $(1, 2, \dots, 2)$ or $(2, \dots, 2)$, which form perfect matchings; and that every path is obviously AP, from which we get that any traceable graph, *i.e.*, any graph admitting a Hamiltonian path, is AP. From this, interesting questions on AP graphs arise when wondering how classical results on perfect matchings and Hamiltonian paths adapt to AP graphs. This line of research was initiated by Marczyk, who, in [16], proved:

27

28

29

**Theorem 1.1** (Marczyk [16]). Let $G$ be a connected $n$-graph in which the degree sum of any two non-adjacent vertices is at least $n-2$. Then $G$ is AP if and only if $G$ admits a perfect matching.

<footnote n="1">¹For convenience, unless stated otherwise, the order of any graph is denoted by $n$ throughout.</footnote>
30

31

32

33

34

35

36

Clearly, Theorem 1.1 stands as a weakening, to APness, of the well-known sufficient condition by Ore for graphs to admit Hamiltonian paths or cycles (stating that any connected $n$-graph in which the degree sum parameter is at least $n$ or $n-1$ admits Hamiltonian cycles or paths, respectively [18]). A remarkable fact also, is that the statement of Theorem 1.1 involves the two notions (perfect matchings and Hamiltonian paths) between which APness is comprised; although these two notions are rather distant in general, this shows there are stronger connections between the two in the context of AP graphs.

37

38

39

40

41

42

43

44

45

Marczyk's Theorem 1.1 opened the way to an interesting line of research on AP graphs, being to investigate how well-known sufficient conditions for Hamiltonicity or traceability weaken to APness. In the very line of Theorem 1.1, better results involving the degree sum of pairs of non-adjacent vertices were established in [12, 17], and such results for triples of pairwise non-adjacent vertices were considered in [3]. In [14], sufficient conditions in terms of number of edges have also been established, while toughness properties of AP graphs have been studied in [5]. Last, in [6], the authors considered several other classical concepts and results for Hamiltonicity and traceability, such as forbidden induced patterns and the square operation, and proved that some adapt to APness while some others do not.

46

47

48

49

50

51

52

53

In the current work, we pursue this line of research by considering yet another classical aspect borrowed from the study of Hamiltonian and traceable graphs, being that of **graph closures**. Recall that, for a graph $G$ and some $k \ge 1$, the $k$-closure $clos(G, k)$ of $G$ is obtained upon repeatedly adding an edge $uv$ between two non-adjacent vertices $u$ and $v$ satisfying $d(u) + d(v) \ge k$. Equivalently, note that the $k$-closure $clos(G, k)$ of $G$ is obtained through a $k$-closing sequence $G_0, \dots, G_m$, being a sequence of $n$-graphs where $G_0 = G$ and $G_m = clos(G, k)$, and, for every $i \in \{1, \dots, m\}$, the graph $G_i$ is obtained from $G_{i-1}$ by adding a single edge $uv$ such that $d_{G_{i-1}}(u) + d_{G_{i-1}}(v) \ge k$.

54

55

Graph closures emerged in a seminal work [7] of Bondy and Chvátal, in which they provided the celebrated Bondy-Chvátal sufficient condition for Hamiltonicity and traceability:

56

57

**Theorem 1.2** (Bondy, Chvátal [7]). An $n$-graph is Hamiltonian if and only if its $n$-closure is Hamiltonian. Likewise, an $n$-graph is traceable if and only if its $(n-1)$-closure is traceable

58

59

60

61

62

63

64

Among other remarkable aspects of interest, Bondy and Chvátal's Theorem 1.2 is important in that it implies several other classical sufficient conditions for Hamiltonicity and traceability, such as Dirac's conditions [11] and Ore's conditions [18]. It is also worth mentioning that the concept of graph closure does not restrict to Hamiltonian cycles and paths only, and can also be employed to express sufficient conditions for graphs to admit other types of objects. For more details on this point, and more generally on anything related to graph closures, we refer the interested reader to the survey [9].

65

66

67

68

69

70

71

72

73

74

75

76

Our main intent in the current work is to initiate the study of graph closures in the very context of AP graphs. In particular, as explained earlier when introducing Marczyk's Theorem 1.1, given any sufficient condition for Hamiltonicity and traceability, it is natural to wonder whether it weakens to APness. Bondy and Chvátal's Theorem 1.2 being one of the most influential results on graph closures, it is thus legitimate to wonder how it adapts (or not) to APness. As a first step, we consider $(n-2)$-closures in Section 2, showing that, for APness, we cannot just weaken Theorem 1.2 to $(n-2)$-closures. Our arguments lead us to considering arbitrary partitions into connected graphs of order at most 3 in Section 3, for which we prove the tight result that it is necessary and sufficient to consider $(n-1)$-closures. Then, in Section 4, we consider weaker closures, and establish more general results for partitions into connected graphs of order any fixed $\lambda$, and for the AP property in full. We finish off in Section 5 with discussions for further work on the topic.
## 2. On the APness of (n-2)-closures

Given how sufficient conditions on degree sums of pairs of non-adjacent vertices essentially weaken from $n$ for Hamiltonicity to $n-1$ for traceability (Ore's Theorem) and to $n-2$ for APness (Marczyk's Theorem 1.1), a first, legitimate question is whether Bondy and Chvátal's Theorem 1.2 weakens the same way to APness, or, in other words, whether $n$-graphs are AP if and only if their $(n-2)$-closure is. Likewise, just like how Bondy and Chvátal's Theorem 1.2 implies Ore's Theorem, one can also wonder whether there is some result on APness and $(n-2)$-closures that would imply Marczyk's Theorem 1.1.

Previous studies on AP graphs have highlighted that, when realising an $n$-partition $\pi$ in an $n$-graph, an important parameter to take into account is the spectrum $sp(\pi)$ of $\pi$, which is the set of all values appearing in $\pi$ (thus, $sp(\pi)$ is essentially $\pi$ with all duplicates removed). Perhaps one of the most significant results on partition spectra is one by Ravaux stating that, in graphs with large diameter, the AP property relies solely on the realisability of partitions with small spectrum [20]. More generally speaking, as described in [5], something we learn from previous works on AP graphs is that, 1) the smaller the spectrum of a partition $\pi$ is, and 2) the smaller the values of $\pi$ are, the less chances there are that $\pi$ is realisable in a given graph. In other words, to establish that some graphs with particular properties are not necessarily AP, very generally speaking one should consider the realisability of partitions with small values and low variety of values.

From these thoughts, regarding the hopes we have exposed for $(n-2)$-closures earlier, we get to the matter of establishing whether, in general, $n$-partitions with small spectrum are realisable if and only if they are in the $(n-2)$-closure. As a starting point, it thus makes sense to wonder about perfect matchings$^2$, or, in other words, about realisations of partitions with spectrum $\{2\}$. Below, we prove that, indeed, already for this particular type of partitions we cannot weaken Bondy and Chvátal's Theorem 1.2 to value $n-2$ as is. For transparency, let us mention that upcoming Theorem 2.3 is actually a particular case of a previous result of Plummer and Saito [19]; still, we provide a straight, thorough proof, as our arguments stand as a good introduction to the ones to be used later on.

To begin with, let us remind Tutte's condition for the existence of perfect matchings.

**Theorem 2.1** (Tutte [21]). A graph $G$ with even order has a perfect matching if and only if for every $S \subseteq V(G)$ the graph $G-S$ has at most $|S|$ connected components with odd order.

We now proceed with our first result, Theorem 2.3. Before that, we just need to introduce an auxiliary result that will show Theorem 2.3 is indeed the best we can hope for. Recall that for any two positive integers $p, q \ge 1$, we denote by $K_{p,q}$ the complete bipartite graph with partition classes of cardinality $p$ and $q$.

**Lemma 2.2.** For any $p \ge 1$, $\text{clos}(K_{p,p+2}, n-2)$ has perfect matchings while $K_{p,p+2}$ has not.

*Proof.* Set $G = K_{p,p+2}$ for some $p \ge 1$, and denote by $U$ the partition class of $G$ with cardinality $p$, and by $V$ that with cardinality $p+2$. Note that all vertices of $U$ have degree $|V| = p+2$, while all vertices of $V$ have degree $|U| = p$. Set $n = |V(G)| = 2p+2$.

First off, note that $G-U$ consists of $p+2$ connected components, all of which have odd order, 1. Meanwhile, $|U| = p$. Thus, by Tutte's Theorem, $G$ admits no perfect matchings.

Now consider $G' = \text{clos}(G, n-2)$. Note that, in $G$, any two non-adjacent vertices $u$ and $v$ either both belong to $U$, or both belong to $V$. Also, if $u, v \in U$, then $d_G(u) + d_G(v) = 2(p+2) = 2p+4 = n+2$; while, if $u, v \in V$, then $d_G(u) + d_G(v) = 2p = n-2$. Thus, for any two

<footnote>$^2$From here on, perfect matchings are only considered for graphs with even order.</footnote>
121

122

non-adjacent vertices $u$ and $v$ of $G$, we have $d_G(u) + d_G(v) \ge n-2$, which implies that $u$ and $v$ are adjacent in $G'$. Thus $G'$ is complete, and hence it admits perfect matchings. $\square$

123

124

**Theorem 2.3.** Every graph $G$ with even order $n \ge 2$ admits perfect matchings if and only if $\text{clos}(G, n-1)$ does. Besides, value $n-1$ in the previous statement is best possible.

125

126

127

128

129

*Proof.* Set $G' = \text{clos}(G, n-1)$. Clearly, if $G$ admits perfect matchings, then so does $G'$. Thus, it remains to prove that if $G'$ admits perfect matchings, then so does $G$. Consider an $(n-1)$-closing sequence $G_0, \dots, G_m$ where $G_0 = G$ and $G_m = G'$. It suffices to prove that, for any $i \in \{1, \dots, m\}$, from any perfect matching of $G_i$ we can deduce one of $G_{i-1}$. Set thus $H = G_{i-1}$ and $H' = G_i$, and let $M$ be a perfect matching of $H'$.

130

131

132

133

134

135

136

137

If $M$ is a perfect matching of $H$, then we are done. Otherwise, it means $M$ contains $uv$, the unique edge of $H'$ not in $H$. Then, by definition, $d_H(u) + d_H(v) \ge n-1$. Now, for every neighbour $w \ne v$ of $u$ in $H$, note that if $ww' \in M$ for some $w' \notin \{u, v, w\}$, and we have $vw' \in E(H)$, then $M \setminus \{uv, ww'\} \cup \{uw, vw'\}$ is a perfect matching of $H$. If there is no such configuration in $H$, then it means that, for every edge $uw \in E(H)$ such that $ww' \in M$, we cannot have $vw' \in E(H)$. From this, we deduce that $d_H(v) \le n-2 - d_H(u)$, and thus that $d_H(u) + d_H(v) \le n-2$, contradicting that $uv$ is an edge of $H'$. Thus we can always derive a perfect matching of $H$ from $M$, and we are done.

138

The last part of the statement follows e.g. from Lemma 2.2. $\square$

<figure><img src="image_2.png" /></figure>

139

140

141

142

143

144

145

Due to Theorem 2.3, it is not true that any $n$-graph is AP if and only if its $(n-2)$-closure is AP, which would have stood as a smooth and natural weakening of Bondy and Chvátal's Theorem 1.2 to APness. The fact that perfect matchings are an obstruction to such a result is actually not that surprising either, as, recall, Marczyk's Theorem 1.1, to weaken Ore's Theorem from $n-1$ to $n-2$, already had to exclude such partitions from the equation. In the present case, however, things are a bit different, as we can actually adapt Theorem 2.3 to partitions with spectrum $\{3\}$, see upcoming Theorem 2.5.

146

147

148

149

150

151

152

As earlier, we start off by introducing some construction that will show the next result is best possible. In the present case, the construction actually holds for any size value $\lambda \ge 2$, although upcoming Theorem 2.5 deals only with the particular case where $\lambda = 3$. For any three positive integers $p, q, r \ge 1$, we denote by $T(p, q, r)$ the graph obtained from the disjoint union of three cliques $K_p, K_q$, and $K_r$ on $p, q$, and $r$ vertices, respectively, by adding a universal vertex $v$. Note that $v$ is a cut-vertex of $T(p, q, r)$, whose removal results in exactly three connected components, being $K_p, K_q$, and $K_r$.

153

154

**Theorem 2.4.** For every $\lambda \ge 2$ and $p \ge 1$ with $p \equiv \lambda - 1 \pmod \lambda$, $\text{clos}(T(1, p, p), n-2)$ has realisations of $(\lambda, \dots, \lambda)$ while $T(1, p, p)$ has not.

155

156

157

158

159

160

*Proof.* For any $\lambda \ge 2$ and $p \ge 1$ with $p \equiv \lambda - 1 \pmod \lambda$, set $G = T(1, p, p)$ and $n = |V(G)| = 2p+2$. Since $G$ has a cut-vertex $v$ whose removal results in three connected components, $K, K'$, and $K''$, having order 1, $p$, and $p$, respectively, and $p \equiv \lambda - 1 \pmod \lambda$, it should be clear that, in any realisation $\mathcal{R}$ of $(\lambda, \dots, \lambda)$ in $G$, there must be one part containing $v$ and $\lambda - 1$ vertices of $K'$, and similarly one part containing $v$ and $\lambda - 1$ vertices of $K''$, which is impossible. Thus $\mathcal{R}$ cannot exist, and $G$ does not admit any realisation of $(\lambda, \dots, \lambda)$.

161

162

163

164

Let us now consider $G' = \text{clos}(G, n-2)$. Note that, in $G$, all vertices of $K'$ and $K''$ have degree $p = \frac{n-2}{2}$, vertex $v$ has degree $n-1$, and the unique vertex of $K$ has degree 1. Thus, in $G'$, any two vertices of $K'$ and $K''$ are adjacent. This implies $G'$ is traceable, from which we get that $G'$ is AP, and thus admits realisations of $(\lambda, \dots, \lambda)$, as claimed. $\square$

<figure><img src="image_3.png" /></figure>
**Theorem 2.5.** Every graph $G$ of order $n \equiv 0 \mod 3$ at least 3 admits realisations of $(3, \dots, 3)$ if and only if $\text{clos}(G, n - 1)$ does. Besides, value $n - 1$ in the previous statement is best possible.

168
169
170
171
172
173
174
175
176
177

*Proof.* Set $G' = \text{clos}(G, n-1)$. As in the proof of Theorem 2.3, we focus on an $(n-1)$-closing sequence $G_0, \dots, G_m$ where $G_0 = G$ and $G_m = G'$, our goal being to prove that, for any $i \in \{1, \dots, m\}$, any realisation $\mathcal{R}$ of $(3, \dots, 3)$ in some $H' = G_i$ can be turned into one of $H = G_{i-1}$. Assume thus $\mathcal{R}$ does not hold as is in $H$; thus, there is a part $S = \{u, v, w\}$ of $\mathcal{R}$ that contains the unique edge $vw$ of $H'$ not in $H$, thereby making $H[S]$ not connected. Then we can assume $H[S]$ contains $uv$, while $w$ is isolated in $H[S]$.

Let $n_3, n_2$, and $n_1$ be the number of parts of $\mathcal{R}$ different from $S$ in which, in $H$, vertex $v$ has exactly three, two, or one neighbour, respectively. Then $d_H(v) = 1+3n_3+2n_2+n_1$. We now analyse the number of possible edges incident to $w$ going to some part $S' = \{x, y, z\}$ of $\mathcal{R}$ different from $S$ in which $v$ also has neighbours (all these adjacencies being in $H$).

178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194

* If $v$ is adjacent to all of $x, y$, and $z$, then we claim a realisation of $(3, \dots, 3)$ in $H$ can be deduced if $w$, in $H$, is also adjacent to any vertex of $S'$. Indeed, assume, w.l.o.g., that $wx$ is an edge of $H$. Since $H[S']$ is connected, $H'$ (and thus $H$) necessarily contains one of $xy$ or $xz$. In the former case, replacing $S$ and $S'$ in $\mathcal{R}$ with $\{u, v, z\}$ and $\{w, x, y\}$ results in a realisation of $(3, \dots, 3)$ in $H$. In the latter case, we can instead replace parts $S$ and $S'$ with $\{u, v, y\}$ and $\{w, x, z\}$.

• If $v$ is adjacent only to, say, $x$ and $y$ in $S'$, then we claim a realisation of $(3, \dots, 3)$ in $H$ can be deduced if $w$, in $H$, is also adjacent to any two vertices in $S'$. First off, note that, for similar arguments as in the previous case, we would be done if these at least two neighbours of $w$ in $S'$ include $z$. So suppose $w$ is only adjacent to $x$ and $y$. Since $H'[S']$ is connected, we have that $xz$ or $yz$ lies in $H'$ (and thus in $H$). In the former case, replace, in $\mathcal{R}$, parts $S$ and $S'$ with $\{u, v, y\}$ and $\{w, x, z\}$ to get a realisation in $H$. In the latter case, replace $S$ and $S'$ with $\{u, v, x\}$ and $\{w, y, z\}$.

• If $v$ is adjacent only to, say, $x$ in $S'$, then, for similar reasons as earlier, we claim a realisation of $(3, \dots, 3)$ in $H$ can be obtained from $\mathcal{R}$ if $w$ is adjacent, in $H$, to all three vertices of $S'$. This is because, in that case, replacing, in $\mathcal{R}$, parts $S$ and $S'$ with $\{u, v, x\}$ and $\{w, y, z\}$ yields a desired realisation.

Now, if none of the situations above occurs, then we deduce that

$$
d_H(w) \le n - 3 - 3n_3 - 2n_2 - n_1 = n - 2 - (1 + 3n_3 + 2n_2 + n_1) = n - 2 - d_H(v),
$$

195
196
197

and hence $d_H(w) \le n - 2 - d_H(v)$, and $d_H(v) + d_H(w) \le n - 2$, a contradiction.

To conclude the proof, remark that e.g. Theorem 2.4 shows the second part of the statement also holds true. □

198
199
200
201
202

Although the first part of the statement of Theorem 2.5 holds only for partitions containing value $\lambda = 3$ only, Theorem 2.4 implies that if the first part of Theorem 2.5 also held for any $\lambda \ge 4$, then value $n-1$ would be best possible. Anyhow, Theorem 2.5 shows that Bondy and Chvátal's Theorem 1.2 does not weaken to APness by just considering threshold $n-2$, and this is not due to perfect matchings only, as Theorem 2.3 could indicate.
203

### 3. Connected partitions into parts of size at most 3

204

205

206

207

208

209

210

211

In previous Theorems 2.3 and 2.5, we were only concerned with connected partitions into parts all having the same size, $\lambda$, for very small values of $\lambda$, namely 2 and 3. To get a flavour of what it would take, with the same approach, to generalise our arguments to any partition, in the next result we consider a generalisation of Theorems 2.3 and 2.5 to partitions with spectrum included in $\{1,2,3\}$, or, in other words, to connected partitions into parts of size at most 3. As will be recalled right after the proof, such a result is not interesting only for generalisation purposes, but also because such partitions, in previous works on APness, have been proved to be of prime interest for certain graph classes.

212

213

214

**Theorem 3.1.** For every $n \ge 2$ and every $n$-partition $\pi$ with spectrum included in $\{1,2,3\}$, every graph $G$ of order $n$ admits realisations of $\pi$ if and only if $\text{clos}(G, n-1)$ does. Besides, value $n-1$ in the previous statement is best possible.

215

216

217

218

219

220

221

222

*Proof.* The proof goes similarly as the proofs of Theorems 2.3 and 2.5. Since one of the two directions is obvious, we focus on proving the less straight direction. Set $G' = \text{clos}(G, n-1)$, and let $\pi$ be an $n$-partition with spectrum included in $\{1,2,3\}$. We consider an $(n-1)$-closing sequence $G_0, \dots, G_m$ where $G_0 = G$ and $G_m = G'$. Again, it suffices to prove that, for any $i \in \{1, \dots, m\}$, any realisation of $\pi$ in $G_i$ yields one of $G_{i-1}$. So, we consider $H = G_{i-1}$ and $H' = G_i$, and let $\mathcal{R}$ be a realisation of $\pi$ in $H'$. If $\mathcal{R}$ does not hold directly in $H$, then it is because of a part $S$ containing the unique edge of $H'$ that does not belong to $H$ (that is, $H[S]$ is not connected while $H'[S]$ is). Then, $|S| \in \{2,3\}$.

223

224

225

To begin with, we assume $S$ has cardinality 2, and set $S = \{u, v\}$. Then, $uv \in E(H')$ and $uv \notin E(H)$. As in the proofs of Theorems 2.3 and 2.5, we analyse the possible neighbours of $v$ in $H$ w.r.t. those of $u$.

226

227

228

* If $u$ has, in $H$, a neighbour in a part $S'$ of cardinality 2 of $\mathcal{R}$ different from $S$, and $v$ is adjacent to the other vertex of $S'$, then, through the exact same arguments as in the proof of Theorem 2.3, we can deduce, from $\mathcal{R}$, a realisation of $\pi$ in $H$.

229

230

* If $u$ is adjacent, in $H$, to a vertex $w$ such that $S' = \{w\}$ is a part of $\mathcal{R}$, then note that, from $\mathcal{R}$, replacing $S$ and $S'$ with $\{u,w\}$ and $\{v\}$ results in a realisation in $H$.

231

* Assume last that $u$ has, in $H$, neighbours in a part $S' = \{w, x, y\}$ of cardinality 3.

232

233

234

235

– If $u$ is adjacent to all of $w$, $x$, and $y$, and $v$ is also adjacent to some vertex of $S'$, then a realisation of $\pi$ in $H$ can be obtained from $\mathcal{R}$ as follows. Assuming, w.l.o.g., that $v$ is adjacent to $w$, then just replace parts $S$ and $S'$ with $\{u, x, y\}$ and $\{v, w\}$. This indeed results in a desired realisation.

236

237

238

– If $u$ is adjacent, in $H$, to exactly two vertices in $S'$, say $w$ and $x$ w.l.o.g., then we claim a realisation of $\pi$ in $H$ can be deduced from $\mathcal{R}$ in case $v$ is also adjacent to two vertices of $S'$ in $H$. We distinguish two cases.

239

240

* Assume first that $v$ is adjacent to $y$. In that case, it suffices to replace parts $S$ and $S'$ of $\mathcal{R}$ with $\{u, w, x\}$ and $\{v, y\}$.

241

242

243

244

* Assume second that $v$ is adjacent to $w$ and $x$ (and not to $y$). Since $H'[S']$ (and thus $H[S']$) is connected, then one of $w$ and $x$ is adjacent to $y$ in $H'$ (and $H$). Assuming w.l.o.g. that $xy$ is an edge of $H$, we can here replace parts $S$ and $S'$ of $\mathcal{R}$ with $\{u, w\}$ and $\{v, x, y\}$ to be done.

245

246

247

– If $u$ is adjacent, in $H$, to only one vertex of $S'$, say $w$ w.l.o.g., and $v$ is adjacent, in $H$, to all of $w$, $x$, and $y$, then we can obtain a desired realisation by replacing parts $S$ and $S'$ of $\mathcal{R}$ with $\{u, w\}$ and $\{v, x, y\}$.
Now denote by $m_1$ and $m_2$ the number of parts of size 2 of $\mathcal{R}$ in which $u$ has (in $H$) exactly one or two neighbours, respectively, and by $n_1$, $n_2$, and $n_3$ the number of parts of size 3 in which $u$ has (in $H$) exactly one, two, or three neighbours. Then

$$d_H(u) = m_1 + 2m_2 + n_1 + 2n_2 + 3n_3.$$

Also, since none of the cases above apply, we have

$$d_H(v) \leq n - 2 - m_1 - 2m_2 - n_1 - 2n_2 - 3n_3 = n - 2 - d_H(u),$$

and thus $d_H(u) + d_H(v) \leq n - 2$, a contradiction.

Now suppose $S = \{u, v, w\}$, where $H[S]$ contains the edge $uv$ while $w$ is isolated (because $H'$ contains the edge $vw$ while $H$ does not contain it). For the same reasons as in the proof of Theorem 2.5, we can assume that, in $\mathcal{R}$, there is no $S' \neq S$ of size 3 in which:

* $v$ has three neighbours and $w$ has one neighbour;

* $v$ has two neighbours and $w$ has two neighbours;

* $v$ has one neighbour and $w$ has three neighbours.

We now lead a similar analysis regarding the possible neighbours of $v$ in $H$ in parts $S' \neq S$ of $\mathcal{R}$ of cardinality 1 or 2.

* Assume first that $v$ has, in $H$, a neighbour $x$ in a part $S' = \{x\}$ of size 1. Then a realisation of $\pi$ in $H$ is obtained upon replacing $S$ and $S'$ with $\{u, v, x\}$ and $\{w\}$.

* Assume second that $v$ has, in $H$, neighbours in a part $S' = \{x, y\}$ of cardinality 2. Recall that $xy$ is an edge of both $H'$ and $H$.

- Assume first $v$ is adjacent to both $x$ and $y$ in $H$. If $w$ is adjacent to any of $x$ and $y$ in $H$, then a realisation of $\pi$ in $H$ is obtained from $\mathcal{R}$ upon replacing parts $S$ and $S'$ with either $\{u, v, x\}$ and $\{w, y\}$, or $\{u, v, y\}$ and $\{w, x\}$.

- Assume second $v$ is adjacent only to $x$ in $G$. If $w$ is adjacent to $x$ and $y$, then a realisation is obtained when replacing parts $S$ and $S'$ with $\{u, v, x\}$ and $\{w, y\}$.

Now set $m_1$ and $m_2$ the number of parts of cardinality 2 of $\mathcal{R}$ in which $v$ has (in $H$) exactly one or two neighbours, respectively, and $n_1$, $n_2$, and $n_3$ the number of parts of cardinality 3 in which $v$ has (in $H$) exactly one, two, or three neighbours. Then

$$d_H(v) = 1 + m_1 + 2m_2 + n_1 + 2n_2 + 3n_3.$$

Meanwhile, by the arguments above, we have

$$d_H(w) \leq n - 3 - m_1 - 2m_2 - n_1 - 2n_2 - 3n_3 = n - 2 - d_H(v),$$

from which we deduce $d_H(v) + d_H(w) \leq n - 2$, a final contradiction.

The very last part of the statement follows e.g. from Lemma 2.2 and Theorem 2.4. $\square$

Theorem 3.1 makes more particular sense in the context of graph classes for which the AP property is known to rely only on the realisability of partitions with spectrum included in $\{1, 2, 3\}$. Such matters relate to questions raised first by Barth and Fournier in [2] on the complexity of determining whether a graph is AP. Note that it is not clear whether this problem lies in NP or co-NP, since the APness of an n-graph relies on the realisability
of an exponential number of $n$-partitions, while the non-APness of an $n$-graph implies an exponential number of partitions of the vertex set do not stand as realisations of particular $n$-partitions. Still, following the terminology from [4], it is believed that, perhaps, every $n$-graph $G$ admits a polynomial kernel of partitions, i.e., a set $K$ of a polynomial number (function of $n$) of $n$-partitions such that $G$ is AP if and only if all partitions of $K$ are realisable in $G$. If this was true, then this would imply deciding APness lies in NP.

Polynomial kernels of partitions have been proved to exist for a few graph classes, such as subdivided stars [1, 2], graphs with large diameter [20], superclasses of split graphs [6, 8, 15], and others [4, 6]. In particular, the polynomial kernel from [8] for split graphs contains partitions with spectrum included in $\{1, 2, 3\}$ only, which kernel also holds for superclasses of split graphs [15], in particular for $\{2K_2, C_4\}$-free graphs. Thus, a direct, general consequence of Theorem 3.1 and of these thoughts, is the following:

**Corollary 3.2.** If $G$ is a class of graphs of order $n \ge 2$ admitting $n$-partitions with spectrum included in $\{1, 2, 3\}$ as a polynomial kernel, then every $G \in G$ is AP if and only if $\text{clos}(G, n-1)$ is.

Note that Corollary 3.2 would extend the same way to any $n$-graph class for which $n$-partitions with spectrum included in $\{1, 2, 3\}$ stand as a polynomial kernel. Recall also that building graph closures can be done in polynomial time (see e.g. [9]).

## 4. More general results for weaker closures

In this section, we investigate how the proof arguments from the proofs of previous Theorems 2.3, 2.5, and 3.1 could be generalised to other partitions with spectrum of size 1 (Subsection 4.1) and even to APness (Subsection 4.2), provided we consider weaker closures.

### 4.1. Connected partitions into parts of size $\lambda$

Before proceeding with our main result here, let us establish the following useful lemma.

**Lemma 4.1.** If $G$ is an $n$-graph with two non-adjacent vertex $u$ and $v$ such that $d(u) + d(v) \ge n + c$, then $u$ and $v$ have at least $c + 2$ common neighbours. In particular, $c \le n - 4$.

*Proof.* Since $u$ and $v$ are not adjacent, we have $N(u) \cup N(v) \subseteq V(G) \setminus \{u, v\}$, which set has cardinality $n - 2$. Now, if $u$ and $v$ had at most $c + 1$ common neighbours only, then we would have

$$d(u) + d(v) \le 2(c + 1) + (n - 2) - (c + 1) = n + c - 1,$$

a contradiction.

The last part is because having $d(u) + d(v) \ge 2n - 3$ would imply $u$ and $v$ have at least $n - 1$ common neighbours, which is impossible in loopless graphs. $\square$

We now essentially adapt the first part of the statement of Theorem 2.5 to partitions with spectrum $\{\lambda\}$ for any $\lambda \ge 4$. Recall that Theorem 2.4 is precisely about such partitions, and thus indicates that, even in this context, we must at least consider $(n - 1)$-closures.

**Theorem 4.2.** For every $\lambda \ge 4$, every graph $G$ of order $n \equiv 0 \bmod \lambda$ at least $\lambda$ admits realisations of $(\lambda, \dots, \lambda)$ if and only if $\text{clos}(G, 2n - (\frac{2n}{\lambda} + \lambda - 1))$ does.

*Proof.* Set $\alpha = 2n - (\frac{2n}{\lambda} + \lambda - 1)$, and $G' = \text{clos}(G, \alpha)$. Consider an $\alpha$-closing sequence $G_0, \dots, G_m$ where $G_0 = G$ and $G_m = G'$. It again suffices to prove that any realisation $\mathcal{R}$ of $(\lambda, \dots, \lambda)$ of $H' = G_i$ for any $i \in \{1, \dots, m\}$ yields one of $H = G_{i-1}$. If $\mathcal{R}$ does not hold
as is in $H$, then it is because a part $S$ of $\mathcal{R}$ is not connected in $H$ (while it is in $H'$). That is, $H'[S]$ contains the only edge $uv$ that is present in $H'$ but not in $H$.

Since $H[S]$ is not connected, and $H[S] = H'[S] - uv$, vertices $u$ and $v$ cannot have any common neighbour in $S$. We claim there is necessarily a part $S' \neq S$ of $\mathcal{R}$ in which $u$ and $v$ have at least $\lambda - 1$ common neighbours. Indeed, note first that the value of $\lambda$ ensures that $n \geq 2\lambda$, as, for $n = \lambda$, we have $\alpha = \lambda - 1$, while $H$ in the present case is not connected and thus $d_H(u) + d_H(v) \leq n - 2 = \lambda - 2$, a contradiction. Thus, $|\mathcal{R}| \geq 2$, and if $u$ and $v$ had at most $\lambda - 2$ common neighbours in all of the $\frac{n}{\lambda} - 1 \geq 1$ parts of $\mathcal{R}$ different from $S$, then $u$ and $v$ would have at most

$$ \left(\frac{n}{\lambda} - 1\right) (\lambda - 2) = n - \left(\frac{2n}{\lambda} + \lambda - 2\right) $$

common neighbours, while, by Lemma 4.1, vertices $u$ and $v$ have at least $n - (\frac{2n}{\lambda} + \lambda - 3)$ common neighbours in $H$, a contradiction.

Thus, let $S' \neq S$ be any part of $\mathcal{R}$ in which $u$ and $v$ have at least $\lambda - 1$ common neighbours. Let also $S_u$ and $S_v$ be the vertex sets of the exactly two connected components of $H[S]$, where $S_u$ contains $u$ while $S_v$ contains $v$. In case $u$ and $v$ have exactly $\lambda - 1$ common neighbours in $S'$, then let also $w$ be the unique vertex of $S'$ not adjacent to both $u$ and $v$; otherwise, if $u$ and $v$ are both adjacent to all vertices of $S'$, then let $w$ be any vertex of $S'$. In both cases, let $w'$ be any neighbour of $w$ in $H[S']$.

Since $\lambda \geq 4$, we must have $\lambda - |S_u| \geq 2$ or $\lambda - |S_v| \geq 2$. Assume w.l.o.g. the former inequality holds. Now replace $S$ and $S'$ in $\mathcal{R}$ with both $S_u \cup \{w, w'\} \cup X$ and $S_v \cup Y$, where $X$ is any set of $\lambda - (|S_u| + 2) \geq 0$ vertices of $S' \setminus \{w, w'\}$, and $Y = S' \setminus \{w, w'\} \setminus X$. Since $ww'$ is an edge of $H$, and $u$ and $v$ are adjacent to all vertices in $S' \setminus \{w\}$, it can be observed that this results in a realisation of $(\lambda, \dots, \lambda)$ in $H$. $\square$

Note that $2n - (\frac{2n}{\lambda} + \lambda - 1)$ is a non-decreasing function of $\lambda$, so the most interesting case, yielding the stronger closure, is for $\lambda = 4$, for which case Theorem 4.2 deals with $(\frac{3}{2}n - 3)$-closures. Recall that, regardless of the actual value of $\lambda$, in any case we cannot hope to establish results involving closures stronger than $(n - 1)$-closures.

## 4.2. APness

We here consider the AP property in full, that is, we wonder about generalisations of Bondy and Chvátal's Theorem 1.2 to AP graphs. By the last part of Lemma 4.1, recall that we must consider degree sum thresholds at most $2n - 4$. In what follows, we prove that an $n$-graph $G$ is indeed AP if and only if its $(2n - 4)$-closure is. This result being surely far from optimal, we then improve it down to $(2n - 5)$-closures and even to $(2n - 6)$-closures, for the sake mainly of showcasing why it might be tedious to go even lower.

**Theorem 4.3.** Every graph $G$ of order $n \geq 3$ is AP if and only if $\text{clos}(G, 2n - 4)$ is.

*Proof.* Set $G' = \text{clos}(G, 2n - 4)$. Again, it suffices to prove that if the $(2n - 4)$-closure $\text{clos}(G, 2n - 4)$ is AP, then $G$ is also AP. Actually, we can consider a $(2n - 4)$-closing sequence $G_0, \dots, G_m$ where $G_0 = G$ and $G_m = G'$, and prove that, for $H' = G_i$ and $H = G_{i-1}$ for some $i \in \{1, \dots, m\}$, any realisation $\mathcal{R}$ of any $n$-partition $\pi$ in $H'$ yields one of $H$. If $\mathcal{R}$ holds as is in $H$, then we are done. Otherwise, some part $S$ of $\mathcal{R}$ contains the only edge $uv$ of $H'$ not in $H$, and we have that $H[S]$ is not connected.

Let us denote by $S_u$ and $S_v$ the subsets of vertices of $S$ such that $S_u$ contains the vertices of $H[S]$ belonging to the same connected component as $u$, and $S_v$ contains those belonging to the same connected component as $v$. Then, $S = S_u \cup S_v$, and we have $u \in S_u$
346

347

348

349

350

351

352

353

and $v \in S_v$. By Lemma 4.1, vertices $u$ and $v$ have at least $n-2$ common neighbours in $H$, and, actually, since $u$ and $v$ are not adjacent in $H$, we have $N_H(u) = N_H(v) = V(H) \setminus \{u, v\}$. In particular, since $H[S]$ is not connected, it must be that $|S_u| = |S_v| = 1$, as otherwise $u$ and $v$ would have, in $H$, a common neighbour in either $S_u$ or $S_v$, making $H[S]$ connected. Thus, $|S| = 2$, and since $n-2 \ge 1$ we have $|\pi| \ge 2$. Now, consider $S' \ne S$ another part of $\mathcal{R}$. Then, as mentioned above, in $H$, vertices $u$ and $v$ are adjacent to all vertices of $S'$. It then suffices, to obtain a realisation of $\pi$ in $H$, to start from $\mathcal{R}$, and, denoting by $w$ any vertex of $S'$, to replace parts $S$ and $S'$ with, say, $\{u, w\}$ and $\{v\} \cup S' \setminus \{w\}$. $\square$

354

**Theorem 4.4.** Every graph $G$ of order $n \ge 4$ is AP if and only if $\text{clos}(G, 2n-5)$ is.

355

356

357

*Proof.* The proof goes similarly as that of Theorem 4.3 (from a $(2n-5)$-closing sequence). This time, in $H$ vertices $u$ and $v$ have at least $n-3$ common neighbours. Since $H[S]$ is not connected, vertices $u$ and $v$ have no common neighbours in $S$, which implies $2 \le |S| \le 3$.

358

359

360

361

362

If $|S| = 3$, then we can assume, w.l.o.g., that $S_u = \{u\}$ and $S_v = \{v, w\}$. Thus $vw$ is an edge of $H$, and $u$ and $v$ admit all vertices of $V(H) \setminus \{u, v, w\}$ as common neighbours. Then, again, we can just consider any part $S' \ne S$ of $\mathcal{R}$ (such exists since $2n-5 \ge 3$), and, denoting by $x$ any vertex of $S'$, a realisation of $\pi$ in $H$ is obtained when starting from $\mathcal{R}$, and replacing parts $S$ and $S'$ with $\{v, w, x\}$ and $\{u\} \cup S' \setminus \{x\}$, respectively.

363

364

365

366

367

368

369

370

Now assume $|S| = 2$, i.e., $S$ contains $u$ and $v$ only. If $N_H(u) = N_H(v) = V(H) \setminus \{u, v\}$, then a realisation of $\pi$ in $H$ can be obtained similarly as in the proof of Theorem 4.3. Hence, we can last assume $u$ and $v$ have only $n-3$ common neighbours in $H$. Let us thus denote by $w$ the only vertex of $V(H) \setminus \{u, v\}$ not adjacent to both $u$ and $v$ in $H$. Again, since $2n-5 \ge 3$, we must have $|\pi| \ge 2$. If $\mathcal{R}$ contains a part $S' \ne S$ not containing $w$, then we can again reach our conclusion similarly as in the proof of Theorem 4.3. Otherwise, $|\pi| = 2$, and $\mathcal{R}$ thus contains only two parts, $S$ and $S'$, where $w \in S'$. By arguments above, $u$ and $v$ are adjacent to all vertices of $S' \setminus \{w\}$.

371

* If $|S'| = 1$, then $n=3$, a case not covered by the statement.

372

373

374

375

* If $|S'| = 2$, then $S' = \{w, x\}$ where $x$ is a common neighbour of $u$ and $v$ in $H$. In that case, $n=4$, and since $d_H(u) + d_H(v) \ge 2n-5=3$, for $uv$ to be an edge of $H'$ it must be that $uw$ is an edge of $H$, w.l.o.g. Then a realisation of $\pi$ in $H$ is obtained upon considering parts $\{u, w\}$ and $\{v, x\}$.

376

377

378

379

380

* If $|S'| \ge 3$, then consider any vertex $x$ of $S' \setminus \{w\}$ such that $H[S' \setminus \{x\}]$ is connected. Such an $x$ can be obtained e.g. by considering a leaf different from $w$ of a spanning tree of $H[S']$. Since $|S'| \ge 3$, recall that $H[S' \setminus \{x\}]$ contains a vertex adjacent to both $u$ and $v$. Then a realisation of $\pi$ in $H$ is obtained from $\mathcal{R}$ when considering parts $\{u, x\}$ and $\{v\} \cup S' \setminus \{x\}$.

381

This concludes the proof. $\square$

<figure><img src="image_4.png" /></figure>

382

**Theorem 4.5.** Every $n$-graph $G$ with $n \ge 5$ is AP if and only if $\text{clos}(G, 2n-6)$ is.

383

384

385

386

*Proof.* We follow the lines of the proofs of Theorems 4.3 and 4.4 (but this time considering a $(2n-6)$-closing sequence). Here, in $H$, vertices $u$ and $v$ have at least $n-4$ common neighbours. Because $H[S]$ is not connected, vertices $u$ and $v$ have no common neighbours in $S$, from which we deduce $2 \le |S| \le 4$. Also, keep in mind throughout that $n \ge 5$.

387

388

389

Similarly as in the proof of Theorem 4.4, if $|S| = 4$, then $u$ and $v$ are adjacent to all vertices of $V(H) \setminus S$. If, say, $|S_u| = 1$ and $|S_v| = 3$, then, again, it suffices to consider any part $S' \ne S$ of $\mathcal{R}$ (it can be checked that such exists, as $n \ge 5$ which implies $2n-6 \ge 4$), and,
390

391

392

denoting by $w$ any vertex of $S'$ (being a common neighbour of $u$ and $v$ in $H$), a realisation of $\pi$ in $H$ is obtained when replacing parts $S$ and $S'$ of $\mathcal{R}$ with $S_v \cup \{w\}$ and $S' \cup \{u\} \setminus \{w\}$. Otherwise, $|S_u| = |S_v| = 2$; we consider a few cases.

393

394

395

* If there is a part $S' \neq S$ of $\mathcal{R}$ with $|S'| \geq 4$, then a realisation of $\pi$ in $H$ is obtained upon replacing $S$ and $S'$ with $S_u \cup \{w, x\}$ (where $w$ and $x$ are any two vertices of $S'$) and $S_v \cup S' \setminus \{w, x\}$.

396

397

* If there is a part $S' \neq S$ with $|S'| = 3$, then, setting $S' = \{w, x, y\}$, it here suffices to replace $S$ and $S'$ with, say, $S_u \cup \{w, x\}$ and $S_v \cup \{y\}$.

398

399

* If there is a part $S' \neq S$ with $|S'| = 2$, then, setting $S' = \{w, x\}$, it here suffices to replace $S$ and $S'$ with, say, $S_u$ and $S_v \cup \{w, x\}$.

400

401

* If there is a part $S' \neq S$ with $|S'| = 1$, then, setting $S' = \{w\}$, it here suffices to replace $S$ and $S'$ with, say, $S_u \setminus \{u\}$ and $S_v \cup \{w, u\}$.

402

Thus, when $|S| = 4$, a realisation of $\pi$ in $H$ can be deduced in all cases.

403

404

405

406

407

408

409

If $|S| = 3$, then set $S = \{u, v, w\}$, where $S_u = \{u\}$ and $S_v = \{v, w\}$ (thus $vw$ is an edge of $H$). If $u$ and $v$ are, in $H$, both adjacent to all vertices of $V(H) \setminus S$ (there are such, since $2n - 6 \geq 4$), then a realisation of $\pi$ in $H$ can be obtained similarly as in the proof of Theorem 4.4. Thus, we can assume there is some $x \in V(H) \setminus S$ such that all vertices of $V(H) \setminus S \setminus \{x\}$ are common neighbours of $u$ and $v$. Actually, again, if there is some part $S' \neq S$ of $\mathcal{R}$ not containing $x$, then a realisation can be obtained. So we get to assuming that $|\pi| = 2$, and that, besides $S$, the only part $S'$ of $\mathcal{R}$ contains $x$.

410

* If $|S'| = 1$, then $n = 4$, a case not covered by the statement.

411

412

413

* If $|S'| \geq 2$, then $S'$ contains a vertex $y$ adjacent to $x$ being a common neighbour of $u$ and $v$. Furthermore, $u$ and $v$ are both adjacent to all vertices of $S' \setminus \{x\}$. Then the two parts $\{u, x, y\}$ and $\{v, w\} \cup S' \setminus \{x, y\}$ form a realisation of $\pi$ in $H$.

414

415

416

417

418

419

420

421

422

It now remains to consider when $|S| = 2$, that is, when $S = \{u, v\}$. In this case, there are at most two vertices of $V(H) \setminus \{u, v\}$ that are not common neighbours of $u$ and $v$ in $H$. We can actually suppose that there exist exactly two such vertices $w$ and $x$ of $V(H) \setminus \{u, v\}$ that are not common neighbours, as, if there is none or only one such vertex, then we can proceed similarly as in the proof of Theorem 4.4. Likewise, if there is a part $S' \neq S$ of $\mathcal{R}$ that contains only common neighbours of $u$ and $v$ in $H$, then a realisation can also be deduced. So, besides $S$, we can last assume either there is only one part $S'$ (that is, $|\pi| = 2$, and $S'$ contains both $w$ and $x$), or there are exactly two parts $S_w$ and $S_x$ (that is, $|\pi| = 3$, and $S_w$ contains $w$ while $S_x$ contains $x$).

423

424

425

426

427

428

429

430

431

432

433

* Assume first $|\pi| = 2$. Thus, $\mathcal{R}$ contains a unique part $S' \neq S$, that contains both $w$ and $x$. If there is a spanning tree of $H[S']$ that contains a leaf $y$ different from $w$ and $x$, then recall that that leaf is adjacent to both $u$ and $v$ in $H$, and the two parts $\{u, y\}$ and $\{v\} \cup S' \setminus \{y\}$ then form a realisation of $\pi$ in $H$ (unless $S' = \{w, x, y\}$, in which case necessarily $wx$ is an edge, and we could instead consider the two parts $\{u, v, y\}$ and $\{w, x\}$). So we can now assume that any vertex of $S' \setminus \{w, x\}$ is a cut-vertex of any spanning tree of $H[S']$, which implies any spanning tree $T$ of $H[S']$ must be a path with end-vertices $w$ and $x$. In that case, a realisation of $\pi$ in $H$ is obtained upon considering parts $\{w, w'\}$ and $\{u, v\} \cup S' \setminus \{w, w'\}$, where $w'$ is the unique neighbour of $w$ in $T$. Note indeed that if this was not the case, then we would have $w' = x$, thus $|S'| = 2$ and $n = 4$, which peculiar case is not covered by the statement.
434

435

436

437

438

439

440

* Assume now $|\pi| = 3$. Thus, $\mathcal{R}$ contains exactly two parts $S_w$ and $S_x$ different from $S$, where $S_w$ and $S_x$ contain $w$ and $x$, respectively. Also, in $H$ vertices $u$ and $v$ are both adjacent to all vertices of $S_w \setminus \{w\}$ and $S_x \setminus \{x\}$. Here, assume, say, that $H[S_w]$ contains a spanning tree with a leaf $y$ different from $w$. Then, a realisation of $\pi$ in $H$ is obtained upon replacing, in $\mathcal{R}$, parts $S$ and $S_w$ with $\{u, y\}$ and $\{v\} \cup S_w \setminus \{y\}$. Now, if none of $H[S_w]$ and $H[S_x]$ admits such a spanning tree, then $|S_w| = |S_x| = 1$ and $n = 4$, which peculiar case is not covered by the statement.

441

We are thus done in all cases.

□

442

## 5. Conclusions

443

444

445

446

447

448

449

450

451

452

In this work, inspired by Bondy and Chvátal's influential Theorem 1.2, we have investigated closure results for connected partitions of graphs, in particular in the context of the AP property which has been regarded as a weakening of Hamiltonicity. Looking at Theorem 1.2, a natural first question (in view of Marczyk's Theorem 1.1) was whether $(n-2)$-closures are necessary and sufficient for the AP property. In Section 2, we proved that this is not true, because of several particular types of $n$-partitions. For such partitions, we proved, in particular throughout Section 3, that it is sufficient and necessary to consider $(n-1)$-closures. In last Section 4, we then considered other $n$-partitions, including the whole set of $n$-partitions (and thus the AP property), and proved that it is here sufficient to consider weaker closures (namely $(2n-c)$-closures for some $c$).

453

454

455

456

457

458

Let us mention that the fact that $(n-2)$-closures do not suffice for APness (Theorems 2.3 and 2.5) is not too surprising, given that Marczyk's Theorem 1.1 already had to exclude perfect matchings from the equation. Given all connections between the results involved, the fact that perfect matchings form an obstruction to APness and $(n-2)$-closures can thus be regarded as a counterpart. What is more surprising is that perfect matchings, in our case, are not the only obstruction, recall Theorem 2.5.

459

460

Given the results we came up with, we thus have no obvious objection again the fact that, perhaps, in general $(n-1)$-closures are necessary and sufficient.

461

**Question 5.1.** Is it true that any graph is AP if and only if its $(n-1)$-closure is?

462

463

464

465

466

467

468

469

470

471

472

473

474

If true, a notable consequence of Question 5.1 is that it would imply Marczyk's Theorem 1.1, just like how Bondy and Chvátal's Theorem 1.2 implies Ore's Theorem. A way to progress towards Question 5.1 could be to first generalise Theorems 4.3 to 4.5 to $(2n-c)$-closures for any fixed $c \ge 4$. However, as highlighted by the proofs of Theorems 4.3 to 4.5, proceeding this way is not quite obvious. In particular, in our arguments, it is important that we keep control over the structure of $H[S]$, which is less and less obvious as $c$ increases, but easy to do when $c$ is very small (as in the cases we considered). Also, the fact that $uv$ is an edge of $H'$ but not of $H$ is a very local property, which becomes less and less easy to exploit as the diameter of $H[S]$ increases (which might be the case when $c$ is large). Altogether, an annoying point is that $|S|$ being large implies $u$ and $v$ have lots of common neighbours in $V(H) \setminus S$ but the structure of $H[S]$ might get hard to handle, while $|S|$ being small implies the structure of $H[S]$ is easier to deal with but $u$ and $v$ have less common neighbours in $V(H) \setminus S$, which is a crucial point.

475

476

477

478

479

To summarise, while some of our arguments in the proofs of Theorems 4.3 to 4.5 could obviously be generalised to larger values of $c$, some others do not; thus, to go further, it would be crucial to come up with other arguments. For instance, it might be useful to exploit that if, for some $c$, the closure $\mathrm{clos}(G, 2n-c)$ is AP but $H[S]$ has a very faulty structure, then we could deduce other $n$-partitions showing that $\mathrm{clos}(G, 2n-c)$ is not AP.
One has to take into account also that if *c* is too large w.r.t. *n*, then we might fall into pathological cases, as better highlighted by Theorem 4.5. Note indeed that if we consider as *G* the disjoint union of two edges, then *n* = 4 and 2*n* − 6 = 2, while, for any two non-adjacent vertices *u* and *v* of *G* we have *d*<sub>*G*</sub>(*u*) + *d*<sub>*G*</sub>(*v*) = 2. Thus in that case clos(*G*, 2*n* − 6) is complete and thus AP, while *G* is obviously not AP (consider partitioning it following (1,3)). So the statement of Theorem 4.5 is actually best possible (w.r.t. *n*), and, as considering larger values of *c*, we must make sure to focus on large enough values of *n* only, or add additional constraints (such as focusing at least on connected graphs only).

Other directions of interest include other results of the type of Theorem 3.1, to establish
other results of the sort of Corollary 3.2, for other polynomial kernels of partitions. As a
more general perspective, we wonder whether it could be worth studying the APness of
graphs w.r.t. the traceability or the Hamiltonicity of some of their closures, and vice versa.

References

[1] D. Barth, O. Baudon, J. Puech. Decomposable trees: a polynomial algorithm for tripodes. *Discrete Applied Mathematics*, 119(3):205-216, 2002.

[2] D. Barth, H. Fournier. A degree bound on decomposable trees. *Discrete Mathematics*, 306(5):469-477, 2006.

[3] J. Bensmail. A $\sigma_3$ condition for arbitrarily partitionable graphs. *Discussiones Mathematicae Graph Theory*, 44(2):755-776, 2024.

[4] J. Bensmail. On three polynomial kernels of sequences for arbitrarily partitionable graphs. *Discrete Applied Mathematics*, 202:19–29, 2016.

[5] J. Bensmail. Toughness Properties of Arbitrarily Partitionable Graphs. Preprint, available online at https://hal.science/hal-04312057. 2023.

[6] J. Bensmail, B. Li. More Aspects of Arbitrarily Partitionable Graphs. *Discussiones Mathematicae Graph Theory*, 42(4):1237-1261, 2022.

[7] J.A. Bondy, V. Chvátal. A method in graph theory. *Discrete Mathematics*, 15(2):111–135, 1976.

[8] H. Broersma, D. Kratsch, G.J. Woeginger. Fully decomposable split graphs. *European Journal of Combinatorics*, 34(3):567-575, 2013.

[9] H. Broersma, Z. Ryjáček, I. Schiermeyer. Closure Concepts: A Survey. *Graphs and Combinatorics*, 16:17–48, 2000.

[10] C. Buchanan, B. Du Preez, K.E. Perry, P. Rombach. Toughness of recursively parti-
tionable graphs. *Theory and Applications of Graphs*, 10(2), Article 4, 2023.

[11] G.A. Dirac. Some theorems on abstract graphs. *Proceedings of the London Mathematical Society*, 2:69–81, 1952.

[12] M. Horňák, A. Marczyk, I. Schiermeyer, M. Woźniak. Dense arbitrarily vertex decomposable graphs. *Graphs and Combinatorics*, 28:807–821, 2012.

[13] M. Horňák, M. Woźniak. On arbitrarily vertex decomposable trees. *Discrete Mathematics*, 308(7):1268–1281, 2008.
[14] R. Kalinowski, M. Pilśniak, I. Schiermeyer, M. Woźniak. Dense arbitrarily partitionable graphs. *Discussiones Mathematicae Graph Theory*, 36:5–22, 2016.

[15] F. Liu, B. Wu, J. Meng. Arbitrarily partitionable {$2K_2, C_4$}-free graphs. *Discussiones Mathematicae Graph Theory*, 42:485–500, 2022.

[16] A. Marczyk. A note on arbitrarily vertex decomposable graphs. *Opuscula Mathematica*, 26(1):109–118, 2006.

[17] A. Marczyk. An Ore-type condition for arbitrarily vertex decomposable graphs. *Discrete Mathematics*, 309:3588–3594, 2009.

[18] O. Ore. Note on hamilton circuits. *American Mathematical Monthly*, 67:55, 1960.

[19] M.D. Plummer, A. Saito. Closure and factor-critical graphs. *Discrete Mathematics*, 215:171–179, 2000.

[20] R. Ravaux. Decomposing trees with large diameter. *Theoretical Computer Science*, 411:3068–3072, 2010.

[21] W.T. Tutte. The factorization of locally finite graphs. *Canadian Journal of Mathematics*, 2:44–49, 1950.