Julien Bensmail

Arbitrarily Edge-Partitionable Graphs

Keywords: arbitrarily partitionable graph, partition into connected graphs, line graph

published or not. The documents may come

Introduction

In this work, we deal with a variant of arbitrarily partitionable graphs, which are defined as follows. Let G be a graph with order n, and π = (λ 1 , . . . , λ p ) be an n-partition (i.e., λ 1 + ⋅ ⋅ ⋅ + λ p = n). A vertex-realisation (V 1 , . . . , V p ) of π in G is a partition of V (G) such that G[V i ] is a connected graph with order λ i for every i ∈ {1, . . . , p}. We say G is arbitrarily partitionable (AP for short) if every n-partition is vertex-realisable in G.

Graph partitions into connected subgraphs have been studied for long, recall e.g. the influential result proved independently by Győri [START_REF] Győri | On division of graphs to connected subgraphs[END_REF] and Lovász [START_REF] Lovász | A homology theory for spanning trees of a graph[END_REF] in the 1970s, stating that, for every k ≥ 1, every graph G with order n is k-connected if and only if all npartitions with size k are vertex-realisable in G (even under additional vertex-membership constraints). AP graphs, as such, have been introduced independently by Barth, Baudon, and Puech in [START_REF] Barth | Decomposable trees: a polynomial algorithm for tripodes[END_REF], and by Horňák and Woźniak in [START_REF] Horňák | On arbitrarily vertex decomposable trees[END_REF], following different motivations. Indeed, the former authors introduced AP graphs in the context of a practical network sharing problem, while the latter ones considered APness as a way to generalise to vertices other graph theoretical notions and objects usually defined for edges. More precisely, given a graph G with m edges, and any m-partition π = (λ 1 , . . . , λ p ), Horňák and Woźniak consider partitions (E 1 , . . . , E p ) of E(G) where each G[E i ] has size λ i and desired properties for every i ∈ {1, . . . , p}. In particular, they mention the peculiar case where each E i is required to induce an Eulerian graph (i.e., a graph having an Eulerian tour -traversing all edges exactly once), and, from here, they get to introduce AP graphs as a vertex counterpart of these notions under the requirement that each part induces a connected graph.

This leads us to wonder about a straight generalisation of AP graphs for edges, in the sense that we require to partition edges into arbitrarily many parts (with arbitrary cardinalities) each of which induces a connected graph. Following all notions behind AP graphs, this could be defined as follows. Let G be a graph with size m (i.e., with m edges), and π = (λ 1 , . . . , λ p ) be an m-partition. An edge-realisation (E 1 , . . . , E p ) of π in G is a partition of E(G) such that G[E i ] is a connected graph with size λ i for every i ∈ {1, . . . , p}. Now, we say G is arbitrarily edge-partitionable (AEP for short) if every m-partition is indeed edge-realisable in G. Somehow, AEPness can be perceived as a particular form of graph packing, with the subtlety that we aim at packing structures with different sizes, and, even among packed structures with the same size, the actual structures can be quite varying.

As a matter of fact, AEPness is not too distant from APness, as it is not too hard to see that a graph G is AEP if and only if its line graph1 L(G) is AP. Thus, one motivation for studying AEPness is that it stands as a way to investigate AP line graphs, a subclass of AP claw-free graphs, which, to the best of our knowledge, have not received any dedicated attention in literature to date. Depending on the graphs considered, throughout this work we will also run into situations where investigating the AEPness of a given graph G, due to the structure of G, is done more naturally in G itself rather than in L(G); in our opinion, this yields another reason why AEPness as such might be worth studying on its own. This work is organised as follows. We start off in Section 2 by studying how several known, fundamental aspects and behaviours of AP graphs adapt (or not) to AEP graphs. In particular, we raise observations and results regarding connectivity properties, connections with line graphs, perfect matchings, Hamiltonian paths, and edge and vertex minimality, among others. Already at this point, we get to observe significant similarities and discrepancies between APness and AEPness. In Section 3, we then focus a bit more on sufficient conditions for AEPness, expressed in terms of degree sums of independent vertices, adapting concerns introduced by Marczyk for AP graphs. Next, in Section 4, we focus on the AEPness of trees, showing, on the negative side, that deciding whether an mpartition is edge-realisable in a tree with size m is NP-complete, and, on the positive side, that deciding whether a subdivided claw is AEP can be done in polynomial time (thereby adapting a result from [START_REF] Barth | Decomposable trees: a polynomial algorithm for tripodes[END_REF]). As going along, we disseminate questions and problems which we think might be of interest for further work on the topic; some of these we summarise in Section 5, which serves as a more general conclusion to the current work.

Early remarks on AEPness, and connections with APness

In this section, we start by investigating how a few more or less obvious properties of AP graphs adapt (or not) to AEP graphs. Since we investigate properties of various and sometimes unrelated natures, for the sake of keeping the whole section legible we voluntarily split its content into a few (sometimes very short) dedicated subsections. Given the aspects we cover, this section can also be perceived as a short, non-exhaustive survey on AP graphs, which might thus be helpful to the reader unfamiliar with the field.

Connectedness

One of the very first, obvious properties of AP graphs, is that they are all connected. Indeed, note that any non-connected graph with order n admits no vertex-realisation of the trivial n-partition (n), and thus is not AP. Likewise, we have the following for AEPness: Observation 2.1. Every AEP graph has at most one connected component with edges.

Formal connection with line graphs

As mentioned in the introductory section, in our context edge-partitioning a graph is equivalent to vertex-partitioning its line graph. We make this statement a bit more formal, as this is an important point for our new notions.

Observation 2.2. The line graph of any connected graph is connected. Therefore, for every graph G with size m, any m-partition is edge-realisable in G if and only if it is vertex-realisable in L(G). Thus, G is AEP if and only if L(G) is AP.

Perfect matchings and paths of length 2

An important property of AP graphs is that they admit perfect matchings or quasiperfect matchings (i.e., sets of ⌊n/2⌋ pairwise disjoint edges, where n is the graph's order). Indeed, note that any vertex-realisation of (2, . . . , 2) (when n is even) or (2, . . . , 2, 1) (otherwise) forms a perfect matching or quasi-perfect matching, respectively. For this reason, AP graphs can be perceived as a stronger version of graphs admitting perfect matchings or quasi-perfect matchings. Another reason why these notions are important in the study of AP graphs, is that previous investigations on the topic have showcased that, in many cases, non-AP graphs tend to be not AP because they lack perfect matchings or quasi-perfect matchings (although this is not always true), see e.g. [START_REF] Bensmail | Toughness Properties of Arbitrarily Partitionable Graphs[END_REF].

In the context of AEP graphs, we can state the following:

Observation 2.3. Every edge-realisation of (2, . . . , 2) in any connected graph with even size forms an edge-partition into paths of length 2. Therefore, since every connected graph with even size admits an edge-partition into paths of length 2 (see e.g. [START_REF] Bensmail | Decomposing graphs into a constant number of locally irregular subgraphs[END_REF]), every connected graph with even size admits edge-realisations of (2, . . . , 2).

In particular, this implies that, when trying to build non-AEP graphs with some properties, there is no point trying to come up with graphs of even size with no edge-realisations of (2, . . . , 2), which showed up to be a viable strategy for this matter and AP graphs.

Eulerianity, traceability, and Hamiltonian paths

AP graphs have also been regarded as a weakening of traceable graphs (graphs admitting a Hamiltonian path, i.e., going through all vertices exactly once) and Hamiltonian graphs (graphs admitting a Hamiltonian cycle), since paths are obviously AP and thus every traceable graph is spanned by an AP graph and is thus AP (see the next subsection).

In our context, since we are partitioning edges, a natural analogue to Hamiltonian paths are Eulerian walks, which are walks traversing all edges exactly once, and Eulerian tours, which are tours going exactly once through every edge. One of the most famous results of graph theory is an old one by Euler, providing an exact characterisation of graphs admitting Eulerian walks and/or tours. Theorem 2.4 (Euler [START_REF] Euler | Solutio problematis ad geometriam situs pertinentis[END_REF]). A connected graph admits an Eulerian tour if and only if all of its vertices have even degree. Likewise, a connected graph admits an Eulerian walk if and only if at most two of its vertices have odd degree.

Clearly, there is a straight connection between Eulerian walks/tours and Hamiltonian cycles/paths in line graphs; namely: Observation 2.5. For any graph G, any Eulerian walk/tour in G corresponds to a Hamiltonian path/cycle in L(G). In particular, every graph admitting an Eulerian walk is AEP.

So, admitting an Eulerian walk is a sufficient condition for the line graph to admit a Hamiltonian path, but obviously this condition is not necessary. To see this is true, consider e.g. any star G with order at least 4: clearly, G does not satisfy Theorem 2.4, while L(G) is complete and thus traceable. However, if we consider, in G, what results from a Hamiltonian path of L(G), then we end up with the notions of edge-Hamiltonian walks (walks going through adjacent edges, traversing all edges exactly once), edge-Hamiltonian tours (tours going through adjacent edges, traversing all edges exactly once), edge-traceable graphs (graphs admitting edge-Hamiltonian walks), and edge-Hamiltonian graphs (graphs admitting edge-Hamiltonian tours), which have already been investigated in literature (in particular, while deciding whether a graph admits a Hamiltonian path is NP-complete [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF] and deciding whether a graph admits an Eulerian walk can be done in polynomial time by Theorem 2.4, deciding whether a graph admits an edge-Hamiltonian walk is NP-complete [START_REF] Bertossi | The edge hamiltonian path problem is NP-complete[END_REF]). These notions stand, for AEPness, as the full analogue to traceability: Observation 2.6. For any graph G, edge-Hamiltonian walks of G correspond exactly to Hamiltonian paths of L(G). Therefore, every graph is edge-traceable if and only if its line graph is traceable. Furthermore, every edge-traceable graph is AEP.

In some of the results to be established, we will employ the fact that edges comprised along any path can be edge-partitioned into connected subgraphs. Namely: Lemma 2.7. For every graph G with a path P = v 1 . . . v q such that G[V (P )] contains exactly m edges, and every m-partition π, there is an edge-realisation of π in G[V (P )].

Proof. Set H = G[V (P )]. Stated differently, note that H can just be regarded as a traceable graph with size m spanned by P . We prove that H is edge-traceable, implying the claim. By Observation 2.6, note that we could equivalently prove that L(H) is traceable. To facilitate some of the later proofs, we instead provide a sequence of successive edges of H forming an edge-Hamiltonian walk. Such a sequence is obtained e.g. as follows. Start with the edges incident to v 1 , ordered arbitrarily but so that v 1 v 2 is last. Then continue with edges (different from v 1 v 2 ) incident to v 2 , ordered arbitrarily but so that v 2 v 3 is last. Then proceed with edges (not incident to v 1 and v 2 ) incident to v 3 , ordered arbitrarily but so that v 3 v 4 is last. And go on like this for all consecutive v i 's. That is, whenever considering a new v i this way, we pursue with edges (not incident to any vertex in {v 1 , . . . , v i-1 }) incident to v i , ordered arbitrarily but so that v i v i+1 is last. When reaching v q , we get an ordering over all edges of H, which can be verified forms an edge-Hamiltonian walk.

Spanning subgraphs and edge-minimality

In the context of AP graphs, an important class of graphs is that of multipodes. Given any k ≥ 3, and k positive integers a 1 , . . . , a k ≥ 1, the multipode (or k-pode) P (a 1 , . . . , a k ) is essentially a subdivided star with center v of degree k such that, when removing v, we end up with k disjoint paths on a 1 , . . . , a k vertices, respectively. Said differently, P (a 1 , . . . , a k ) is obtained by considering k disjoint paths on a 1 + 1, . . . , a k + 1 vertices, then picking an end-vertex in each path, and last identifying the k picked vertices into a single one. Note that P (a 1 , . . . , a k ) has order 1 + a 1 + ⋅ ⋅ ⋅ + a k . In the special case where k = 3, we sometimes call P (a 1 , a 2 , a 3 ) a tripode, and denote it T (a 1 , a 2 , a 3 ) for convenience. The APness of tripodes has been investigated in one of the very first works on AP graphs [START_REF] Barth | Decomposable trees: a polynomial algorithm for tripodes[END_REF], and, as will be seen later on, this is for interests that go beyond the restricted scope of trees.

An important property of AP graphs is that APness is preserved upon adding edges. Put the other way round, any graph having a spanning AP subgraph is AP itself. It turns out that this property is unfortunately not shared by AEP graphs. We show that things are actually worse, in the sense that there exist graphs in which AEPness can repeatedly appear or disappear as we keep on adding edges. Theorem 2.8. There are AEP graphs which, for any k ≥ 0, can be added 3k + 1 or 3k + 3 edges while preserving AEPness, while 3k + 2 edges can be added so that AEPness is lost.

Proof. Consider any tripode G = T (2, 2, x) with x ≡ 0 mod 3, where we denote by u the unique vertex of degree 3, by a 1 a 2 u and b 1 b 2 u the two pendant paths of length 2 attached at u, and by c 1 . . . c x u the pendant path of length x. Note that G has size m = x+4 ≡ 1 mod 3.

To begin with, we note that G is AEP. Indeed, consider π, any m-partition.

• If 1 ∈ π, then pick {a 1 a 2 } as a part of size 1. By Lemma 2.7, note that G -a 1 is edge-traceable; thus, the rest of π can be edge-realised in G -a 1 .

• If 2 ∈ π, then pick {a 1 a 2 , a 2 u} as a part of size 2. Since G -{a 1 , a 2 } is a path, the rest of π can then be edge-realised in G -{a 1 , a 2 }.

• If λ ∈ π and λ ≥ 4, then start from S = {a 1 a 2 , a 2 u, b 1 b 2 , b 2 u} and add to S the λ-4 ≥ 0 first edges of (uc x , c x c x-1 , c x-1 c x-2 , . . . ). Clearly, G[S] is connected, and G -S is a path in which the rest of π can be edge-realised. Now, since m / ≡ 0 mod 3, it cannot be that π contains 3's only, so one of the cases above must apply, from which we deduce π is edge-realisable in G, and G is AEP.

We now consider adding edges to G, to reach another graph G ′ on the same vertex set. All edges we add join pairs of non-adjacent vertices in {c 1 , . . . , c x }. Precisely, assuming we need to add one more edge, we consider the smallest i ∈ {1, . . . , x -2} such that c i misses an incident edge going to a vertex c j with j ∈ {i + 1, . . . , x}, and, among all such c j 's, we consider the one with the smallest index j. That is, we add the edge c i c j with j > i where i is as small as possible, and, for this value of i, we also have j as small as possible.

We claim that, after adding any number of such edges in G, the resulting graph G ′ with size m ′ > m is AEP if m ′ / ≡ 0 mod 3, and not AEP otherwise.

• The latter claim is easy to see. Indeed, if m ′ ≡ 0 mod 3, then π = (3, . . . , 3) is an m ′ -partition, and it can be noticed that, in any edge-realisation of π in G ′ , either, say, {a 1 a 2 , a 2 u, uc x } or {a 1 a 2 , a 2 u, ub 2 } must be a part S, and G ′ -S contains a connected component (that containing b 1 ) on only one or two edges, which makes it impossible for the rest of the edge-realisation to hold.

• We now focus on proving the former claim, which follows mainly from the fact that the way we have added edges in G to form G ′ guarantees there is an edge-Hamiltonian walk P with ends c 1 and u of G ′ [{c 1 , . . . , c x , u}] (to see this is true, consider the ordering of the edges starting from those c i c 1 with i > 1 incident to c 1 finishing with c 1 c 2 , then continuing with those c i c 2 with i > 2 incident to c 2 finishing with c 2 c 3 , and so on). Assuming now m ′ / ≡ 0 mod 3, and π is any m ′ -partition:

-If 1 ∈ π, 2 ∈ π, or λ ∈ π and λ ≥ 4, then arguments we used earlier for G, and the fact that P exists, imply an edge-realisation of π in G ′ can be deduced.

-If 3 ∈ π, then, since m ′ / ≡ 0 mod 3, there must be a value different from 3 in π, from which previous arguments can be applied to deduce an edge-realisation. Thus, π can always be edge-realised in G ′ , and G ′ is AEP.

This concludes the proof.

The fact that AEPness is not preserved upon adding edges makes uncertain the study of another interesting aspect of AP graphs, being the concept of AP minimality. In the very first studies on AP graphs, it was believed that, perhaps, every AP graph should be spanned by an AP tree. This was refuted first by Ravaux in [START_REF] Ravaux | Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques[END_REF], through exhibiting a non-tree AP graph with order 20 that is not spanned by any AP tree. This resulted in the study of minimal AP graphs, defined as those graphs in which removing any edge breaks APness. The main conjecture here, due to Ravaux [START_REF] Ravaux | Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques[END_REF], is that minimal AP graphs should have linear size. This was later investigated in further works, see [START_REF] Baudon | On minimal arbitrarily partitionable graphs[END_REF][START_REF] Bensmail | Some Properties of Minimal Arbitrarily Partitionable Graphs[END_REF].

Due to the fact that removing edges from an AEP graph results in a smaller graph that might have or not have the AEP property, it is not clear how one should define a notion of minimality in the context of AEPness. Perhaps one way to go could be to define a minimal AEP graph as an AEP graph which is not spanned by an AEP graph on fewer edges, or, in other words, which, when removed any set of edges, is not AEP any more. As is, this definition is not viable either, as it can be noted that an edgeless graph is, by definition, AEP, and thus, given any (AEP) graph, it would suffice to remove all edges to get a smaller AEP graph. To overcome this issue, one possibility is to add a connectivity condition. Namely, in what follows, we define a minimal AEP graph as a connected graph that is not spanned by a smaller connected AEP graph. With this definition of minimal AEP graphs, we can reuse some of the ideas from Theorem 2.8, combined with Observation 2.1, to prove that non-tree minimal AEP graphs2 do exist: Theorem 2.9. There exist arbitrarily large non-tree minimal AEP graphs.

Proof. Consider e.g. the following construction. Start from a tripode T (2, 2, a) for any a ≥ 3 with a ≡ 0 mod 3. Denoting u the end-vertex of the pendant path of order a, then attach a triangle uvwu to u, where v and w are two new vertices. Let G denote the resulting non-tree graph on m = a + 7 edges; thus, we have m ≡ 1 mod 3.

First off, it can be checked that G is AEP, through, essentially, the same arguments as in the first part of the proof of Theorem 2.8 (in particular, the fact that m / ≡ 0 mod 3 implies we do not have to consider edge-realising (3, . . . , 3)). Now, regarding the minimality of G, note first that removing any at least two edges of G makes it disconnected. So, to attain a connected spanning subgraph contradicting the minimality of G, we must remove only one edge, and since all edges of G not part of the triangle uvwu are cut-edges, still by Observation 2.1 we must remove only one edge of uvwu. Regardless of the edge we remove, we get a graph G ′ of size m ′ ≡ 0 mod 3, which can be checked has no edge-realisation of the m ′ -partition (3, . . . , 3). Thus G ′ cannot be AEP, and G is minimal AEP.

Vertex-minimality

APness is not that common of a property, and this is attested by the fact that very small connected graphs are not AP. Namely, the smallest connected graph that is not AP is T (1, 1, 1), and more generally it is easy to construct larger connected graphs that are not AP, in particular because, as explained earlier, they admit no perfect matchings.

As seen earlier through Observation 2.3, partition (2, . . . , 2) cannot prevent AEPness, and, as a result, we cannot just use similar arguments to show that there exist very small connected graphs that are not AEP. A point also, is that small connected graphs tend to have very small diameter, implying they tend to be edge-traceable, and thus AEP by

(a) (b) (c) (d) (e)
Figure 1: The five connected graphs on 7 and 8 vertices that are not edge-traceable.

Observation 2.6. From these arguments, it is not too complicated to check that the smallest (order-wise) non-AEP graph is the tripode T (2, 2, 2) (because of the 6-partition (3, 3)), depicted in Figure 1(a), which has order 7 and is actually the unique non-AEP graph on 7 vertices. Out of all connected graphs with order 8, only four are not edge-traceable, namely those depicted in Figures 1(b)-(e) 3 . It can be checked however that these four graphs are actually AEP. Thus, T (2, 2, 2) apart, the smallest connected graphs that are not AEP have order at least 9 (P (2, 2, 2, 2) being an obvious next one).

APness versus AEPness

We now observe that there is no equivalence between APness and AEPness, in that, connections with line graphs apart, APness does not imply AEPness, and vice versa.

Theorem 2.10. There are arbitrarily large connected AEP graphs that are not AP.

Proof. Just consider e.g. any star G on n ≥ 4 vertices. Indeed, on the one hand, G is edge-Hamiltonian (as any sequence of edges forms an edge-Hamiltonian tour), and thus AEP by Observation 2.6. On the other hand, G has no two disjoint edges, implying the n-partition (2, 2, n -4) (where n -4 ≥ 0) is not vertex-realisable in G , and G is not AP.

Theorem 2.11. There are arbitrarily large connected AP graphs that are not AEP.

Proof. Consider e.g. the following ideas. In [START_REF] Cichasz | Arbitrarily vertex decomposable caterpillars with four or five leaves[END_REF], the authors proved, following our terminology, that any tripode

T (2, a, b) is AP if and only if gcd(a+1, b+1) ≤ 2, gcd(a+2, b+1) ≤ 2, gcd(a + 1, b + 2) ≤ 2, gcd(a + 2, b + 2) ≤ 3,
and there are no x, y ≥ 0 such that a + b + 3 = x(a + 1) + y(a + 2). In particular, according to this characterisation, for every a ≥ 8 with a ≡ 2 mod 3, the tripode G = T (2, a, a -2) is AP, and |E(G)| ≡ 1 mod 3. Quite similarly as in the proof of Theorem 2.8, now consider G ′ , the graph obtained from G by adding two more edges along the pendant path containing a -2 vertices. As a result, note that G ′ contains a cut-vertex, to which are attached two pendant paths of order 2 modulo 3. Also, |E(G ′ )| is a multiple 3. Then, again, note that G ′ admits no edge-realisation of (3, . . . , 3), and thus G ′ is not AEP (while it is spanned by G, and is thus AP).

Toughness properties

We here consider interesting structural properties of AP graphs, established following some of the first investigations on AP trees. Namely, an important result of the field, due to Barth and Fournier [START_REF] Barth | A degree bound on decomposable trees[END_REF], asserts that AP trees have maximum degree at most 4, and that any vertex of degree 4 in an AP tree must be adjacent to a leaf. This result generalises to a more general property, being that removing any cut-vertex from an AP graph can result in at most four connected components, one of which must have order 1. This was later considered more widely by Baudon, Foucaud, Przybyło, and Woźniak [START_REF] Baudon | On the structure of arbitrarily partitionable graphs with given connectivity[END_REF], who proved that the removal of any cut-set of size k ≥ 2 from an AP graph might result in arbitrarily many connected components, but their orders must grow in an exponential way.

In the context of AEP graphs, exploiting some of our previous tools and ideas, we prove that there is no such phenomenon. Namely, not only removing any cut-set from an AEP graph can result into arbitrarily many connected components, but also their orders can essentially be anything. This is a notable consequence of the following result: Theorem 2.12. For every s ≥ 1 and every k ≥ 2 positive integers n 1 , . . . , n k ≥ 1, there is a connected AEP graph G with a cut-set S of size s such that G -S has k connected components of order n 1 , . . . , n k , respectively. Proof. Assume p ≥ 0 of the n i 's are equal to 1, and q ≥ 0 of the n i 's (which we denote by n ′ 1 , . . . , n ′ q in what follows) are greater than 1. Then, k = p + q and p + q ≥ 2. Now let G be the graph obtained as follows:

• start from a clique S = {v 1 , . . . , v s } on s vertices;

• if p ≥ 1, then, for every i ∈ {1, . . . , p}, add an isolated vertex u i ;

• if q ≥ 1, then, for every i ∈ {1, . . . , q}, add an isolated path P i of order n ′ i with end-vertices w i and x i ;

• for every i ∈ {1, . . . , s}, add edges joining v i and all u i 's, add edges joining v i and all w i 's, and add edges joining v i and all x i 's.

Note that S is a cut-set of size s of G, and that G -S contains exactly p connected components of order 1 (the u i 's), and q connected components of order n ′ 1 , . . . , n ′ q (the P i 's). Thus G has the desired cut-set properties; to be done, it thus remains, now, to show that G is AEP, which we do by showing that G is actually edge-traceable, so that we get the desired conclusion by Observation 2.6.

To see that G indeed admits an edge-Hamiltonian walk, consider e.g. any following sequence of edges. We consider the v i 's one after another, following their indexes, starting with v 1 . We first consider (in any order) all edges incident to v 1 going to the u i 's, if any; then, if q ≥ 1, for every i ∈ {1, . . . , q} in turn, we consider v 1 w i , then all edges of P i as they are traversed when going from w i to x i in P i , and finish with x i v 1 back to v 1 ; last, we consider all edges incident to v 1 going to other v i 's in any order, except that v 1 v 2 is considered last in the ordering. Note that, thus far, this covers all edges incident to v 1 as well as all edges of the P i 's, in a path way (w.r.t. L(G)). We then continue the sequence around v 2 , taking into account that v 1 v 2 and the edges of the P i 's have already been included to the ordering. We start by considering (in any order) edges incident to v 2 going to u i 's, w i 's, and x i 's, and last consider (in any order) edges going to v i 's with larger index, so that v 2 v 3 is considered last. We then continue on this way until v s is reached. Altogether, it can be checked that any so-obtained resulting sequence of edges forms an edge-Hamiltonian walk of G, as desired. Thus G is AEP and the result holds.

Note that Theorem 2.12, via the same construction, could be generalised to the sizes of the connected components resulting from the deletion of a cut-set in an AEP graph. Namely, the same construction can be employed to prove that, for every s ≥ 1 and every k ≥ 2 positive integers m 1 , . . . , m k ≥ 0, there is an AEP graph G with a cut-set S of size s such that G -S has k connected components of size m 1 , . . . , m k , respectively.

Sufficient conditions for AEPness

An interesting line of research when it comes to AP graphs, is the weakening, to APness, of known sufficient conditions for traceability and Hamiltonicity. As mentioned earlier, AP graphs can be perceived as a weaker form of traceable graphs, and, as such, one can consider pretty much any notion of literature on traceability and wonder whether it adapts to APness. Such concerns have been considered first by Marczyk in [START_REF] Marczyk | A note on arbitrarily vertex decomposable graphs[END_REF], and later in other works [START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF][START_REF] Horňák | Dense arbitrarily vertex decomposable graphs[END_REF][START_REF] Kalinowski | Dense arbitrarily partitionable graphs[END_REF][START_REF] Marczyk | An Ore-type condition for arbitrarily vertex decomposable graphs[END_REF], sometimes for notions different from the following ones we develop.

For a graph G, we denote by σ 2 (G) the largest value of d(u) + d(v) over all pairs of non-adjacent vertices u and v. By a well-known result of Ore [START_REF] Ore | Note on hamilton circuits[END_REF], any connected graph G with order n is Hamiltonian provided σ 2 (G) ≥ n, and traceable provided σ 2 (G) ≥ n -1.

In [START_REF] Marczyk | A note on arbitrarily vertex decomposable graphs[END_REF], Marczyk proved that having σ 2 (G) ≥ n -2 guarantees APness, provided G has a perfect matching or quasi-perfect matching. This result was later extended by Marczyk in [START_REF] Marczyk | An Ore-type condition for arbitrarily vertex decomposable graphs[END_REF], in which he proved the bound can even be decreased down to n -3, provided (still under the (quasi-) perfect matching condition) G is not one of two exceptional graphs; and by Horňák, Marczyk, Schiermeyer, and Woźniak in [START_REF] Horňák | Dense arbitrarily vertex decomposable graphs[END_REF], in which they proved (still under the (quasi-) perfect matching condition) that the bound can be decreased even lower down to n -5, provided n ≥ 20 so that G cannot be part of a certain list of additional exceptions.

As mentioned earlier through Observation 2.3, we do not have an equivalent to perfect matchings and quasi-perfect matchings in the context of AEP graphs, which makes it easier for graphs to be AEP. As an illustration, below we provide a Marczyk-like result for AEPness requiring no conditions other than being connected. Before that, we need a few results, starting with a connection between paths of a graph and of its line graph. Proof. To see this is true, it suffices to consider, in L(G), what corresponds to the following sequence of edges of G. Start with the edges incident to v 1 (including those going to a vertex not in P ) in any order, but finishing with v 1 v 2 . Next consider the edges incident to v 2 (including those not going to P ) that have not been considered earlier in the process (thus omitting v 1 v 2 ), in any order, but finishing with v 2 v 3 . And so on. Whenever considering a new vertex v i of P , next consider the edges incident to v i (including those going to a vertex not in P ) that have not been considered earlier in the process (i.e., of the form v j v i with j < i), in any order, but finishing with v i v i+1 . It can be checked that this sequence yields, in L(G), a path on m -α vertices.

We now introduce a useful result of Ravaux on the vertex-realisability of partitions in graphs with large diameter, and derive an obvious analogue in our edge context. For a partition π, we denote by sp(π) the spectrum of π, being the set of distinct values (thus with no duplicates) appearing in π. Theorem 3.2 (Ravaux [START_REF] Ravaux | Decomposing trees with large diameter[END_REF]). If G is a connected graph of order n with a path of length n -α, then every n-partition π with |sp(π)| ≥ α is vertex-realisable in G. We also recall the following famous result of Pósa, on graphs with large value of σ 2 .

Theorem 3.4 (Pósa [START_REF] Pósa | A theorem concerning Hamiltonian lines[END_REF]). Let G be a connected graph of order n ≥ 3 with σ 2 (G) ≥ α. If α < n, then G contains a path of length α. Otherwise, G is Hamiltonian.

We are now ready to prove our two main results in this section.

Theorem 3.5. If G is a connected graph of order n with σ 2 (G) ≥ n -2, then G is AEP.
Proof. By Theorem 3.4, we get that G has a path P of order at least n -1. Regardless of whether P goes through n -1 or n vertices, there are no edges of G not incident to at least one vertex of P . Thus, by Lemma 2.7, we get that G is edge-traceable, and thus AEP.

Theorem 3.6. If G is a connected graph of order n with σ 2 (G) ≥ n -3, then G is AEP.
Proof. By the same arguments as in the proof of Theorem 3.5, we have that G has a path P of order at least n -2. Actually, if P has order at least n -1, then G is edge-traceable and thus AEP. Hence, we can narrow our attention down to the case where P = v 1 . . . v n-2 . Let us denote by x and y the two vertices of V (G) ∖ V (P ). As in the previous proof, we can assume that xy is an edge, as otherwise all edges of G would be incident to at least one vertex of P , implying G is edge-traceable, and thus AEP, by Lemma 2.7.

Let π be an m-partition, where |E(G)| = m. Our goal is to show that π is edge-realisable in G. By Corollary 3.3, we have that π is edge-realisable in G whenever |sp(π)| ≥ 2. Thus, we can last assume π = (λ, . . . , λ) for some λ ≥ 2. Actually, we can even assume λ ≥ 3, because of Observation 2. [START_REF] Barth | A degree bound on decomposable trees[END_REF]. In what follows, we say any edge v i v j joining two vertices of P with i < j is a forward edge from v i 's point of view, and a backward edge from v j 's point of view. We say v i v j is a chord if j > i + 1, that is, if v i v j is not an edge of P .

First, we claim that, say, x must have at least one neighbour on P . Indeed, since P is a longest path of G, note that v 1 cannot be adjacent to x. Likewise, v 1 cannot be adjacent to v n-2 (as otherwise the v i 's would actually form a cycle with at least one incident edge going to x or y by connectedness of G, and we could contradict the maximality of P ). For the same reason, and because xy is an edge, it cannot be also that v 1 v n-3 is an edge. Thus, d(v 1 ) ≤ n -5, and, so that d(v 1 ) + d(x) ≥ σ 2 (G) ≥ n -3, we must have d(x) ≥ 2, implying, since xy is an edge, that x must be adjacent to at least one vertex of P .

Let thus v α be any neighbour of x in P . First off, if v α is also a neighbour of y, then G is actually edge-traceable (to see this is true, consider e.g. any sequence of edges obtained from P in Lemma 2.7, make sure v α x and v α y are consecutive in that sequence, and modify the sequence by adding xy in-between v α x and v α y). Thus, from here on we can assume v α is a neighbour of x but not a neighbour of y.

We now consider the following process to try to build an edge-realisation of π in G. Essentially, we just add edges to parts of size λ following the sequence of edges provided by the proof of Lemma 2.7 for P . More formally, we start from vertex v 1 , and we split as many forward edges incident to v 1 different from v 1 v 2 as possible into parts of size λ, while the remaining at most λ forward edges incident to v 1 (including v 1 v 2 ) are added to a last part of size at most λ. We then consider v 2 , and proceed the same way, taking into account that, after dealing with v 1 , if v 1 v 2 was added to a part S of size less than λ, then the first at most λ -|S| forward edges incident to v 2 are added to S, before resuming with parts of size λ (unless there are not enough forward edges incident to v 2 , in which case the partial part becomes a bigger partial part which is treated first upon considering v 3 ). And so on. Note that if we lead the process from start from finish with edges incident to P only, then this results almost in an edge-realisation of π in G, as only xy gets not added to a part (thus the very last part constructed, containing v n-3 v n-2 has size λ -1).

During this process, if, when starting treating v α , the current part (which might be partial, due to how many edges have been considered up to this point) needs at least two edges more, then we can start by adding v α x and xy to it, before resuming the process from v α , to eventually get an edge-realisation of π in G. So we can assume that, when reaching v α , we are currently dealing with a partial part S of size exactly λ -1. If there is a forward chord v α v i (thus i > α+1), then we can just add v α v i to S to achieve a complete part of size λ, and then resume the process (omitting v α v i ) creating a new part around v α , starting with adding v α x and xy to it (which is possible since λ ≥ 3), and resuming the process, so that eventually we are done. If this is not possible, then, if we set X = {v α+2 , . . . , v n-2 }, then v α has no neighbour in X. Likewise, note that if we run the same process but along the ordering (v n-2 , . . . , v 1 ) (and reversing the notions of forward and backward edges), then we deduce (as otherwise we would be done) that, for Y = {v 1 , . . . , v α-2 }, vertex v α has no neighbour in Y . Now, since y is not adjacent to v α , this means d(v α ) = 3, and, because v α and y are not adjacent, then d(v α ) + d(y) ≥ σ 2 (G) ≥ n -3 and thus d(y) ≥ n, and d P (y) ≥ n -1 since xy is an edge, which is impossible since |V (P )| = n -2. Thus, some of the previous arguments must apply, yielding an edge-realisation of π in G.

Note that improving previous Theorem 3.6 to value n -4 might require some more efforts, as, going through the exact same arguments, we would deduce that there might be up to three vertices not in P , and these three vertices can be joined by as many as three edges, a situation where Corollary 3.3 implies that π can be assumed to have spectrum of size at most 3, which is a far less constrained assumption on the spectrum's size.

The fact that AEPness is quite related to Eulerianity also leads to natural interesting questions. For instance, recalling Theorem 2.4, Observation 2.5, and the fact that the number of vertices of odd degree in any graph is always even, one could legitimately wonder whether graphs with at most four vertices of odd degree are always AEP. Unfortunately, such a statement is not true, as the k-pode G = P (2, . . . , 2) for any odd k ≥ 3 admits no edge-realisation of the m-partition (3, 3, m -6), where m = 2k is the size of G. Note that G has k + 1 ≥ 4 vertices of odd degree, and, thus, indeed, G is not AEP.

AEPness of trees

In this section, we investigate AEPness in trees, which, as seen earlier, in this class of graphs can be rather different from APness (recall the case of stars mentioned in the proof of Theorem 2.10). More precisely, we provide two main results. On the negative side, we prove that deciding whether a given m-partition is edge-realisable in a tree with size m is NP-complete, which matches a similar result for the vertex case [START_REF] Barth | A degree bound on decomposable trees[END_REF]. On the positive side, we then prove that deciding whether a given tripode is AEP can be determined in polynomial time, which, again, matches a similar result for the vertex case [START_REF] Barth | Decomposable trees: a polynomial algorithm for tripodes[END_REF]. In both cases, although we provide a result that is close to one in the vertex case, it is worth mentioning that the very properties of the edge context make our proofs employ dedicated, novel arguments.

Negative result

The main problem we are interested in here, is thus the following:

Edge-Realisation

Instance: A graph G of size m, and an m-partition π. Question: Is π edge-realisable in G?

The vertex version of Edge-Realisation, Vertex-Realisation, is well known to be NP-complete, as first proved by Dyer and Frieze [START_REF] Dyer | On the complexity of partitioning graphs into connected subgraphs[END_REF]; more precisely, they even proved that deciding whether partition (3, . . . , 3) is vertex-realisable in a given graph is NP-complete. In [START_REF] Barth | A degree bound on decomposable trees[END_REF], Barth and Fournier proved that Vertex-Realisation remains NP-complete when restricted to trees. In later works [START_REF] Bensmail | On the complexity of partitioning a graph into a few connected subgraphs[END_REF][START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF][START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF][START_REF] Broersma | Fully decomposable split graphs[END_REF], Vertex-Realisation was proved to remain NP-complete even under various restrictions on the partition (such as being of any fixed cardinality at least 2) or on the graph (such a being a multipode, a split graph, a series-parallel graph, a graph of any fixed connectivity, etc.). In [START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF], the authors proved that Vertex-Realisation is actually NP-complete when restricted to line graphs, which implies our problem Edge-Realisation is also NP-complete; however, the NP-hardness proof there provides reduced graphs that are line graphs of graphs that are not trees. For this reason, we believe our main result in the current section, upcoming Theorem 4.2, stating that Edge-Realisation remains NP-complete in trees, remains of interest.

Before getting to Theorem 4.2, we first introduce the problem we will build our reduction from, 3-Partition, which is well known to be NP-complete, see [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF].

3-Partition

Instance: A set E = {e 1 , . . . , e 3k } of size 3k, a B ∈ N * , and an s ∶ E → N * such that:

• B 4 < s(e) < B
2 for every e ∈ E, and • ∑ e∈E s(e) = kB.

Question: Can E be partitioned into k parts E 1 , . . . , E k with ∑ e∈E i s(e) = B for all i?

In our upcoming proof, we will need to restrict 3-Partition to particular instances, which will be possible according to the following previous result: Observation 4.1 (Bensmail,Li [9]). Let <E, B, s> be an instance of 3-Partition. Then, for any α ≥ 1, the instance <E, B ′ , s ′ > where B ′ = αB, and s ′ (e) = αs(e) for e ∈ E, is equivalent to <E, B, s>. Besides, we have ∑ e∈E s ′ (e) = kB ′ , and B ′ 4 < s ′ (e) < B ′ 2 for e ∈ E.

We are now ready to prove our main result.

Theorem 4.2. Edge-Realisation is NP-complete, even when restricted to trees.

Proof. The problem is clearly in NP, so we focus on proving its NP-hardness. This is done by reduction from the 3-Partition problem. Namely, from an instance <E, B, s> of 3-Partition, we build, in polynomial time, a tree G with size some m and an m-partition π such that <E, B, s> is positive if and only if π is edge-realisable in G.

We assume the elements of E are sorted in increasing order w.r.t. s, that is, s(e 1 ) ≤ ⋅ ⋅ ⋅ ≤ s(e 3k ). Also, by Observation 4.1, free to multiply all s(e i )'s and B by 4, we can further assume for free that all s(e i )'s are even, and that B 2 is also even. We obtain G as follows. Start from a single vertex v. Now, to v, attach k pendant paths B 1 , . . . , B k with length B + 1 (thus each containing B + 1 vertices different from v). Next, attach k leaves u 1 , . . . , u k to v, and, last, for every i ∈ {1, . . . , k}, attach 3kB pendant paths Q i,1 , . . . , Q i,3kB with length s(e 1 ) -1 to u i (thus each containing s(e 1 ) -1 vertices different from u i ). Note that |E(G)| = m = k(B + 1) + k + k(3kB(s(e 1 ) -1)). Now, setting a = 3kB(s(e 1 )-1)+2, the m-partition we consider is π = (s(e 1 ), . . . , s(e 3k ), a, . . . , a) containing k occurrences of a. It can be checked π is an m-partition. Clearly, G and π are both obtained in polynomial time, and it is easy to check that G is a tree, as desired.

For every i ∈ {1, . . . , k}, we denote by F i the subgraph of G containing vu i and all Q i,j 's (that is, the "branch" attached to v containing vu i ). To see now why the desired equivalence between <E, B, s> and <G, π> holds, it is crucial to highlight the following: Claim 4.3. In every edge-realisation R of π in G, every part of cardinality a:

• contains vu i for some i ∈ {1, . . . , k};

• contains all edges of F i ;

• contains exactly one edge of the B j 's incident to v.

Proof of the claim. First off, it can be observed that there cannot be an edge vu i belonging to a part S of R with cardinality different from a. Indeed, if this was the case, then, since a = 3kB(s(e 1 )-1)+2 > 3kB(s(e 1 )-1)+1 = |E(F i )|, no single part of R could cover all other edges of F i , and, thus, the 3kB(s(e 1 )-1)+1 edges of F i would have to be covered by parts of R cardinality s(e 1 ), . . . , s(e 3k ), which is impossible since s(e 1 ) + ⋅ ⋅ ⋅ + s(e 3k ) = kB < |E(F i )|.

We claim also that if some vu i belongs to a part S of cardinality a, then, actually, S has to contain all edges of F i . Indeed, if this was not the case, then this would mean some part S ′ ≠ S of R would have to contain edges of F i -vu i . For similar reasons as earlier, the cardinality of S ′ would have to lie in {s(e 1 ), . . . , s(e 3k )}. Assuming S ′ contained edges of, say, Q i,1 , then, since |S ′ | ≥ s(e 1 ) and Q i,1 contains s(e 1 ) -1 edges only, note that S ′ would actually have to contain all edges of Q i,1 , at least one edge of, say, Q i,2 , and actually all edges of Q i,2 , implying |S ′ | ≥ 2(s(e 1 ) -1). We know however that B 4 < s(e 1 ) ≤ s(e k ) < B 2 ; if we had s(e k ) ≥ 2(s(e 1 ) -1), then we would deduce that s(e k ) > B 2 -2, while s(e k ) < B 2 , which, since s(e k ) and B 2 are both even, implies actually s(e k ) < B 2 -1. This is a contradiction. Thus, S must indeed contain all edges of F i . To finish off the proof of the claim, consider a part S of cardinality a of R containing all edges of some F i . Note that the last edge (besides those of F i ; there is only one such) of S must be incident to v. If S contains some vu j for j ≠ i, then, by previous arguments, we get a contradiction to the fact that all edges of F j must be covered by a single part of cardinality a of R. Thus, the last edge of S is an edge incident to v going to some B j . ◇ Thus, by Claim 4.3, in any edge-realisation R of π in G, the edges of all F i 's, as well as the k edges incident to v going to the B i 's, must be covered exactly by the k parts of cardinality a. What remains of R in the rest of the graph is then an edge-realisation of (s(e 1 ), . . . , s(e 3k )) in a forest of m paths of length B, and from this we can easily deduce a solution to 3-Partition. Likewise, we can easily turn a solution of 3-Partition into a realisation of (s(e 1 ), . . . , s(e 3k )) in these k paths of length B, and cover the remaining edges of G by parts of cardinality a (as described above), to altogether get an edge-realisation of π in G. Thus, the two instances are indeed equivalent, and the claim is proved.

Positive result

In this section, we prove that, although determining whether a given m-partition is edge-realisable in a tree G with size m is NP-complete (Theorem 4.2), the same problem is polynomial-time solvable when restricted to tripodes. This meets a similar result for the vertex case in one of the first works on the topic [START_REF] Barth | Decomposable trees: a polynomial algorithm for tripodes[END_REF], which result was later reproved and generalised by several authors [START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF][START_REF] Ravaux | Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques[END_REF], through different approaches and arguments.

Note that, for a given k-pode G with k ≥ 3, its line graph L(G) is essentially obtained from a complete graph of order k by attaching a (possibly empty) pendant path to each vertex. Thus, although L(G) is very close to a k-pode itself (essentially, we get back to G when contracting the clique of size k to a single vertex), we cannot infer right away that determining the AEPness of multipodes can be done exactly the same way their APness is determined. The close proximity between the structure of a tripode and the structure of the line graph of a tripode makes it possible, however, to adapt realisation arguments from earlier works ( [START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF][START_REF] Ravaux | Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques[END_REF], to be precise), which we do below.

Namely, our main result below stands mainly as an edge version of results from [START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF][START_REF] Ravaux | Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques[END_REF], stating that the APness of a tripode of order n relies solely of the vertex-realisability of all n-partitions with very small spectrum. We start off by proving a crucial piece first. Proof. We assume throughout that G is a tripode T (a, b, c) with size m = a + b + c, for some a, b, c ≥ 1. We denote by u the unique vertex of degree 3 of G, and by a 1 , . . . , a a , b 1 , . . . , b b , and c 1 , . . . , c c the vertices of the three branches A, B, C, respectively, where a 1 , b 1 , and c 1 are all adjacent to u. In the argumentation below, we regard the edges ua 1 , ub 1 , and uc 1 as being part of A, B, and C, respectively.

Let K denote the set of all m-partitions π with |sp(π)| ≤ 7. First, if G is AEP, then all m-partitions, including those of K, are edge-realisable in G. Thus, to prove the claim, it suffices to focus on proving the second direction. That is, we need to prove that if G is not AEP, then there is an m-partition of K that is not edge-realisable in G. Or, the other way round, that if every m-partition of K is edge-realisable in G, then, for any m-partition not in K, we can deduce an edge-realisation in G as well.

Let π be an m-partition not in K; this means |sp(π)| ≥ 8. Our goal is to build, from π, a sequence π = π 0 , π 1 , . . . , π r of m-partitions obtained consecutively from π, such that |sp(π 1 )|, . . . , |sp(π r-1 )| ≥ 8 and |sp(π r )| ≤ 7, such that, for any i ∈ {1, . . . , r}, an edgerealisation of π i in G can be turned into one of π i-1 . The way these π i 's are obtained, is based on relationships fulfilled by a set of four of their elements with the same parity. More precisely, for any i ∈ {0, . . . , r -1}, focus on any such m-partition π i with |sp(π i )| ≥ 8. Then sp(π i ) = {λ q 1 , . . . , λ qs } with s = |sp(π i )|, and, since s ≥ 8, there must be, in {λ q 2 , . . . , λ qs }, at least four elements λ p 1 , λ p 2 , λ p 3 , λ p 4 of sp(π i ) with the same parity (where λ p 1 > λ p 2 > λ p 3 > λ p 4 ), that are not the largest element of sp(π i ) (below, we denote by λ p = λ q 1 this largest element). To obtain π i+1 , we essentially consider two main cases:

• There is some i ∈ {1, 2} such that λ p i -λ p i+1 ≥ λ p i+1 -λ p i+2 . -If this is true for i = 1, then we set λ m = λp 2 -λp 3 2
, and replace, in π i , one occurrence of λ p 2 and one occurrence of λ p 3 with two of λ m , to get π i+1 .

-Otherwise, if this is true for i = 2, then we set λ m = λp 3 -λp [START_REF] Baudon | On minimal arbitrarily partitionable graphs[END_REF] 2

, and replace, in π i , one occurrence of λ p 3 and one occurrence of λ p 4 with two of λ m , to get π i+1 .

• λ p 1 -λ p 2 < λ p 2 -λ p 3 < λ p 3 -λ p 4 .
We here set

λ m = λp 1 -λp 2 2
, and replace, in π i , one occurrence of λ p 1 and one occurrence of λ p 2 with two occurrences of λ m , to get π i+1 .

Note that we might actually end up with |sp(π i )| < |sp(π i+1 )|. However, as going from π 0 to π r , the largest elements of the consecutive m-partitions keep on decreasing, until they get equal (or closer, to the least) to 1. Thus, from π, we indeed get a sequence π = π 0 , π 1 , . . . , π r of m-partitions such that π 0 , . . . , π r-1 / ∈ K and π r ∈ K. It now remains to show that, due to how we constructed these partitions, any edge-realisation in G of some π i with i ≥ 1 yields one of π i-1 . This means we must turn two connected parts of cardinality λ m into either one connected part of cardinality λ p 2 and one of cardinality λ p 3 (first case above), or one of cardinality λ p i+1 and one of cardinality λ p i+2 for some i ∈ {1, 2} (second case above).

To turn an edge-realisation R of some π i in G into one of π i-1 , we will mainly make use of the following operations, used to modify R (and actually any edge-realisation in G; below, for convenience, we define these operations for R only) to an edge-realisation of another m-partition in G. In what follows, two parts of R are said adjacent if they share a vertex. Since G is a tree, note that any two parts can share at most one vertex.

Y ′ = {v 1 , . . . , v j-i+1 } and X ′ = X ∪ Y ∖ Y ′ . -If ∆(G[Y ]) = 3 and ∆(G[X]) = 2, then G[X] is a path v 1 . . . v i
, where v i also belongs to Y . Then, here, we set

Y ′ = {v 1 , . . . , v i } and X ′ = X ∪ Y ∖ Y ′ .
• Assume R contains three parts X, Y, Z, where Y is adjacent to both X and Z. Note that, since G is a tripode, it cannot be that X and Z are adjacent, unless, together with Y , they all share u, and

G[X], G[Y ], G[Z] are all paths.
Assume X and Z are not adjacent. By transferring one edge from Z to X through Y , we mean modifying R by, for vx ∈ X and xy ∈ Y , and v ′ x ′ ∈ Y and x ′ y ′ ∈ Z (such edges exist, since Y is adjacent to both X and Z), moving xy to from Y to X, and moving x ′ y ′ from Z to Y . As a result, note that (still calling the resulting parts X, Y, Z in the obvious way) Y remains of the same cardinality, that |X| increased by 1, and that |Z| decreased by 1. For this operation to be valid, however, it is important that G[X], G[Y ], G[Z] remain connected, so that what results remains an edge-realisation in G. This implies this operation should not be used if x = u and Y contains edges from the third branch of G (not containing edges of X and Z).

We generalise the transfer operation to more than one edge. That is, given any ∆ ≥ 1, by transferring ∆ edges from Z to X through Y , we mean repeating the atomic transfer operation above ∆ times, assuming of course this does not break, at any point, the fact that we have an edge-realisation of some m-partition.

• In certain circumstances, the previous operations imply we can transfer edges between two adjacent parts directly, without having a third auxiliary part separating them (in other words, with Y = ∅). For similar reasons as above, this should not be applied in all configurations, due to the requirement that we want an edge-realisation to result. However, this applies, notably, for two adjacent parts inducing paths, from a part inducing a path to an adjacent part inducing a graph with a vertex of degree 3, and the other way round when the shared vertex is not u.

We are now ready to proceed with the core of the proof. For any i ∈ {1, . . . , r}, we assume we have an edge-realisation R of π ′ = π i in G, which we we want to turn into one of π = π i-1 . Recall that sp(π) contains four elements λ p 1 , λ p 2 , λ p 3 , λ p 4 (where λ p > λ p 1 > λ p 2 > λ p 3 > λ p 4 , element λ p being the largest value in π) with the same parity, and that two occurrences of some of these elements in π have been replaced, in π ′ , with two occurrences of their mean value λ m . We consider three main cases.

• There is only one part of R containing edges incident to u.

We consider two main subcases below, involving the two kinds of relationships that λ p 1 , λ p 2 , λ p 3 , λ p 4 can share.

-There is some i ∈ {1, 2} such that

λ p i -λ p i+1 ≥ λ p i+1 -λ p i+2 .
For convenience, we assume i = 1, w.l.o.g. Recall that, to go from π to π ′ , one occurrence of λ p 2 and one occurrence of λ p 3 were replaced with two occurrences of

λ m = λp 2 -λ p-3 2
, where we set ∆ = λ p 2 -λ m = λ m -λ p 3 . Consider, in R, two parts X and Y with cardinality λ m . To get an edge-realisation of π in G, we essentially need to transfer ∆ edges from X to Y , or vice versa. Note that λ m is not the largest element of π ′ (since λ p 1 ∈ π ′ ). Through repeated uses the absorption operation, we can thus assume the part Z of R containing all three edges incident to u is of largest cardinality (thus at least λ p 1 ). Let thus z A , z B , z C ≥ 1 be the number of edges of A, B, C, respectively, in Z. Since Z / ∈ {X, Y }, each of X and Y covers edges (not incident to u) from a single of branches A, B, C. If X and Y cover edges from the same branch, then, through repeated uses of the absorption operation, we can guarantee X and Y are adjacent, so that ∆ edges can then be transferred e.g. from X to Y to get an edge-realisation of π in G. So, we can now assume w.l.o.g. that X contains edges of A only, while Y contains edges of B only. Through the absorption operation, we can also assume that Z is adjacent to both X and Y . First off, if z A ≥ ∆ (or z B ≥ ∆), then note that we can transfer ∆ edges from Y to X (or vice versa) through Z to be done. Thus, from now on we can assume z A , z B < ∆. Thus,

z A + z B < 2∆ -1. Now, since |Z| = z A + z B + z C ≥ λ p 1 , we have z C ≥ λ p 1 -(z A + z B ) > λ p 1 -2∆ + 1.
Note then that λ p 1 can be written as λ p 2 + (λ p 1 -λ p 2 ), and that, since λ p 1 -λ p 2 ≥ λ p 2 -λ p 3 = 2∆, altogether we deduce z C > λ p 2 + 1 > λ m + ∆. In this situation, through the absorption and transfer operations, we can modify R to an edge-realisation R ′ of π ′ in G where, essentially, the main differences are that X moved to C, and Z, as a result, expended along A (while Y still contains edges of B only). If we now denote by z ′ A , z ′ B , z ′ C the number of edges of A, B, C, respectively, in Z by R ′ , we now have that z ′ C > ∆, meaning that we can now transfer ∆ edges from Y to X (through Z) to get an edge-realisation of π in G.

-λ p 1 -λ p 2 < λ p 2 -λ p 3 < λ p 3 -λ p 4 .
In this case, recall that π ′ was obtained from π by replacing one occurrence of λ p 1 and one of λ p 2 with two occurrences of λ m = λp 1 -λp 2 2

, where ∆ = λ p 1 -λ m = λ m -λ p 2 . Consider thus, in R, two parts X and Y of cardinality λ m , and one part Z of largest cardinality containing the three edges incident to u. Again, we can assume Z / ∈ {X, Y } (as otherwise through the absorption operation we could make X and Y adjacent, so that ∆ edges can be transferred). Actually, recall that the largest value of π ′ is λ p > λ m ; through the absorption operation, we can thus actually assume that |Z| = λ p . We set again z A , z B , z C ≥ 1 the number of edges of Z in A, B, C, respectively. For the same reasons as earlier, we can assume z A , z B < ∆; thus, z C ≥ λ p -(z A +z B ) > λ p -2∆+1. Since λ p 1 -λ p 2 = 2∆ and λ p > λ p 1 , this implies z C > λ p 2 +1. Consider now a part W (different from X, Y, Z) of cardinality λ p 3 of R (note that such a part exists, since π ′ contains value λ p 3 ). We consider two cases: * W contains edges of, say, A only.

Here, through the absorption and transfer operations, we can modify R to an edge-realisation R ′ of π ′ in G where W essentially moved from A to C, and X expended along A. Such an R ′ indeed exists since z

C > λ p 2 > λ p 3 . Let now z ′ A , z ′ B , z ′ C denote the number of edges of Z in A, B, C by R ′ . Then z ′ A > λ p 3 , and since λ p 3 > λ p 3 -λ p 4 > λ p 2 -λ p 3 > λ p 1 -λ p 2 = 2∆, we have z ′ A > 2∆. Since X still
Z expanded along A (while Z lost edges along C). Denote by z ′ A , z ′ B , z ′ C the resulting number of edges of Z in A, B, C, respectively, by R ′ . In particular, z ′ C = z C -(λ m -λ p 3 )
, where we observed earlier that z C > λ p 2 , and thus that z

′ C > λ p 2 -λ m + λ p 3 . Since λ m -λ p 2 = ∆, we get z ′ C > λ p 3 -∆. Now, because λ p 3 > λ p 3 -λ p 4 > λ p 2 -λ p 3 > λ p 1 -λ p 2 = 2∆,
we have z ′ C > ∆. Now, since, in R ′ , part X contains edges of C only, and Y still contains edges of B only, we can transfer ∆ edges from Y to X through Z to get an edge-realisation of π in G.

• There are exactly two parts of R containing edges incident to u.

Let λ α and λ β (where λ α > λ β ) be two elements of π that were turned into two occurrences of λ m = λα+λ β 2

as going from π to π ′ , and set again ∆ = λ α -λ m = λ m -λ β . Then, in R, there are two parts X and Y of cardinality λ m , and, by assumption, there are two parts Z and Z ′ containing u such that G[Z] and G[Z ′ ] are w.l.o.g. a path along A and B and a path along C, respectively. If X or Y lies in {Z, Z ′ }, then, through repeated uses of the absorption operation, note that can make X and Y adjacent so that ∆ edges can be transferred from one part to the other, to get an edge-realisation of π in G. So, now, we can suppose each of X and Y contains edges (not incident to u) of a single of A, B, C. Of course, if X and Y both contain edges of, say, A only, then through the absorption operation we can make them adjacent so that, again, ∆ edges can be transferred from one part to the other. Up to symmetry, this leaves only two more cases to consider:

-X contains edges of A only, while Y contains edges of B only.

In that case, through the absorption operation we can first guarantee Z is adjacent to both X and Y . Then G[X ∪ Z ∪ Y ] is a path; thus, through e.g. the absorption operation again, we can make X and Y adjacent, so that ∆ edges can then be transferred from one of the two parts to the other, to eventually get an edge-realisation of π in G.

-X contains edges of A only, while Y contains edges of C only.

Recall that uc 1 ∈ Z ′ and ua 1 ∈ Z. Let us denote by z A , z B ≥ 1 the number of edges of A and B, respectively, belonging to Z. If λ m < z B , then note that, after applying the absorption operation along C to guarantee Z and Y are adjacent, we can have Z absorb Y to get an edge-realisation of π ′ in G where X still covers edges of A only while Y now covers edges of B only, and Z now contains all three edges incident to u and we fall back into a previous case. Now, if λ m ≥ z B , then we can here have Z absorb X to get an edge-realisation where Y still contains edges of C only, part X now contains edges of B (including ub 1 ) and (perhaps) of A, and Z contains edges of A only. Then, through the absorption operation, we can make sure Y contains uc 1 , so that X and Y get adjacent, and we can obtain an edge-realisation of π in G by transferring ∆ edges from Y to X.

• There are exactly three parts of R containing edges incident to u.

Let λ α and λ β (where λ α > λ β ) be the two elements of π that were turned into two occurrences of λ m = λα+λ β 2

when building π ′ from π, where ∆ = λ α -λ m = λ m -λ β . So, in R, there are two parts X and Y of cardinality λ m , and, by the main hypothesis of the current case, there are three parts Z, Z ′ , Z ′′ where G[Z], G[Z ′ ], G[Z ′′ ] are, w.l.o.g., paths along A, B, C, respectively, containing u.

-If X, Y / ∈ {Z, Z ′ , Z ′′ }, then X and Y both contain edges (not incident to u) from a single of A, B, C. If X and Y are both contained in, say, A, then, through, the absorption operation, we can make sure X and Y are adjacent, so that we can transfer ∆ edges from, say, X to Y to get an edge-realisation of π in G. Now, if, say, X is contained in A and Y is contained in B, then, through the absorption operation, we can make sure X is adjacent to Z while Y is adjacent to Z ′ . Then G[X ∪ Z ∪ Z ′ ∪ Y ] is a path, so we can now make X and Y adjacent so that it then suffices to transfer ∆ edges from, say, X to Y to be done.

-If X, Y ∈ {Z, Z ′ , Z ′′ }, then X and Y are adjacent, and G[X ∪ Y ] is a path. In that case, we can thus transfer ∆ edges from X to Y to be done.

-Assume last that, say, X ∈ {Z, Z ′ , Z ′′ } and Y / ∈ {Z, Z ′ , Z ′′ }. Then X contains edges (including one incident to u) of a single branch of G, say A w.l.o.g. If Y contains edges of A only, then, through the absorption operation, we can make sure X and Y are adjacent, so that ∆ edges can be transferred to be done. Otherwise, assume, w.l.o.g., that Y covers edges of B only. Again, through the absorption operation, we can make sure Y and Z ′ are adjacent so that G[X ∪ Z ′ ∪ Y ] is a path. So, again through the absorption operation, we can modify R to make sure X and Y are adjacent, and, from here, we can transfer ∆ edges from one part to the other to get an edge-realisation of π in G.

Thus, in all cases we can deduce an edge-realisation of π in G from one of π ′ in G, implying the claim holds true.

Another crucial ingredient for our upcoming result, is the following result by Ravaux [START_REF] Ravaux | Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques[END_REF] for the vertex case, and its obvious corollary in our edge case. Lemma 4.5 (Ravaux [26]). Let F be a linear forest of order n consisting of α paths. For every n-partition π, it can be decided in time O(n O(α) ) whether π is vertex-realisable in F .

Of course, if none of the three routines above results in an edge-realisation of π in G, then we can assert that G is not AEP. Thus, it can be decided in polynomial time whether π is edge-realisable in G, and thus whether G is AEP. This concludes the proof.

An interesting fact behind Theorem 4.7 is that we essentially reuse (through the set K) the concept of polynomial kernel of n-partitions, which is, for a graph of order n, a set (with polynomial size) of n-partitions attesting its APness. Due to Observation 2.2, note that we essentially provided such a kernel for the class of line graphs of tripodes.

Conclusion

In this work, we introduced the concept of AEP graphs, which can be perceived as an edge version of AP graphs. As seen earlier, an interesting point is that AEPness can serve as a way to study APness in special classes of line graphs, since a graph is AEP if and only if its line graph is AP (Observation 2.2). In Section 2, we started by investigating how the most fundamental properties of AP graphs adapt to AEP graphs, showing that some of these adapt naturally while some others do not. In Section 3 we focused a bit more on the parameter σ 2 , establishing (through Theorems 3.5 and 3.6), in the same way initiated by Marczyk for APness, sufficient conditions for AEPness inspired by some for Hamiltonicity. Last, in Section 4, we focused on algorithmic aspects, showing that determining whether an m-partition is edge-realisable in a tree with size m is NP-complete (Theorem 4.2), while determining AEPness can be done in polynomial time for tripodes (Theorem 4.7).

In most of the previous sections, we have already raised a number of directions and ideas for further work on the topic, which we think are of interest. Among these, we believe it would be appealing to investigate whether Theorem 3.6 can be improved further to lower upper bounds. Regarding Theorem 4.2, we wonder whether the result can be improved to more restricted classes of trees; in particular, the vertex version of the Edge-Realisation problem (Vertex-Realisation) is NP-complete for subdivided stars [START_REF] Bensmail | More Aspects of Arbitrarily Partitionable Graphs[END_REF], and we wonder whether the same also holds in our context. Regarding Theorem 4.7, an interesting aspect is that AEP trees can be of arbitrarily large maximum degree (recall Theorem 2.10), which is not the case for AP trees [START_REF] Barth | A degree bound on decomposable trees[END_REF]; so, a first, interesting question could be to decide whether Theorem 4.7 holds as well for k-podes in general (for any fixed value of k ≥ 3). Last, we would like to mention as well that the complexity of determining whether a given graph is AP is still unknown (it is still unknown whether it lies in NP or co-NP at all, and whether it is hard for some complexity class, see [START_REF] Barth | A degree bound on decomposable trees[END_REF][START_REF] Bensmail | On the complexity of partitioning a graph into a few connected subgraphs[END_REF][START_REF] Bensmail | On three polynomial kernels of sequences for arbitrarily partitionable graphs[END_REF]), so a natural question is whether we can go farther regarding the problem of determining AEPness.

Lemma 3 . 1 .

 31 If a graph G with size m has a path P = v 1 . . . v p such that α ≥ 0 edges of G are not incident to any vertex of P , then L(G) has a path on m -α vertices.

Corollary 3 . 3 .

 33 If G is a connected graph of size m such that L(G) has a path of length m -α, then every m-partition π with |sp(π)| ≥ α is edge-realisable in G.

Lemma 4 . 4 .

 44 A tripode G with size m is AEP if and only if all m-partitions π with |sp(π)| ≤ 7 are edge-realisable in G.

  • Assume R contains two adjacent parts X and Y , where, say, |X| ≥ |Y |, and we have ∆(G[X]) ≤ 2. Then, by having X absorbing Y , we mean modifying R through replacing X and Y with two parts X ′ and Y ′ (and keeping the other parts of R unmodified) where Y ⊆ X ′ . Essentially because G is a tree, this is always possible under the assumption that |X| ≥ |Y |. Indeed: -If G[X] and G[Y ] are two paths v 1 . . . v i and v i . . . v j sharing vertex v i (i.e., ∆(G[X]), ∆(G[Y ]) ≤ 2), then we set

  contains edges of A only, this means that, from R ′ , we can now transfer ∆ edges from Y to X through Z to obtain an edge-realisation of π in G. * W contains edges of C only. Since λ m = λ p 2 +∆ > λ p 3 , we can modify R to an edge-realisation R ′ of π ′ in G where W moved to A, and since z C +λ p 3 > λ p 2 +λ p 3 > λ p 2 +2∆ = λ p 1 (since λ p 3 > 2∆ as mentioned earlier), part X moved to C as a replacement, and

Given a graph G, its line graph L(G) is the graph having a vertex ve for every edge e ∈ E(G), and an edge vev f whenever e and f are adjacent, i.e., share a vertex, in G.

Obviously, any AEP tree is minimal AEP.

We verified this through computer programs, but it is not too difficult to check this by hand too.

Observation 4.6. The line graph L(P ) of any path P is a path itself. Therefore, if F is a linear forest of size m consisting of α paths, then, by Lemma 4.5, for every m-partition π, it can be decided in time O(m O(α) ) whether π is edge-realisable in F .

We can now state our main result in this section: Theorem 4.7. We can decide in polynomial time whether any tripode is AEP.

Proof. Let G be any tripode of size m. By Lemma 4.4, we have that G is AEP if and only if all m-partitions of K are edge-realisable in G, where, recall, K denotes the set of all m-partitions with spectrum of cardinality at most 7. Thus, it suffices to show that, for any π ∈ K, it can be decided in polynomial time whether π is edge-realisable in G.

Let u denote the unique vertex of degree 3 of G, and let ua 1 a 2 . . . a x , ub 1 b 2 . . . b y , and uc 1 c 2 . . . c z be the three pendant paths attached to u, for some x, y, z ≥ 1. As seen throughout the proof of Lemma 4.4, any edge-realisation of an m-partition in G can be of three main kinds: either all three edges incident to u belong to a single part, they belong to exactly two parts, or they belong to exactly three parts. For each of these three possible configurations, we show we can decide in polynomial time whether π can be edge-realised in this precise way. Note that our goal below is not to optimise the running time of a solving algorithm, which is why some arguments are a bit shallow.

• Regarding the existence of edge-realisations of π in G where the three edges incident to u belong to a single part X, we can, for every λ ≥ 3 of the at most seven distinct values in π, consider all λ-partitions

and, by Observation 4.6, check in polynomial time whether the rest of π can be edgerealised in G -X, which is a forest of at most three paths (so that, together with X, we get an edge-realisation of π in G). The whole process can clearly be performed in polynomial time.

• Regarding the existence of edge-realisations of π in G where the three edges incident to u belong to exactly two parts X and Y , we can, for every two λ ≥ 2 and λ ′ ≥ 1 (possibly λ = λ ′ ) of the at most seven distinct values in π, consider all λ-partitions (x A , x B ) with x A , x B ≥ 1 (there are O(m 2 ) of them), set

and, by Observation 4.6, check in polynomial time whether the rest of π can be edge-realised in G -X -Y , which is a forest of at most three paths. In this, note that we have made the assumption that X covers edges ua 1 and ub 1 , but we also have to consider when X covers ua 1 and uc 1 , and when X covers ub 1 and uc 1 , which can be simply done through renaming the vertices of G different from u. Altogether, the whole process can clearly be performed in polynomial time.

• Regarding the existence of edge-realisations of π in G where the three edges incident to u belong to exactly three parts X, Y, Z, we can, for every three λ, λ ′ , λ ′′ ≥ 1 (possibly some of λ, λ ′ , λ ′′ can be the same) of the at most seven distinct values in π , set andZ = {uc 1 , c 1 c 2 , . . . , c λ ′′ -1 c λ ′′ }, and, by Observation 4.6, check in polynomial time whether the rest of π can be edge-realised in G -X -Y -Z, which is a forest of at most three paths (so that, together with X, Y, Z, we get an edge-realisation of π in G). The whole process can clearly be performed in polynomial time.