J.-Ph Karr
email: karr@lkb.upmc.fr

H + 2 and HD + : candidates for a molecular clock

Keywords:

We investigate the leading systematic effects in ro-vibrational spectroscopy of the molecular hydrogen ions H + 2 and HD + , in order to assess their potential for the realization of optical clocks that would be sensitive to possible variations of the proton-to-electron mass ratio. Both two-photon (2E1) and quadrupole (E2) transitions are considered. In view of the weakness of these transitions, most attention is devoted to the light shift induced by the probe laser, which we express as a function of the transition amplitude, differential dynamic polarizability and clock interrogation times. Transition amplitudes and dynamic polarizabilites including the effect of hyperfine structure are then calculated in a full three-body approach to get a precise evaluation of the light shift. Together with the quadrupole and Zeeman shifts that are obtained from previous works, these results provide a realistic estimate of the achievable accuracy. We show that the lightshift is the main limiting factor in the case of two-photon transitions, both in H + 2 and HD + , leading to expected accuracy levels close to 5 × 10 -16 in the best cases. Quadrupole transitions have even more promising properties and may allow reaching or going beyond 1 × 10 -16 .

I. INTRODUCTION

Space-time variations of the proton-to-electron mass ratio µ is one area where high-precision molecular spectroscopy plays an important role in testing the fundamental laws of physics. While astrophysical studies on the spectra of molecular hydrogen, ammonia and methanol have set stringent limits on the variations of µ over cosmological time scales, laboratory tests provide complementary information on its variations in the current epoch (see [START_REF] Jansen | [END_REF]2] for recent reviews). So far, the most severe model-independent limit from a laboratory measurement, obtained by comparing rovibrational transitions in SF 6 with a Cs clock, is at a level of several 10 -14 /year [3]. A large number of theoretical proposals relying on molecular lines with greatly enhanced sensitivities to µ variations, due to a cancellation between energy contributions from different origins (electronic, vibrational, rotational, fine or hyperfine structure...), have been formulated in recent years (see e.g. [4][5][6]).

Ro-vibrational transitions in the hydrogen molecular ions H + 2 and HD + were among the very first candidates to be studied in the perspective of high-precision laboratory tests [7]. Despite the fact that they do not benefit from any sensitivity enhancement effect, several factors still make hydrogen molecular ions attractive. First are the small natural widths of ro-vibrational lines, which lye in the 10 Hz [8,9] and 10 -7 Hz [10] range for HD + and H + 2 respectively, and the possibility to probe single trapped molecular ions with ultra-high resolution using quantum-logic spectroscopy (QLS) [11,12]. The demonstration of efficient schemes to prepare the molecules in a selected ro-vibrational state, such as resonance-enhanced multi-photon ionization [13,14] or rotational cooling [15,16], is another important asset; in general, state preparation is a major experimental challenge to be considered since transitions of enhanced sensitivity are often rather exotic, i.e. involving highly excited states in complex molecules. Finally, the simplicity of hydrogen molecular ions allows for precise theoretical calculations of the main systematic shifts that affect the accuracy of the measurement, and thus reliable performance estimates of the envisaged quantum-logic clock. The purpose of the present work is to obtain such estimates for a few ro-vibrational transitions of interest in H + 2 and HD + . This study builds upon a previous investigation of systematic effects for a large number of transitions in HD + , by D. Bakalov and S. Schiller [START_REF] Bakalov | Applied Physics B[END_REF], which included the combined contributions of Zeeman, quadrupole, Stark, and black-body radiation shifts, and concluded that frequency measurements with a relative accuracy of about 5 × 10 -16 should be achievable on a few selected one-photon ro-vibrational transitions. Two-photon transitions, which enable suppression of the first-order Doppler effect even without strong spatial confinement of the ions, were also considered (see also [START_REF] Tran | [END_REF]). However, one of the potentially most important systematic effects that is the light shift induced by the probe laser, was not calculated. The first Section is devoted to a precise estimate of this effect, and consideration is extended to the H + 2 ion. One attractive feature of H + 2 in this context is the extremely small natural width of the transitions, to which one might add the simpler spin structure. In the second Section, we study one-photon quadrupole transitions in H + 2 , which benefit from smaller light shifts. It is shown that these transitions could allow for even more accurate frequency measurements, and are thus highly promising candidates for a molecular ion clock.

II. TWO-PHOTON TRANSITIONS

A. Expression of the light shift

In order to give a correct estimate the light shift, one should first discuss the typical intensity of the probe laser to be used for optimal operation of a molecular ion clock. Here, the envisaged experimental realization is QLS of a Be + /HD + (or Be + /H + 2 ) ion pair. The use of two-photon transitions implies reaching a regime of two-photon Rabi oscillations; the generalized two-photon Rabi frequency for a transition between states i and f is given by

Ω = S Q if ǫǫ (E) I ǫ 0 hc (1)
where I, ǫ are the intensity and polarization of the probe laser, and

S Q if ǫ1ǫ2 (E) = i| S Q ǫ1ǫ2 (E)|f the two-photon transition matrix element. E = (E i + E f )/2 is
the intermediate energy, and the two-photon operator S Q ǫ1ǫ2 (E) is defined by

S Q ǫ1ǫ2 = 1 2 (Q ǫ1ǫ2 + Q ǫ2ǫ1 ) , Q ǫ1ǫ2 = d • ǫ 1 1 E -H d • ǫ 2 . ( 2
)
QLS clocks are operated with a single interrogation π-pulse [19] whose duration τ is adjusted according to the desired resolution. τ is typically of the order of 100 ms [20,21], and we will assume the same value in the case of H + 2 . However, in HD + the shorter lifetime τ f of excited ro-vibrational state (τ f ∼ 15 -55 ms for v = 1 -4) constrains τ to lower values; in the following we will assume τ = τ f /10. The probe laser intensity is determined from the relationship Ωτ = π yielding

I = πǫ 0 hc τ S Q if ǫǫ (3)
The corresponding shift of the transition energy

(E f -E i )/2 is ∆E if = - 1 4 ∆α if ǫ I c = πǫ 0 h 4τ ∆α if ǫ S Q if ǫǫ (E) , (4)
where

∆α if ǫ = α f ǫ (ω if ) -α i ǫ (ω if ), ω if = (E f -E i )/2h
being the two-photon probe laser frequency and α n ǫ (ω) the dynamical polarizability of a state n:

α n ǫ (ω) = -4πa 3 0 S Q nn ǫǫ (E n + hω) + S Q nn ǫǫ (E n -hω) . (5)
Using the atomic units for polarizabilites and two-photon transition matrix elements (i.e. α n ǫ in units of 4πa 3 0 and S Q if ǫ1ǫ2 in units of (ea 0 ) 2 /E h = h2 e 2 /m e ) one obtains the following simple expression for the frequency shift:

∆f LS = - 1 8τ ∆α if ǫ S Q if ǫǫ (E) . (6)
In order to get a reliable estimate of the light shift, we have calculated the dimensionless transition amplitudes S Q if ǫǫ (E) and associated differential polarizabilities ∆α if ǫ for a large range of two-photon transitions in HD + and H + 2 . Selected results are presented in Tables I andII. The methods for calculating two-photon line strengths with account of the hyperfine structure have been described in detail in [22] in the context of H + 2 (see also [START_REF] Bakalov | Proceedings of International Conference on Exotic Atoms and Related Topics[END_REF][START_REF] Bakalov | [END_REF] for similar calculations in HD + ); they can also be applied for evaluating dynamical polarizabilities of hyperfine sublevels since both quantities are expressed in terms of matrix elements of the same operator S Q ǫ1ǫ2 (E). A summary of these methods can be found in the Appendix.

B. HD +

In the case of HD + (Table I), two-photon transitions from ro-vibrational states (v = 0, L) were considered, since v = 0 states, having by far the longest lifetimes, are the only ones in which the ions can be conveniently prepared. We mainly investigated the transitions towards states with a vibration quantum number v ′ = 2 or 1 which are the strongest, as shown in [25]. Indeed, in a (v = 0, L) → (v ′ = 2, L ′ ) transition, a (v ′′ = 1, L ′′ ) state lies close to the one-photon resonance, leading to a strong enhancement of the line strength. Transitions towards higher vibrational states are much weaker and more difficult to observe experimentally; in view of Eq. ( 6) they will also be affected by large lightshifts unless the dynamical polarizabilities of the ground and excited states cancel each other almost exactly. We also investigated v = 0 → v = 4 transitions but found no such cancellations.

The angular momentum coupling scheme used to denote the hyperfine sublevels (v, L, F, S, J, J z ) of HD + is the following [26]: F = S d + S e , S = F + S p , J = L + S where S i , i = e, p, d denote the spin operator of the electron, proton and deuteron; only J is an exact quantum number whereas (F, S) are approximate quantum numbers. As discussed in [START_REF] Bakalov | Applied Physics B[END_REF]27], two types of transitions are particularly interesting for clock applications:

• J z = 0 → J ′ z = 0 transitions, which only have a quadratic Zeeman shift; • pairs of transitions between "stretched states" where all the angular momenta have their maximum values:

(v, L, F = 1, S = 2, J = L + 2, J z = ±(L + 2)) → (v ′ , L ′ , F ′ = 1, S ′ = 2, J ′ = L ′ + 2, J ′ z = ±(L ′ + 2))
. Since these transitions have strictly linear opposite Zeeman shifts, the effect of the magnetic field can be nulled by measuring both transition frequencies and computing the average value.

A few J z = 0 → J ′ z = 0 transitions benefit from a relatively low Zeeman shift (below 100 Hz in a magnetic field of 1 G): [27]). However, none of them were found to have interesting properties in terms of systematic effects, and they will not be considered further. In the following we only discuss transitions between stretched states.

(v = 0, L = 0) → (v ′ = 2, L = 0) with (F, S, J) = (0, 1, 1), (v = 0, L = 3) → (v = 2, L = 3) with (F, S, J) = (1, 2, 4), and (v = 0, L = 4) → (v = 2, L = 4) with (F, S, J) = (1, 2, 3) (see Table 2 of
The first seven lines of Table I give the lightshifts of all v = 0 → v = 2 stretched-state transitions with an initial rotational state L ≤ 2. v = 0 → v = 2 transitions are obvious candidates since they are the most intense, and the first three of them were considered in [START_REF] Bakalov | Applied Physics B[END_REF] (Table IX). Their lightshifts range from a few to a few hundred Hertz, the most promising among them being the (v = 0, L = 0) → (v ′ = 2, L ′ = 0) transition which has a 4.0 Hz light shift and is not affected by Zeeman and quadrupole shifts. The relative frequency shift amounts to ∆f LS /f 0 = 7 × 10 -14 and is the main limitation to the accuracy. Assuming that it could be calibrated to the percent level, a residual systematic uncertainty of 7 × 10 -16 could be achieved; lightshift calibration beyond that level would be a difficult experimental challenge. The (v = 0, L = 1) → (v ′ = 2, L ′ = 1) transition, which seemed promising due to its large intensity as pointed out in [25], turns out to have a large lightshift, partly due to the weakness of the Zeeman sub-lines which connect the stretched states. We extended our search to L ≤ 5 initial states and found one more interesting transition (line before last in Table I

): (v = 0, L = 4) → (v ′ = 2, L ′ = 2)
, which has both a moderate light shift (∆f LS /f 0 = 1.9 × 10 -13 ) and low quadrupole shift (∆f Q /f 0 = 3.5 × 10 -15 ).

The v = 0 → v = 1 transitions, although less intense, may also be of interest in case of a fortuitous cancellation of the lightshift. A scan of all transitions from (v = 0, L ≤ 5) states revealed one such instance (last line of Table I

): (v = 0, L = 2) → (v ′ = 1, L ′ = 0)
, with a lightshift of 0.34 Hz (∆f LS /f 0 = 1.3 × 10 -14 ). For this transition, the accuracy would be limited by the quadrupole shift (∆f Q /f 0 = 2 × 10 -13 ), which according to the discussion in Ref. [START_REF] Bakalov | Applied Physics B[END_REF] could be reduced to a residual uncertainty of about 1 × 10 -15 by applying a nulling procedure. II), two-photon transition amplitudes and polarizabilities follow a very different behaviour from the HD + case. Neighbouring rovibrational states not being dipole-allowed, there are no resonant enhancement effects. Only excited electronic states contribute to the two-photon amplitudes, leading to a smooth variation as a function of vibration and rotation quantum numbers. It has been shown that only ∆v = 1 two-photon transitions are sufficiently intense to be conveniently detected [29]. In contradistinction with HD + the initial vibrational state could take any value (excited rovibrational states are metastable); however the selectivity in H + 2 production by resonance-enhanced multiphoton ionization gets worse when the targeted vibrational quantum number increases [14].

C. H + 2 In H + 2 (Table
(v = 0, L) → (v ′ = 1, L ′ ) and (v = 1, L) → (v ′ = 2, L ′ ) transitions with L ≤ 3 are listed in Table II.
The spin structure of H + 2 is slightly simpler than in HD + [30]. The adopted angular momentum coupling scheme is F = S e + I, J = L + F where I is the total nuclear spin, whose value is 0 (resp. 1) for even (resp. odd) values of L. No J z = 0 → J ′ z = 0 transitions exist since the total angular momentum is half integer. There are however

(v, L) (v ′ , L ′ ) f 0 f 0 τ f Q (0) v,L,v ′ ,L ′ Q (2) v,L,v ′ ,L ′ |Q if | α (0) v,L α (2) v,L α i α (0) v ′ ,L ′ α (2) v ′ ,L ′ α f ∆α ∆f LS ∆f Z ∆f Q [cm -1 ] [THz] [
i = (v, L, F = 1, S = 2, J = L + 2, Jz = ±(L + 2)) → f = (v ′ , L ′ , F ′ = 1, S ′ = 2, J ′ = L ′ + 2, J ′ z = ±(L ′ + 2)) in HD + . f0 = (E f -Ei)/2
is the spin-independent transition frequency (including leading-order relativistic and QED corrections) taken from [28]. τ f is the excited state lifetime from [9].

Q (k)
v,L,v ′ ,L ′ are the scalar (k = 0) and tensor (k = 2) two-photon matrix elements (see Eq. ( 18)), and Q if is the resulting amplitude for the hyperfine component that connects the stretched states i, f , obtained using Eq. ( 15) or (16) according to the polarization case, and Eq. (27). Similarly, α

(k) v,L and α (k)
v ′ ,L ′ (k = 0, 2) are the scalar and tensor dynamic polarizabilities (Eq. ( 5)) of the initial and final ro-vibrational states, αi, α f are the hyperfine state polarizabilities (obtained through Eq. ( 15) or [START_REF] Bakalov | Applied Physics B[END_REF] with Eq. ( 27)), and ∆α = α f -αi. A linearly (resp. circularly) polarized laser field was assumed for L → L (resp. L → L ± 2) transitions for which |∆Jz| = 0 (resp. 2). Finally, ∆fLS is the estimated light shift, obtained from Eq. (6). Estimates of the two other most important systematic effects are also given: the Zeeman shift ∆fZ in a magnetic field of 1 G from [27], and the quadrupole shift ∆fQ in an electric field gradient of 0.67 × 10 8 V/m 2 (see [START_REF] Bakalov | Applied Physics B[END_REF] and corrigendum to be published).

stretched states which have the same properties as in HD + : (v, L, F = 1/2, J = L + 1/2, J z = ±(L + 1/2)) for even L and (v, L, F = 3/2, J = L + 3/2, J z = ±(L + 3/2)) for odd L. In the following only transitions between such states are considered.

The light shifts lie in the few-Hz range, which is comparable to the best transitions in HD + . In the absence of resonant enhancement effects, the ∆α/|Q if | ratio is less favorable, but this is compensated by the possibility of using longer probe times and thus lower intensities. L → L -2 transitions (especially L = 2 → L ′ = 0) have the lowest lightshifts, followed by L → L transitions, while L → L + 2 transitions are less favourable. The quadrupole shift has the same order of magnitude, and is lowest for L → L transitions. When v is increased from 0 to 1, the lightshift slightly decreases but the quadrupole shift slightly increases. The best trade-off depends on the degree of accuracy to which the different systematic effects can be calibrated and corrected for. We will make the same assumptions as in Ref. [START_REF] Bakalov | Applied Physics B[END_REF] where this issue has been discussed in detail.

The Zeeman shift is nulled by computing the average of the stretched-state transitions J z → J ′ z and -J z → -J ′ z . In [START_REF] Bakalov | Applied Physics B[END_REF] it was assumed that each transition frequency can be measured with a resolution equal to 1% of the natural linewidth. In H + 2 the natural width is extremely small, so that the transition width would probably be limited by the probe laser. For illustration let us assume a value of 1 Hz. Then the uncertainty on the mean frequency of the doublet would be 0.01 × √ 2 = 0.014 Hz. By repeating these measurements for a set of magnetic field values the error could be reduced by a further factor of 5, i.e. slightly below 10 -16 relative to the transition frequency.

The quadrupole shift is nulled by measuring the transition frequencies for three orthogonal directions of the magnetic field. Again, the uncertainty of each measurement can be assumed to be 1% of the linewidth, yielding an overall uncertainty of 0.01/ √ 3 = 0.0058 Hz. In addition, the inaccuracy in establishing three perfectly orthogonal magnetic field directions leads to a residual uncertainty of 0.5% of the value calculated in Table II for an electric field gradient of 0.67 × 10 8 V/m 2 (assuming this can be performed with the same accuracy as in the Hg + ion clock [31]). Supposing, finally, that the residual uncertainty on the lightshift is equal to 1% of the shift, and adding quadratically the different errors, the best trade-off would be obtained for L → L transitions, with overall accuracies between 5 and 7 × 10 -16 depending on the values of v and L.

III. QUADRUPOLE TRANSITIONS IN H + 2

In the H + 2 ion, quadrupole transitions are a promising alternative as potential clock transitions. Their oscillator strengths have recently been calculated [10]; they are more intense than two-photon transitions, so that the lighshift could be significantly reduced. In addition, the possibility to excite transitions towards higher vibrational states is attractive because increasing the transition frequency generally leads to improving clock performances. However, transitions become weaker when ∆v is increased, and again it is useful to estimate the lightshift in order to determine the ∆v range where it does not represent a limitation to the accuracy.

We will thus derive an expression of the light shift along the same lines as in Sec. II A. In the case of quadrupole transitions, the Rabi frequency writes [34]

Ω = ea 2 0 E 0 2h 2π λ |Θ if ǫ,n | (7)
with

Θ if ǫ,n = 1 3 ij i|Θ ij |f ǫ i n j (8)
E 0 , ǫ are respectively the electric field amplitude and polarization of the incident wave, and n the unit vector along the propagation direction (k = kn). Θ is the quadrupole tensor operator in the center-of-mass frame in atomic units (i.e. units of ea 2 0 ). We use the definition of [START_REF] Bakalov | Applied Physics B[END_REF]:

Θ ij = (3/2) k Z k R ki R kj -δ ij R k 2 /3 . ( 9
)
where R k is the position of the particle k with respect to the center of mass, and Z k its electric charge. The condition Ωτ = π (where τ is the probe pulse duration) yields

E 0 = hλ ea 2 0 τ |Θ if ǫ,n | , ( 10
) (v, L) (v ′ , L ′ ) f 0 f 0 Q (0) v,L,v ′ ,L ′ Q (2) v,L,v ′ ,L ′ |Q if | α (0) v,L α (2) v,L α i α (0) v ′ ,L ′ α (2) v ′ ,L ′ α f ∆α ∆f LS ∆f Z ∆f Q [cm -1 ] [THz] [a.u
i = (v, L, F = 3/2, J = L + 2, Jz = ±(L + 2)) → f = (v ′ , L ′ , F ′ = 1, S ′ = 2, J ′ = L ′ + 2, J ′ z = ±(L ′ + 2)) in H + 2 .
The spin-independent transition frequencies are taken from [32], and the Zeeman shift ∆fZ is obtained from [33]. The relationship between hyperfine matrix elements of the two-photon operator and its reduced matrix elements (26).

Q (i) v,L,v ′ ,L ′ is given in Eq.
from which the corresponding lightshift is easily deduced:

∆f LS = - m e λ 2 4h ∆α if ǫ τ 2 |Θ if ǫ,n | 2 . ( 11
)
The choices of propagation direction and polarization of the probe laser, which influence both the quadrupole transition amplitude and lightshift, are given in the Appendix. We calculated the dimensionless transition amplitudes |Θ if ǫ,n | and associated differential polarizabilities ∆α if ǫ for (v = 0, L) → (v ′ , L ′ ) transitions with v ′ = 1, 2, 3. Our results are summarized in Table III. L → L (with L ≤ 3), L = 3 → L ′ = 1 and L = 4 → L ′ = 2 transitions were considered. L → L + 2 and L = 2 → L ′ = 0 transitions were omitted because they have larger quadrupole shifts as can be seen in Table II.

This study shows that the lightshift is negligible for v = 0 → v ′ = 1 transitions; for v = 0 → v ′ = 2 transitions, they are still significantly lower (by at least an order of magnitude) than in two-photon transitions. However, for v = 0 → v ′ = 3 transitions they are already much higher. Under the same assumptions as above regarding calibration of the main systematic effect, we estimate that a relative accuracy of about 1 -1.5 × 10 -16 could be reached using the transitions

(v = 0, L) → (v ′ , L ′ = L) with v ′ = 1 or 2. Especially promising is the transition (v = 0, L = 4) → (v ′ = 2, L ′ = 2
) which benefits from almost perfect cancellation of the quadrupole shift (about 5 × 10 -17 relative to the transition frequency). Here, nonadiabatic calculations of the quadrupole moments were performed to get sufficient accuracy on the differential shift since the results of [START_REF] Bakalov | Applied Physics B[END_REF] are limited by the Born-Oppenheimer approximation. On that transition, it could be possible to reach a relative accuracy of about 6 × 10 -17 . The blackbody radiation is not a limiting factor at this level: at 300K it represents about 10 -16 relative to the frequency, and the uncertainty could be reduced further by at least one order of magnitude by a careful determination of the environment temperature. The second-order Doppler effect is more likely to play a role, since it amounts to a few 10 -17 in the Al + /Be + clock [20] and could become larger in the H + 2 /Be + case where the mass ratio is less favorable.

IV. CONCLUSION

Our analysis of light shifts in high-resolution spectroscopy of hydrogen molecular ions has allowed assessing the performances of different types of transitions for a molecular ion clock that would set new limits on the variations of µ. The lightshift was shown to be the main limiting factor in the case of two-photon transitions, both in H + 2 and HD + , it seems however possible to reach accuracy levels close to 5 × 10 -16 in a few cases. Quadrupole transitions are even more promising in view of the smaller required intensity; one particular transition that could allow going below the 10 -16 level was pointed out. Hydrogen molecular ions thus have potential to improve the currently best laboratory limits on µ-variation by several orders of magnitude. Finally, the lightshift can, in principle, be reduced by using a longer interrogation time, which would make the use of v = 0 → v = 3 quadrupole transitions a realistic possibility. One advantage of such transitions is that they lye in a convenient wavelength range (λ ∼ 1.6 -1.7 µm) for laser technology and absolute frequency measurements. Of course, there are several experimental challenges on the way towards realization of molecular ion clocks, one of which being the preparation of the ions in the required hyperfine and Zeeman sublevel.

(v, L) (v ′ , L ′ ) f 0 f 0 Θ (2) v,L,v ′ ,L ′ |Θ if ǫ,n | α (0) v,L α (2) v,L α i α (0) v ′ ,L ′ α (2) v ′ ,L ′ α f ∆α ∆f LS ∆f Z ∆f Q
as follows:

Ψ π LM (r 1 , r 2 ) = l1+l2=L Y l1l2 LM (r 1 , r2 )G Lπ l1l2 (r 1 , r 2 , r 12 ), G Lπ l1l2 (r 1 , r 2 , r 12 ) = N n=1
C n Re e -αnr12-βnr1-γnr2 + D n Im e -αnr12-βnr1-γnr2 .

(

) 12
where r 1 , r 2 , r 12 are the interparticle distances, and the complex exponents α, β, γ are generated in a pseudorandom way. Since very high accuracy is not required for transition probabilities, relatively small basis lengths of N = 1000 -2000 were used, yielding a relative accuracy of at least a few parts in 10 9 for the nonrelativistic energies, and a few parts in 10 5 for the matrix elements.

Two-photon matrix elements

The two-photon operator S Q defined in Eq. ( 2), being a symmetrical tensor obtained by coupling of two vector operators, has a representation in terms of irreducible tensors that involves a scalar tensor Q (0)a and a tensor Q (2)a of rank 2. Its components S Q q1,q2 (where q i = -1, 0, 1 correspond to the standard polarizations σ -, π, σ + ) can be expressed in terms of the components of these irreducible tensors:

S Q q1q2 = 2 q=-2 a (2) q Q (2)a q + a (0) 0 Q (0)a 0 (13)
The values of the coefficients a (k) q for all combinations of the standard polarizations can be found in Table IV of [22]. Here, we have adopted a slightly different definition for the irreducible tensors:

Q (0) = -Q (0)a / √ 3, Q (2) = 2/3 Q (2)a (14)
so that the linear-linear polarization component is simply written as:

S Q 00 = Q zz = Q (0) 0 + Q (2) 0 . (15)
Other components used in transition amplitude and lightshift calculations are:

S Q ±1±1 = 3/2 Q (2) 2 (16)
-S Q ±1∓1 = Q (0) 0 -Q (2) 0 /2 (17)
The first step is to calculate the reduced matrix elements vL Q (k) v ′ L ′ with k = 0, 2. More precisely, the quantities given in the Tables are

Q (k) v,L,v ′ ,L ′ = vL Q (k) v ′ L ′ √ 2L + 1 (18)
The calculation of two-photon reduced matrix elements has been described in [22]; for easier reference we recall the main formulas here. The following three terms, which correspond to the possible values L-1, L+1, L for the angular momentum of the intermediate state, are evaluated numerically:

a -= - v ′′ vL d v ′′ L-1 v ′′ L-1 d v ′ L ′ (2L+1)(2L ′ +1)(hω -E v ′′ L-1 ) (19)
a + = - v ′′ vL d v ′′ L+1 v ′′ L+1||d||v ′ L ′ (2L+1)(2L ′ +1)(hω -E v ′′ L+1 ) (20)
a 0 = v ′′ vL d v ′′ L v ′′ L d v ′ L ′ (2L+1)(2L ′ +1)(hω -E v ′′ L ) (21)
where E v ′′ ,L ′′ is the energy of the intermediate state |v ′′ L ′′ and ω is the photon energy. The reduced matrix elements of Q (k) are related to a -, a + , a 0 in the following way:

vL Q (0) v ′ L √ 2L + 1 = 1 3 a -+ a 0 + a + , (22) vL
Q (2) v ′ L-2 √ 2L + 1 = - 2(2L-3) 3(2L-1) a -, (23) vL
Q (2) v ′ L √ 2L + 1 = - 1 3 (2L+3)(2L-1)L(L+1) a - L(2L-1) - a 0 L(L+1) + a + (2L+3)(L+1) , ( 24
) vL Q (2) v ′ L+2 √ 2L + 1 = - 2(2L+5) 3(2L+3) a + . (25)
Standard angular algebra procedures are then used to obtain the matrix elements between the initial and final hyperfine states. The expressions are made simpler by the fact that we only consider the "stretched states" which are "pure" states of angular momentum coupling. In the case of H + 2 one obtains v, L, F, J = L + F, J z = ±J|Q (k) q |v ′ , L ′ , F,

J ′ = L ′ + F, J ′ z = ±J ′ = - √ 2J ′ + 1 J ′ kJ ′ z q|JJ z L k L ′ J ′ F J vL Q (k) v ′ L ′ (26)
where F = 1/2 (resp. 3/2) for even (resp. odd) values of L. The expression for HD + is similar:

v,L,F = 1,S = 2,J = L+2,J z = ±(L+2)|Q (k) q |v ′ ,L ′ ,F = 1,S = 2,J ′ = L ′ +2,J ′ z = ±(L ′ +2) =

- √ 2J ′ + 1 J ′ kJ ′ z q|JJ z L k L ′ L ′ + 2 2 L + 2 vL Q (k) v ′ L ′ . (27)
The incident light is assumed to be linearly polarized for ∆L = 0 transitions where ∆J z = 0 and circularly polarized for ∆L = ±2 transitions where ∆J z = ±2.

Quadrupole matrix elements

In order to calculate its matrix elements, the quadrupole operator (9) of a three-body system with masses m i and charges Z i (i = 1, 2, 3) is written in terms of irreducible tensor operators associated with the coordinates r 1 , r 2 and r 12 :

Θ ij = c 1 r 1i r 1j - δ ij 3 r 2 1 +c 2 r 2i r 2j - δ ij 3 r 2 2 +c 3 r 12i r 12j - δ ij 3 r 2 12 , (28)
c 1 = (m 1 + m 3 ) 2 Z 2 + m 2 2 (Z 1 + Z 3 ) m 2 T (29) c 2 = (m 1 + m 2 ) 2 Z 3 + m 2 3 (Z 1 + Z 2 ) m 2 T ( 30
)
c 3 = m 2 m 3 Z 1 --m 3 (m 1 + m 3 )Z 2 -m 2 (m 1 + m 2 )Z 3 m 2 T ( 31
)
with m T = m 1 + m 2 + m 3 . Using this expression one obtains the reduced matrix elements v, L Θ (2) v ′ , L ′ (denoted Θ

v,L,v ′ ,L ′ in Table III). Matrix elements between stretched hyperfine states i|Θ

q |f can then be obtained from Eq. ( 26) (with the replacement of Q (k) by Θ (2) ). The quantity Θ if ǫ,n defined in Eq. ( 8) which appears in the Rabi frequency (7) can be expressed in terms of matrix elements of the standard components of the quadrupole operator:

Θ if ǫ,n = 1 3 ij 2 q=-2
i|Θ (2) q |f c (q) ij ǫ i n j (32) where the expressions of the second rank tensors c (q) ij can be found in [34]. The choice of polarization and propagation direction of the probe laser is made so as to maximize the transition amplitude:

• for L → L, ∆J z = 0 transitions, we choose a propagation direction n making an angle of π/4 with the z axis, and polarization in the plane defined by n and the z axis. The geometrical factor |g 0 | = | ij c (0) ij ǫ i n j | is then equal to 1/2.

• for L → L±2, ∆J z = ±2 transitions, we choose a propagation direction orthogonal to the z axis, and polarization orthogonal to the plane defined by n and the z axis. The geometrical factor

|g ±2 | = | ij c (±2) ij ǫ i n j | is equal to 1/ √ 6.

TABLE I :

 I Light shifts of selected two-photon ro-vibrational transitions between stretched states

TABLE II :

 II Same as TableI, for two-photon ro-vibrational transitions between stretched states

Acknowledgements. I am grateful to V.I. Korobov for sharing his program for variational calculations of threebody systems, B. Dailly for his work on lightshift calculations, and L. Hilico and D. Bakalov for helpful discussions.

Appendix

In this Appendix the methods used to compute the two-photon and quadrupole matrix elements including the effect of the hyperfine structure are briefly summarized.

Nonadiabatic wave functions

To compute the wave functions of ro-vibrational states, the Schrödinger equation of the three-body Coulomb system is solved using a variational approach with exponential basis functions developed by V. Korobov [35]. The wave function for a state with total orbital angular momentum L and of a total spatial parity π = (-1) L is expanded


Gastón Garbarino

Ruben Weht

Amadou Sow

Claudine Lacroix

André Sulpice

Mohamed Mezouar

Xiyu Zhu

Fei Han

Hai Hu

Manuel Núñez-Regueiro

Direct observation of the influence of the FeAs 4 tetrahedron on superconductivity and antiferromagnetic correlations in Sr 2 VO 3 FeAs

Keywords: Tetrahedra, superconductivity and antiferromagnetic correlations in Sr 2 VO 3 PACS: 72.80.Ga, 61.50.Ks, 62.50.-p

We measure the pressure dependence of the electrical resistivity and the crystal structure of iron superconductor Sr 2 VO 3 FeAs. Below ~10 GPa the structure compresses but remains undeformed, with regular FeAs 4 tetrahedrons, and a constant T c . Beyond 10GPa, the tetrahedron strongly distorts, while T c goes gradually to zero. Band structure calculations of the undistorted structure show multiple nesting features that hinder the development of an antiferromagnetic ground state (AF), allowing the appearance of superconductivity. The deformation of the tetrahedra that breaks band degeneracy degrades multiple nesting, thus favouring one particular AF state at the expense of T c .

A frequent trend in the iron pnictides [1] is to have an antiferromagnetic parent compound and a Fermi surface nesting [2], that yields to high temperature superconductivity on doping [3].

On the other hand, as do flat CuO 2 planes in cuprates, regular FeAs 4 tetrahedra have been empirically shown [4,5,6] to maximize the superconducting transition temperature (T c ).

Different theoretical models [7,8] based on the strong sensitivity of the bands near the Fermi energy to atomic positions have been advanced to explain this relation. Understanding the differences and similarities between both families of superconductors grants key insight into a general theory of high temperature superconductivity. Sr 2 VO 3 FeAs [9] has particular characteristics, different from the other Fe pnictides, as the parent stoichiometric compound has a superconducting ground state and shows no evidence of magnetic order in the iron sublattice. Its FeAs layers are relatively distant from each other, separated by thick Sr 2 VO 3 blocks (Fig. 1a). Stoichiometric Sr 2 VO 3 FeAs with the highest reported T c has indeed a near regular tetrahedron [4,10,11]. Strong pressure is expected to deform the structure, becoming an excellent probe to understand the anomalous properties of this compound [12], as has been shown in other cases [13].

The polycrystalline samples were synthesized by using a two-step solid state reaction method [9]. Firstly, SrAs powders were obtained by the chemical reaction method with Sr pieces and As grains. Then they were mixed with V 2 O 5 (purity 99.9%), SrO (purity 99%), Fe and Sr powders (purity 99.9%), in the formula Sr 2 VO 3 FeAs, ground and pressed into a pellet shape. The weighing, mixing and pressing processes were performed in a glove box with a protective argon atmosphere (the H 2 O and O 2 contents are both below 0.1 PPM). The pellets were sealed in a silica tube with 0.2 bar of Ar gas and followed by a heat treatment at 1150 °C for 40 hours. Then it was cooled down slowly to room temperature. (between 4.2K and 300K), were done in a sintered diamond Bridgman anvil apparatus using a pyrophillite gasket and two steatite disks as the pressure medium [14]. Pressure cannot be cycled and thus measurements are done only with increasing pressure.

The angle dispersive X-ray diffraction studies on Sr 2 VO 3 FeAs powder samples were performed at the ID27 high-pressure beamline of the European Synchrotron Radiation Facility using monochromatic radiation (λ=0.3738Å) and diamond anvil cells. Two transmitting media were used, nitrogen for the room temperature experiment and helium for the low temperature one. The pressure was determined using the shift of the fluorescence line of the ruby. The diffraction patterns were collected with a CCD camera, and the intensity vs.

2! patterns were obtained using the fit2d software [15]. A complete Rietveld refinement was done with the GSAS-EXPGUI package [16].

The electronic properties for the different structures are analyzed within the Density Functional Theory (DFT) framework. We used the full-potential linearized augmented plane wave code (Wien2k) [START_REF] Blaha | WIEN2K, An Augmented Plane Wave and Local Orbitals Program for Calculating Crystal Properties[END_REF] and GGA [START_REF] Perdew | [END_REF] to represent the exchange correlation potential. The positions for the "heavy" elements are taken directly from the experiments while oxygen coordinates were optimized. To calculate the weighted real part of the Lindhard susceptibility we evaluate the integral

! Q = A k .A k +Q " ( f k # f k +Q ) ($ k # $ k +Q + i% ) k &
. ! is a small energy smearing and k A and k Q A + the contributions of the FeAs layers to the electronic states at k and k+Q. They are evaluated as the corresponding LAPW projections inside the muffin-tin spheres for the Fe and As atoms. Q ! is evaluated averaging 20 different slices along the k z axis of the reciprocal space. A fine mesh of 100x100 was used for the k x / k y plane.

On Fig. 1b we show the evolution of electrical resistance with pressure on two different samples. They are metallic, following a T 2 dependence, with a magnitude that decreases with pressure, while the transition to the superconducting state decreases gradually. Normalizing the resistance with respect to the near ambient value and zooming (Fig. 1c), it is clear that there is a change of the low temperature behaviour starting at pressures around 10GPa, with a less metallic behaviour at high pressures in this region. The detail of the variation of the superconducting T c , presented on Fig. 4a, shows that T c is almost constant up to ~8GPa decreasing monotonously above, with an extrapolated null value at about 25GPa.

The structural measurements are shown on Fig. A straightforward way to understand the properties of Sr 2 VO 3 FeAs and the effect of compression is to calculate the electronic properties directly from the actual, measured atomic positions at each particular pressure. Fig. 3a shows the band structures for three different pressures, indicating the contributions of the different subsystems: the states coming from the FeAs layers (in red) and from the Sr 2 VO 3 block (in blue). We will concentrate only on the states coming from the FeAs subsystem, supposedly to be the important ones for superconductivity, as suggested by Mazin [19], weighting the electronic states with the corresponding FeAs contributions. The respective weighted Fermi surfaces are shown on Fig. 3b. Comparing with other pnictides, the electron FS are no more circular cylinders, but flatter, open vertex square cylinders due to the deformation of the tetrahedra and the partial hybridization with V orbitals [14,20,21]. An important parameter to analyse the antiferromagnetic correlations or a spin density wave (SDW) state on these compounds is the real part of the Lindhard electronic susceptibility,

! Q = ( f k " f k +Q ) (# k " # k +Q ) k $
, where f k and ! k are the occupation and the energy of the electronic state of wavevector k, for a particular wavevector Q. It is large when it connects large "parallel" (energy degenerate and thus diverging in Q ! ) portions of the FS. At certain temperature, the electronic system can overreact to any spin wave fluctuation of Q, developing a permanent SDW. Doping (addition or subtraction of electrons) modifies the FS, diminishing Q ! , that below a certain value can no longer trigger the SDW. In the spin fluctuation driven scenario for superconductivity [22], the residual, though still strong, value of Q ! is then the main item responsible for a strong pairing interaction generating a high superconducting transition temperature T c .

From our band structures and analysing the weighted Q ! it is further clear that the V bands and their charge transfer ("self-doping") do not wipe away the characteristic ΓM (Q=1/2) peak held responsible for the SDW in pnictides, that remains strong (Fig. 3c). The main outcome of the FS change of shape is that incommensurate nesting peaks in the real part of the bare susceptibility appear at q'~1/4, smaller but of comparable magnitude, as shown on Fig. 3c. They are particular to this compound and do not appear in other Fe superconductors.

Multiple nesting features can be held responsible for the quenching of the itinerant magnetic order, as, plainly speaking, the entropy introduced by the different possible ground states prevents the electron system from developing one of them. Following Moriya's Self Consistent Renormalization theory [START_REF] Moriya | Spin Fluctuations in Itinerant Electron Magnetism[END_REF], the effective on site electron repulsion U eff that defines the actual SDW transition temperature

T * when 1 ! Q 0 T ( ) < U eff , becomes U' eff = U eff ! 5gT " q' q'
# , (g is a positive constant depending on band structure and ! q' the susceptibilities for the other nestings), effectively lowering the temperature for the appearance of the ordered antiferromagnetic state. The quenching leaves the FS of the compound ungapped down to the temperatures where a superconducting state, originated from the same magnetic interaction, may appear. The peculiar FS of Sr 2 VO 3 FeAs explains its unusual properties: no magnetic ground state but superconductivity for the undoped material.

Although at this stage it is only a hypothesis, the behaviour of the compound and its band structure at high pressures will give strong support for this scheme as is shown below. Above ~10GPa the FeAs 4 tetrahedra becomes irregular and the e g derived bands (red in the Fig. 3a) are no more degenerate at the Γ point. The d xy band increases in energy while the d yz +d zy band decreases. The consequence on the FS is that the hole circular cylinders at the Γ point break up, spreading out the incommensurate nesting peaks at q'~1/4, notably diminishing their magnitude. While the commensurate Q=1/2 is broadened, but without losing appreciably its relative weight. To quantify this effect by separating it from the overall variation of the system, the background is subtracted from the amplitude of both peaks. Both !" 1 Experimental searching for a low temperature magnetic order at these pressures is presently impossible. We have looked for a possible lattice distortion, as due to fundamental symmetry reasons, the expected SDW order cannot appear in a tetragonal lattice [START_REF] Cano | [END_REF]. However, we have not observed any lattice distortion at low temperatures and high pressures, situation that only allows the SDW fluctuations that affect the resistance.

On the other hand, in our analysis the perovskite V bands contribute only by seriously deforming the Fe bands. This causes an electron charge transfer between Fe and V bands that we have evaluated by considering the corresponding LAPW projections inside the muffin-tin spheres. The obtained charge transfer is monotonous with pressure and cannot explain the non-monotonous variation of T c . In some recent papers, ferromagnetic ordering of the V atoms at low temperatures has been reported [25,26,27,28]. However, this ordering is only observed in samples with low T c (25K< T c <35K) at ambient pressure. It has been shown [29] that low T c -s are the result of oxygen deficiencies. These, comparative to ours, low T c samples also show a remarkably different behaviour at low pressures[26], increasing monotonously up to values similar to ours. The only ARPES measurements existing in the literature [27], shows closed Fermi surfaces different to ours, that support an ordered magnetic state for the V atoms, but once more with c lower than ours. Also, clear evidence of V magnetic ordering [30] has been observed in samples with a T c ~33K, that according to Ref. [29] corresponds to a stoichiometry Sr 2 VO 2.65 FeAs. However, no magnetic ordering has up to date been reported on samples with correct oxygen stoichiometry, T c -s~40K, as is the case of our samples. We claim that stoichiometric samples do not present V magnetic ordering, justifying our analysis.

Nonetheless, careful measurements with well determined oxygen stoichiometry are necessary to clarify the issue.

Changes of charge transfer under pressure can explain the evolution of superconductivity in a large number of cuprates [START_REF] Núñez-Regueiro | High pressure measurements on mercury cuprates[END_REF]. Furthermore, measurements of the evolution of T c under pressure in K x Sr 1-x Fe 2 As 2 for different show the relevance of this effect in 122 pnictides, as pressure has the same effect as doping as shown in Ref [START_REF] Gooch | [END_REF]. Thus, it is necessary to check the importance of this effect in Sr 2 VO 3 FeAs. However, the calculated evolution of charges as a function of pressure is monotonous, and cannot explain a T c pressure dependence with the abrupt change observed at ~10GPa, although it could be important in a quantitative calculation of T c .

To verify if the deformation of the tetrahedra is the reason behind the !" 1 ¡ change, the electronic band structure corresponding to a putative crystal with the 19.47GPa a and c lattice parameters but with an undeformed tetrahedron was calculated. The calculated !" 1 ¢ falls now on the same curve as the !" 1

2

, showing that the decrease is effectively due to the deformation of the tetrahedron.

If the q'~1/4 incommensurate peaks quenches the SDW state switching the antiferromagnetic fluctuations strength towards superconductivity, it should be possible to scale the dependence of T c with pressure on that of !" 1 £ as a parameter. One possible phenomenological scaling

(V ~!" 1 4
) is shown on Fig. 4d. The correlation between the two trends is clear, taking into consideration that, from our calculations, the Fe projected N(E F ) is almost constant as a function of pressure. Furthermore, the value calculated for the undeformed tetrahedron simulation falls at a value near to the ambient pressure T c .

In conclusion, we have measured the evolution with pressure of superconductivity and crystallographic structure, calculating the electronic properties for the actual positions at each pressure. Contrary to other pnictides, we find here multiple nesting that should play an important role in antiferromagnetism and superconductivity. Above ~10 GPa, we observe that the regular FeAs 4 tetrahedron strongly distorts, breaking band degeneracy and degrading the multiple nesting of the Fermi surface, with an simultaneous effect on T c , that goes gradually to zero. Our data provide a transparent explanation for the dependence of T c with the regularity of the FeAs 4 tetrahedron for this material, while strongly supporting the importance of the antiferromagnetic correlations for superconductivity. .

2 .

 2 Although there seems to be no phase transition to a new crystallographic structure, once more several anomalies are present in the region around 10GPa. There is a kink in the variation of the c/a ratio (mid panel of Fig.2a), that as shown on Fig.2bcorresponds to a sudden halt of the decrease of the FeAs distance (upper panel), with almost no variation within error bars of the width of FeAs layer (middle panel) or an end to the decrease of the As 1 -As 2 distance (lower panel). All these dependences can be summarized clearer by the variation of the angles of the FeAs 4 tetrahedron (Fig.4b), that pass, within error, from a regular (109°47') and almost constant value below ~10GPa, to irregular values that correspond to a deformed, stretched along the z direction, tetrahedron.

2 and !" 1 R 1 2

 211 are plotted as a function of pressure on Fig.4c. While !" varies slightly, !" 1 decreases monotonously, parting away from the former at ~10GPa, which coincides with the beginning of both the deformation of the FeAs 4 tetrahedron and the decrease of T c . As a result the antiferromagnetic Q=1/2 ground state is now favoured, explaining both the low temperature less metallic behaviour above 10GPa, together with the decrease of the superconducting T c. .

Figure 1 (

 1 Figure 1

Figure 2 (K'

 2 Figure 2 (a) X-ray diffraction pattern measured and calculated (black dots and red lines,

Figure 3 (

 3 Figure 3

Figure 4 ( 1 ¤

 41 Figure 4

  The electrical resistance measurements were performed using a Keithley 220 source and a Keithley 2182 nanovoltmeter. Pressure measurements,

	4 . 1 !	GPa 22

Acknowledgements

This work was partially supported by the project TetraFer ANR-09-BLAN-0211 of the Agence Nationale de la Recherche of France. R.W. is member of CONICET-Argentina and gratefully acknowledges partial support from CONICET (Grant No. PIP 112-200801-00047) and ANPCyT (Grant No. PICT 837/07).


C Bautista-Santiago

J Cano

R Fabila-Monroy

D Flores-Peñaloza

H González-Aguilar

D Lara

E Sarmiento

J Urrutia

On the Connectedness and Diameter of a Geometric Johnson Graph

Keywords: Johnson graph, intersection graph, diameter, connectedness, islands

Let P be a set of n points in general position in the plane. A subset I of P is called an island if there exists a convex set C such that I = P ∩ C. In this paper we define the generalized island Johnson graph of P as the graph whose vertex consists of all islands of P of cardinality k, two of which are adjacent if their intersection consists of exactly l elements. We show that for large enough values of n, this graph is connected, and give upper and lower bounds on its diameter.

Introduction

Let [n] := {1, 2, . . . , n} and let k ≤ n be a positive integer. A k-subset of a set is a subset of k elements. The Johnson graph J(n, k) is the graph whose vertex set consists of all k-subsets of [n], two of which are adjacent if their intersection has size k -1. The Kneser graph K(n, k) is the graph whose vertex set consists of all k-subsets of [n], two of which are adjacent if they are disjoint. The generalized Johnson graph GJ(n, k, l) is the graph whose vertex set consists of all k-subsets of [n], two of which are adjacent if they have exactly l elements in common. Thus GJ(n, k, k -1) = J(n, k) and GJ(n, k, 0) = K(n, k).

Johnson graphs have been widely studied in the literature. This is in part for their applications in Network Design-where connectivity and diameter (i) are of importance. (Johnson graphs have small diameter and high connectivity.) Geometric versions of these graphs have been defined in the literature. In [START_REF] Araujo | On the chromatic number of some geometric type Kneser graphs[END_REF] the chromatic numbers of some "geometric type Kneser graphs" were studied. In this paper we study the connectedness and diameter of a "geometric" version of the generalized Johnson graph.

Let P be a set of n points in the plane. A subset I ⊂ P is called an island if there exists a convex set C such that I = P ∩ C. We say that I is a k-island if it has cardinality k (see Figure1). Let 0 ≤ l < k ≤ n be integers. The generalized island Johnson graph IJ(P, k, l) is the graph whose vertex set consists of all k-islands of P , two of which are adjacent if their intersection has exactly l elements. Note that IJ(P, k, l) is an induced subgraph of GJ(n, k, l). If P is in convex position, then IJ(P, k, l) and GJ(n, k, l) are isomorphic-since in this case every subset of k points is a k-island.

Fig. 1: A subset of 5 points which is a 5-island, and a subset of 5 points which is not (both painted black).

Graph parameters of IJ(P, k, l) can be translated to problems in Combinatorial Geometry of point sets.

Here are some examples.

-The number of vertices of this graph is the number of k-islands of P -the problem of estimating this number was recently studied in Fabila-Monroy and Huemer (2011).

-An empty triangle of P is a triangle with vertices on P and without points of P in its interior.

The empty triangles of P are precisely its 3-islands (or the number of vertices in IJ(P, 3, l)).

Counting them has been a widely studied problem [START_REF] Bárány | Empty simplices in Euclidean space[END_REF]; [START_REF] Bárány | Planar point sets with a small number of empty convex polygons[END_REF]; [START_REF] Dumitrescu | Planar sets with few empty convex polygons[END_REF]; [START_REF] Katchalski | On empty triangles determined by points in the plane[END_REF][START_REF] Valtr | On the minimum number of empty polygons in planar point sets[END_REF].

-A related question [START_REF] Bárány | Problems and results around the Erdős-Szekeres convex polygon theorem[END_REF] is: What is the maximum number of empty triangles that can share an edge? This translates to the problem of determining the clique number of IJ(P, 3, 2).

The paper is organized as follows. In Section 2, we prove that IJ(P, k, l) is connected when n is large enough with respect to k and l. The proof of this result implies an upper bound of O n k-l + O(kl) on the diameter of this graph. In Section 3, we improve this bound for the case when l ≤ k/2, where we show that the diameter is at most O(log n)+O(k -l). We also exhibit a choice of P for which IJ(P, k, l) has diameter at least Ω log n-log k log(k-l)

. Note that these bounds are asymptotically tight when l ≤ k/2 and, Fig. 2: A 4-island which is projectable, and a 4-island which is not projectable.

k and l are constant with respect to n. A preliminary version of this paper appeared in [START_REF] Bautista-Santiago | On the diameter of a Geometric Johnson type graph[END_REF].

Connectedness

In this section we prove the following theorem.

Theorem 2.1 If n > (k -l)(k -l + 1) + k, then IJ(P, k, l) is connected and its diameter is O n k-l + O(k -l).
The proof is divided in two parts:

• First we choose F, an appropriate 'core' subgraph from IJ(P, k, l) which has small diameter and is connected.

• Next we prove that for every vertex in IJ(P, k, l) there is a path of length at most O n k-l connecting it to a vertex in F.

2.1 Choosing a core subgraph from IJ(P, k, l)

Let P := {p 0 , p 1 , . . . , p n-1 } be a set of n points in general position in the plane. So that p 0 is the topmost point of P , and p 1 , . . . , p n-1 are sorted counterclockwise by angle around p 0 . For 0 ≤ i ≤ j ≤ n, let P i,j := {p i , p i+1 , . . . , p j } and let P ′ i,j := P i,j ∪ {p 0 }. Observe that P i,j and P ′ i,j are both islands of P . We call these two types of islands projectable, and define this concept next.

Definition 2.2

The projection of a point p i , i = 0, is the intersection of the ray emanating from p 0 and passing through p i with a horizontal line. The projection of an island is the projection of its point set after omitting p 0 . Projectable islands are those islands that can be "projected" in such a way that its points are consecutive in the image of the whole set; see Figure 2.

Let F be the subgraph of IJ(P, k, l) induced by the projectable k-islands of P . Let S be a set of n -1 points on a horizontal line h, and let S ′ := S ∪ {x}, where x is a point not in h. It is not hard to see that F is isomorphic to IJ(S ′ , k, l). We classify the islands of S ′ into two types: those that contain x, and those that do not. Notice that these two types correspond to the two types of projectable islands of P . Now we show that IJ(S ′ , k, l) is connected. First we consider the subgraph of IJ(S ′ , k, l) induced by those islands of S ′ that do not contain x. Note that this is precisely IJ(S, k, l). Without loss of generality assume that S is a set x 1 < x 2 < • • • < x n-1 of points on the real line. Observe that a k-island of S is an interval of k consecutive elements {x i , . . . , x i+k-1 }. For the sake of clarity, in what follows we refer to k-islands of S as k-intervals.

Two k-intervals of S are adjacent in IJ(S, k, l) if they overlap in exactly l elements. It follows easily that if l > 0, each k-interval is adjacent to at most two different k-intervals, one containing its first element, and the other containing its last; see Figure 3. Since IJ(S, k, l) has no cycles and its maximum degree is at most two, it is a union of pairwise disjoint paths. These paths can be described as follows. For i < j, let A i and A j be the intervals ending at x i and x j respectively. There is a path between A i and A j if and only if i ≡ j mod (kl). Consider the interval adjacent with A i to its right, this interval must end at point x i+(k-l) (leaving exactly l points on the intersection). On the other hand, the interval adjacent with A i to its left, must end at point x i-(k-l) ; see Figure 3. For 0 ≤ r < kl, let P r be the subgraph of IJ(S, k, l) induced by those k-intervals ending at a point with index congruent to r mod (kl). Thus we have:

Proposition 2.3 If l > 0, P r is an induced path of IJ(S, k, l). Moreover IJ(S, k, l) is the union of {P r |0 ≤ r < k -l}.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

A 7 A 11 A 15 Fig. 3: Three different k-intervals, for |S| = 16, k = 6, l = 2.
For l = 0 and n ≥ 3k -1, every k-interval would either intersect the left-most k-interval or the rightmost k-interval, but not both. In this case IJ(S, k, 0) is connected and its diameter is at most 3. Note that except for some special cases, IJ(S, k, l) is disconnected. Remarkably, as we show next, for a large enough value of n, the addition of one extra point makes the graph connected.

As before A i is the k-island (k-interval) that ends at point x i and does not contain x. Let A ′ i be the k-island ending at point x i and containing x; see Figure 4. The structure of IJ(S ′ , k, l) when l < 2 is different from when l ≥ 2. In what follows, we assume that l ≥ 2 and briefly discuss the case l < 2 at the end of this section. Note that the subgraph of IJ(S ′ , k, l) induced by the A i 's is precisely IJ(S, k, l); and the subgraph induced by the islands A ′ i is isomorphic to IJ(S, k -1, l -1). From these observations, the following lemma is not hard to prove:

Lemma 2.4 If l ≥ 2, then in IJ(S ′ , k, l): 1. A i is adjacent to A ′ i-(k-l) and A ′ i+(k-l)-1 (if they exist). 2. A ′ i is adjacent to A i+(k-l) and A i-(k-l)+1 (if they exist).
The following theorem provides sufficient and necessary conditions for IJ(S ′ , k, l) to be connected.

Theorem 2.5 For l ≥ 2, the graph IJ(S ′ , k, l) is connected if and only if n ≥ 3k -2l -1 or n = k. Proof: Let I and J be two k-islands of S ′ . As long as the intermediate islands exists we can repeatedly use Lemma 2.4 to find a path from I to an island whose endpoint is in the same residue class of (kl) as the endpoint of J, and that contains x if and only if J does. This is the case whenever n ≥ 3k -2l -1: Consider the set of islands {A k , A k+1 , A k+2 , . . . , A k+(k-l-1) }. Notice that, for any value of k and l ≥ 2, all islands in this set exist. Furthermore, there is exactly one island in the set for each residue class. Afterwards Proposition 2.3 ensures that there is a path from this island to J. Suppose that n < 3k -2l -1, then there exists a k-island containing x and having less than kl points to its left and less than kl points to its right. This island is an isolated vertex in IJ(S ′ , k, l). This sole vertex is all of IJ(S ′ , k, l) when n = k (in which case the graph is connected). However, if n > k, there are at least two such k-islands. ✷

The proof of Theorem 2.5 implicitly provides the following bound on the diameter of IJ(S ′ , k, l).

Proposition 2.6 If IJ(S ′ , k, l) is connected, then its diameter is O n-k k-l + O(k -l).
Proof: Suppose that n ≥ 3k -2l -1, as otherwise the bound trivially holds. Let I and J be two k-islands of S ′ . Note that it takes at most 2(kl) applications of Lemma 2.4 to take I to an island whose endpoint is in the same residue class of (kl) as the endpoint of J, and that contains x if and only if J does. The path in IJ(S ′ , k, l) or in IJ(S, k, l)-depending on whether J contains x or not-connecting this island to J has length at most ⌈ n-k k-l ⌉. ✷

Finally we consider the case when l < 2. As we mentioned before, if l = 0 and n ≥ 3k -1, IJ(S, k, 0) is connected and its diameter is at most 3. This is the case also for IJ(S ′ , k, 0). On the other hand, if l = 1, then the islands containing x induce a graph isomorphic to IJ(S, k-1, 0). From these observations and Lemma 2.4, we get the following result.

Proposition 2.7 If n ≥ 3k, IJ(S ′ , k, 0) and IJ(S ′ , k, 1) are connected and of diameter at most 4. ✷

Paths between projectable and non projectable islands

To finish the proof of Theorem 2.1, we prove that for any island of P , there is a path connecting it to a projectable island. At the end of this section we present a first bound on the diameter of IJ(P, k, l).

Recall that P = {p 0 , p 1 , . . . , p n-1 }; p0 is its topmost point and p 1 , . . . , p n-1 are sorted counterclockwise by angle around p 0 . Let A be an island of P such that |A \ {p 0 }| ≥ 2. Define the weight of A as the difference between the largest and the smallest indices of the elements of A \ {p 0 }-an island of weight k -1 is always projectable. The following lemma ensures the existence of a path between any island and a projectable island, by eventually reducing the weight of any given island.

Lemma 2.8 (Shrinking Lemma). If n > (kl)(kl + 1) + k, then every non projectable k-island A of P has a neighbor in IJ(P, k, l) which is either a projectable island or an island whose weight is less than that of A by at least kl.

Proof: Let the elements of A different from p 0 be p i1 , . . . , p im . Thus m is equal to k or to k -1 depending on whether A contains p 0 or not. Consider all maximal intervals of P \{p 0 } containing exactly l elements of A. (That is maximal sets of consecutive elements of P \ p 0 containing exactly l elements of A.)

We distinguish two of these intervals: the one containing the first point of P \ {p 0 } and the one containing the last. We refer to them as end intervals, and to the rest as interior intervals.

Note that there are at most kl + 1 such intervals and that every element of P \ {p 0 } is in at least one of them. Since n > (kl)(kl + 1) + k, one of these intervals, I, must contain at least (kl) points of P \ A.

Suppose that I is an interior interval. Let J := A ∩ I, note that |J| = l (if l = 0, set J := ∅). If J is non empty let B be the set of the kl points of I \ A closest (ii) to Conv(J). If J is empty then let B be any k-island contained in I \ A. Then J ∪ B is a k-island adjacent to A in IJ(P, k, l), and its weight is smaller than the weight of A by at least kl. Now suppose that I is an end interval, let p S and p E be the first and last elements in A ∩ I. If [p S , p E ] contains at least kl elements of P \ A, then proceed as with interior intervals. Otherwise, there are r < kl points of P \ A in I. If I is the first interval, then let B be the klr points previous to p S in P \ {p 0 }. If I is the last interval, then let B be the klr points after p E . Note that in either case, [p S , p E ] ∪ B is a projectable island adjacent to A. ✷

We are ready to finish the proof of Theorem 2.1.

Theorem 2.1 If n > (kl)(kl + 1) + k, then IJ(P, k, l) is connected and its diameter is

O n k-l + O(k -l).
Proof: Let A and B be k-islands of P . We apply Lemma 2.8 successively to find a sequence of consecutive adjacent islands A = A 0 , A 1 , . . . , A m and B = B 0 , B 1 , . . . , B m ′ , in which each element has weight smaller than the previous by at least kl, and the last element is a projectable island. Since the weight of the initial terms is at most n, these sequences have length O n k-l . As noted before the subgraph induced by the projectable islands is isomorphic to ii) The distance between Conv(J) and a point p / ∈ Conv(J), is defined as the length of the shortest line segment having p and a point of Conv(J) as endpoints.

IJ(S ′ , k, l). Simple arithmetic shows that if n > (k -l)(k -l + 1) + k, then n > 3k -2l -2. Thus this subgraph is connected and has diameter O n-k k-l + O(k -l) (Theorem 2.

and Proposition 2.6). Hence the diameter of

IJ(P, k, l) is O n k-l + O(k -l) as claimed. ✷ (
δ(x 16 ) = 5 δ(x 14 ) = 2 δ(x 12 ) = 3 δ(x 10 ) = 2 δ(x 8 ) = 4 δ(x 6 ) = 2 δ(x 4 ) = 3 δ(x 2 ) = 2 x 1 x 2 x 3 x 4 x
δ(x 1 ) = 1 δ(x 3 ) = 1 δ(x 5 ) = 1 δ(x 7 ) = 1 δ(x 9 ) = 1 δ(x 11 ) = 1 δ(x 13 ) = 1 δ(x 15 ) = 1
Fig. 5: A Horton set with 16 points, and the depth of its elements.

then δ(z) = δ(B), and this point has depth less than δ(C). Consider an edge of the convex hull of C, whose supporting line separates C and z. Let x and y be its endpoints. Then by Lemma 3.4, the island H 0 ∩ Conv({x, y, z}) contains at least 2 δ({x,y})-δ(z)-1 -1 ≥ 2 δ(A)-δ(B)-1 -1 points, none of which is in C. However, since these points do lie in B, there are at most kl of them. Therefore δ(A)δ(B) is O(log(kl)) as claimed. ✷ Theorem 3.6 The diameter of IJ(H 0 , k, l) for l ≥ 2 is Ω log n-log k log(k-l)

Proof: Let A be an island with the largest possible depth, which is ⌈log 2 n/k⌉. Let B be an island of depth 1. By Lemma 3.5 in any path joining A and B in IJ(H 0 , k, l), the depth of two consecutive vertices differs by O(log(kl)).Therefore any such path must have length Ω log n-log k log(k-l)

. ✷

We point out that there was an error in the proof of Theorem 11 in the preliminary version of this paperBautista-Santiago et al. ( 2010); thus the bounds stated there are incorrect.

The diameter of the generalized Johnson graph can be substantially different from that of the generalized island Johnson graph. The diameter of GJ(n, k, l) is O(k) when n is large enough, while the diameter of IJ(P, k, l) can be Ω log n-log k log(k-l)

. Determining upper and lower bounds for the diameter of IJ(P, k, l) seems to be a challenging problem when l > k/2. It might happen that there is a sharp jump in the diameter when l rises above k/2. We leave the closing of this gap as an open problem.

Fig. 4 :

 4 Fig.4:Four different k-islands in S ′ , for |S ′ | = 16, k = 6, l = 2.

Acknowledgements

Part of the work was done during the 2nd Workshop on Discrete Geometry and its Applications, held at Instituto de Matemáticas UNAM, Oaxaca, Mexico, September 2009. We thank all participants for useful discussions.

R.F-M and D. L. partially supported by Conacyt of Mexico, grant 153984. D. F-P. partially supported by grants 168277 (CONACYT, Mexico) and IA102513 (PAPIIT, UNAM, Mexico). J. U. partially supported by CONACyT of Mexico, grant CB-2012/178379.

Bounds

Upper bound

In this section, for the case when l ≤ k/2, we improve the upper bound on the diameter of IJ (P, k, l) given in Theorem 2.1. We use a divide and conquer strategy. Let A and B be two vertices of IJ(P, k, l). First we find a neighbor of A and a neighbor of B; discarding half of the points of P in the process. We iterate on the new found neighbors. Just before P has very few points and IJ(P, k, l) may be disconnected; we apply Theorem 2.1.

The following lemma provides the divide and conquer part of the argument. The proof uses some of the ideas of the proof of the Shrinking Lemma.

Lemma 3.1 Let A and B be two vertices of IJ(P, k, l). If n ≥ 2((kl)(kl + 1) + k), and l ≤ k/2, then there exists a closed halfplane, H, containing at most n/2 and at least (kl)(kl + 1) + k points of P . With the additional property that A and B, each have a neighbor contained entirely in H.

Proof:

We use the ham-sandwich theorem to find a line ℓ so that each of the two closed halfplanes bounded ℓ by contain ⌈k/2⌉ points of A and ⌈k/2⌉ points of B.

Without loss of generality suppose that the halfplane H above ℓ contains at most n/2 points of P . If H, however, does not contain at least (kl)(kl + 1) + k points of P , move ℓ parallel down until it does. In this case H would contain at least as many points of A and B as it previously did and since we are assuming that n ≥ 2((kl)(kl + 1) + k), it still contains at most n/2 points of P .

We will now show the existence of a neighbor of A in IJ(P, k, l) with the desired properties. The corresponding neighbor of B can be found in a similar way. Let P := P ∩ H and sort its elements by distance to ℓ. As in the proof of Lemma 2.8 we consider maximal intervals of P ′ containing exactly l consecutive elements of A. There is at least one such interval, given that H contains at least k/2 points of A and that we are assuming l ≤ k/2. The rest of the proof employs the same arguments as the proof of Lemma 2.8 to find a neighbor of A contained in one of these intervals.

Proof: Consider the following algorithm. Let A and B be two k-islands of P . We start by setting

Lower bound

For the lower bound we use Horton sets [START_REF] Horton | Sets with no empty convex 7-gons[END_REF]. We base our exposition on [START_REF] Matoušek | Lectures on Discrete Geometry[END_REF]. Let X and Y be two point sets in the plane. We say that X is high above Y (and that Y is deep below X), if the following conditions are met:

• No line passing through a pair of points of X ∪ Y is vertical.

• Each line passing through a pair of points of X lies above all the points of Y .

• Each line passing through a pair of points of Y lies below all the points of X.

For a set X = {x 1 , x 2 , . . . , x n } of points in the plane with no two points having the same x-coordinate and with the indices chosen so that the x-coordinate of x i increases with i, we define the sets X 0 = {x 2 , x 4 , . . .} (consisting of the points with even indices) and X 1 = {x 1 , x 3 , . . .} (consisting of the points with odd indices). Thus X 00 = {x 4 , x 8 , . . .}, X 01 = {x 2 , x 6 , . . .}, X 10 = {x 3 , x 7 , . . .} and X 11 = {x 1 , x 5 , . . .}. Definition 3.3 A finite set of points H 0 , with no two of points having the same x-coordinate, is said to be a Horton set if |H 0 | ≤ 1, or the following conditions are met:

• Both H 00 and H 01 are Horton sets.

• H 00 is high above H 01 .

Horton sets of any size were shown to exist in [START_REF] Horton | Sets with no empty convex 7-gons[END_REF]. We remark that in [START_REF] Matoušek | Lectures on Discrete Geometry[END_REF], in the definition of Horton sets, the second condition is that "H 00 is high above H 01 or H 01 is high above H 00 ". For our purposes we need to fix one of these two options.

Let H 0 := {x 1 , . . . , x n } be a Horton set of n points. Given an island A of H 0 , we define its depth, δ(A), to be the length of the longest string s := 00 . . . 0 of all zeros such that H s contains A. Thus for example, δ( 5. Note that the depth of an island is the depth of its shallowest point.

Lemma 3.4 Let x and y be two points of H 0 , such that x is to the left of y, and z is a point with depth less than δ({x, y}). Then the island H 0 ∩ Conv({x, y, z}) contains at least 2 δ({x,y})-δ(z)-1 -1 points with depth greater than that of z, and lying in between x and y.

Proof: Let A := H 0 ∩ Conv({x, y, z}). We will proceed by induction on r = δ({x, y})δ(z). If r = 1 there is nothing to prove, since 2 r-1 -1 = 0. Assume then that r > 1. Let s be the unique string of all zeros, such that H s contains A but H s0 and H s1 do not. Note that z lies in H s1 while x and y both lie in H s0 ; actually since we are assuming r > 1, they both lie in H s00 . Consider the set H s0 , since it is a Horton set, A contains at least a point in H s01 , between x and y. Of all such points, choose x ′ k to be the shallowest. The depth of x ′ k is one more than that of z. By induction, the island H 0 ∩ Conv({x, y, x ′ k }) contains a set I of at least 2 r-2 -1 points. These points have depth greater than that of x ′ k (thus contained in H s00 ) and lay between x and y. Therefore I is contained in A. For each point in I, consider the next point x m to its right in H s 0. This point must be in H s 01 and δ(z) < δ(x m ). Thus we have 2 r-2 -1 additional points in A. Note that the point to the right of x in H s 0 is not in the previous counting. Therefore A has at least 2 r-2 -1 + 2 r-2 -1 + 1 = 2 r-1 -1 points with depth greater than that of z, and lying between x and y. ✷ Lemma 3.5 If A and B are two adjacent islands in IJ(H 0 , k, l) (with l ≥ 2), then their depths differ by at most O(log(kl)).

Proof: Without loss of generality assume that the depth of A is greater than the depth of B. Let C be the island A ∩ B. Note that the depth of C is at least the depth of A. If z is the shallowest point of B,


Andrej Taranenko
email: andrej.taranenko@uni-mb.si

A new characterization and a recognition algorithm of Lucas cubes

Keywords: Lucas cubes, characterization, recognition algorithm

Fibonacci and Lucas cubes are induced subgraphs of hypercubes obtained by excluding certain binary strings from the vertex set. They appear as models for interconnection networks, as well as in chemistry. We derive a characterization of Lucas cubes that is based on a peripheral expansion of a unique convex subgraph of an appropriate Fibonacci cube. This serves as the foundation for a recognition algorithm of Lucas cubes that runs in linear time.

Introduction

Graphs based on binary strings are used as models for interconnection networks. Hypercube, being a popular interconnection scheme for multicomputers, has often been replaced by other models with similar properties comparable to those of hypercubes, where the number of vertices and edges in these alternative models does not increase as rapidly.

As such a model Fibonacci cubes have been defined in [START_REF] Hsu | Fibonacci cubes -a new interconnection topology[END_REF]; [START_REF] Hsu | Fibonacci cubes -a class of self-similar graphs[END_REF], followed by extended Fibonacci cubes [START_REF] Wu | Extended fibonacci cubes[END_REF] and Lucas cubes [START_REF] Dedó | The observability of the fibonacci and the lucas cubes[END_REF]. Various studies have been made on the structure and different properties of Fibonacci cubes, Lucas cubes as well as Fibonaccilike cubes, see [START_REF] Klavžar | On median nature and enumerative properties of fibonacci-like cubes[END_REF][START_REF] Klavžar | The degree sequence of fibonacci and lucas cubes[END_REF][START_REF] Klavžar | Edge-counting vectors, fibonacci cubes, and fibonacci triangle[END_REF][START_REF] Munarini | On the lucas cubes[END_REF][START_REF] Taranenko | Fast recognition of fibonacci cubes[END_REF], to name a few. We also refer to the extensive survey on Fibonacci cubes by [START_REF] Klavžar | Structure of fibonacci cubes: a survey[END_REF]. Both, Fibonacci and Lucas cubes, also appear in connection with resonance graphs in chemistry [START_REF] Taranenko | Fast recognition of fibonacci cubes[END_REF][START_REF] Žigert | Lucas cubes and resonance graphs of cyclic polyphenanthrenes[END_REF].

A Fibonacci string of length n is a binary string b 0 b 1 . . . b n-1 such that b i •b i+1 = 0, for i = 0, 1, . . . n-2. Equivalently, it is a binary string of length n without two consecutive ones.

The Fibonacci cube Γ n of order n has the Fibonacci strings as vertices, with two vertices being adjacent whenever they differ in exactly one coordinate. We also set Γ 0 = K 1 . See Fig. 1 for Fibonacci cubes of order n, for n = 0, 1, . . . , 5, with appropriate Fibonacci strings assigned to the vertices (these are omitted for Γ 5 for the clarity of the figure). The Lucas cube Λ n of order n is the graph with Lucas strings as vertices, again, with two vertices being adjacent whenever they differ in exactly one coordinate. We set Λ 0 = K 1 . See Fig. 2 for Lucas cubes of order n, for n = 0, 1, . . . , 5, with appropriate Lucas strings assigned to the vertices (again, these are omitted for Λ 5 for the clarity of the figure). Note, that vertices of Λ n can be obtained from the vertices of Fibonacci cubes Γ n-1 and Γ n-3 as follows: V (Λ n ) = 0V (Γ n-1 ) ∪ 10V (Γ n-3 )0 [START_REF] Munarini | On the lucas cubes[END_REF].

Γ 0 Γ 1 Γ 2 Γ 3 Γ 4 Γ 5 100
It is known that Fibonacci cubes and Lucas cubes are median graphs [START_REF] Klavžar | On median nature and enumerative properties of fibonacci-like cubes[END_REF]. For median graphs several efficient recognition algorithms are known. To mention the first polynomial algorithm with complexity O(nm) presented in [START_REF] Jha | Convex-expansions algorithms for recognition and isometric embeddings of median graphs[END_REF] and the much more advanced O((m log n) 1.41 ) algorithm stated in [START_REF] Hammack | Handbook of Product Graphs[END_REF]. This raises the natural question whether a faster recognition algorithm for special families of median graphs exists. For Fibonacci cubes this question was partially answered by presenting a recognition algorithm with the complexity O(m log n) [START_REF] Taranenko | Fast recognition of fibonacci cubes[END_REF]. Even more, [START_REF] Vesel | Linear recognition and embedding of fibonacci cubes[END_REF] recently answered the problem of existence of a linear recognition algorithm for Fibonacci cubes, presented in [START_REF] Klavžar | Structure of fibonacci cubes: a survey[END_REF]. For Lucas cubes no recognition algorithm exists to our knowledge and is presented in this paper.

The paper is structured as follows. The next section contains some basic definitions and results concerning median graphs and Lucas cubes. In Section 3 several structural properties and a characterization of Lucas cubes are given. Using these results in the final Section 4 a recognition algorithm for Lucas cubes is presented. The presented algorithm correctly recognizes a Lucas cube in linear time.

Preliminaries

The hypercube Q n of order n is the graph with the vertex set containing all binary strings of length n, where two vertices are adjacent whenever the two strings differ in exactly one position. Isometric graphs of hypercubes are called partial cubes.

Λ 0 Λ 1 Λ 2 Λ 3 Λ 4 Λ 5 0
The Fibonacci numbers form a sequence of positive integers F n , where F 0 = 0, F 1 = 1 and for n ≥ 2 satisfy the recurrence

F n = F n-1 + F n-2 .
Since a Lucas string is a binary string without two consecutive ones and without one both in the first and last position, we can say that a Lucas string contains no two consecutive ones in a circular manner. Moreover, in the rest of the paper, when dealing with Lucas strings, we will always compute indices modulo n, even when not explicitly stated.

For a triple of vertices u, v and w of a given graph G, a vertex x of G is a median of u, v and w if x lies simultaneously on shortest paths joining u and v, u and w, and v and w, respectively. If G is connected and every triple of vertices admits a unique median, then G is a median graph. It is well known that median graphs are partial cubes (cf. [START_REF] Hammack | Handbook of Product Graphs[END_REF]).

Let G be a connected graph with e = xy and f = uv two edges in G. We say that e is in relation

Θ to f if d(x, u) + d(y, v) = d(x, v) + d(y, u).
Θ is reflexive and symmetric, but need not be transitive. We denote its transitive closure by Θ * . It was proved in [START_REF] Winkler | Isometric embeddings in products of complete graphs[END_REF] that G is a partial cube if and only if G is bipartite and Θ = Θ * .

For X ⊆ V (G) we denote the subgraph of G induced by the set

X with G[X]. A subgraph H of a graph G is called convex, if it is connected and if any shortest path of G between two vertices of H is completely in H.
Let H be a fixed subgraph of a graph G, H ⊆ G. The peripheral expansion pe(G; H) of G with respect to H is the graph obtained from the disjoint union of G and an isomorphic copy of H, in which every vertex of the copy of H is joined by an edge with the corresponding vertex of H.

For an edge ab of graph G we define:

• W ab = {w ∈ V (G) | d(a, w) < d(b, w)} • W ba = {w ∈ V (G) | d(b, w) < d(a, w)} • F ab = {xy ∈ E(G) | x ∈ W ab and y ∈ W ba } • U ab = {w ∈ W ab | w is the end vertex of an edge in F ab } • U ba = {w ∈ W ba | w is the end vertex of an edge in F ab }
Let ab be an edge of a median graph G for which

U ab = W ab . Then G[W ab ] is called a peripheral subgraph of G. A Θ-class E of a median graph G is called peripheral, if at least one of G[W ab ] and G[W ba ] is peripheral for ab ∈ E. E is internal if it is not peripheral.
We will need the following well known lemma, cf. [START_REF] Hammack | Handbook of Product Graphs[END_REF].

Lemma 2.1 Let e = ab be an edge of a connected bipartite graph G.

Then (i) F ab = {f |f ∈ E(G), eΘf },
(ii) G\F ab has exactly two components.

The next theorem characterizes median graphs.

Theorem 2.2 [START_REF] Mulder | The structure of median graphs[END_REF] Let ab be an edge of a connected, bipartite graph G. Then G is a median graph if and only if the following three conditions are satisfied:

(i) G[U ab ] is convex in G[W ab ] and G[U ba ] in G[W ba ]. (ii) F ab is a matching defining an isomorphism between G[U ab ] and G[U ba ].
(iii) G[W ab ] and G[W ba ] are median graphs.

Characterization

Before we present the theorem that characterizes Lucas cubes, we will state some properties concerning this family of graphs.

Proposition 3.1 [START_REF] Klavžar | Edge-counting vectors, fibonacci cubes, and fibonacci triangle[END_REF] Let E be a Θ-class of the Lucas cube Λ n . Then |E| = F n-1 .

Let 0 p denote a binary string of length p ≥ 0 with all bits equal to zero, similarly 1 p is a binary string of length p with all bits equal to 1. Let x and y be two arbitrary binary strings, we write xy for the concatenation of x and y.

Obviously the vertex 0 n , has exactly n neighbours in Λ n , moreover it is the only vertex of degree n in Λ n [START_REF] Klavžar | The degree sequence of fibonacci and lucas cubes[END_REF]. Proposition 3.2 All neighbours of the vertex 0 n in the Lucas cube Λ n of order n ≥ 3 are of degree n -2.

Proof: Let v = 0 n . All the neighbours of v are binary strings with exactly one 1. Consider such a vertex u with one 1, say at p th position, 0 ≤ p ≤ n -1. Since the bits at positions p -1 and p + 1 must be 0, there are n -3 vertices with exactly two bits equal to 1, that are adjacent to u. The vertex v is also adjacent to u, therefore u is of degree n -2. Since u was arbitrarily chosen, this concludes the proof. ✷ While it is known [START_REF] Munarini | On the lucas cubes[END_REF]) that a Lucas cubes of order n is composed from two Fibonacci cubes of order n -1 and n -3 with some additional edges between the two, the next proposition characterizes, how these two Fibonacci cubes are induced.

Proposition 3.3 Let a = 0 n ∈ V (Λ n ) and ab ∈ E(Λ n ).
Then the following hold:

(i) Λ n [W ab ] is isomorphic to Γ n-1 . (ii) Λ n [W ba ] is isomorphic to Γ n-3 .
Proof: Since b has exactly one 1, assume it is at p th position, 0 ≤ p ≤ n -1. Then W ab = {x ∈ V (Λ n ) | where x has 0 at p th position} and From Theorem 2.2 and Propositions 3.3 and 3.4 we immediately obtain the following corollary.

W ba = {x ∈ V (Λ n ) |
Corollary 3.5 Let a = 0 n ∈ V (Λ n ) and ab ∈ E(Λ n ). Then the graph Λ n [U ab ] is isomorphic to Γ n-3 .
Let H be a subgraph of a graph G. Then ∂H is the set of all edges xy of G with x ∈ H and y / ∈ H.

Theorem 3.6 There exist exactly one convex subgraph H ⊆ Γ n isomorphic to Γ n-2 , such that the peripheral expansion pe(Γ n ; H) is isomorphic to the Lucas cube Λ n+1 .

Proof: Let H be a convex subgraph of Γ n such that pe(Γ n ; H) is isomorphic to Λ n+1 (assuming such H exists). Note that the peripheral expansion increases the degree of each vertex in the chosen subgraph H by 1 in the graph obtained by the peripheral expansion. Since Λ n+1 contains exactly one vertex of degree n+1, the vertex 0 n ∈ V (Γ n ) must be in H. Moreover, the vertices 10

n-1 ∈ V (Γ n ) and 0 n-1 1 ∈ V (Γ n ),
in G[W ab ] and the proof of Theorem 3.6 we can choose the labelling such that the vertices in G[U ab ] are of the form 0b 1 b 2 . . . b n-2 0. The set F ab defines an isomorphism between G[U ab ] and G[U ba ], so assign to the vertices in G[U ba ] the same Fibonacci string as their corresponding vertex in G[U ab ]. Now, add a 0 and 1 at the left hand side to all labels in G[W ab ] and G[W ba ], respectively. Since U ba = W ba , all the vertices have been assigned a (different) label. Moreover, the construction of the labels implies, that they are all Lucas strings of length n. What is left to prove is that two vertices are adjacent whenever the assigned labels differ in exactly one position. This clearly holds for all pairs of vertices, when both are either in W ab or W ba . Suppose, x ∈ U ab and y ∈ U ba . Then xy ∈ E(G) whenever xy ∈ F ab , it follows that the corresponding labels differ in exactly one position. By Lemma 2.1 the sets W ab and W ba are disjoint, therefore two vertices x ∈ W ab \U ab and y ∈ U ba are not adjacent in G. By construction, the labels of x and y differ in more than one position. It follows that G is isomorphic to Λ n . This concludes our proof. ✷

Note that condition (1) of Theorem 3.7 is necessary, since b has been arbitrarily chosen. There exists a graph G = pe(Γ n ; H) such that H is a convex subgraph of Γ n isomorphic to Γ n-2 where G is not isomorphic to Λ n+1 . See Fig. 3 for an example.

Fig. 1 :

 1 Fig. 1: Fibonacci cubes Γn, for n = 0, 1, . . . , 5.A Lucas string of length n is a binary string b 0 b 1 . . . b n-1 such that b i • b i+1 = 0, for i = 0, 1, . . . , n -1, where indices are computed modulo n. In other words, Lucas string is a binary string without two consecutive ones and without one both in the first and last position.The Lucas cube Λ n of order n is the graph with Lucas strings as vertices, again, with two vertices being adjacent whenever they differ in exactly one coordinate. We set Λ 0 = K 1 . See Fig.2for Lucas cubes of order n, for n = 0, 1, . . . , 5, with appropriate Lucas strings assigned to the vertices (again, these are omitted for Λ 5 for the clarity of the figure). Note, that vertices of Λ n can be obtained from the vertices of Fibonacci cubes Γ n-1 and Γ n-3 as follows: V (Λ n ) = 0V (Γ n-1 ) ∪ 10V (Γ n-3 )0[START_REF] Munarini | On the lucas cubes[END_REF].It is known that Fibonacci cubes and Lucas cubes are median graphs[START_REF] Klavžar | On median nature and enumerative properties of fibonacci-like cubes[END_REF]. For median graphs several efficient recognition algorithms are known. To mention the first polynomial algorithm with complexity O(nm) presented in[START_REF] Jha | Convex-expansions algorithms for recognition and isometric embeddings of median graphs[END_REF] and the much more advanced O((m log n) 1.41 ) algorithm stated in[START_REF] Hammack | Handbook of Product Graphs[END_REF]. This raises the natural question whether a faster recognition algorithm for special families of median graphs exists. For Fibonacci cubes this question was partially answered by presenting a recognition algorithm with the complexity O(m log n)[START_REF] Taranenko | Fast recognition of fibonacci cubes[END_REF]. Even more,[START_REF] Vesel | Linear recognition and embedding of fibonacci cubes[END_REF] recently answered the problem of existence of a linear recognition algorithm for Fibonacci cubes, presented in[START_REF] Klavžar | Structure of fibonacci cubes: a survey[END_REF]. For Lucas cubes no recognition algorithm exists to our knowledge and is presented in this paper.The paper is structured as follows. The next section contains some basic definitions and results concerning median graphs and Lucas cubes. In Section 3 several structural properties and a characterization of Lucas cubes are given. Using these results in the final Section 4 a recognition algorithm for Lucas cubes is presented. The presented algorithm correctly recognizes a Lucas cube in linear time.

Fig. 2 :

 2 Fig. 2: Lucas cubes Λn, for n = 0, 1, . . . , 5.

  where x has 1 at p th position}. (i) Consider a vertex x ∈ W ab . We know that the vertex x is of the form b 0 . . . b p-1 0b p+1 . . . b n-1 , which is a Lucas string. Then the binary string of length n -1 defined as b p+1 . . . b n-1 b 0 . . . b p-1 is clearly a Fibonacci string, since binary strings b 0 . . . b p-1 and b p+1 . . . b n-1 contain no two consecutive 1s, and b 0 and b n-1 cannot both be 1, since they are at the first and the last position of a Lucas string. The set W ab contains all Lucas string of the described form, therefore we obtain all Fibonacci strings of length n -1 in this manner. Since two vertices of W ab are connected if they differ in exactly one position, and the bit at position p, in the original Lucas string, we removed with this construction was equal to 0 in all strings, W ab induces a Fibonacci cube of order n -1 in Λ n and the assertion follows. (ii) Consider a vertex x ∈ W ba . We know that the vertex x is of the form b 0 . . . b p-1 1b p+1 . . . b n-1 , which is a Lucas string. Moreover, b p-1 = b p+1 = 0. Again, we construct a binary string of the form b p+2 . . . b n-1 b 0 . . . b p-2 , which is of length n -3. The rest follows the same line of thought as in (i), therefore the assertion follows. ✷ Proposition 3.4 Let E be a Θ-class of the Lucas cube Λ n . Then E is peripheral. Proof: Let a = 0 n be the unique vertex of degree n in Λ n . All the edges with one end-vertex equal to a belong to different Θ classes. Since there are n such edges and Λ n contains n different Θ-classes, we can arbitrarily choose one such edge. Let b be a vertex with exactly one 1 at p th position, 0 ≤ p ≤ n -1. Let e = ab ∈ E(Λ n ) and E = {f ∈ E(Λ n ) | eΘf }. We claim that E is peripheral with W ba = U ba . By Proposition 3.3 the graph Λ n [W ba ] is isomorphic to Γ n-3 . A vertex x ∈ W ba is adjacent (among others) to the vertex y which differs from x in exactly position p. Since W ba contains all and only vertices with 1 at position p, all vertices in W ba are adjacent to a vertex in W ab . It follows by definition of U ba that U ba = W ba and therefore E is peripheral. ✷

H Γ 4 Fig. 3 :

 43 Fig.3: A peripheral expansion pe(Γ4; H) where H is a convex subgraph isomorphic to Γ2

Acknowledgements

This work has been financed by ARRS Slovenia under the grant P1-0297 and within the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation. The author is also with Institute of Mathematics, Physics and Mechanics, Ljubljana.

which are both of degree n -1 cannot be in H, since by Proposition 3.2 all the neighbouring vertices of a = 0 n+1 ∈ V (Λ n+1 ) are of degree n -1, these two would be of degree n in the graph pe(Γ n ; H), they would of course both be adjacent to a in this graph.

Let b = 10 n-1 ∈ V (Γ n ). Suppose a vertex x ∈ W ba is in V (H). Since H is connected and we have established that a ∈ V (H), there exists a shortest path from x to a, which is completely in H (since H is convex). But a ∈ W ab , therefore any shortest path from a to x must contain an edge uv from F ab (due to Lemma 2.1). By the Convexity lemma [START_REF] Imrich | A convexity lemma and expansion procedures for bipartite graphs[END_REF] By the same reasoning, with c = 0 n-1 1 ∈ V (Γ n ), none of the vertices from W ca are in H.

Recall, that W ba (W ca ) contains all the vertices with 1 in the first and the last position, respectively. Consider the set S := V (Γ n )\(W ba ∪ W ca ) = W ab ∩ W ac . Since the graphs induced by W ab and W ac are convex in Γ n , the intersection (the graph induced by S) is also convex in Γ n . Then every vertex s ∈ S is of the form 0b 1 b 2 . . . b n-2 0, moreover it clearly contains all such vertices where b 1 b 2 . . . b n-2 is a Fibonacci string. Since two vertices are adjacent if they differ in exactly one position it follows that S induces a Fibonacci cube of order n -2. Set H := Γ n [S], which is clearly the unique subgraph induced on vertices of S isomorphic to Γ n-2 , so H exists.

It remains to prove, that pe(Γ n ; H) is isomorphic to Λ n+1 . As seen, the vertices of H are all of the form 0b 1 b 2 . . . b n-2 0. Let all the vertices in the isomorphic copy of H (introduced by the peripheral expansion) have the same assigned Fibonacci string as the corresponding vertices in H. Add a 0 to the beginning all vertices of Γ n , and a 1 to the beginning of all vertices in the isometric copy. In this way we obtain all Lucas strings of length n + 1. From the construction of the strings it is clear that two strings are connected in pe(Γ n ; H) if and only if they differ in exactly one position. ✷

The next theorem characterizes Lucas cubes.

Theorem 3.7 Let G be a connected bipartite graph, a ∈ V (G) of degree n and ab ∈ E(G). G is isomorphic to Λ n if and only if the following conditions are upheld:

(1) All the neighbours of a are of degree n -2.

(

(3) F ab defines an isomorphism between G[U ab ] and

(5) W ba = U ba .

Proof: Suppose G is isomorphic to Λ n . Condition (1) is true by Proposition 3.2. Since Λ n is a median graph [START_REF] Klavžar | On median nature and enumerative properties of fibonacci-like cubes[END_REF], by Theorem 2.2 conditions (2) and ( 3) are also true. Proposition 3.3 settles the condition (4). From Proposition 3.4 and its proof the final condition is also satisfied. For the reverse, suppose for a graph G all conditions are met. Let a ∈ V (G) be the vertex of degree n, and b ∈ V (G) be an arbitrary neighbour of a (which by assumption is of degree n -2). Clearly, if no such a exists or if there exists a neighbour b of a, such that the degree of b differs from n -2, G is not isomorphic to a Lucas cube of order n, therefore these conditions are necessary. Assign Fibonacci strings of length n -1 to all vertices of G[W ab ], we will refer to them as labels. From the convexity of G[U ab ] n = F h+1 + F h-1 for some h ≥ 1 and it is bipartite, otherwise graph is rejected. The computed value of h is also an input parameter of procedure LUCAS. The input graph fulfilling these conditions is declared isomorphic to a Lucas cube of order h if procedure LUCAS terminates without encountering REJECT statement.

In the presented procedure we denote by N S (v) the set of all neighbours of a vertex v, where neighbours are from the set S .

Procedure LUCAS(G, h)

Result: Proof: The steps from preprocessing can clearly be done in linear time. Note, that Steps 2-4 of procedure LUCAS can be computed in O(m) time. It has been show in [START_REF] Jha | Convex-expansions algorithms for recognition and isometric embeddings of median graphs[END_REF] that Steps 5-7 can be performed in time linear in the number of edges of the input graph. Moreover, Step 8 can be easily executed in linear time in the number of elements of the sets. Steps 9 and 10 can be done in constant time. So the complexity of the recognition algorithm depends on the complexity of the procedure Fibonacci(G,h,uv), which runs in linear time in the number of edges of the input graph [START_REF] Vesel | Linear recognition and embedding of fibonacci cubes[END_REF]. So the time complexity of the procedure LUCAS is linear in the number of edges, ie. O(|E(Λ h )|).

✷