Marthe Bonamy
email: marthe.bonamy@u-bordeaux.fr

Paul Dorbec
email: paul.dorbec@unicaen.fr

Paul Ouvrard
email: paul.ouvrard@u-bordeaux.fr

Dominating sets reconfiguration under token sliding

come

Introduction

General introduction. Reconfiguration problems arise when, given an instance of a problem, we want to find a step-by-step transformation (called a reconfiguration sequence) between two feasible solutions such that all intermediate solutions are also feasible. Unfortunately, such a transformation does not always exist and some solutions may even be frozen, i.e., they can not be modified at all. In this context, two natural questions arise: (i) When can we ensure that there exists such a transformation? (ii) What is the complexity of deciding whether a reconfiguration sequence exists?

Interest in combinatorial reconfiguration steadily increased during the last decade. Reconfiguration of several problems, including COLORING [START_REF] Bonamy | On a conjecture of mohar concerning kempe equivalence of regular graphs[END_REF][START_REF] Cereceda | Connectedness of the graph of vertexcolourings[END_REF][START_REF] Feghali | Paths between colourings of sparse graphs[END_REF], INDEPENDENT SET [START_REF] Bonsma | Independent set reconfiguration in cographs and their generalizations[END_REF][START_REF] Bousquet | Token jumping in minor-closed classes[END_REF][START_REF] Lokshtanov | The complexity of independent set reconfiguration on bipartite graphs[END_REF], DOMINATING SET [START_REF] Haddadan | The complexity of dominating set reconfiguration[END_REF][START_REF] Lokshtanov | Reconfiguration on sparse graphs[END_REF][START_REF] Amer | On the parameterized complexity of reconfiguration problems[END_REF][START_REF] Suzuki | Reconfiguration of dominating sets[END_REF] and SATISFIABILITY [START_REF] Gopalan | The connectivity of boolean satisfiability: Computational and structural dichotomies[END_REF][START_REF] Mouawad | Shortest reconfiguration paths in the solution space of boolean formulas[END_REF] have been studied. For an overview of recent results on reconfiguration problems, the reader is referred to the surveys of van den Heuvel [START_REF] Van Den | The complexity of change[END_REF] and Nishimura [START_REF] Nishimura | Introduction to reconfiguration[END_REF]. In this article, we focus on the reconfiguration of dominating sets.

A dominating set is a set of vertices such that every vertex not in the set has a neighbor in it. One can represent a dominating set as a set of tokens, where exactly one token is placed on each vertex that is part of the dominating set. Then, modifying a dominating set corresponds to shifting the tokens according to some rule, called a reconfiguration rule. In the literature, three kinds of operations have been mainly studied:

1. Token Addition and Removal (TAR): one can add or remove a token as long as the total number of tokens does not go beyond a given threshold;

2. Token Jumping (TJ): one can move a token to any vertex of the graph;

3. Token Sliding (TS): one can slide a token along an edge, i.e., one moves a token to a neighbor of its current location.

One can observe that in the last two models, the size of each solution remains constant at any time, as opposed to what happens in the TAR model. In this article, we are mostly interested in the Token Sliding model.

We define the reconfiguration graph for domination, denoted R k (G) as follows: the vertices of R k (G) are the dominating sets of size k and there is an edge between two vertices if and only if one can Related results. The reconfiguration of dominating sets has been mainly studied under the Token Addition and Removal model. Haas and Seyffarth gave sufficient conditions to guarantee the connectivity of the reconfiguration graph according to k, the cardinality threshold of dominating sets [START_REF] Haas | The k-dominating graph[END_REF]. More precisely, they proved that R n-1 (G) (where n is the number of vertices of G) is connected if G has at least two independent edges. This value can be lowered to Γ+1 (where Γ is the maximum size of a minimal dominating set) if the input graph G is chordal or bipartite. Suzuki et al. [START_REF] Suzuki | Reconfiguration of dominating sets[END_REF] showed that this result cannot be generalized to any graph since they constructed an infinite family of graphs for which R Γ+1 (G) is not connected. On the positive side, they proved that R n-µ (G) is connected if G has a matching of size µ + 1.

Haddadan et al. [START_REF] Haddadan | The complexity of dominating set reconfiguration[END_REF] studied the complexity of the reconfiguration of dominating sets under the token addition and removal rule from a graph classes perspective. They proved that the reachability problem is PSPACE-complete, even if the input graph is a split graph, a bipartite graph, has bounded bandwidth or is planar with maximum degree six. On the other hand, they gave linear-time algorithms for trees, interval graphs or cographs.

Mouawad et al. [START_REF] Amer | On the parameterized complexity of reconfiguration problems[END_REF] studied the parameterized complexity of DOMINATING SET RECONFIGURATION under token addition and removal. They proved that this problem is W [START_REF] Bertossi | Dominating sets for split and bipartite graphs[END_REF]-hard when parameterized by k + , where k is the threshold and the length of the reconfiguration sequence. As a positive result, Lokshtanov et al. [START_REF] Lokshtanov | Reconfiguration on sparse graphs[END_REF] gave a fixed-parameter algorithm with respect to k for graphs excluding K d,d as a subgraph, for any constant d.

The third author also considered this problem (still in the TAR model) through the lens of an optimization variant (see Blanché et al. [START_REF] Blanché | Decremental optimization of dominating sets under the reconfiguration framework[END_REF]) as recently introduced by Ito et al. for independent sets [START_REF] Ito | Incremental optimization of independent sets under the reconfiguration framework[END_REF].

To the best of our knowledge, the reconfiguration of dominating sets under TS has only been studied from a structural perspective. Fricke et al. [START_REF] Fricke | γ-graphs of graphs[END_REF] introduced the concept of γ-graph which corresponds to the reconfiguration graph R γ (G) under the token sliding rule. In particular, they proved that R γ (G) is connected and bipartite if G is a tree. For a more complete overview, the reader is referred to [START_REF] Mynhardt | Reconfiguration of colourings and dominating sets in graphs: a survey[END_REF].

Our contribution. In this article, we are interested in the reachability question of dominating sets reconfiguration under token sliding. This reconfiguration rule has already been studied for various reconfiguration problems but not for dominating sets, to the best of the authors' knowledge.

We tackle this problem with a complexity perspective according to several graph classes: in Section 3, we prove for instance that DSR TS is PSPACE-complete for split graphs or bipartite graphs. Note that the reductions used in the proofs of Theorems 5 and 6 are identical to the ones of [START_REF] Haddadan | The complexity of dominating set reconfiguration[END_REF], which are quite standard (see, e.g., [START_REF] Bertossi | Dominating sets for split and bipartite graphs[END_REF]). Our reduction to prove the PSPACE-completeness of DSR TS for split graphs is similar but not identical to the one of [START_REF] Haddadan | The complexity of dominating set reconfiguration[END_REF], as we reduced from DSR TJ and not from VERTEX COVER CONFIGURATION.

In Section 4, we show that this problem can be solved in polynomial time on other graph classes such as cographs or dually chordal graphs (the formal definitions of these two graph classes is given in Subsections 4.1 and 4.2, respectively). Note that our result for cographs is a consequence of Theorem 7 which is more general (see the discussion in Subsection 4.1). Note also that our result on dually chordal graphs generalizes the ones of [START_REF] Haddadan | The complexity of dominating set reconfiguration[END_REF] for trees and interval graphs since the class of dually chordal graphs is a superclass of both interval graphs and trees as discussed in Subsection 4.2. Figure 1 gives an overview of our results where A → B means that the class B is properly included in the class A.

Preliminaries

This section is devoted to some basic definitions of graph theory used in this article, followed by a more formal introduction of the problem we are interested in.

Each graph G = (V, E) considered is simple (i.e., G is undirected and has no multiple edges or loops) where V represents the vertex set of G and E its edge set. We denote by n = |V | and m = |E| the number of vertices and edges of G. The eccentricity of a vertex u denoted by (u) is the maximum distance between u and any other vertex. For a subset of vertices S ⊆ V , we denote by G[S] the subgraph induced by S. For a vertex u ∈ V , we denote by N G (u) its open neighborhood, i.e., the set {v | uv ∈ E} and by N G [u] its closed neighborhood, i.e. the set N G (u) ∪ {u}. For a subset of vertices S ⊆ V , we define the closed neighborhood of S as the union of the closed neighborhood of the vertices in S, i.e., N G

[S] = u∈S N G [u].
Let G 1 and G 2 be two graphs. We recall two basic binary operations on graphs: the disjoint union and the join operations. The disjoint union G 1 ∪ G 2 of two graphs on disjoint vertex sets is the graph

with vertex set V (G 1 ∪ G 2 ) = V (G 1 ) ∪ V (G 2 ) and edge set E(G 1 ∪ G 2 ) = E(G 1 ) ∪ E(G 2 ).
The join operation can be obtained from the disjoint union by adding all possible edges between G 1 and G 2 . More formally, the join of G 1 and G 2 denoted by G 1 + G 2 is the following graph:

• V (G 1 + G 2 ) = V (G 1 ) ∪ V (G 2 ); • E(G 1 + G 2 ) = E(G 1 ) ∪ E(G 2 ) ∪ {uv | u ∈ V (G 1 ), v ∈ V (G 2 )}.
A dominating set for a graph G = (V, E) is a subset of vertices D ⊆ V such that N [D] = V , i.e., each vertex either belongs to D or has a neighbor in D. For a graph G, we denote by γ(G) the domination number of G defined as the minimum size of a dominating set. Let G be a graph and D a dominating set of G. We say that u is a private neighbor of v (with respect to D) if u ∈ D and v is the only neighbor of u in D. Therefore, a dominating set is inclusion-wise minimal if and only if each of its vertices has a private neighbor.

Our problem.

In the token sliding model, a natural question is whether we should authorize more than one token to be placed on a vertex during the reconfiguration sequence. Here is an example where Indeed, for problems like independent set, there can be no question of superposing two tokens, as two tokens cannot be adjacent in the first place. In the aforementioned paper considering token sliding for dominating sets, they exclusively consider that model in the case of minimum dominating sets: if superposition was an option, there would be a smaller dominating set, which is impossible.

(a) D 0 = D s (b) D 1 (c) D 2 (d) D 3 = D t
Let G be a graph, D s and D t be two dominating sets of G of same size k. We say that D s is reconfigurable into D t by token sliding if there exists a sequence S = D 0 = D s , D 1 , . . . , D -1 , D = D t that satisfies the two following properties:

• each D i is a multiset of size k that is a dominating set of G;

• there exists an edge uv such that D i+1 = D i \{u}∪{v}, i.e., we slide the token placed on the vertex u along the edge uv. We denote this move by u TS v.

We call such a sequence a TS-sequence and we denote this property by D s TS D t . We also say that (G, D s , D t ) is a yes-instance for the DSR TS problem. We also introduce the two following notation, where D s and D t are two dominating sets of G of size k. 2 gives an example of a TS-sequence.

We are now ready to define properly the DOMINATING SET RECONFIGURATION problem under token sliding.

DSR TS

Instance: A graph G = (V, E) and two dominating sets D s and D t of cardinality k of G.

Question: Is there a TS-sequence between D s and D t , i.e., does D s TS D t hold?

We end this section by the following observation, showing that being reconfigurable is not a monotone property. Theorem 1. For every ≥ 3, there exists a graph G where, for every k < , every dominating set of size k can be reconfigured into any other, while there are two dominating sets of size that cannot be reconfigured one into the other.

Proof. We first prove the statement for k = 2. For every integer > 2, we define the graph G such that G contains exactly one dominating set of size γ(G) = 2 but for which the dominating sets of size are not reconfigurable. To construct G , we first create pairs of triangles

{(G i 1 , G i 2 ), . . . , (G 1 , G 2 )} such that G i
1 and G i 2 share exactly one vertex w i . Moreover, let all the G i 1 's share a vertex u and all the G i 2 's share a vertex v (see Figure 3 for G 3 as an example). Note that we have γ(G ) = 2 since {u, v} is a dominating set and G does not contain a universal vertex (i.e., a vertex adjacent to all the other vertices).

Consider the dominating set D s = {w 1 , . . . , w }. It is a dominating set of G of size . By token sliding, D s cannot be reconfigured into any other dominating set of size . Indeed, in D s we cannot move any w i in a triangle because it would leave the other triangle of the pair (G i 1 , G i 2 ) not dominated. Note that any set of vertices containing u and v is a dominating set of G , hence the existence of two dominating sets of size as desired.

Consider now k < . Any dominating set of G on fewer than vertices contains both u and v. Indeed, if for instance u is not in the dominating set, then extra vertices are necessary to dominate the triangles G i 1 . Therefore, any dominating set D of G on k vertices contains both u and v. The other vertices are therefore not necessary for domination purposes, and we can slide them around as desired, superposing them with u and v arbitrarily. There are many dominating sets on k vertices, but they all contain u and v and can be trivially reconfigured one into another.

PSPACE-completeness

In this section, we study the complexity of DSR TS in the general case. We show that this problem is PSPACE-complete, even when restricted to split graphs, bipartite graphs or bounded treewidth graphs. Let us first recall the following result from Haddadan et al. [START_REF] Haddadan | The complexity of dominating set reconfiguration[END_REF], stating the complexity of the reconfiguration problem for the TAR model.

Theorem 2 ([17]

). Let G be a graph and D s , D t be two dominating sets of G of size k. Deciding whether

D s TAR D t is PSPACE-complete.
Note that the problem remains PSPACE-complete, even if the input graph is a planar graph with maximum degree 6, has bounded bandwidth, is bipartite or is a split graph as pointed out previously. Let us now show that the TJ and TAR rules are equivalent under some constraints. Note that a similar proof can be found in [START_REF] Haas | The k-dominating graph[END_REF].

Lemma 3.

Let G be a graph and D s and D t be two dominating sets of G of size k. We have D s TAR D t if and

only if D s TJ D t .
Proof. The proof is an adaptation of the Theorem 1 of Kami ński et al. [START_REF] Kami Ński | Complexity of independent set reconfigurability problems[END_REF]. (⇒) For the other direction, let S be a TAR-sequence that reconfigures D s into D t . Note that since

v 1 v 2 v 3 v 4 (a) G v 1 v 2 v 3 v 4 w 1 w 2 w 3 w 4 (b) G
|D s | = |D t | = k, S
is of even length. Moreover, by hypothesis, S does not contain a configuration of size more than k + 1. If all the configurations of S are of size k or k + 1, this means that S corresponds to an alternation of an addition of a token on some vertex v immediately followed by the deletion of a token on a vertex u. Therefore, to get a TJ-sequence, we simply replace each of these subsequences by a move u TJ v. Suppose now that S contains some configuration of size less than k and consider a configuration, let us say D i , of smallest size. Since D i is a configuration of smallest size, this means that it has been obtained from D i-1 by the deletion of some vertex x. We also know that the configuration D i+1 is obtained from D i by the addition of some vertex y. If x = y, then these two steps are redundant and can simply be ignored. Otherwise, observe that if we first add y and then delete x, the new sequence is still valid. If all the configurations are of size k or k + 1, we immediately obtain a TJ-sequence.

Otherwise, we can repeat this process until this is the case.

As a corollary of Theorem 2 and Lemma 3, we obtain that deciding whether two dominating sets of size k of a graph G can be reconfigured under the token jumping model is a PSPACE-complete problem. We are now ready to prove Theorem 4. Theorem 4. DSR TS is PSPACE-complete on split graphs.

Proof. First, note that the problem is in PSPACE [START_REF] Ito | On the complexity of reconfiguration problems[END_REF]. We give a polynomial-time reduction from DSR TJ , which is PSPACE-complete as discussed above. Let G = (V, E) be a graph with V (G) = {v 1 , . . . , v n }. We construct the corresponding split graph G as follows:

• V (G ) = V 1 ∪ V 2 where V 1 = {v 1 , . . . , v n } and V 2 = {w 1 , . . . , w n }; • E(G ) = {uv | u, v ∈ V 1 } ∪ {v i w j | v j ∈ N G [v i ]}, i.e., we add all possible edges in V 1 so that V 1
forms a clique. We also add an edge between a vertex v i ∈ V 1 and a vertex w j ∈ V 2 if and only if the corresponding vertex v j in the original graph G belongs to the closed neighborhood of v i in G.

Observe that G is a split graph since V 1 forms a clique and V 2 an independent set (see Figure 4 for an example). To a set of vertices of G, we associate the corresponding vertices of V 1 in G . By definition of G , any dominating set D of G is also a dominating set for G : indeed, a vertex v i ∈ V 1 dominates all the vertices in V 1 (since it is a clique) and all the vertices in V 2 that correspond to vertices in its closed neighborhood in G. That D dominates G allows us to conclude that the corresponding set also dominates V 2 . Hence, D is also a dominating set of G .

Let (G, D s , D t ) be an instance of DSR TJ ; we reduce this instance to the instance of DSR TS (G , D s , D t ).

This reduction can be done in quadratic time. Now, we need to prove that D s TS D t if and only if there is a reconfiguration sequence between D s and D t in G using the token jumping model. (⇐) Consider a TJ-sequence in G, and translate it to G . All intermediate sets still are dominating sets, and since all pairs of vertices are joined by an edge in V 1 , this sequence is a valid TS-sequence in G .

(⇒) We now prove the other direction. Let D 0 = D s , . . . , D p = D t be a TS-sequence in G . First, observe that any dominating D of G such that D ⊆ V 1 corresponds to a dominating set of G. Indeed, any vertex w j ∈ V 2 is dominated by a vertex v i ∈ V 1 and by construction of G , v i v j ∈ E(G). Hence, v j is dominated by v i and thus D is also a dominating set of G. Hence, if the sequence does not use vertices in V 2 , we immediately obtain a TJ-sequence in G from D s to D t , as the token jumping model does not require adjacency. Suppose on the other hand that the sequence goes through some vertices in V 2 . Since all vertices are initially in V 1 , there is a subsequence that contains a move v i TS w j . Since

w j / ∈ V 1
, there exists a later step where the token on w j is moved to an adjacent vertex v k in V 1 (since V 2 is independent). However, w j does not dominate any vertex in V 2 (since V 2 is a stable set) and thus

N [w j ] ⊆ N [v k ]
. Therefore, we simply replace these two moves by a single move v i TS v k . We can thus assume that the reconfiguration sequence only uses vertices in V 1 . The conclusion follows.

Next, we prove that DSR TS is PSPACE-complete on bipartite graphs. We use a reduction from the VERTEX COVER RECONFIGURATION problem under token sliding (or VCR TS for short). Recall that a vertex cover is a set of vertices such that every edge has an endpoint in the set. The complement of a vertex cover is an independent set whose reconfiguration is known to be PSPACE-complete on planar graphs of maximum degree 3 [START_REF] Hearn | Pspace-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation[END_REF][START_REF] Bonsma | Finding paths between graph colourings: Pspace-completeness and superpolynomial distances[END_REF] or on bounded bandwidth graphs [START_REF] Wrochna | Reconfiguration in bounded bandwidth and tree-depth[END_REF]. Hence, VCR TS is PSPACEcomplete, even when restricted to these two classes. Theorem 5. DSR TS is PSPACE-complete on bipartite graphs.

Proof. We give a polynomial-time reduction from VCR TS . This is an adaptation of the well-known reduction from VERTEX COVER to DOMINATING SET [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. Let G = (V, E) be a graph. We construct the corresponding bipartite graph G = (V 1 V 2 , E ) as follows: for each edge uv ∈ E, add u and v to V 1 and a new vertex z uv of degree two to V 2 that is adjacent to exactly u and v. Note that E does not contain the edge uv so that V 1 induces an independent set. Finally, add to V 2 a vertex x adjacent to all the vertices in V 1 and attach to x a degree-one vertex y which is added to V 1 (see Figure 5 for an example). Formally, the graph G is the following:

• V (G ) = V 1 ∪ V 2 where V 1 = V (G) ∪ {y} and V 2 = {z uv | uv ∈ E} ∪ {x}; • E = {uz uv and z uv v | u, v ∈ V 1 and z uv ∈ V 2 } ∪ {xv | v ∈ V 1 } ∪ {xy}.
Observe that G is bipartite and the reduction can be done in polynomial time. We now prove that the vertex covers of G of size k are reconfigurable if and only if the dominating sets of G of size k + 1 are. Let (G, C s , C t ) be an instance for the VCR TS problem. We define the corresponding instance for the (⇒) We start with the only if direction. First, it immediately follows from the definition of D s and D t that D s \ {x} = C s and D t \ {x} = C t . Let us assume that (G, C s , C t ) is a yes-instance for the VCR TS problem. Then, there exists a reconfiguration sequence S using the token sliding model between C s and C t . One can construct a sequence S for G by replacing a move u v (where uv ∈ E(G)) of S into two moves: u z uv followed by z uv v. We need to prove that the domination property is preserved at every step. First, observe that each intermediate solution contains x, so each move of the form z uv v is safe because u is still dominated by x and z uv by v. Therefore, the only risk is to leave some vertex z wu non dominated after a move u z uv . In that case, this implies that w does not belong to the solution, which in turn means that the edges wu and uv are covered only by u. Therefore, the move u v of the sequence S is not valid (because the edge wu is no longer covered), a contradiction. Therefore, (G , D s , D t ) is a yes-instance for the DSR TS problem.

(⇐) It remains to prove the if direction. Suppose that (G , D s , D t ) is a yes-instance for the DSR TS problem. Then, there exists a reconfiguration sequence S = D s , . . . , D t in G . First, observe that at each step, y needs to be dominated and thus either x or y belongs to each solution. Moreover, initially, D s does not contain y. We can ignore all moves of the form x y (each such move will be eventually followed by a move y x), and assume that x contains at least one token in each solution. Therefore, the only vertices whose domination is not immediate by the existence of a token on x are the vertices of the form z uv , i.e., the vertices that correspond to the edges of G. Recall that D s = C s ∪ {x}, so every vertex in D s \ {x} belongs to V (G ) ∩ V (G). We consider in turn the two other possible moves u v, where u ∈ V (G) ∩ V (G ) (i.e., u corresponds to a vertex of the original graph G), and v either belongs to V (G ) \ V (G) or v = x. We focus on the next operation (which may not be consecutive) that touches the vertex v. Suppose first that v ∈ V (G ) \ V (G), i.e., v corresponds to a vertex z uu for some vertex u ∈ N G [u]. If the next move that touches z uu is z uu u, these two operations can be ignored. Otherwise, since z uu has degree two, the next operation that touches z uu is z uu u . Moreover, we claim that we can assume that z uu v is the operation that immediately follows the move u z uu . Indeed, N G [z uu ] ⊆ N G [u] so if a dominating set D contains z uu , D = (D \ {z uu }) ∪ {u } is also a dominating set of G . So one can assume that in S , if we have a move u z uu , it will be immediately followed by a move z uu u . In that case, one can replace these two moves by u u in a reconfiguration sequence from C s to C t . Let us now consider the other possible move: u

x. If the next move that touches x is x u, we again simply ignore these two steps. Let D i be the dominating set of S to which the move u

x is applied. Recall that when a token is moved from a vertex a to a vertex z ab (for some neighbor b of a), it is followed by z ab b. Therefore, we know that D i does not contain any vertex of the form z uv . So for every edge uu incident to u, D i+1 must contain u (this is possible if u has at least two tokens in D i ) or u in order to dominate z uu . Hence, C i+1 = D i+1 \ {x} is a vertex cover of G. If the next move that touches x is x u , one can safely replace these two moves u x and x u by d moves where d is the distance between u and u in G.

Therefore, one can obtain from S a TS-sequence that reconfigures C s into C t and thus (G, C s , C t ) is a yes-instance for VCR TS , as desired. This concludes the proof of Theorem 5.

Next, we prove that DSR TS is PSPACE-complete on planar graphs of maximum degree 6 and bounded bandwidth graphs. Recall that a graph has bandwidth at most k if there exists a numbering of the vertices with distinct integers between 1 and n (where n is the number of vertices of the graph) such that adjacent vertices must have labels at distance at most k (i.e., for every edge uv ∈ E, | (u) -(v)| ≤ k). Theorem 6. DSR TS is PSPACE-complete on planar graphs of maximum degree 6 and bounded bandwidth graphs.

Proof. First, recall that VCR TS is PSPACE-complete on planar graphs of maximum degree 3 [START_REF] Hearn | Pspace-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation[END_REF][START_REF] Bonsma | Finding paths between graph colourings: Pspace-completeness and superpolynomial distances[END_REF] and on bounded bandwidth graphs [START_REF] Wrochna | Reconfiguration in bounded bandwidth and tree-depth[END_REF]. The proof for dominating sets reconfiguration under TAR on planar graphs from [START_REF] Haddadan | The complexity of dominating set reconfiguration[END_REF] works also here since VCR TS is PSPACE-complete on planar graphs. We use the wellknown reduction mentioned in Theorem 5, which is the following: start with a copy of the original graph G and for each edge uv, add a vertex z uv of degree two adjacent to u and v. Let G be the resulting graph, and note that the planarity property of G is preserved.

Let G be a graph whose bandwidth is bounded by some constant k. Since a vertex can have at most k neighbors of lower label and k neighbors of higher label, this implies that the maximum degree of G is bounded by 2k. We use this observation to prove that the graph G obtained from the reduction has its bandwidth bounded by k • (k + 1). We explain how to obtain a labeling of G from that satisfies the bandwidth property. The underlying idea is to leave k free values between any two vertices labeled consecutively in the original labeling (i.e., vertices u and v such that (v) = (u) + 1) in order to label the vertices in V (G ) \ V (G).

More precisely, for all i > 1, we relabel the vertex labeled i in with the label 1 + (i -1) • (k + 1) in . Let u and v be two adjacent vertices of G with (u) < (v), then (v) -(u) ≤ k and thus (v)-(u) ≤ k •(k +1). Moreover, we label the new vertex z uv with label (u)+( (v)-(u)), which lies between (u)+1 and (u)+k by the bandwidth hypothesis. We also have (v)-(z uv ) < k•(k+1), and the bandwidth condition is satisfied. So the difference between the labels of any two adjacent vertices in G is at most k • (k + 1).

Observe however that not all vertices have k neighbors of higher label in G, and thus the labeling does not use consecutive values. To fix this, we just relabel the graph with values between 1 and |V (G )|, maintaining the ordering of . The new labeling obtained does not increase the distance from , and thus satisfies the bandwidth condition, as required.

Böttcher et al. observed that the pathwidth and thus the treewidth of a graph are bounded by its bandwidth [START_REF] Böttcher | Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs[END_REF]. Therefore, we immediately get from Theorem 6 that DSR TS is PSPACE-complete for bounded pathwidth and bounded treewidth graphs.

Polynomial-time algorithms

In this section, we focus on graph classes for which DSR TS can be solved in polynomial time. A natural way to solve this problem is to distinguish a special dominating set (that we call canonical) and then show that each dominating set can be reconfigured into this special one [START_REF] Haddadan | The complexity of dominating set reconfiguration[END_REF]. The canonical dominating set is not part of the original instance, so it is crucial to be able to compute it in polynomial time if we aim to compute the reconfiguration sequence in polynomial time. However, this is not an issue if we are only interested in the decision problem. We emphasize the fact that this canonical dominating set must be uniquely defined, i.e., the set of vertices that hold a token as well as the number of tokens on each of these vertices must be fixed.

Joins and cographs

In this section, we prove the following theorem, that is of special interest for the case of cographs. Recall that the domination number of a join G 1 + G 2 is always at most two, since taking a vertex from each operand of the join dominates the whole graph.

Theorem 7.

Let G 1 and G 2 be two graphs, and D s and D t be two dominating sets of G 1 + G 2 of the same size. The dominating set D s can be reconfigured into D t by token sliding if and only if one of the three following conditions holds:

(i) |D s | = |D t | ≥ 3, (ii) the domination number of G 1 or of G 2 is at most two, (iii) both G 1 and G 2 are connected.
Proof. We first show that if none of these conditions hold, then (G 1 + G 2 , D s , D t ) is a no-instance. Let G 1 and G 2 be two graphs with γ(G 1 ) > 2 and γ(G 2 ) > 2, and assume without loss of generality that G 1 is not connected, say with two components C 1 and C 2 . Note that γ(G 1 + G 2 ) = 2 since neither G 1 nor G 2 has a universal vertex.

Let D s = {u, v} and D t = {w, v} be two minimum dominating sets of G with u ∈ C 1 , w ∈ C 2 and v ∈ V (G 2 ). We prove that D s can not be reconfigured into D t . Since G 1 is not connected, there is no path between u and w in G[V 1 ]. Therefore, the only way to reach w from u is to go through V (G 2 ). But since γ(G 2 ) > 2 no pair of vertices in G 2 can dominate G 2 , and thus no move from V (G 1 ) to V (G 2 ) is possible.

We now prove that each of the above conditions is sufficient for the dominating sets to be reconfigured.

Condition (i) Suppose |D s | = |D t | ≥ 3.
Recall that picking a vertex of G 1 and one of G 2 always forms a dominating set of G 1 + G 2 . We infer that it is always possible to make one move from D s to reach a configuration with tokens in both G 1 and G 2 , then from such position tokens can be slid freely in their part, until reaching D t with a last move.

We assume now that

|D s | = |D t | ≤ 2.

Condition (ii)

For the case when G 1 or G 2 has domination number at most two, we consider different cases depending on whether a graph has domination number one or not.

Case 1. If γ(G 1 ) = 1 or γ(G 2 ) = 1: then G 1 + G 2 contains
a universal vertex. Then, from D s , one can place a token on this vertex, reconfigure other possible tokens freely, then move that token to reach D t .

Case 2. If γ(G 1 ) = 2 and γ(G 2 ) = 2. Assume without loss of generality that γ(G 1 ) = 2. Note that in this case, γ(G 1 + G 2 ) = 2, let D s = {v 1 , v 2 }.
We define an arbitrary canonical dominating set C by taking a vertex (e.g., of smallest index) in each of G 1 and G 2 ; we denote these vertices u 1 ∈ V (G 1 ) and u 2 ∈ V (G 2 ). Recall that each reconfiguration sequence is reversible. Hence, it is sufficient to prove that both D s and D t can been transformed into C. We only show this statement for D s ; the proof for D t follows by symmetry.

Suppose first that v 1 and v 2 belong to the same original graph, say

v 1 , v 2 ∈ V (G 1 ). We show how to reconfigure D s into C in at most two steps. First, observe that since C is a dominating set of G, u 1 ∈ N [{v 1 , v 2 }], say u 1 belongs to N [v 1 ]
. Our first step is to slide the token from v 2 to u 2 , along the corresponding edge of the join. Then, by our observation that u 1 ∈ N [v 1 ], we can slide if necessary the token from v 1 to u 1 .

Suppose now that v 1 and v 2 belong respectively to V (G 1 ) and V (G 2 ). Since γ(G 1 ) = 2, let {w 1 , w 2 } be a dominating set of G 1 and thus of G 1 + G 2 (it can be computed naively in cubic time. It dominates v 1 so assume without loss of generality that v 1 w 1 is an edge. First moving the token from v 1 to w 1 (if v 1 = w 1 ) and then from v 2 to w 2 , at most two steps permit us to reconfigure D s into {w 1 , w 2 }, which we can then reconfigure into C by the above argument.

Condition (iii)

Suppose finally that γ(G 1 ) ≥ 3 and γ(G 2 ) ≥ 3 but both G 1 and G 2 are connected. Then γ(G 1 + G 2 ) = 2 and the minimum dominating sets of G 1 + G 2 are exactly the sets containing a vertex in G 1 and a vertex in

G 2 . Let D s = {v 1 , v 2 } and D t = {w 1 , w 2 } with v 1 , w 1 ∈ V (G 1 ) and v 2 , w 2 ∈ V (G 2 ). Since G 1 is connected, there exists a path from v 1 to w 1 in G[V (G 1 )].
Moving the token along this path, we always keep a dominating set by the above observation. Doing similarly along a path from v 2 to w 2 , we have a reconfiguration sequence from D s to D t .

We now consider the special case of cographs. Recall that the family of cographs can be defined as the family of graphs with no induced P 4 , or equivalently by the following recursive definition:

• K 1 is a cograph; • for G 1 and G 2 any two cographs, the disjoint union G 1 ∪ G 2 is a cograph; • for G 1 and G 2 any two cographs, the join G 1 + G 2 is a cograph.
Brandelt and Mulder gave in [START_REF] Bandelt | Distance-hereditary graphs[END_REF] an alternative characterization of cographs: G is a cograph if and only if G is the disjoint union of distance-hereditary graphs with diameter at most two. Note that computing a minimum dominating set in distance-hereditary graphs is linear-time solvable [START_REF] Nicolai | Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs[END_REF]. Hence, we can compute the domination number of a cograph in linear time as well.

By the previous theorem, we infer that if a cograph is constructed as a join of two cographs, the case is polynomial-time decidable. The case when disjoint union of two cographs, then for two dominating sets D s and D t , deciding whether D s TS D t is equivalent to deciding whether

G = K 1 , is straightforward. If G = G 1 ∪ G 2 is the v 8 v 7 v 6 v 5 v 3 v 4 v 2 v 1
D s ∩ V (G 1 ) TS D t ∩ V (G 1 ) in G 1 , and D s ∩ V (G 2 ) TS D t ∩ V (G 2 ) in G 2
, which can be done inductively by induction. As a consequence, we obtain the following:

Theorem 8. There is a polynomial-time algorithm deciding DSR TS in cographs.

Dually chordal graphs

Let G = (V, E) be a graph with V = {v 1 , v 2 , . . . , v n }. We denote by G i the graph G[{v i , v i+1 , . . . , v n }]. A maximum neighbor of a vertex u is a vertex v ∈ N [u] such that we have N [w] ⊆ N [v] for every vertex w ∈ N [u].
In other words, v contains in its closed neighborhood every vertex at distance at most two from u. A maximum neighborhood ordering (or mno for short) is an ordering of the vertices in such a way that v i has a maximum neighbor in the graph G i . A graph is dually chordal if it has a maximum neighborhood ordering. This ordering can be computed in linear time [START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF]. Moreover, the mno computed by this algorithm is such that for every vertex v i (with i < n), v i s maximum neighbor is different from v i (for connected graphs). An alternative proof of a similar statement for not necessarily connected graphs can be found in [START_REF] Dorbec | The domination game played on unions of graphs[END_REF]. In the following, we always assume that an mno is associated with a function mn : V -→ V that associates with each vertex a maximum neighbor. Note that a dually chordal graph is not necessarily chordal. Figure 6 gives an example of a graph which is dually chordal but not chordal, since it contains an induced cycle on four vertices. The label inside each vertex corresponds to its rank in the ordering, and its maximum neighbor is the endpoint of its single outgoing edge (note that v 8 's maximum neighbor is itself). Moreover, observe that any tree T is a dually chordal graph: root the tree in some vertex and orient all edges toward the root; any numbering keeping all G i connected is an mno where arcs point towards the vertex maximum neighbor.

Link with interval graphs. An interval graph is the intersection graph of a family of intervals on the real line. In other words, let {I 1 , I 2 , . . . , I n } be a set of intervals. Each interval I can be represented by its extremities (I), r(I) with (I) ≤ r(I) ∈ R. We call these values respectively the -value and r-value (for left and right). The corresponding interval graph G = (V, E) is the following:

• V = {I 1 , I 2 , . . . , I n }; • I i I j ∈ E ⇔ I i ∩ I j = ∅, i.e., (I j ) ≤ r(I i ) and (I i ) ≤ r(I j ).
Let G = (V, E) be an interval graph. For convenience, we denote by v i the vertex related to the interval I i . We now order the vertices of G with respect to their r-values, i.e., v i < v j if and only if r(I i ) < r(I j ) (or r(I i ) = r(I j ) and (I i ) < (I j )). Then, we get the following useful property:

Observation 9. Let v i and v j be two vertices of G such that v i < v j . If v i v j ∈ E, then for any v k such that v i < v k < v j , we have v k v j ∈ E.
Proof. Since v i < v k < v j , we have r(I i ) ≤ r(I k ) ≤ r(I j ). Since v i v j is an edge, (I j ) ≤ r(I i ). Thus, we get that (I j ) ≤ r(I k ). Adding that (I k ) ≤ r(I k ) ≤ r(I j ), the conclusion follows. Proof. To see this observation, we prove that the ordering described above is an mno. For every vertex v i , we show that its neighbor of maximum index v j in the ordering is a maximum neighbor. Indeed, consider any neighbor v k of v i in G i . By definition of v j , we have v i < v k ≤ v j , and v k is adjacent to v j . Moreover, any other neighbor v > v i of v k either satisfies v i < v < v j or v k < v j < v . In both cases, Observation 9 concludes the proof.

An example of the construction used above on an interval graph is given in Figure 7 where the maximum neighbor of I i is its only out-neighbor (the endpoint of the only directed edge incident to I i ).

Computing the canonical dominating set. Let G be a dually chordal graph, whose vertices are ordered by an mno. Let C = {c 1 , c 2 , . . . , c k } be a dominating set of G and T = {t 1 , t 2 , . . . , t k } a set of vertices, both sets in increasing order according to the mno. We say that C is a triggered dominating set with triggering vertices T if and only if:

(i) c i = mn(t i ) for all 1 ≤ i ≤ k,
(ii) following the mno, t i is the least vertex not in N [c 1 , . . . , c i-1 ], for all 1 ≤ i ≤ k.

It is known that the MINIMUM DOMINATING SET problem is linear-time solvable on dually chordal graphs [START_REF] Brandstädt | The algorithmic use of hypertree structure and maximum neighbourhood orderings[END_REF]. In our case, we give another algorithm to compute a triggered dominating set, that will serve as a canonical dominating set.

Observe that an mno is associated with exactly one triggered dominating set. The following algorithm, called MDS, is strongly inspired by the classical algorithm for computing minimum dominating sets in trees [START_REF] Mitchell | Linear algorithms on recursive representations of trees[END_REF]. It takes as input a dually chordal graph G = (V, E) with an mno and computes a triggered dominating set C of size γ(G) and its corresponding set of triggering vertices T in running time O(|V | + |E|).

Lemma 11 is devoted to proving the correctness of the algorithm MDS. Proof. The fact that C is a triggered dominating set with triggering vertices T is a direct consequence of the construction of the algorithm. Statement (i) comes from line 5 of the algorithm, while statement (ii) simply comes from the fact that we deal with the vertices in increasing order in the loop of line 3. Still we need to prove that this dominating set is of size γ(G).

A labeled graph is a graph whose vertices are labeled FREE, REQUIRED or BOUNDED, such that a vertex is labeled FREE if and only if it is adjacent to a vertex labeled REQUIRED and it is not labeled REQUIRED. Observe that the algorithm MDS maintains all along a labeled graph. In a labeled graph, we define a labeled dominating set a set of vertices containing all the vertices labeled REQUIRED and dominating all vertices labeled BOUNDED. The labeled domination number is the minimum size of a labeled dominating set. We show that the algorithm MDS keeps the labeled domination number of the graph invariant. At the beginning, when all the vertices are labeled BOUNDED, the labeled domination y i ← mn(x i )

9:

x i TS y i 10:

y i TS c i 11:
end if 12: end for Proof. Let T = (t 1 , t 2 , . . . , t γ ) and C = {c 1 , c 2 , . . . , c γ } be the output of algorithm MDS, with c i = mn(t i ). We denote by C i = {c 1 , . . . , c i } the set of i first vertices of C according to the mno.

In order to prove the correctness of the algorithm, we need to prove that the two following constraints are satisfied: (i) each move is valid with respect to the token sliding model;

(ii) every intermediate set is a dominating set of G. (Note that this ensures the existence of the x i of line 4.)

We prove these two properties by induction on the index i (0 < i ≤ γ). For some i > 0, assume that the algorithm reconfigured properly D into D i-1 = (D \ {x 1 , . . . , x i-1 }) ∪ {c 1 , . . . , c i-1 } . We explain how to extend this up to rank i. By definition, t i is the least vertex which is not dominated by N [C i-1 ] = N [{c 1 , . . . , c i-1 }]. Let x i be the least vertex dominating t i in D. Observe that x i / ∈ {c 1 , . . . , c i-1 } since t i is the triggering vertex of c i . To simplify notation, we denote by G the subgraph of G induced by vertices larger than t i in the mno (i.e., the subgraph G j where j is the index of t i in the mno). Note that since C i-1 ⊂ D i-1 , all vertices in G \ G are dominated. We consider two cases: Case 1. x i is adjacent to c i . Observe first that this case occurs whenever x i ≥ t i in the mno (where

x i ∈ N G [t i ] ⊆ N G [c i ]).
In that case, the algorithm executes line 6 and the token sliding constraint (i) is satisfied. Now, since c i = mn(t i ) and x i is adjacent to t

i , N G [x i ] ⊆ N G [c i ],
and constraint (ii) is also satisfied. The conclusion follows from the fact that all vertices in G \ G are dominated. Case 2. x i is not adjacent to c i . This is possibly the case when x i < t i in the mno. The algorithm then first reconfigures x i into its maximum neighbor y i , which is adjacent to x i and dominates all neighbors of x i that might not be dominated yet by {c 1 , . . . , c i-1 }, satisfying constraint (ii). Moreover, x i is adjacent to t i and x i < t i in the mno, so y i , as the maximum neighbor of x i , must be adjacent to t i and all its neighbors in G , among which there is c i . So the next move to c i satisfies the token sliding constraint (i). Also, since y i is adjacent to t i and c i is the maximum neighbor of t i , N G (y i ) ⊆ N G [c i ], and constraint (ii) is also satisfied. This concludes the proof.

Theorem 13. DSR TS can be solved in quadratic time on dually chordal graphs.

Proof. Let G = (V, E) be a dually chordal graph and D s , D t be two dominating sets of G of size k (i.e., (G, D s , D t ) is an instance of the DSR TS problem). Assume that G is connected (otherwise we proceed independently for each connected component, checking first that the number of tokens on each component fit). We explain how to reconfigure D s into D t in at most quadratic time.

First, we compute in linear time the canonical dominating set C of G with the algorithm MDS. By Lemma 12, one can transform D s and D t in such a way that both contain C. This can be done in linear time (with respect to the order of G) since we move at most γ(G) tokens and each move requires at most two steps. If k = γ(G), we are done. Otherwise, choose a vertex v of minimum eccentricity and move all the remaining tokens by a shortest path to v. Therefore, the total time complexity is

O(|V | + |E|) + O(|V |) + O((k -γ(G)) • (v))
, which is at most quadratic (when k = Ω(n)).

Observe that when k is close to γ, the algorithm is linear. However, when the number of extra tokens is large (i.e., is linear in n), the quadratic overhead may be necessary. Indeed, consider a path on n vertices P n . The minimum eccentricity of P n is that of the middle vertex v which is n/2 . Therefore, if all the extra tokens are on an extremity of the path, the time needed to move all of them to v is quadratic. Since a path is a dually chordal graph, the conclusion follows.

Open questions

In all of our polynomial results presented in Section 4, computing a minimum dominating set can be done in polynomial or even linear time on the graph classes considered. Therefore, a challenging question is the following: does there exist a graph class for which computing a minimum dominating set is NP-complete but DSR TS can be solved in polynomial time? As a result of Theorem 13, we get that DSR TS is polynomial-time solvable on interval graphs. Recall that a circle graph is the intersection graph set of chords of a circle. The DOMINATING SET PROBLEM has been shown to be NP-complete on this graph class [START_REF] Keil | The complexity of domination problems in circle graphs[END_REF]. Hence, we ask the following question: Question 1. What is the complexity of DSR TS on circle graphs?

If the answer is positive, note that it would generalize our result on cographs. A circular-arc graph is the intersection graph of a set of arcs on the circle. Even if computing a minimum dominating set can be computed in linear time on circular-arc graphs [START_REF] Shang | Efficient algorithms for the domination problems on interval and circular-arc graphs[END_REF], we are interested in the complexity of the reconfiguration version under token sliding. More precisely, we ask for the following: Question 2. Is DSR TS polynomial-time solvable on circular-arc graphs?

Besides, we found polynomial-time algorithms for cographs and dually chordal graphs but the underlying reconfiguration sequence is most likely not optimal. Indeed, it may be possible that the shortest path in R k (G) between the two given solutions does not go through the canonical dominating set. Therefore, can we bound the diameter of the reconfiguration graph? In other words, what is the maximum length of a shortest reconfiguration sequence between any pair of dominating sets? Moreover, what is the complexity of finding the optimal solution, i.e., the shortest reconfiguration sequence between two dominating sets on cographs or dually chordal graphs? Is it polynomial-time solvable, as the reachability variant studied here? Or does it become harder?

Figure 1 :

 1 Figure 1: Our results: the frontier between PSPACE-completeness and tractability.

Figure

  Figure 2: Example of TS-sequence from D s to D t .

3 Figure 3 :

 33 Figure 3: Graph G 3 .

Figure 4 :

 4 Figure 4: Example for the reduction of Theorem 4.

Figure 5 :

 5 Figure 5: Example for the reduction of Theorem 5.

Figure 6 :

 6 Figure 6: A dually chordal graph.

Observation 10 .

 10 Interval graphs are dually chordal graphs.

Figure 7 :

 7 Figure 7: Interval graph and its maximum neighborhood ordering.

Lemma 11 .

 11 Given a dually chordal graph G = (V, E), the algorithm MDS computes a triggered dominating set of G of order γ(G) in time O(|V | + |E|).

  2: Example of TS-sequence from D s to D t .it makes a difference: consider the star graph S n on n + 1 vertices and two dominating sets D 1 andD 2 of S n of size k, with k ∈ [2, n -1].Any dominating set of that size necessarily contains the central vertex. To reconfigure D 1 into D 2 , we are forced to move a token from one leaf to another, which can only be done by going through the central vertex which already contains a token. Given such artificially negative examples, we choose to allow the superposition of tokens on a vertex. Note that this question did not arise in previous papers considering the token sliding model, to the best of our knowledge.

  Algorithm 2 DUALLY-CHORDAL-RECONF Require: A dually chordal graph G = (V, E), a minimum dominating set D of G 1: Compute an mno for G 2: (C, T ) ← MDS(G). Let x i be the least vertex of D ∩ N [t i ]

	4:
	5:	if x i c i ∈ E then
	6:	x i	TS c i
	7:	else
	8:

3: for i from 1 to γ(G) do

Acknowledgements

We thank the anonymous referees for several remarks which helped improve the presentation of this paper. This work was supported by ANR project GraphEn (ANR-15-CE40-0009).

Algorithm 1 MDS

Require: A dually chordal graph G with an mno. Ensure: A minimum triggered dominating set C and its set of triggering vertices T .

1: Mark all vertices BOUNDED 2: C ← ∅ 3: for all i from 1 to n do 4:

label mn(v i ) with REQUIRED 6:

Add v i to the set of triggering vertices T 7:

if u is not labeled REQUIRED then 9:

Label u with FREE

end if 16: end for 17: return C and T number of the graph is exactly its domination number. This will allow us to conclude that the set of vertices marked REQUIRED at the end forms a minimum dominating set of G, of order γ(G).

Let S be a minimum labeled dominating set of a labeled graph G, and let v i be the minimum vertex in the mno that is labeled BOUNDED. Let w be the maximum neighbor of v i in G i . If w ∈ S, then S is also a minimum labeled dominating set of the graph G where w is labeled REQUIRED and all its neighbors previously labeled BOUNDED are labeled FREE, so the algorithm does not change the labeled domination number of G. Otherwise, say v j is the vertex that dominates v i in S. Since v i is marked BOUNDED, v j is not marked REQUIRED. If j ≥ i, then by the maximum neighbor property, w is adjacent to all the neighbors of v j that are in G i , so w dominates all neighbors of v j that are still marked BOUNDED. Thus we can replace v j by w in S and keep a minimum labeled dominating set of G. This concludes the case j ≥ i. Suppose now j < i. Consider v k the maximum neighbor of v j in G j . Observe that since no vertex less than v i is BOUNDED, by the maximum neighbor definition, v k dominates any BOUNDED vertex adjacent to v j . Thus, we can again replace v j by v k in S and keep a minimum dominating set. We can iterate until the vertex dominating v i in S is no less than v i , and then refer to the above argument, used when j ≥ i. This concludes the proof that the algorithm MDS keeps the labeled domination number of the graph invariant, and thus that it produces a minimum dominating set of G.

For the time complexity of the algorithm, observe that the algorithm visits every vertex at most once in the main loop, and it visits the neighborhoods of each vertex at most once when it possibly labels it REQUIRED. So the complexity is upper bounded by v∈V O(1

The reconfiguration algorithm. We show how to use the canonical triggered dominating set C computed by the MDS algorithm in order to reconfigure two dominating sets of a dually chordal graph. To do that, we provide an algorithm called DUALLY-CHORDAL-RECONF that modifies any dominating set D of a dually chordal graph in such a way that C ⊆ D. The idea of this algorithm is to pick one vertex in D that dominates the triggering vertex t i (from the output of algorithm MDS) and to replace it by the corresponding vertex c i of C. Recall that the notation u TS v is used for sliding the token along the edge uv.


Olivia Chitarra

Marie-Aline Martin-Drumel

Zachary Buchanan

Olivier Pirali

Rotational and vibrational spectroscopy of 1-cyanoadamantane and 1-isocyanoadamantane

Keywords: Cyano-adamantanes, Rotational and vibrational spectroscopy, Astrophysical relevance

Because of their high stability, the presence of diamond-type molecules has long been suspected in the interstellar medium, a hypothesis supported by the extraction of diamond nanocrystal from some meteorites. We report the rotational and vibrational investigation of two polar derivatives of adamantane (C 10 H 16 ), 1cyanoadamantane (C 10 H 15 -CN) and 1-isocyanoadamantane (C 10 H 15 -NC), using room temperature gas phase absorption spectroscopy. Pure rotational spectra have been recorded at millimeter wavelengths (75-220 GHz) while vibrational spectra were obtained in the far-and mid-infrared domains (50-3500 cm -1 ). Quantum chemical calculations have been performed on these two C 3v rotors to support the spectral analysis enabling the assignment, for both species, of more than 7000 pure rotational transitions in the ground (A 1 symmetry) and first vibrationally excited (E symmetry) states, and of most of the infrared active bands. The pure rotational lines were fit to their experimental accuracy using a symmetric-top Hamiltonian. Our study provides all necessary information for an active search of these species in space.

Introduction

Diamond-related materials relevance for a wide range of different research areas has motivated a great wealth of studies on these compounds since decades. Within this very large variety of materials, diamondoids possess tridimensional sp3 hybridized carbon cage structures terminated by hydrogen * olivia.chitarra@universite-paris-saclay.fr atoms conferring exceptional electronic, optical, and mechanical properties to these systems [START_REF] Demján | Electronic and optical properties of pure and modified diamondoids studied by many-body perturbation theory and time-dependent density functional theory[END_REF][START_REF] Landt | Optical response of diamond nanocrystals as a function of particle size, shape, and symmetry[END_REF][START_REF] Mansoori | Diamondoid molecules[END_REF] which have received strong interest for various applications such as material science, biomedecine, nanotechnology, and environmental science (see, e.g., reviews on the synthesis and applications of diamondoids in Refs. [START_REF] Schwertfeger | Diamonds are a chemist's best friend: Diamondoid chemistry beyond adamantane[END_REF][START_REF] Stauss | Diamondoids: Synthesis, Properties, and Applications[END_REF]). In the context of astrochemistry, these molecules have long been suspected to be present in various objects of the universe. Early 1969, based on the high stability of these samples and their resistance to UV photons, Saslaw and Gaustad [START_REF] Saslaw | Interstellar dust and diamonds[END_REF] proposed diamond-like particles to be an important part of the gas and dust material present in space. This hypothesis was confirmed in 1987 by Lewis et al. [START_REF] Lewis | interstellar diamonds in meteotites[END_REF], who extracted nanometer sized diamond material from meteorites, and more recently by Jones et al. [START_REF] Jones | Surface CH stretch features on meteoric nanodiamonds[END_REF], who demonstrated the large abundance of these samples in primitive meteorites. In the interstellar medium, a striking agreement between the absorption spectra of synthetic nanodiamond thin films [START_REF] Chang | Infrared spectroscopy and vibrational relaxation of CHx and CDx stretches on synthetic diamond nanocrystal surfaces[END_REF][START_REF] Sheu | Laboratory investigation of hydrogenated diamond surfaces: implication for the formation and size of interstellar nanodiamonds[END_REF] with the unusual emission bands located at 3.43 µm and 3.53 µm of few Herbig AeBe stars (in particular HD 97048 and Elias 1) has been reported by Guillois et al. [START_REF] Guillois | Diamond Infrared emission bands in circumstellar media[END_REF]. To provide complementary insights into the size and structure of the proposed emitters, solid state as well as gas phase infrared (IR) spectroscopy were performed on pure diamondoids, at the molecular level, in the group of J. Oomens [START_REF] Oomens | Infrared spectroscopic investigation of higher diamondoids[END_REF][START_REF] Pirali | Infrared spectroscopy of diamondoid molecules: New insights into the presence of nanodiamonds in the interstellar medium[END_REF]. These samples, ranging from adamantane (C 10 H 16 ) to hexamantane (C 26 H 30 ), were provided by the group of Carlson et al. who succeeded in isolating pure samples of large diamondoids using successive distillation processes in petroleum [START_REF] Dahl | Isolation and structure of higher diamondoids, nanometer-sized diamond molecules[END_REF]. It is important to note that even though the chemical syntheses of adamantane and some of its derivatives are known since 1957 [START_REF] Schleyer | A simple preparation of adamantane[END_REF] and that several of these samples are commercially available nowadays, the laboratory synthesis of larger diamondoids only exists for diamantane (2 cages, C 14 H 20 ) [START_REF] Fǎrcaşiu | Stepwise elaboration of diamondoid hydrocarbons. synthesis of diamantane from adamantane[END_REF], triamantane (3 cages, C 18 H 24 ) [START_REF] Hollowood | Synthesis of Triamantane[END_REF], tetramantane (4 cages, C 22 H 28 ) [START_REF] Dahl | Synthesis of higher diamondoids and implications for their formation in petroleum[END_REF], and pentamantane (5 cages, C 26 H 32 ) [START_REF] Dahl | Synthesis of higher diamondoids and implications for their formation in petroleum[END_REF]; the field thus remains very active in organic chemistry because of the exceptional properties of these materials [START_REF] Schwertfeger | Diamonds are a chemist's best friend: Diamondoid chemistry beyond adamantane[END_REF]. The relatively recent access to pure molecular samples of large diamondoids from the Carlson group (up to undecamantane, 11 cages), opened the possibility to characterize their optical properties in the astrophysical context [START_REF] Bauschlicher | Electronic and vibrational spectroscopy of diamondoids and the interstellar infrared bands between 3.35 and 3.55 µm[END_REF] and compare it to the infinite diamond lattice [START_REF] Landt | Optical Response of Diamond Nanocrystals as a Function of Particle Size, Shape, and Symmetry[END_REF]. In addition to all these spectroscopic characterizations of the neutral molecules, laser-based IR multi-photon dissociation spectra were obtained for the dehydrogenated cationic forms of adamantane [START_REF] Polfer | The infrared spectrum of the adamantyl cation[END_REF] as well as diamantane and triamantane [START_REF] Pirali | Infrared spectra and structures of diamantyl and triamantyl carbocations[END_REF].

Similarly to the well studied polycyclic aromatic hydrocarbons (PAHs) species, the smallest samples of the diamondoid family lack permanent dipole moment (the lightest diamondoid which exhibits a relatively small permanent dipole moment is tetramantane) preventing their searches in the interstellar medium using powerful radioastronomy observational platforms (e.g., GBT, NOEMA, ALMA). In the laboratory, rotational structure information on the smallest samples, e.g., the tetrahedral species adamantane and its N-substituted derivative hexamethylenetetramine (C 6 H 12 N 4 ), has been obtained using gas phase mid-IR and far-IR spectroscopy techniques.

Spectra recorded at the SOLEIL synchrotron facility enabled the observation of the most intense IR-active bands in the 400-1500 cm -1 range [START_REF] Pirali | Rotationally resolved infrared spectroscopy of adamantane[END_REF][START_REF] Pirali | Rotationally resolved IR spectroscopy of hexamethylenete-tramine (HMT) C 6 N 4 H 12[END_REF][START_REF] Pirali | Synchrotron-based Fourier transform spectra of the ν 23 and ν 24 IR bands of hexamethylenetetramine C 6 N 4 H 12[END_REF] while the powerful technique of buffer gas cooling allowed the investigation of the congested 3 µm region in rotationally cold conditions [START_REF] Spaun | Continuous probing of cold complex molecules with infrared frequency comb spectroscopy[END_REF]. The recent interstellar detections of several hydrocarbons containing a cyano functional group by the GOTHAM team, i.e., benzonitrile (c-C 6 H 5 -CN) [START_REF] Mcguire | Detection of the aromatic molecule benzonitrile (c-C 6 H 5 CN) in the interstellar medium[END_REF][START_REF] Burkhardt | Ubiquitous aromatic carbon chemistry at the earliest stages of star formation[END_REF], cyanocyclopentadiene (c-C 5 H 5 -CN) [START_REF] Mccarthy | Interstellar detection of the highly polar five-membered ring cyanocyclopentadiene[END_REF], the cyanopolyyne HC 11 N [START_REF] Loomis | An investigation of spectral line stacking techniques and application to the detection of HC 11 N[END_REF], and cyanonaphthalenes (C 10 H 7 -CN [START_REF] Mccarthy | Interstellar detection of the highly polar five-membered ring cyanocyclopentadiene[END_REF][START_REF] Loomis | An investigation of spectral line stacking techniques and application to the detection of HC 11 N[END_REF]) open up the possibility of detecting other families of functionalized large C-bearing species possessing a strong permanent dipole moment.

In this context, we have investigated the rotational and vibrational absorption spectra of the 1cyanoadamantane (C 10 H 15 CN, hereafter AdaCN) and 1-isocyanoadamantane (C 10 H 15 NC, hereafter AdaNC) molecules (Fig. 1). To our knowledge, a single high resolution spectroscopic investigations has been reported on these samples. Chadwick et al. [START_REF] Chadwick | Microwave-spectra and strcutures of 1-cyano-Adamantane and 1-iodo-Adamantane[END_REF] measured 4 transitions of AdaCN, with unresolved K structures, around 30 GHz allowing a first estimation of the B rotational constant in the ground and 3 vibrationally excited states. In the present work, the pure rotational spectra of AdaCN and AdaNC have been recorded at room temperature in the millimeter-wave region allowing the determination of accurate rotational constants in the ground and first excited vibrational states. In addition, we measured their gas-phase vibrational spectra in the 50-3500 cm -1 spectral range at room temperature and we performed quantum chemical calculations to support the analysis. The paper contains the experimental and computational details in section 2, the results and discussion are presented in section 3.

Laboratory methods

Samples

Samples of AdaCN (97 % purity) and AdaNC (95 % purity) were purchased from Sigma Aldrich and used without further purification.

Infrared spectroscopy

The vibrational spectra of AdaCN and AdaNC have been recorded on the AILES beamline of SOLEIL synchrotron using a Fourier-transform interferometer (Bruker IFS 125) and a long absorption pathlength cell; an experimental set-up often employed to record absorption spectra of relatively large molecules (see for example Ref. [START_REF] Martin-Drumel | Low-energy vibrational spectra of flexible diphenyl molecules: biphenyl, diphenylmethane, bibenzyl and 2-, 3-and 4phenyltoluene[END_REF]). In the mid-IR range (600-3000 cm -1 ), the interferometer was equipped with a KBr beamsplitter together with a liquid-nitrogen cooled HgCdTe detector, and in the far-IR range (50-600 cm -1 ) a 6 µm mylar composite beamsplitter and a liquid He cooled bolometer detector were used. The room temperature vapor pressure (a few µbar) of the samples was injected in the multi-pass cell allowing for 150 m absorption pathlength. The set of windows separating the absorption cell and the FT interferometer were made of ZnSe (0.5 °wedged) when recording the mid-IR spectra and of 50 µm thick polypropylene films when recording the far-IR spectra.

The black upper traces of Fig. 2 show the absorption spectra of both AdaCN and AdaNC recorded in the far-IR and mid-IR spectral ranges, respectively. The spectra consist of the co-addition of 500 scans recorded with a spectral resolution of 1 cm -1 . Because the vibrational bands are broad, yielding rotationally unresolved features, we estimate the accuracy of the band positions to be a few cm -1 in average for all the bands. Attempts to resolve the rotational structure of the far-IR bands have been undertaken using the synchrotron radiation extracted by the AILES beamline and the highest spectral resolution of the FT interferometer (about 30 MHz), without success. The high density of lines and the presence of numerous hot bands, involving several quanta of low frequency modes populated at room temperature, are causing significant spectral congestion.

Millimeter-wave spectroscopy

The rotational spectra of both molecules were recorded using an absorption set-up adapted to investigate the millimeter and sub-millimeter wave spectra of non reactive species [START_REF] Pirali | Characterization of isolated 1-aza-adamantan-4-one (C 9 H 13 NO) from microwave, millimeter-wave and infrared spectroscopy supported by electronic structure calculations[END_REF]. The spectrometer consists of a radio-frequency synthesizer feeding a solid-state multiplication chains from Radiometer Physics GmbH (RPG) or Virginia Diode Inc. (VDI) covering the 75-950 GHz range. The absorption cell is a 2 m long, 50 mm inner diameter Pyrex tube equipped with Teflon windows at both ends. The spectra were recorded in the 75-220 GHz range, where the most intense absorption signals are expected at room temperature for both species. We used a frequency modulation scheme associated with a second harmonic phase sensitive lock-in detection. The modulation frequency was set to 48.157 kHz for all recordings. The modulation depth, the time constant, and the frequency steps depend on the spectral region studied, on the absorption signal, and on the line density of the spectrum. The vapor pressure of both samples (in the µbar range at room temperature) was injected in the cell using a constant slow flow of gas ensured by a turbomolecular pump. To record the absorption spectrum of AdaCN in the 75-110 GHz, we injected about 3.3 µbar of the sample in the cell; we chose a modulation depth corresponding to 130 kHz, a time constant of 100 ms, and a frequency step of 30 kHz. In the 140-220 GHz range, the pressure was 1.7 µbar, the frequency depth was set to 260 kHz, the time constant was 20 ms, and the frequency step was 30 kHz. For the 75-110 GHz spectrum of AdaNC, the pressure was 1.7 µbar, the frequency depth was 130 kHz, the frequency step was set to 30 kHz, the time constant was 100 ms. Finally, we used a 260 kHz frequency depth, 50 kHz frequency step, and 50 ms time constant to record the AdaNC spectrum in the 140-220 GHz range. The line position accuracy is estimated based on the signal-to-noise ratio of the transitions: for AdaCN a unique value of 30 kHz is used over the whole spectral range while for AdaNC 30 kHz and 50 kHz are used in the 75-110 GHz and 140-220 GHz ranges, respectively. The black traces of Fig. 3 show a portion of the pure rotation spectrum of AdaCN recorded in our work. The left part of the figure shows a portion recorded in the 166.5-171 GHz region, where 3 dense clusters of a-type transitions involving the ground vibrational state (GS) as well as few excited states (ES) populated at room temperature can be clearly observed. The right part of the figure gives a zoom into one K ladder involving GS pure rotation transitions with J = 99.

Quantum chemical calculations

In order to support the analysis of the rotational and vibrational spectra of AdaCN and AdaNC, we performed quantum chemical calculations using the Gaussian09 software [START_REF] Frisch | Gaussian 09 Revision B.01[END_REF]. Geometry optimization as well as the energies of vibrational states in the harmonic approximation were calculated using MP2 method and cc-pVTZ basis set [START_REF] Dunning | Gaussian basis sets for use in correlated molecular calculations .1. The atoms boron through neon and hydrogen[END_REF]. The optimized equilibrium structures are reported in the supplementary material and represented on Fig. 1.

Results and discussion

Spectroscopic considerations

Both AdaCN and AdaNC molecules belong to the C 3v group of symmetry and possess a 1 A 1 electronic ground state, 75 vibrational degrees of freedom, and 50 vibrational modes. The irreducible representation for the vibrational modes is:

Γ = 17 A 1 ⊕ 8 A 2 ⊕ 25 E (1)
The A 1 and E vibrational bands are labeled parallel and perpendicular bands, respectively. Those of A 2 symmetry are IR inactive. Concerning the rotational structure of the molecules, both species are symmetric tops with calculated permanent dipole moments along the a axis of symmetry of 4.9 Debye for AdaCN and 4.2 Debye for AdaNC. We used the conventional equation to calculate the energy levels of both molecules in their GS and ES [START_REF] Gordy | Microwave Molecular Spectra[END_REF] as implemented in the Pickett's CALPGM software:

Ev(J, K, l) =BvJ(J + 1) + (Av -Bv)K 2 (2)
-DJ v J 2 (J + 1) 2 -DJK v J(J + 1)K 2 -DK v K 4 -2AvKlζ + 2[(2DJ v + DJK v )J(J + 1) + (2DK v + DJK v )K 2 ]Klζ + P (J, K, l) + ...
with :

P (J, K, l) = ± [J(J + 1) -K(K ∓ 1)] 8(K ∓ 1) (3)
× [J(J + 1) -(K ∓ 1)(K ∓ 2)] [(1 -ζ)Av -Bv] q 2 (4)
where :

q ≈ 2B 2 v ω (5)
In equations ( 3)-( 5), J and K are the rotational quantum numbers; A and B the rotational constants; D J , D JK , and D K the centrifugal distortion constants; v denotes the vibrational state. For singly degenerated states of A 1 symmetry, ζ = 0 and P (J, K, l) = 0. For E degenerated vibrational states (e.g., v 50 = 1 in our study), the q parameter is the l-type doubling parameter, ζ is the Coriolis coupling constant, and ω is the fundamental vibrational frequency of the considered E state.

Assignment of the vibrational spectra

Figure 2 contains panels corresponding to the spectra recorded in the far-IR (upper panels) and mid-IR (middle and lower panels) of AdaCN and AdaNC, plotted in absorbance. At the spectral resolution used, the rotational contour (P-, Q-, Rbranches) is distinguishable for some of the bands. Below the experimental spectra (black traces), we plotted the calculated positions and intensities of fundamental parallel bands (involving upper states of A 1 symmetry) in red, and perpendicular bands (involving upper states of E symmetry) in blue. We initially performed a simulation of the rotational contour of these calculated bands using the PGOPHER software [START_REF] Western | PGOPHER: A program for simulating rotational, vibrational and electronic spectra[END_REF], but many Q-branches of simulated parallel bands showed largely overestimated intensities (most likely because the same rotational constants were used for the upper and lower states) which complicated the assignment procedure rather than supported it. We preferred comparing the experimental trace with simple vertical bars corresponding to the frequencies and intensities of the calculated vibrational bands, directly available from the output files of Gaussian. Using this graphical comparison, we report in table 1 the proposed band assignments of the IR spectra for both molecules.

At first sight, the vibrational spectra of both AdaCN and AdaNC are very similar to the parent adamantane molecule and higher diamondoid species [START_REF] Oomens | Infrared spectroscopic investigation of higher diamondoids[END_REF]. For both species, several intense (more than 100 km/mol) CH stretching modes absorb in the 3000 cm -1 region leading to two distinct features located around 2860 cm -1 and 2930 cm -1 and dominating the IR spectrum. All the other bands appear much weaker (few km/mol) with the exception of the scissoring mode bands located at about 1500 cm -1 (ν 7 and ν 31 ) with calculated intensities of about 20 km/mol for both species. In the case of AdaNC, an additional intense band corresponding to the CCN asymmetric stretching mode (ν 5 ) is calculated at 2108 cm -1 with an intensity of 78 km/mol. It is assigned to the 2133 cm -1 feature in the experimental spectrum with good confidence. In the case of AdaCN, the equivalent asymmetric stretching mode appears very weak both in the calculated and experimental spectra, but an intense feature is detected at about 1718 cm -1 and has no counterparts in the calculated spectrum. Because of its location and intensity, this band most likely arises from a contaminant containing a carbonyl group. The vibrational bands associated to CO stretching modes are extremely intense and a band at a similar energy (1740 cm -1 ) has been observed for the CO stretching mode of 1-aza-adamantan-4one (C 9 H 13 NO) [START_REF] Pirali | Characterization of isolated 1-aza-adamantan-4-one (C 9 H 13 NO) from microwave, millimeter-wave and infrared spectroscopy supported by electronic structure calculations[END_REF] which was the most intense feature of its IR spectrum. In the hypothesis that the 1718 cm -1 feature arises from a molecule similar to adamantanone (C 10 H 14 O), its vibrational spectrum certainly affects other spectral regions of the AdaCN spectrum, in particular the CH stretching mode regions. We were not able to identify unambiguously any additional vibrational bands to guide our search for the nature of the impurity present in our sample.

Beside the relatively intense bands discussed above, the mid-IR experimental spectra exhibit several weaker bands located between 900 and 1400 cm -1 . The comparison with the calculated spectra allows us to propose assignments for some of these features (Table 1).

The far-IR spectra of both molecules (see the upper panel of figure 2) exhibit weak absorption bands corresponding mostly to deformations of the carbon cages. The calculated spectra are in good agreement with our experimental recordings and allow us to propose several relatively secure assignments. Note that for both AdaCN and AdaNC, the lowest frequency mode located around 135 cm -1 is assigned to a wagging of the CN group with respect to the rest of the carbon cage (ν 50 ). They are actually the most intense bands observed in the far-IR region (with calculated intensities of about 10 km/mol).

In absence of anharmonic calculations, the Calc./Exp. values can be compared with scaling factors commonly used in the literature [see, e.g., Ref. 12]. For both species, in the CH stretching region we obtain an average ratio of 0.94 while in the mid-IR range (500-2200 cm -1 ) an average ratio of 0.98 is found. These values are in very good agreement with the expected scaling factor of 0.95 recommended by the NIST for MP2/cc-pVTZ harmonic calculations [START_REF]NIST Computational Chemistry Comparison and Benchmark Database[END_REF].

Assignment of the rotational spectra

As in previous studies concerning the spectroscopy of relatively large C-bearing species, the high density of lines complicates the assignment of the pure rotation spectra. However, the combined use of different programs facilitated and secured the analysis. Our 3-steps assignment procedure is described in the following. (i) Using the results of the quantum chemical calculations and the PGOPHER software [START_REF] Western | PGOPHER: A program for simulating rotational, vibrational and electronic spectra[END_REF], we were able to simulate the ground state pure rotational spectra at 300 K and compare the calculated transitions with the experimental traces. A very rough fit of successive clusters of a-type transitions in PGOPHER provides a good estimation of the B 0 rotational constant which can then be inserted in a parameter file for the SPFIT/SPCAT suite of programs [START_REF] Pickett | The fitting and prediction of vibration-rotation spectra with spin interactions[END_REF]. (ii) The calculated energy levels are then used by the LWW program for symmetric tops [START_REF] Lodyga | Advanced graphical software for assignments of transitions in rovibrational spectra[END_REF], creating Loomis-Wood plots hence providing a very convenient graphical support to search for branches involving the same K values and increasing values of J. (iii) Finally, all assigned branches are fit using the SPFIT program. Step (ii) and (iii) are performed as an iterative process. This approach has proven to be very efficient when dealing with highly congested spectra involving pure rotation or rotation-vibration transitions.

In the present study, as shown on the right panel of Fig. 3, the K-ladder assignment is not straightforward. Indeed, for low values of K, the high density of lines in a J cluster prevents at first an unambiguous assignment. However, with increasing K values, lines separated by one quantum of K are very well resolved. Therefore, to provide a secure assignment of the K-ladders, we used the LWW software to rapidly assign several tens of branches involving successive values of K and containing values of J typically ranging from J = K up to J = 100. The definitive assignment of K was provided by performing fits in SPFIT while the values of K is incremented in all assigned branches. For this part of the analysis, we typically used a subset of more than 50 successive branches to perform the trials fits, and only the B and centrifugal distortion parameters were included in the model. Fig. 4 shows the results of this procedure for the assignment of the GS transitions of the AdaNC molecule. In this case, we used a subset of 68 successive branches (for a total of 3455 lines) to perform the fits. The upper plot of Fig. 4 provides the results of the fit for our initial guess assignment (represented as "shift of K = 0", RMS=73.5 kHz) as well as all results corresponding to shifts of the K values in all branches by ±1, 2, 3, 4. It is clear that the best fit is obtained when all values of K are shifted by -1 (RMS=41.7 kHz) from the initial assignment. A final confirmation of the K-ladder assignment is obtained by inputting the fitted rotational parameters in PGOPHER. An example of this comparison between the experimental spectrum of AdaNC and 3 simulated spectra produced from the different sets of constants is given on Fig. 4. On the figure, it is clear that while most of isolated lines seem to be well predicted in the simulation, the head of the K-ladder is clearly shifted when changing the assignment of K by one quantum. In this particular case, the initial assignment predicts the position of the band head at lower frequency (few hundreds of kHz) than the experiment. Subtracting one quantum from all values of K in every branch nicely reproduces the position of the band head, confirming the results of the fit. Both the standard deviation and the comparison of the band heads in PGOPHER confirmed our assignments.

Using the assignment procedure described above, we could relatively rapidly perform the assignment and fit of both AdaCN and AdaNC molecules in their vibrational ground state (which possesses A 1 symmetry). The list of fitted GS parameters is given in Table 2 for AdaCN and Table 3 for AdaNC. In the case of AdaCN, 4929 transitions were assigned in v = 0 involving K values from 0 to 119 and J up to 128; and 4375 transitions were assigned in v 50 = 1 with similar J and K ≤ 91 values. For AdaNC, 3968 and 3703 lines were assigned in v = 0 and v 50 = 1, respectively, with K ≤ 91 and J ≤ 123. In both cases, the present experimental dataset allowed us to accurately fit B, D J , D JK , and the sextic H JK and H KJ terms (which were added to the model to include branches involving high values of J and K). Because only a-type transitions are observed, the A and D K constants are kept fixed to the value derived from the equilibrium calculation. The standard deviation of each fit is close to 1.

The agreement between the calculated (equilibrium) and experimental (ground state) values for B is very good (less than 1 % relative differ- ence for both molecules). D J shows a similarly good agreement while D JK has similar values for both molecules but the calculations gave a slightly lower value, leading to a larger discrepancy between observed and calculated parameters for AdaCN. Like adamantane and its derivatives, AdaCN and AdaNC are rigid rotors as reflected by the small values of their centrifugal distortion constants (about 6 orders of magnitude smaller than B).

In addition to the pure rotation in the GS, we as-signed pure rotation transitions within the first vibrationally excited state (ES), v 50 = 1 (doubly degenerated state of E symmetry). For both AdaCN and AdaNC, v 50 = 1 lies around 130 cm -1 above GS, which correspond to about 50 % of the ground state population at room temperature. In the ES, the structure of the a-type transitions clusters differs from the GS because of l-type doubling. Fig. 5 displays a small portion of the rotational absorption spectrum of AdaNC, showing a frequency span of 150 MHz around a cluster of GS lines in the 102 GHz spectral region (left part of the figure). A zoom into the cluster of lines involving v 50 = 1 is shown on the right panel of Fig. 5. The splitting between l = 1 and l = -1 components is well resolved in our spectrum showing line progressions starting a few MHz higher in frequency for the l = -1 components. Using an estimated value of q = 0.36 MHz for AdaCN and 0.39 MHz for AdaNC (equation 5), we could repeat the GS assignment procedure, using independent Loomis-Wood diagrams for l = 1 and l = -1. As the lines involving K = 0 for l = -1 appear isolated, we started the analysis of successive branches rapidly and checked the K assignment, similar to what was done for the GS, by incrementing all values of K in the dataset and finding the lowest standard deviation of the fit. For branches involving l = 1, the assignment of the K structure was more complicated due to the branch head involving a multitude of small values of K (e.g., between 7 and 14 for AdaNC, see Fig. 5). As a consequence of the large number of potential assignments, our initial guess for assigning the K values was off by 10 quanta but fitting together l = 1 and l = -1 allowed us to rapidly find an unambiguous assignment. The results of the fit for the ES dataset are quite similar to the GS in terms of number of assigned transitions and values of J and K included in the fit. The fits, presented in tables 2 and 3, are very satisfactory, both rotational constants and l-type doubling parameters being well determined.

Many unassigned lines grouped in clusters very similar to those assigned but with weaker intensity are present in the experimental spectra of both AdaCN and AdaNC. These lines most likely involve higher vibrational states populated at room temperature. We clearly see on Figure 3 a progression of hot bands involving higher quanta of v 50 . Despite significant efforts to find a satisfactory analysis for v 50 = 2, we were not able to provide any definitive assignment for the K ladders. One possi- ble reason is that v 50 = 2 falls in near coincidence with v 49 = 1 (for which we did not succeed to per- form any assignment either) and might be subject to some perturbations complicating even more the assignment of K branches. The fit files in Pickett's format (.lin, .par, .fit) are provided in the supporting information.

Conclusion

In this work, we provide a spectroscopic study of two cyano containing isomers of adamantane, AdaCN and AdaNC; both species belonging to the C 3v point group of symmetry. Both the vibrational (50-3000 cm -1 ) and pure rotational (75-220 GHz) gas phase spectra of the two molecules were recorded at room temperature and their assignments were supported by quantum chemical calculations. Despite the relatively high density of rotational lines, the unambiguous analysis of the K structure for these heavy symmetric tops species was eased by careful investigation of the effect of successive K-values assignments on the RMS of the fit and typical spectral fingerprints. Accurate spectroscopic constants have been determined for both the GS and first ES (v 50 = 1) of the two species.

Considering the large dipole moment of the two compounds, close to 4.5 Debye, these cyanocontaining molecules appear as promising proxy for the centro-symmetric parent adamantane that possesses no pure rotational spectrum, similar to what has been seen for benzene using benzonitrile. Searches for AdaCN and AdaNC in the interstellar medium can now be undertaken with confidence using the reliable constants derived in this work.

Figure 1 :

 1 Figure 1: Molecular structure of the AdaCN (left) and AdaNC (right) molecules (the bond orders are not represented).

Figure 2 :

 2 Figure 2: Far-IR (top traces) and mid-IR (middle and bottom traces) of AdaCN (top left and middle) and AdaNC (top right and bottom) recorded using the FT-IR interferometer of the AILES beamline at SOLEIL. Black traces correspond to the experimental absorbance spectra and stick plots correspond to calculated band positions at the MP2/cc-pVTZ level of theory. Vibrational bands of E symmetry are represented in blue, and those of A 1 symmetry in red. Note the different intensity scale for the lower and upper frequency region of each spectrum (split at 250 cm -1 in the far-IR and 2000 cm -1 in the mid-IR). The band identified by an asterisk in the mid-IR spectrum of AdaCN (middle panel) arises from an impurity containing a carbonyl group.

Figure 3 :

 3 Figure 3: Left: 5 GHz portion of the millimeter-wave spectrum of AdaCN recorded in the 140-220 GHz spectral range displaying 3 clusters of a-type transitions involving J = 98, J = 99 and J = 100. Right: Zoom onto one cluster of GS pure rotation transitions involving J = 99. The black traces represent the experimental spectrum. The red and blue traces correspond to pure rotation transitions within the GS and v 50 = 1, respectively, simulated using the final set of parameters (see the discussion). To enable visual comparison with the experimental trace, the plotted simulations correspond to the second derivative of the traces obtained with the PGOPHER software a full width at half maximum of 250 kHz (gaussian shape).

Figure 4 :

 4 Figure 4: Upper panel: Results of different fits of AdaNC involving 68 successive branches plotted against incremented values of K in all assigned branches. The value 0 is our initial guess of K assignment. The lowest value of the RMS (about 42 kHz) indicates unambiguously the definitive assignment of the K ladders which is shifted by -1 from our initial guess. Lower panel: Comparison of the experimental spectrum (black trace) with 3 simulated spectra obtained by fitting the line list of GS transitions of AdaNC and applying a shift of -1 and -2 to K in all assigned branches. We clearly see the effect of misassignment of the K ladder by one quantum on the band head.

a

  Calculated equilibrium value, MP2/cc-pVTZ, this work b in % using the formula δ = (B0 exp. -B e calc. )/B e calc. × 100 c Fixed to the calculated value d Calculated value of q in v50 = 1 e Number of assigned transitions f Unitless g Reduced standard deviation, unitless

Figure 5 :

 5 Figure 5: Portion of the pure rotation absorption spectrum of AdaNC showing a cluster of transitions involving J = 57. Black traces are the experimental spectrum, blue and red traces are simulated spectra in the ground and ν 50 states, respectively, using the fitted parameters. The right panel shows a zoom of a typical cluster of pure rotation lines within the E symmetry ν 50 state. As for the AdaCN plots displayed in Fig.3, the simulations corresponds to the second derivative of the trace obtained using the PGOPHER software for the final set of rotation constants and a full width at half maximum of 250 kHz.

Table 1 :

 1 Vibrational modes of AdaCN and AdaNC calculated at the MP2/cc-pVTZ level and comparison with experimental assignments. Experimental bands are separated into two columns: confident assignments are presented in the column "Assign." and tentative ones in the column "Prop.". No scaling factor has been used in the calculated frequencies columns. For vibrational bands with an E symmetry, the reported intensity corresponds to the sum of the two equivalent band intensities calculated by Gaussian

				AdaCN				AdaNC
	ν	Calculated a	Experimental		Calculated a	Experimental
		Freq. Int. b	Assign. Prop.	δ c	Freq. Int. b	Assign. Prop.	δ c
	A1 Symmetry
	1	3110	59.5	2927	-5.9	3113	58.7	2928	-5.9
	2	3088	17.3	2927	-5.2	3091	27.0	2928	-5.3
	3	3062	25.7	2866	-6.4	3067	21.4	2869	-6.5
	4	3054	21.2	2866	-6.2	3056	21.4	2869	-6.1
	5	2179	0.7	2254	3.4	2108	78.1	2133	1.2
	6	1517	0.1			1518	0.1
	7	1495	14.5	1458	-2.5	1496	11.4	1459	-2.5
	8	1391	1.0	1358 -2.4	1388	5.2	1361	-2.0
	9	1352	2.6	1320 -2.4	1345	10.1	1316	-2.1
	10	1157	0.2			1141	5.9	1111	-2.6
	11	1120	2.6	1099	-1.8	1110	17.8	1089	-1.9
	12	1003	2.8	979	-2.4	1001	0.1
	13	924	0.1			927	3.4	900	-2.9
	14	791	0.3			793	0.6
	15	712	1.2	700 -1.7	722	1.9	709	-1.8
	16	498	0.3	501	0.6	507	1.4	507	0.0
	17	384	0.01			393	0.2	400	1.6
	E Symmetry
	26	3118	63.7	2927	-6.1	3125	57.5	2928	-6.3
	27	3107	15.7	2927	-5.8	3109	17.0	2928	-5.8
	28	3086 134.1	2927	-5.2	3089 126.1	2928	-5.2
	29	3060	21.4	2866	-6.3	3064	18.3	2869	-6.4
	30	3054	48.3	2866	-6.2	3056	48.6	2869	-6.1
	31	1493	24.3	1458	-2.3	1493	24.5	1459	-2.3
	32	1480	0.1			1481	0.04
	33	1403	0.1			1404	0.5
	34	1378	2.2	1358 -1.4	1378	1.8
	35	1345	0.1			1345	0.9
	36	1328	0.04			1328	0.2
	37	1288	0.1			1298	0.3
	38	1212	0.69			1215	2.3	1189	-2.1
	39	1124	4.2	1104	-1.8	1124	6.0	1111	-1.2
	40	1077 0.007			1078	0.5
	41	1000	3.6	979	-2.1	1006	1.2
	42	963	0.6			964	2.4	936	-3.0
	43	898	0.03			899 0.003
	44	834	1.6			835	3.1	793 -5.1
	45	652	0.3			650	0.2	614 -5.5
	46	541 0.003			486	2.5	478	-1.6
	47	437	0.2	442	1.1	432	0.1
	48	399	0.3	397 -0.6	399	0.3	400	0.3
	49	307	0.5	309	0.5	300	0.1
	50	134	9.1	137	2.4	135	11.2	134	-1.0

a Positions (Freq., ν) are given in cm -1 and intensities in km/mol. b c In % using δ = (νexp. -νcalc. )/ν calc. × 100

Table 2 :

 2 Rotational constants of the ground state and the first excited state of AdaCN. Comparison of the fit with calculations. Values are in MHz unless otherwise noted.

		Eq.	GS		v50=1 (ES)
		Calc. a	Exp.	δ b	Exp.
	Rotational constants
	A	1698.76	[1698.76] c		[1698.76] c
	B	858.47	852.218045 (11)	-0.73	852.771240 (13)
	Centrifugal distortion constants
	DJ × 10 5	1.22	1.231404 (47)	0.93	1.241490 (51)
	DJK × 10 4	1.23	1.166870 (32)	-5.13	1.157348 (63)
	DK × 10 5	-9.01	[-9.01] c		[-9.01] c
	HJK × 10 11		4.443 (13)		4.068 (23)
	HKJ × 10 11		-6.048 (18)		-5.811 (64)
	l -doubling parameters
	-2Aζ				-2700.90 (35)
	ηJ × 10 3				0.823705 (61)
	q	0.36 d			0.386501 (53)
	Relevant fit parameters
	N e		4929		4375
	J max , K max	f	128,119		128,91
	rms			0.033
	σ g			1.11

Table 3 :

 3 Rotational constants of the ground state and the first excited state of AdaNC. Values are in MHz unless otherwise noted. Calculated equilibrium value, MP2/cc-pVTZ, this work b in % using the formula δ = (B0 exp. -B e calc. )/B e calc. × 100

		Eq.	GS		v50=1 (ES)
		Calc. a	Exp.	δ b	Exp.
	Rotational constants
	A	1701.93	[1701.93] c		[1701.93] c
	B	889.95	882.475497 (16)	-0.84	883.199299 (20)
	Centrifugal distortion constants
	DJ × 10 5	1.27	1.286431 (76)	1.29	1.301015 (92)
	DJK × 10 4	1.10	1.099262 (81)	-0.07	1.08068 (13)
	DK × 10 5	-7.78	[-7.78] c		[-7.78] c
	HJK × 10 11		4.698 (30)		3.763 (43)
	HKJ × 10 11		-6.834 (88)		-6.39 (23)
	l -doubling parameters
	-2Aζ				-2850.2 (10)
	ηJ × 10 3				1.11643 (12)
	q	0.39 d			0.41759 (14)
	Relevant fit parameters
	N e		3968		3703
	J max , K max	f	123,91		123,77
	rms			0.048
	σ g			1.01

a c Fixed to the calculated value d Calculated value of q in v50 = 1 e Number of assigned transitions f Unitless g Reduced standard deviation, unitless

Acknowledgement

This project received funding from the Région Ile-de-France, through DIM-ACAV + , from the Programme National "Physique et Chimie du Milieu Interstellaire" (PCMI) of CNRS/INSU with INC/INP co-funded by CEA and CNES, from the "Investissements d'Avenir " LabEx PALM (ANR-10-LABX-0039-PALM), and from the Agence Na-

Appendix: Supplementary data Supplementary data associated with this article (parameter and fit files) are available on ScienceDirect (www.sciencedirect.com).

Author contributions

Olivia Chitarra: Investigation, Formal analysis, Visualization, Writing -review & editing; Zachary Buchanan: Investigation, Writing -review & editing; Marie-Aline Martin-Drumel: Funding acquisition, Investigation, Supervision, Validation, Writing -review & editing; Olivier Pirali: Funding acquisition, Investigation, Supervision, Project administration, Validation, Writing -original draft;