Trista Lin
email: trista.lin@inria.fr

Hervé Rivano
email: herve.rivano@inria.fr

Frédéric Le Mouël
email: frederic.le-mouel@insa-lyon.fr

Performance Comparison of Contention-and Schedule-based MAC Protocols in Urban Parking Sensor Networks

Keywords: C.2.2 [Computer Systems Organization]: Computer Communication Networks-Network Protocols, Wireless communication; C.4 [Computer Systems Organization]: Performance of Systems Performance, Experimentation urban sensor network, network traffic modeling, information delay, TDMA, CSMA

Network traffic model is a critical problem for urban applications, mainly because of its diversity and node density. As wireless sensor network is highly concerned with the development of smart cities, careful consideration to traffic model helps choose appropriate protocols and adapt network parameters to reach best performances on energy-latency tradeoffs. In this paper, we compare the performance of two off-the-shelf medium access control protocols on two different kinds of traffic models, and then evaluate their application-end information delay and energy consumption while varying traffic parameters and network density. From the simulation results, we highlight some limits induced by network density and occurrence frequency of event-driven applications. When it comes to realtime urban services, a protocol selection shall be taken into account -even dynamically -with a special attention to energy-delay tradeoff. To this end, we provide several insights on parking sensor networks.

INTRODUCTION

As the urban population is increasing, it brings the economic growth and the denser urban mobility [START_REF] Schrank | Urban Mobility Report[END_REF]. The first to be affected is the traffic congestion. Thanks to the smartphone technology, drivers can get diverse urban information simply from mobile apps. Thus, the availability and quality of urban information become the most important criteria for cities. User-generated urban information is the first proposed and enriches the information sources at different prospects. Various interesting information can also be shared according to users' sudden or periodic urban mobility. The published content could, however, be outdated or false because of insufficient participants or malicious users, as well as limited to human's observation. In view of this fact, wireless networked sensor devices help obtain more various types of information and assure of the accurate measurement. According to information types, sensor devices send updated information periodically or on-demand. That is, a network packet which consists of certain information, shall be treated with its corresponding priority in order to respect an acceptable information delay. Thanks to the increasing mobility need, some interesting urban services can be carried out by networked sensor devices. Among which, the traffic congestion is the greater thought at present and a huge percent of traffic jams are caused by the vehicles looking for parking spaces. So far as urban drivers are concerned, smart streetside parking system assisted by networked sensor devices is needed to shorten the parking search time and the parking distance from destinations.

These networked parking sensor devices detect the availability of parking spaces and form a wireless sensor network (Wsn). Such a so-called parking sensor network (Psn) has the following characteristics: First, parking sensors are stationary, in-ground and scattered with a minimum adjacent distance. Second, the network topology is linear and limited by urban street layout. Third, the sensing area of each parking sensor does not have any intersection because of the lack of multiple detection. Fourth, packet generation rate depends on the vehicle's arrival and departure. Fifth, the availability parking information is the data of real-time parking service. Based on these, we see the importance of device lifetime considering their maintenance and latency while providing real-time service to urban citizens. Hence, we can say that Psn is a specialized form of Wsn and also inherits its energy and delay constraints.

To optimize network parameters for best performance, the network traffic is significant. Three mainstream traffic models are request, event and time-driven. Request-driven models are irrelevant for parking sensor networks since continuous recording is required for municipalities. Time-driven or periodic application is often used in testing the performance of network protocols because of its low dependence on the environment. Event-driven application is tricky due to its variety on different types of observed events. Considering different configurations of parking sensor networks, the Mac protocol, which deals with the bandwidth allocation, will be the first to be confronted. The Wsn Mac protocols are mainly classified as contention-based and schedulebased. Contention-based protocols provide a contentionbased bandwidth allocation for sensor nodes and are widely discussed in urban applications. Schedule-based, also known as contention-free, protocols require at least one central node time-synchronized or asynchronized networks. Asynchronous method needs to perform a low power listening (Lpl) before transmitting each packet, thus its cumulative energy dissipation is not favorable for parking sensor network. From our survey, we are only interested in the impact of traffic intensity on time-synchronized Mac protocols. Our body of work is to simulate the traffic influence on stationary Wsn with the aim of improving the design of network architecture. Our contributions are summarized as follows: First, modeling of periodic and event-driven urban parking sensor applications by observing vehicle's arrival and departure. Second, energy and delay performance evaluation of two different applications through extensive experiments on urban scenarios, so as to compare two fundamental Mac protocols. Third, some key thresholds help to find a best configuration and highlight the importance to develop an adaptive Mac protocol which can distributedly detect the traffic intensity and switch between different configurations when required. Fourth, we also highlight some notbale issues while deploying multiple-hop parking Psn.

The remainder of this paper is structured as follows. In Section 2, we give a review on different MAC protocols. In Section 3 we introduce the network traffic model and the calculation of the information delay. In Section 4 we construct the urban environment and then perform the simulations by using contention-based and schedule-based Mac protocols. Finally, we summarize our works in Section 6.

RELATED WORKS

Smart on-street parking application has received a lot of attention in recent years. Its main mission are to collect the realtime parking availability information and to disseminate the information to mobile users simply through a smartparking app. Two types of collection methods are mobile and stationary. The former is to take advantage of vehicle's mobility to collect information along the route. In which, the most economical is crowdsourcing based mobile application. Therefore, it is obvious that crowdsourcing parking assistance system cannot provide a reliable realtime service required by municipalities [START_REF] Polycarpou | Smart parking solutions for urban areas[END_REF]. Neither does the mobile sensor side-mounted on a taxicab or bus for detecting an onstreet parking map. For example, the ParkNet system in San Francisco [START_REF] Mathur | Parknet: drive-by sensing of road-side parking statistics[END_REF], collects data with the location information from GPS receiver and then transmit it over a cellular uplink to the central server. Such a mobile parking sensor system requires much less installation, yet needs a longer average inter-polling time, to wit, 25 minutes for 80% of the cells in busier downtown area with only 300 cabs. Stationary collection method is to install on-site vehicle detection sensors [START_REF] Revathi | Smart parking systems and sensors: A survey[END_REF] to monitor the occupancy status of parking spaces. Based on this, large-scale road-side parking sensor network has been implemented in many cities, e.g., SFpark project [START_REF] Sfmta | Sfpark: Putting theory into practive[END_REF] in San Francisco, LA Express Park in Los Angeles, FastPrk in Barcelona, Connected Boulevard in Nice and so forth. Among them, the efficiency of parking sensor network is the first concern. A lot of protocols have been proposed for urban Wsn applications. We sort them out as the following three groups.

• Contention-based protocols are much widely studied in Wsn and generally based on or similar to Csma.

When one node has a packet to send, it will have to struggle with the other competitors to get permitted of using the medium. The winner selection is somehow randomized. The synchronous Mac protocols are generally duty-cycled and require time-synchronized, such as S-mac, T-mac, Conti [START_REF] Abichar | Conti: Constant-time contention resolution for wlan access[END_REF], Sift [START_REF] Jamieson | Sift: a MAC Protocol for Event-Driven Wireless Sensor Networks[END_REF] and so forth.

The state-of-the-art synchronization method is to be done through hardware or message exchange, and then a piggybacked acknowledge can be used to solve the clock shifting effect [START_REF] Stanislowski | Adaptive synchronization in ieee802.15.4e networks[END_REF]. The asynchronous versions use low-power listening(Lpl) or its preamble-shortened approach to match up the transmission period between transmitter and receiver end, such as B-mac, Wisemac, X-mac, Scp-mac [START_REF] Ye | Ultra-low duty cycle mac with scheduled channel polling[END_REF], Ri-mac [START_REF] Sun | Ri-mac: A receiverinitiated asynchronous duty cycle mac protocol for dynamic traffic loads in wireless sensor networks[END_REF] and so on. Among them, [START_REF] Kim | Performance evaluation of synchronous and asynchronous mac protocols for wireless sensor networks[END_REF][START_REF] Lampin | Wireless Urban Sensor network: Applications, characterization and protocols[END_REF][START_REF] Lampin | Cascading tournament mac: Low power, high capacity medium sharing for wireless sensor networks[END_REF] compared the power dissipation between asynchronous and synchronous contention-based protocol. In which, Lpl method is interesting in very low traffic intensity (less than one packet per day) or dynamically changing topologies. Otherwise, synchronous protocol outperforms asynchronous one. The drawback of such a protocol is the packet collision causing by increasing network density and hidden terminal.

• Schedule-based protocols are generally centralized and suitable for static topologies. Assigned nodes play the master role to allocate slotted network resource to their slaves. The mechanism is generally based on Tdma or Cdma. The clock of each node must be time-synchronized. Scheduled slots can be fixed or ondemand. Some noted protocols are like Drand [START_REF] Rhee | Drand: Distributed randomized tdma scheduling for wireless ad-hoc networks[END_REF], Leach [START_REF] Heinzelman | Energy-efficient communication protocol for wireless microsensor networks[END_REF], Trama [START_REF] Rajendran | Energy-efficient collision-free medium access control for wireless sensor networks[END_REF] and Tsmp [START_REF] Pister | Tsmp: Time synchronized mesh protocol[END_REF]. They use Tdma as the baseline Mac scheme, and then take Csma, Aloha or Cdma for improving these join/leave/synchronize messages. The drawbacks are firstly not easy to adapt to the dynamics of network, and secondly the slower response of the centralized control while adapting the schedule to the traffic variation.

• Hybrid contention-& schedule-based is to combine the advantages of both protocols in order to reach the best performance. Z-mac [START_REF] Rhee | Zmac: A hybrid mac for wireless sensor networks[END_REF] behaves like Csma under low competition and under high competition, like Tdma. Funneling-mac [START_REF] Ahn | Funneling-mac: A localized, sink-oriented mac for boosting fidelity in sensor networks[END_REF] uses Csma as the baseline, and changes to Tdma while receiving on-demand beaconing from the sink, that is to say, nodes close to the sink performs Tdma. Funneling-mac works in the application of data collection. iQueue-mac [START_REF] Zhuo | iqueue-mac: A traffic adaptive duty-cycled mac protocol with dynamic slot allocation[END_REF] runs in Csma in light load and then uses queue-length The occupancy and vacant durations are different to get due to the constraint of real Psn implementation. The arrival and departure were generally assumed Poisson distributed, and the occupancy rate of the parking system can be analyzed by Markov process. However, the newest report in Santander shows that the vehicle's occupied time can be described by Weibull distribution [START_REF] Vlahogianni | Exploiting new sensor technologies for real-time parking prediction in urban areas[END_REF]. Therefore, which type of MAC protocol suites best the urban smart parking application in terms of network density and traffic intensity? In this paper, we configure several different scenarios with different network density, traffic intensity and two mainstream Mac protocols in order to find the best configuration while constructing urban WSN applications.

NETWORK TRAFFIC MODEL

In urban sensor network, sensors are often stationary to monitor certain events, and thence the packet transmission shall always happen and never end. In other words, the key point of modeling an event-driven application will be to find an appropriate distribution to define the traffic interval, viz inter-event interval. Next, we present the modeling of the event occurrence and the definition of information delay with respect to urban smart parking applications.

Vehicle's arrival and departure

In parking sensor networks, the main observed events are vehicles' arrivals and departures. For any parking sensor, each vehicle arrival accompanies exact by one departure prior to next arrival. To model it, we first look at the event occurrence sequence on one parking sensor. We suppose each parking sensor is precise enough and provides merely two status, namely occupied and vacant. The occupied interval from vehicle's arrival to departure is so-called parking time Tp,t, conversely, the vacant interval is available time Tv,t. During which, each sensor detects vehicle's presence or absence at a given time t, shown in Figure 1. Both Tp,t and Tv,t proper shall be described by a fitting distribution in order to approximate their randomness. From Vlahogianni's report [START_REF] Vlahogianni | Exploiting new sensor technologies for real-time parking prediction in urban areas[END_REF], the massive real-time parking availability data, obtained by an on-street parking sensor network in Santander, shows that the occupied duration is best described by a Weibull distribution. By assuming that Tp,t and Tv,t are both Weibull distributed with rate parameters λ and µ and shape parameters α and β, we have:

• P r(Tp,t = X) = α λ α X α-1 e -( X λ
) α stands for the probability of choosing a occupancy time X.

• P r(Tv,t = Y ) = β µ β Y β-1 e -( Y µ ) β
stands for the probability of choosing a vacant time Y . The vehicle's interarrival duration can be expressed as Z = Tp,t + Tv,t in which, one turnover is counted. The occupancy rate will be E[Tp,t/(Tp,t + Tv,t)] = λΓ(1

+ 1 α )/(λΓ(1 + 1 α ) + µΓ(1 + 1 β )).
From literature, Pareto and Weibull distribution have been discussed to describe the burstiness of network traffic. While looking at the Figure 5 in [START_REF] Vlahogianni | Exploiting new sensor technologies for real-time parking prediction in urban areas[END_REF], the occupancy duration in four different regions follow the Weibull distribution with the shape parametes approximately 0.4∼0.7. When the shape parameter is smaller than 1, the occupancy duration is heavy-tailed [START_REF] Arfeen | The role of the weibull distribution in internet traffic modeling[END_REF]. We took the Weibull parameters in [START_REF] Vlahogianni | Exploiting new sensor technologies for real-time parking prediction in urban areas[END_REF] and then get its CDF and survival of Z in Figure 2. Hence, if Tp,t and Tv,t are both heavy-tailed, so is Tp,t + Tv,t. From [START_REF] Mitov | Superposition of renewal processes with heavy-tailed interarrival times[END_REF], the cdf F (t) of interarrival time Z has regularly varying tail such that:

1 -F (t) ∼ t -ǫ L(t) as t → ∞. L(t) is a slowly varying function at infinity, that is, limt→∞ L(tx)/L(t) = 1 ∀x > 0. From Mitov's model, the distribution function of the interarrival times is Weibull with 0 < ǫ ≤ 1, the shape parameter ν = 1 -ǫ and scale parame- ter γ = C sin πǫ π(1-ǫ) , provided that N t 1-ǫ → C, 0 < C < ∞
and N is the number of traffic sources, namely parking sensors. If we increase the amount of observed parking sensors, i.e., N , the vehicle interarrival time is shown in Figure 3 and the shape parameter is approximating to 1. The count model based on Weibull interarrival times is studied in [START_REF] Bradlow | Count models based on weibull interarrival times[END_REF]. The probability of k arriving vehicles in a given interval is calculated as below:

P (N (t) = k) = ∞ j=k (-1) j+k ( t γ ) νj ∆ k j Γ(νj + 1) k = 0, 1, • • • (1)
where

∆ k+1 j = j-1 m=k ∆ k m Γ(νj-νm+1) Γ(j-m+1) for k = 0, 1, 2, • • • and j = k + 1, k + 2, k + 3, • • • . ∆ 0 j = Γ(νj+1) Γ(j+1) j = 0, 1, 2, • • • .
In a business area or on weekdays, the average occupied time can be shorter according to the area hourely activities or parking policy. Its impact to network traffic will have to be considered as well.

Network traffic models

Event-driven traffic

The event occurrence frequency has a great impact on event-driven applications. Each parking sensor sends one packet while one vehicle arrives and another when it leaves, that is, sensor sends two packets every Tp,t+Tv,t which is the interarrival time of vehicles. The average interarrival of network packets from parking sensor i is 1 2 (λiΓ(1+

CN (∆t) = N i=1 2∆t λiΓ(1 + 1 α i ) + µiΓ(1 + 1 β i ) ( 2
)
Where ∆t is the observation period. When CN 1 (∆t) = CN 2 (∆t), the packet and vehicle interarrival durations are the same. However, in such a case, even though N1 = N2, we can still find several sets of different combinations of λi, αi, µi and βi. These parameters decide the variation of Tp,t and Tv,t which give the information about the utilisation of street parking.

Exponential distribution has been widely used for simulating the vehicle's arrival. It is one shape of Weibull distribution while shape parameter is equal to 1. Hence, we try to compare the differences while applying Weibull distribution in the network traffic model with respect to Exponential distribution. Figure 4 shows that the packet generation rate is strongly decided by the sum of Tp,t and Tv,t from equation [START_REF] Ahn | Funneling-mac: A localized, sink-oriented mac for boosting fidelity in sensor networks[END_REF], and also proportional to the shape parameter(ν) when the scale parameter(γ) is fixed. The reason of reducing packet generation rate is caused by part of longer parking occupancy time, which is well described by heavy-tailed distribution.

Then we fix the average of vehicle interarrival time and compare two different shape parameters 0.5 and 1. In Figure 5, we see that the non-uniform property is more obvious when the shape parameter is smaller than 1. This is because the infinite mean and infinite variance which make a larger variations among parking sensors. Moreover, what is the impact to the network coordinator? Figure 6 shows the network load while managing 24 parking sensors. We can see clearly that when the shape parameter is 0.5, the burstiness of network traffic is more significant but might not be considered in Exponential distribution.

Periodic/Time-driven traffic

On the contrary, periodic application is only affected by the traffic interval ω instead of event occurrence frequency. The amount of generated packets is inversely proportional to the traffic interval. While using periodic traffic model, the amount of network traffic is unaffected by the sensory information. It simply sends out a packet with the current time-stamped status when the time is up. Definition 1. Information delay T delay is the required time for knowing a changed occupancy status of a parking sensor.

In event-driven application, each sensor sends out the updated information at once when detecting any event, namely, application delay is almost zero. Periodic application is subject to the traffic interval so that an application delay shall be added up.

PARKING SENSOR NETWORK EXPER-IMENTS 4.1 Bandwidth allocation methods

Before starting the simulation, we compared several different MAC protocols. From the literature, we find that to choose a contention-or schedule-based Mac protocol has been the subject of much controversy. To compare their efficiency, we evaluate two off-the-shelf Mac protocols: dutycycled Tdma for schedule-based and duty-cycled Csma/ca for contention-based. From the reason mentioned in section 2, both of them are running under a time-synchronized environment. To minimize the idle listening period in each data slot, each transmitter sends a very small beacon to reserve an appointment before starting the data transmission. If the reservation fails, the transmitter will put the packet into the queue, turn off its radio and wait for the next time slot. Instead of wasting energy to do a vain transmission, sensor nodes prefer to evaluate the receiver's availability through these very small beacons.

Schedule-based bandwidth allocation

Considering the sensor network is often bandwidth-limited, the only medium resource is time divisions in a single-channel scenario. Each node arrived in the network will send a request in order to be preassigned to one partition of medium resource to transmit their packets. While the network coordinator does not know in advance the traffic model and node position, it preallocates an equal partition to all the nodes in his subnet. If a node has no packets to send in its term, the others still cannot seize this occasion to send their packets out. The duty cycle comprises an inactive period and at least N + 1 time slots for N parking sensors and 1 coordinator, shown in Figure 7. Each sensor can only send its packet on its pre-assigned time slots. The duration of duty cycle can be calculated by T dc = T slot * (N +1)+Tinactive. If the packet transmission fails on the current time slot, the next retrial will be in T slot (N + 1) seconds. The advantages of schedulebased B.A. are the nearly very little packet collision rate and lower energy consumption since nodes only send beacons in certain slots. If sensor nodes' traffic model is given, schedulebased B.A. can optimize the resource assignment to reach a better performance. The drawbacks are that many time slots are wasted and a longer delay time is caused, also the urban traffic model is dynamic and time-variant. Else, if there is a new node which intends to join this network, the gateway will have to reallocate the resource while there is no enough time slots.

Contention-based bandwidth allocation

Contention-based B.A. uses competition based medium access control due to the inflexible resource allocation previously mentioned. The principle is that the node gets its partition of network resource when it asks for. If more than two nodes declare their demands, a competition will be held to choose who is the current transmitter. The transmitter candidates randomly choose a waiting time for sending the reservation beacon and then listen to the medium before the waiting time expires. If these candidates hear any beacon in the meantime, they will turn off the radio and wait for next resource allocation. Otherwise, the candidate will send out a beacon message to announce its transmission. The duty cycle contains the competition, data transmission and inactive periods, shown in Figure 8, T dc = T slot + Tinactive. The advantages of contention-based resource allocation are the better use of network resource and a short network delay. The drawbacks is the inevitable packet collision which causes arbitrarily high energy consumption and latency on grounds of endless competitions triggered by high node density. If there is a new node which intends to join this network, it will just join the competition and increase the packet collision rate.

Simulation experiences

From the real implementation in SFpark project [START_REF] Sfmta | Sfpark: Putting theory into practive[END_REF], we find that the network coordinators (router or gateway) are always installed in crossroads considering the maximum coverage and the facility of relays. Hence, we first take one small cell in a crossroad with different network density. The topologies are depicted in Figure 9. Our simulations, performed with the WSNet simulator [START_REF]An event-driven simulator for large scale wireless sensor networks[END_REF], use the simulation parameters in table 1. We set the slot durations are both 0.1 seconds in order to have the same active time and so does the throughput. [START_REF] Watteyne | Implementation of gradient routing in wireless sensor networks[END_REF] Propagation: Corner pathloss(λ = 0.125) [START_REF] Sun | Analytical formulae for path loss prediction in urban street grid microcellular environments[END_REF]+Rayleigh fading els. The x-axis stands for the sensor number in the network. In schedule-based B.A., the minimum energy depletion is required to arrange the schedule. As the network dimension increases, each sensor also consumes more energy. Contention-based B.A. suffers from packet collision when the network competitors increase. Else, periodic traffic, which generates one packet per 60 seconds, has too much interference and cannot send more packets after there are more than 84 network competitors. Figures 12 and13 show the information delay of event-driven application under scheduleand contention-based B.A.. The information delay of periodic application is strongly related to the traffic interval and not appropriate for real-time urban application. We will show the result in next subsection. Event-driven application is more sensitive to the bandwidth allocation methods and generally proportional to the duration of duty cycle T dc . From the result, we know that: First, the probability of a packet arriving in k th duty cycle is p k k-1 i=1 (1 -pi) where pi is the probability that the packet is received in i th cycle. Second, when a packet arrives in k th duty cycle, the arriving time point is uniformly distributed with the mean T dc 2 . The expectation of information delay of event-driven application is calculated as below: Here pi is mainly a function of the network load, duty cycle and resource allocation method. In contention-based protocol, we see that packets have a very low chance to arrive the destination if they do not arrive in first duty cycle. When the network load is affordable for the network, p1 is quite high and {pi} ∞ i=2 are all similarly very low. If packets do not arrive within first duty cycle, the delay time starts to be arbitrarily large. That is the drawback of Csma. In schedule-based protocol, if packets do not arrive in first duty cycle, they still have a good chance to arrive in the coming cycles. In a word, we can get the following equations to calculate the information delay from the results:

Impact of network density

E[T delay ] = ∞ k=1 (p k k-1 i=1 (1 -pi))(k - 1 2 )T dc (3) = p1T dc 2 + ∞ k=2 (1 -p1)(1 -p2) k-2 p2(k - 1 2 )T dc (4)
E[T delay.contention ] = T dc ( 1 -p1 p2 + 1 2 ) E[T delay.schedule ] = T dc ( 1 p1 - 1 2
) for p1 = p2

Impact of traffic intensity and burstiness

The simulation we ran in this section used the topology depicted in Figure 9(b) with 24 nodes. Figure 14 shows the relationship between traffic interval ω and per-node energy consumption, we see that periodic traffic is less affected by the B.A. method and strongly related to the traffic interval. The periodic traffic is equivalent to constant bit rate so that the traffic is known and uniform among all sensor nodes. Hence the deviation of consumed energy is not apparent. In Figure 15, we see that the information delay between periodic and event-driven applications is not that different. Since the arriving time point during the traffic interval is uniformly distributed, its expected value can be calculated by the summation of the application-layer delay and Maclayer end-to-end delay, that is,

ω 2 + T dc ( 1-p 1 p 2 + 1
2 ). If the event occurrence frequency is much higher than traffic interval, the sensory status could change more than one time in ω seconds. In this way, some update information will be missed if the sensor does not store it into packet and the information delay will be also shorter and exponentially distributed. However, it is obvious that the consumed energy is extremely low while ω ≥ 1200. In other words, the information delay which is more than 1200 seconds will not be acceptable for realtime urban services. But it is interesting to assign a periodic traffic with a long interval on sensor nodes simply to inform gateways of their existences and current battery status. On the contrary, event-driven application, affected by Weibull distribution, has a larger variation on packet generation rate, and so does the energy consumption, shown in Figure 16. The burstiness of Weibull traffic model creates a strong non-uniform traffic on each sensor node because of its infinite variance. Figure 17 shows the information delay while the network dimension is fixed. When the network load is affordable for the network (p1 → 1), the information delay is generally proportional to T dc . When we increase the event occurrence rate (Tp,t + T v, t = 4800 → 320), p1 starts to reduce from 0.96 to 0.88 in schedule-based B.A. and from 0.99 to 0.96 in contention-based B.A.. Even the network load is high, contention-based protocol can still delivery more packets (79%) than schedule-based (68%) in first duty cycle thanks to its dynamic bandwidth allocation method. Schedule-based protocol requires more central information exchange between sensors and network coordinator so that it is much less adaptive to the traffic variation and not preferable for distant sensor nodes.

Impact of duty cycle

From Figure 18, duty cycle is generally determined by slot duration which is, however, bounded by traffic model. The minimum slot duration T slot.min shall be long enough to complete a reservation and a piggybacked packet transmission so that packet size and data rate are the important factors. Nevertheless, the maximum slot duration T slot.max is limited by the minimum required throughput according to applications carried out in the network. That is to say, if the slot duration is equal to T slot seconds, the maximum throughput will not exceed 1 T slot packets per second by assuming that the inactive period is zero. We varied slot duration from 0.1 to 1.2 seconds by applying the topology in Figure 9(b) with 24 nodes and then got the energy-delay T slot and results in more network competitors in each data slot. However, thanks to the extremely low collision rate in schedulebased B.A., the energy deviation is still low even though we increase the slot duration. Accordingly, while having the same slot duration, the energy consumption in contentionbased B.A. is a bit higher, yet the information delay is much shorter. In other words, subject to the throughput conditions, for the same information delay, contention-based B.A. consumes significantly less energy than schedule-based one.

Impact of multiple-hop

While deploying a large-scale parking sensor network, multiple hop is inevitable considering the complexity of urban environment and the limitation of transmission range. Since the transmission range is generally proportional to the transmit power output (Tpo), to reduce Tpo and transmit packets with a shorter transmission distance will be a good idea to extend the lifetime of parking sensors. The longer lifetime the sensor has, the fewer maintenance the municipality has. From the previously discussed, we see the problem of energy hole and hop limit (delay). For a better consideration, we take a parking map from SFpark [START_REF] Sfmta | Sfpark: Putting theory into practive[END_REF] and construct it in our simulation depicted in Figure 19. Here, all sensors work as a reduced function device and can only communicate with repeaters or gateways. Only repeaters and gateway, namely full function device, can forward any received packets until the packet arrives the gateway. Since parking sensor is generally in-ground and repeater can be installed on the streetlight and powered by solar cell, this configuration is greatly preferable to municipalities. With the parking map we have, we first deploy repeaters in each intersection and in the middle of the road section when needed. In this simulation, we take four different Tpo = {3, 0, -3, -7} dBm. In Figure 19, the red repeaters are needed when Tpo is equal to 3 and 0 dBm. When Tpo is -3 dBm, the red, blue and grey repeaters are all needed as well. When Tpo is -7 dBm, the grey repeater cannot provide a stable support and have to add some more repeaters to guarantee the quality of service. When Tpo is smaller than -10 dBm, the density of repeater will be very high (at least 2 repeaters per road section). The energy and information delay results are shown in Figure 20 while applying contention-and schedule-based B.A.. Also, we get some facts from this experiences: First, the update frequency of gradient routing, which affects the transmission path, shall be high enough according to the dynamic urban environment. Second, the network is divided into several small dimension cells so that contention-based protocol shall be favorable. Third, a minimum Tpo is required considering the router deployment limited by the street layout. Fourth, the load of each router, labeled as a numeric in Figure 19, shows that the load balancing is needed for gradient routing; otherwise, certain routers will run out of energy soon.

ENGINEERING INSIGHTS

In this section, we summarize our results in section 4 and provide engineering insights to streamline the Wsn construction of urban smart parking application. The B.A. method is the utmost important key point of determining energy consumption and information delay when traffic and node densities are known a priori. We applied two fundamental types of B.A. to our simulations instead of choosing particular protocols. In this way, we can see clearly that how the traffic intensity and node density affect the network performance and the results could serve as guidelines for urban sensor network designers. We discuss it separately from the following viewpoints by referring to Figure 21.

• Network traffic models We showed that the impact of the periodic traffic interval for selecting an appropriate ω > 1200, and then the influence of event triggered application with Weibull distributed vehicle occupancy time. From literature, the shape parameter is always smaller than 1 and heavy-tailed. Weibull distributed packet interarrival time also shows the burstiness and non-uniform packet generation rate of network traffic comparing to exponentially distributed. The traffic characteristics requires a dynamic bandwidth allocation, e.g., contention-based Mac. When the event occurrence frequency is 2 times more than ω = 1200, part of event-driven packets can be combined with the periodic traffic so as to reduce the network load and energy consumption after evaluating the information delay.

• Information delay From the results, the delay time can be calculated by equation( 3) and then mainly determined by the probability of arriving in 1 st duty cycle (p1) and the duration of duty cycle (T dc ). In schedule-based B.A., if packets do not arrive in 1 st duty cycle, they can still have quite high chance to arrive in 2 nd or 3 rd duty cycle. In contention-based B.A., the packets, which do not arrive in 1 st duty cycle, will probably never arrive or have a very long information delay due to the exponential backoff time. Thus, while the ratio of network dimension to network load is higher than 0. to apply periodic application, certainly 1 ω exceeds T dc faster than 1 2ω . By assuming Nm is the maximum number of nodes to apply periodic application in schedulebased B.A., we have ((N +1) * T slot +Tinactive) -1 = 1 ω . Thus, Nm = ω T slot -1 if Tinactive = 0. • Transmit power output The Psn architecture introduced in subsection 4.2.4 is good for extending the lifetime of in-ground sensor nodes. Based on this, the communication range is significant for router/gateway deployment. A minimum Tpo is required for sensor nodes so as to reach these routers or gateways in crossroads.

• Load balancing In multi-hop network, the routing path is maintained by gradient routing. From the results in Figure 19, we see the network load in each router is highly non-uniform. The load balancing shall be considered into the implementation of routing protocol.

CONCLUSION

In this paper, we studied parking sensor networks, especially focusing on delay constraints and energy efficiency issues from a viewpoint of network traffic. Two types of traffic models are performed with different rate parameters. While deploying in different topologies and traffic variation, the network limit is revealed. With the simulation results, we then provide our engineering insights for urban sensor network designers, in particular the best combination of traffic models and bandwidth allocation depending on the urban activity and the network density. We also highlight some issues while deploying parking sensors in multi-hop networks.

The protocol selection figure, shown in previous section, gives a good picture of the impact from the variation of traffic and node density. Each combination performs a set of information in respective circumstances. While knowing the network limits, the performance is easier to be maintained by adjusting the protocol behaviors and parameters to reach the optimization goal. Even though these thresholds can be slightly shifted by particular optimized protocols, no doubt it retains a clear overview to build urban applications over Psn. These insights highlight the importance to develop an adaptive Mac protocol which is able to distributedly detect the intensity of traffic and switch between event-and periodic traffic model when required.

Figure 2 :Figure 3 :

 23 Figure 2: The CDF and survival function of vehicle and packet interarrival times of one inground parking sensor

Figure 4 :

 4 Figure 4: Generated packets by event-driven traffic model while all sensors have the same scale parameters(γ).

Figure 5 :

 5 Figure 5: Traffic difference between sensor nodes while all the sensors have the same mean of interarrival time( Z 2 ) but different shape parameters(0.5 and 1).

Figure 6 :

 6 Figure 6: Timeline of Network Traffic when having the same scale parameter but different shape parameters 0.5 and 1

s 0 s 1 Figure 7 :

 17 Figure 7: Duty cycle of schedule-based B.A.

s 0 inactive s 0 Figure 8 :

 08 Figure 8: Duty cycle of contention-based B.A.

Figures 10 and 11 Figure 9 :

 119 Figures 10 and 11 shows the per-node energy consumption using periodic and event-driven network traffic mod-

Figure 10 :

 10 Figure 10: Per-node energy consumption of (left) periodic and (right) event-driven applications while varying N and traffic parameters under schedulebased B.A.

Figure 13 :

 13 Figure 13: Information delay of event-driven application while varying traffic parameters and node number under contention-based B.A.

Figure 14 :

 14 Figure 14: Per-node energy consumption: Periodic application under (left) contention-and (right) schedule-based B.A. while N = 24

Figure 15 :

 15 Figure 15: Information delay: Periodic application while varying traffic parameters (N = 24) under (left) contention-and (right) schedule-based B.A.

Figure 16 :

 16 Figure 16: Per-node energy consumption: Eventdriven application under (left) contention-and (right) schedule-based B.A. while N = 24

Figure 17 :

 17 Figure 17: Information delay: Event-driven application while varying traffic parameters (N = 24) under (left) contention-and (right) schedule-based B.A.

Figure 19 :

 19 Figure 19: Parking Map with 120 parking sensors

Figure 20 :

 20 Figure 20: Per-node consumed energy and delay of event-driven application under (left) contentionand (right) schedule-based B.A.

Figure 21 :

 21 Figure 21: Best configuration versus vehicle activity and network density

Table 1 :

 1 Simulation parameters

	Simulation time: 86400 seconds Batch: #20
	Sensor number: 12 ∼ 96	Gateway number: 1
	Distance between two adjacent sensors: 5 meters
	Distance from the gateway to its vicinal sensors: 10 meters
	Transmit power output 3 dBm	Receive sensitivity -85 dBm
	Data rate 250 kbps	802.15.4 Radio
	Ptx 65.7 mW Prx 56.5 mW	Pcs 55.8 mW P of f 30 µW
	E radio.switch 0.16425mJ	Packet size 84 bytes
	MAC: duty-cycled schedule & contention-based bandwidth
	allocation, slot duration=0.1s. Retransmission&piggyback.

Application: Event-drivenλ, µ & α = β = 0.5 , Periodicω Routing: gradient

  Tv,t = 160, T slot.max << 3.33 considering the routing overhead. Hence, we can see that the energy deviation is more obvious when the slot duration is approximating to T slot.max in contention-based B.A.. That is because the number of data slot decreases with1

	Per-node energy consumption	50 100 150 200 250				Event -T p,t +T v,t = 160 Event -T p,t +T v,t = 800 Event -T p,t +T v,t = 4800	Per-node energy consumption	50 100 150 200 250			Event -T p,t +T v,t = 160 Event -T p,t +T v,t = 800 Event -T p,t +T v,t = 4800
		0							0
		0	0.4	0.8	1.2	1.6	2	2.4	0	10	20	30	40	50
				Information delay (s)					Information delay (s)
	Figure 18: Per-node energy-delay tradeoff of event-
	driven application in (left) contention-and (right)
	schedule-based B.A. while N = 24
	tradeoff. For Tp,t +

  3, schedule-based B.A. shall be applied to ensure the packet delivery ratio. N = 0.3 * 1 2 * (Tp,t + Tv,t) = 0.3( 1 2 λγ(1 + 1 α ) + 1 2 µγ(1 + 1 β )). • Energy-delay tradeoff The energy consumption is proportional to network dimension, traffic variation and duty cycle. The duty cycle is generally determined by slot duration and limited by T slot.max < 1 N ( 1 2 λγ(1+1α ) + 1 2 µγ(1 + 1 β )).While giving a desired information delay, contention-based Mac consumes much less energy. What will happen if the network traffic and node densities are both high? T dc shall be greater than

	2 Tp,t+Tv,t or 1 ω respectively. Since	2 Tp,t+Tv,t ≪ 1 2ω

ACKNOWLEDGMENTS

Funding for this project was provided by two grants from the Rhône-Alpes Region, France: F. Le Mouël currently holds a mobility grant Explora'Pro and T. Lin a doctoral fellowship ARC 07 n o 7075.


Raquel Águeda
email: raquel.agueda@uclm.es

Valentin Borozan

Marina Groshaus
email: groshaus@dc.uba.ar

Yannis Manoussakis
email: yannis@lri.fr

Gervais Mendy
email: mendy@lri.fr

Leandro Montero
email: lmontero@lri.fr

Proper Hamiltonian Paths in Edge-Coloured Multigraphs

Keywords: Multigraph, Proper Hamiltonian Path, Edge-Coloured Graph

Given a c-edge-coloured multigraph, a proper Hamiltonian path is a path that contains all the vertices of the multigraph such that no two adjacent edges have the same colour. In this work we establish sufficient conditions for an edge-coloured multigraph to guarantee the existence of a proper Hamiltonian path, involving various parameters as the number of edges, the number of colours, the rainbow degree and the connectivity.

Introduction

The study of problems modelled by edge-coloured graphs have resulted in important developments recently. For instance, the research on long coloured cycles and paths for edge-coloured graphs has provided interesting results [START_REF] Bang-Jensen | Digraphs[END_REF]. From a practical perspective, problems arising in molecular biology are often modeled using coloured graphs, i.e., graphs with coloured edges and/or vertices [START_REF] Pevzner | Computational molecular biology[END_REF]. Given an edge-coloured graph, the original problems are equivalent to extract subgraphs coloured in a specified pattern. The most natural pattern in such a context is that of proper colourings, i.e., adjacent edges have different colours.

In this work we give sufficient conditions involving various parameters as the number of edges, rainbow degree, etc, in order to guarantee the existence of proper Hamiltonian paths in edge-coloured multigraphs where parallel edges with same colours are not allowed. Notice that the proper Hamiltonian path and proper Hamiltonian cycle problems are both N P -complete in the general case. However it is polynomial to find a proper Hamiltonian path in c-edgecoloured complete graphs, c ≥ 2 [START_REF] Feng | Characterization of edge-colored complete graphs with properly colored Hamilton paths[END_REF]. It is also polynomial to find a proper Hamiltonian cycle in 2-edge-coloured complete graphs [START_REF] Bánkfalvi | Alternating Hamiltonian circuit in two-coloured complete graphs[END_REF], but it is still open to determine the computational complexity for c ≥ 3 [START_REF] Benkouar | Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: some complexity results[END_REF]. Many other results for edge-coloured multigraphs can be found in the survey by Bang-Jensen and Gutin [START_REF] Bang-Jensen | Alternating cycles and paths in edge-coloured multigraphs: a survey[END_REF]. Results involving only degree conditions can be found in [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF].

Formally, let I c = {1, 2, . . . , c} be a set of c ≥ 2 colours. Throughout this paper, G c denotes a c-edge-coloured multigraph such that each edge is coloured with one colour in I c and no two parallel edges joining the same pair of vertices have the same colour. Let n be the number of vertices and m be the number of edges of G c . If H is a subgraph of G c , then N i H (x) denotes the set of vertices of H adjacent to x with an edge of colour i. Whenever H is isomorphic to G c , we write N i (x) instead of N i G c (x). The coloured i-degree of a vertex x, denoted by d i (x), is the cardinality of N i (x). As usual N (x) denotes the neighbourhood of x, d(x) its degree and δ(G) the minimum degree among all vertices of G c . The rainbow degree of a vertex x, denoted by rd(x), is the number of different colours on the edges incident to x. The rainbow degree of a multigraph G c , denoted by rd(G c ), is the minimum rainbow degree among its vertices. An edge with endpoints x and y is denoted by xy, and its colour by c(xy). A rainbow complete multigraph is the one having all possible coloured edges between any pair of vertices (its number of edges is therefore c n 2 ). The complement of a multigraph G c denoted by G c , is a multigraph with the same vertices as G c and an edge vw ∈ E(G c ) on colour i if and only if vw / ∈ E(G c ) on that colour. We say that an edge xy is a missing edge of G c if xy ∈ E(G c ).

The graph G i is the spanning subgraph of G c with edges only in colour i. A subgraph of G c is said to be properly edge-coloured if any two adjacent edges in this subgraph differ in colour. A Hamiltonian path (cycle) is a path (cycle) containing all vertices of the multigraph. A path is said to be compatible with a given matching M if the edges of the path are alternatively in M and not in M . We assume that the first and the last edge of the path are in M otherwise we just remove one (or both) of them in order to have this property. All multigraphs are assumed to be connected. This paper is organized as follows: In Section 2 we present some preliminary results that will be useful for the rest of the paper. In Section 3 we study proper Hamiltonian paths in 2-edge-coloured multigraphs. In Section 4 we study proper Hamiltonian paths in c-edge-coloured multigraphs, for c ≥ 3. Notice that in this work we focus only on edge-coloured multigraphs since it makes no sense to study such conditions for simple edge-coloured graphs. x in G c , rd(x) = 2, we have that d i (x) ≥ 1 for i ∈ {r, b}. Observe also that m i ≥ n-3 2 + 4 for i ∈ {r, b}, since this threshold is tight when the multigraph is complete on one of the colours. Now, if n is odd, by Lemma 2.2 there exist two matchings M r and M b , each one of size n-1 2 , so the result follows straightforward. Next, if n is even, suppose without loss of generality that m r ≥ m b . Then m r ≥ ( n 2 + n-3

Preliminary results

M in G of size |M | = ⌊ n 2 ⌋.✷ Lemma 2.2 ([8]) Let G be a simple non-coloured graph on n ≥ 14 vertices. If m ≥ n-3 2 +4 and δ(G) ≥ 1, then G has a matching M of size |M | ≥ ⌈ n-2 2 ⌉. Lemma 2.3 Let G c
2 + 4)/2 > n-2 2 + 3. It is sufficient to show that G r has a matching of size ⌊ n 2 ⌋ because G b has one of size ⌈ n-2 2 ⌉ by Lemma 2.2. Since δ(G r ) ≥ 1, G r is connected, thus, Lemma 2.1 implies that G r has a matching of size ⌊ n 2 ⌋ as desired. ✷ Lemma 2.4 Let G c be a connected c-edge-coloured multigraph, c ≥ 2. Sup- pose that G c contains a proper path P = x 1 y 1 x 2 y 2 . . . x p y p , p ≥ 3, such that each edge x i y i is red. If G c does not contain a proper cycle C such that V (C) = V (P ) then there are at least (c -1)(2p -2) missing edges in G c .
Proof. We show that there are at least 2p -2 missing edges in G c per colour different from red. As there are c -1 such colours the total number of missing edges will be (c -1)(2p -2) as claimed. Let us consider some colour, say blue, different from red. The blue edge x 1 y p cannot be in G c otherwise x 1 y 1 . . . x p y p x 1 is a proper cycle. Suppose that the blue edge x 1 x i is present in G c for some i = 2, . . . , p. Then the blue edge y i-1 y p cannot be in G c otherwise the proper cycle x 1 x i . . . y p y i-1 . . . x 1 contradicts our hypothesis. Therefore for each edge y i-1 x i either the blue edge x 1 x i or the blue edge y i-1 y p is missing. So there are p -1 blue missing edges in G c . Now suppose that the blue edge x 1 y i is present in G c , for some i = 2, . . . , p -2. Then the blue edge x i+1 y p cannot be together with the blue edges x i y i+1 , y i-1 x i+2 or y i-1 y i+1 , x i x i+2 in G c , otherwise the proper cycles x 1 y i x i y i+1 x i+1 y p . . . x i+2 y i-1 . . . x 1 or x 1 y i x i x i+2 . . . y p x i+1 y i+1 y i-1 . . . x 1 contradict again our hypothesis. Then for each edge y i x i+1 , at least one of the edges x i+1 y p , x 1 y i is missing in G c for i = 2, . . . , p -2. Therefore there are p -3 blue missing edges.

Up to now we have 2p -3 blue missing edges. To obtain the last missing edge observe that one of the blue edges x 2 y p , x 1 y 2 , y 1 x 3 (x 2 y p , x 1 x 3 , y 1 y 2 ) is missing in G c , otherwise we obtain the proper cycle x 1 y 2 x 2 y p . . . x 3 y 1 x 1 (x 1 x 3 . . . y p x 2 y 2 y 1 x 1 ). We remark that the blue edges x 2 y p and y 1 x 3 (y 1 y 2 ) were not counted before. The edge x 1 y 2 (x 1 x 3 ) was supposed to exist, otherwise, to obtain the last missing edge we consider the symmetric case, i.e., using the blue edge x 1 y p-1 (if it exists).

In conclusion there are 2p -2 blue missing edges in G c as required. This completes the argument and the proof. ✷ Lemma 2.5 Let G c be a connected c-edge-coloured multigraph, c ≥ 2. Let M be a matching of G c in one colour, say red, of size |M | ≥ ⌈ n-2 2 ⌉. Let P = x 1 y 1 x 2 y 2 . . . x p y p , p ≥ 3, be a longest proper path compatible with M .

Let f (n, c) denote the minimum number of missing edges in G c on colours different from red. Then the following holds:

f (n, c) =          (2n -4)(c -1) if n is even, |M | = n 2 and 2p < n (2n -6)(c -1) if n is odd, |M | = n-1 2 and 2p < n -1 (2n -8)(c -1) if n is even, |M | = n-2
2 and 2p < n -2

Proof. Here we consider only the case n is even, |M | = n 2 and 2p < n, as the two other cases are similar. Observe that, as the red matching M has n 2 edges and by hypothesis P uses p edges of M , there are precisely n-2p 2 edges of M in G c -P . Let us denote these edges by

e i = w i z i , w i , z i ∈ G c -P , i = 1, . . . , n-2p
2 . Suppose first that there is no proper C cycle such that V (C) = V (P ). Let blue be some colour different from red. By Lemma 2.4 there are 2p -2 blue missing edges in the subgraph induced by V (P ). Furthermore there are no blue edges between the vertices x 1 , y p and the endpoints of every edge e i . Otherwise if such an edge exists for some i, say x 1 w i , then the path z i w i x 1 y 1 . . . x p y p contradicts the maximality property of P . Thus, there are 2(n-2p) blue missing edges. In adittion, for each edge y j x j+1 , j = 1, . . . , p-1, at least two of the blue edges y j w i , y j z i , x j+1 w i and x j+1 z i are missing in G c , otherwise if at least three among them exist, we can easily find a path longer than P , a contradiction. So, in this case there are (n -2p)(p -1) blue missing edges. Summing up we obtain (n -2 + pn -2p 2 ) blue missing edges in G c . As there are c -1 colours different from red, we finally have a total of (n -2 + pn -2p 2 )(c -1) missing edges in G c . For n and c fixed, the minimum value of this function is obtained for

p = n-2 2 . Thus f (n, c) = [n -2 + n-2 2 n -2( n-2 2 ) 2 ](c -1) = (2n -4)(c -
1) as required. Suppose next that there is a proper cycle C such that V (C) = V (P ). Then every edge (if any) between a vertex of C and the endpoints of the edges e i = w i z i should be red. Otherwise if such a non red edge exists, say x j w i for some i and j, x i ∈ C, then appropriately using the segment x j w i z i along with C, we may find a path longer than P , a contradiction. Therefore there are at least (2pn -4p 2 )(c -1) missing edges in G c . Again, by minimizing the function we obtain f (n, c) = (2n -4)(c -1) for p = n-2 2 . ✷

2-edge-coloured multigraphs

In this section we study the existence of proper Hamiltonian paths in 2-edgecoloured multigraphs. We present two main results. The first one involves the number of edges. The second one involves both the number of edges and the rainbow degree. All results are tight. edges, it has no proper Hamiltonian path, since there is no blue matching of size (n -1)/2.

Proof. By induction on n. For n = 8, 9 by a rather tedious but easy analysis the result can be shown. Suppose now that n ≥ 10. As G c has at least , then G c has a proper Hamiltonian path. Thus, we can assume that there exists a vertex x ∈ G c such that d r (x) ≤ ⌈ n+1 2 ⌉ -1, otherwise there is nothing to prove. Suppose first that there exist two distinct neighbours y, z of x such that c(xy) = b and c(xz) = r. We then construct a new multigraph G ′c by replacing the vertices x, y, z to a new vertex s such that N r (s) = N r G c -{x,z} (y) and

n 2 + n-2 2 edges then |E(G c )| ≤ 2n -4. By a theorem in [1], if every vertex x ∈ G c has d r (x) ≥ n+1
N b (s) = N b G c -{x,y} (z). We remark that N r G c -{x,z} (y) and N b G c -{x,y} (z) cannot both be empty, otherwise |E(G c )| ≥ 3n -5 -⌈ n+1
2 ⌉ > 2n -4, a contradiction. By doing, in the worst case we remove at most n -1 blue and ⌈ n+1 2 ⌉ -1 red edges from x, n -3 blue edges from y, n -3 red edges from z and one red and one blue between y and z. Therefore

G ′c has at least n 2 + n-2 2 + 1 -(n - 1) -(⌈ n+1 2 ⌉ -1) -2(n -3) -2 ≥ n-2 2 + n-4
2 + 1 edges. Thus by induction, G ′c has a proper Hamiltonian path P . From this path P we can easily obtain a proper Hamiltonian path in G c . Suppose now that there does not exist two distinct neighbours y, z of x such that c(xy) = b and c(xz) = r. Suppose first that both y and z exist but they are not distinct, i.e., y = z. In this case, it is easy to observe that G c -{x} has (n -1)(n -2) edges, i.e., it is a rainbow complete multigraph. Therefore, it contais a proper Hamiltonian path starting at y. This path can be easily extended to a proper Hamiltonian path of G c by adding one of the edges xy in the appropriate colour. Suppose next that all edges incident to x are on the same colour, say b. Observe that for every vertex w = x, there exists at least one red edge wu, u ∈ G c -{x, w}, otherwise |E(G c )| ≥ 2n -3 > 2n -4, which is a contradiction. In the following we distinguish between to cases depending on the neighbourhood of x. Assume first that N b (x) ≤ n -2. Consider a neighbour y of x and remove all its blue incident edges. Then remove x from G c and call this multigraph G ′c . In G ′c , y is monochromatic in red and G ′c has at least n-1 2 + n-3 2 + 1 edges. Thus by the inductive hypothesis, G ′c has a proper Hamiltonian path. This path starts at y since it was monochromatic. So we have a proper Hamiltonian path in

G c . Assume next that N b (x) = n-1.
If for some neighbour y of x, N b (y) ≤ n -3, we complete the argument as before. Otherwise for every vertex y, N b (y) = n -2. It follows that the underlying blue subgraph G ′b of G ′c = G c -{x} is complete. Furthermore, G ′c has at least n 2 -4n + 5 edges. Now remove all the blue edges from G ′c . This new (red) graph has n -1 vertices and at least n-2 2 + 1 edges. Therefore by a theorem in [START_REF] Byer | Edge bounds in nonhamiltonian k-connected graphs[END_REF], it has a Hamiltonian path P . Now since G ′b is complete, we can appropriately use some blue edges of G ′b along with the edges of P to define a proper Hamiltonian path P ′ in G ′c that always starts with an edge on colour red. Finally, we can join x to the first vertex of P ′ in order to obtain a proper Hamiltonian path in G c . ✷ For the extremal example, n ≥ 14 odd, consider a complete blue graph, say A, on n -3 vertices. Add three new vertices v 1 , v 2 , v 3 and join them to a same vertex v in A with blue edges. Finally, superpose the obtained graph with a complete red graph on n vertices. Although the resulting 2-edge-coloured multigraph has n 2 + n-3 2 + 3 edges, it has no proper Hamiltonian path since one of the vertices v 1 , v 2 , v 3 cannot belong to such a path.

Proof. Let us suppose that G c does not have a proper Hamiltonian path. We will show that G c has more than 3n -10 edges, i.e., G c has less than n 2 + n-3 2 + 4 edges, contradicting the hypothesis of the theorem. We distinguish between two cases depending on the parity of n.

Case A: n is even. By Lemma 2.3 G c has two matchings M r , M b such that |M r | = n 2 and |M b | ≥ n-2 2 .
Take two longest proper paths, say P = x 1 y 1 x 2 y 2 . . . x p y p and

P ′ = x ′ 1 y ′ 1 x ′ 2 y ′ 2 . . . x ′ p ′ y ′ p ′
, compatibles with M r and M b , respectively.

Notice now that if 2p = n or 2p ′ = n then we are finished. In addition, if 2p ′ < n -2, then by Lemma 2.5 there are at least 2n -4 blue missing edges and 2n -8 red ones. This gives a total of 4n -12 > 3n -10 missing edges, which is a contradiction. Consequently, in what follows we may suppose that

2p = 2p ′ = n -2.
Suppose first that there exists a proper cycle C in G c such that V (C) = V (P ). Let e = wz be the red edge of M r -E(C). If there exists a blue edge e ′ between w or z and some vertex of C, we can easily obtain a proper Hamiltonian path considering e, e ′ and the rest of C in the appropriate direction. Otherwise as the multigraph is connected, all edges e ′ between the endpoints of e and C are red. Now as rd(G c ) = 2, there must exist a blue edge e ′′ between w and z and therefore we can obtain a proper Hamiltonian path just as before but starting with e ′′ instead of e.

Next suppose that there exists no proper cycle C in G c such that V (C) = V (P ). By Lemma 2.5 there are at least 2n -4 blue missing edges. Consider now the path P ′ and let v 1 , w 1 be the two vertices of G c -P ′ . It is clear that if there exists a blue edge joining v 1 and w 1 , then |M b | = n 2 . Thus, by symmetry on the colours there are at least 2n -4 red missing edges. This gives a total of 4n -8 > 3n -10 blue and red missing edges, a contradiction. Otherwise, assume that there is no blue edge between v 1 and w 1 . In this case we will count the red missing edges assuming that we cannot extend P ′ to a proper Hamiltonian path. If there exists no cycle C ′ in G c such that V (C ′ ) = V (P ′ ), then by Lemma 2.4 there are 2p ′ -2 = n -4 red missing edges. By summing up we obtain 3n-8 > 3n-10 missing edges, which is a contradiction. Finally, assume that there exists a proper cycle

C ′ in G c such that V (C ′ ) = V (P ′ ). Set C = c 1 c 2 . . . c 2p ′ c 1 where c(c i c i+1 ) = r for i = 1, 3, . . . , 2p ′ -1.
If there are three or more red edges between {v 1 , w 1 } and {c i , c i+1 }, for some i = 1, 3, . . . , 2p ′ -1, then either the edges v 1 c i and w 1 c i+1 , or v 1 c i+1 and w 1 c i are red. Suppose v 1 c i and w 1 c i+1 are red. In this case, the path v 1 c i c i-1 . . . c 1 c 2p ′ . . . c i+1 w 1 is a proper Hamiltonian one. Otherwise, there are at most two red edges between {v 1 , w 1 } and {c i , c i+1 }, for all i = 1, 3, . . . , 2p ′ -1, then there are 2p ′ -2 = n -4 red missing edges. If we sum up we obtain a total of 3n -8 > 3n -10 missing edges, which is a contradiction.

Case B: n is odd. By Lemma 2.3 G c has two matchings M r , M b such that |M r | = |M b | = n-1 2 .
As in Case A, we consider two longest proper paths P and P ′ compatibles with the matchings M r and M b , respectively. Suppose first that 2p < n -1 and 2p ′ < n -1. By Lemma 2.5 there are at least 2n -6 blue and 2n -6 red missing edges. We obtain a total of 4n -12 > 3n -10 missing edges, which is a contradiction.

Suppose next 2p = 2p ′ = n-1 (the cases where 2p < n-1 and 2p ′ = n-1, or 2p = n -1 and 2p ′ < n -1 are similar). In the rest of the proof, we will consider only the path P since, by symmetry, the same arguments may be applied for P ′ . In this case we will count the blue missing edges assuming that we cannot extend P to a proper Hamiltonian path. Now let v be the unique vertex in G c -P . It is clear that if there is a proper cycle C in G c such that V (C) = V (P ), we can trivially obtain a proper Hamiltonian path since the multigraph is connected. Then, as there is no proper cycle C in G c such that V (C) = V (P ), by Lemma 2.4 there are 2p -2 = n -3 blue missing edges. If there exists a blue edge between x 1 and x i , for some i = 2, . . . , p, then the blue edge vy i-1 cannot exist in G c , otherwise we would obtain the proper Hamiltonian path vy i-1 . . . x 1 x i . . . y p . We can complete the argument in a similar way if both edges y p y i and vx i+1 , i = 1, . . . , p -1 exist in G c and are on colour blue. Note that since there is no proper cycle C in G c such that V (C) = V (P ), then the blue edges x 1 x i and y p y i-1 , i = 2, . . . , p cannot exist simultaneously in G c . Therefore there are p -1 = n-3 2 blue missing edges. If we make the sum and multiply it by two (since the same number of red missing edges is obtained with P ′ ), we conclude that there are 3n-9 > 3n-10 missing edges, which is a contradiction. This completes the argument and the proof of the theorem. ✷ 4 c-edge-coloured multigraphs, c ≥ 3

In this section we study the existence of proper Hamiltonian paths in c-edgecoloured multigraphs, for c ≥ 3. We present three main results that involve:

(1) the number of edges, (2) the number of edges and the connectivity of the multigraph, (3) the number of edges and the rainbow degree. All results are tight.

In the next lemma we present a key result that reduces the case c ≥ 4 to c = 3. Lemma 4.1 Let ℓ be a positive integer. Let G c be a c-edge-coloured connected multigraph on n vertices and m ≥ c ℓ + 1 edges, c ≥ 4. There exists one colour c j such that if we colour the edges of G c j with another colour and we delete parallel edges with the same colour, then the resulting (c -1)-edge-coloured multigraph G c-1 is connected and has m ′ ≥ (c -1)ℓ + 1 edges. Furthermore, if G c-1 has a proper Hamiltonian path then G c has one too. Also, if rd(G c ) = c, then rd(G c-1 ) = c -1.

Proof. Let c i denote the colour i, for i = 1, . . . , c, and denote by |c i | the number of edges of G c with colour i. Let c j be the colour with the least number of edges. Colour the edges on colour c j with another colour, say c l , and delete (if necessary) parallel edges with that colour. Call this multigraph G c-1 . By this, we delete at most |c j | edges. It is clear that this multigraph is connected since we deleted just parallel edges. Also if G c-1 has a proper Hamiltonian path, then this path is also proper Hamiltonian in G c but perhaps with some edges on colour c j (in the case that they have been recoloured with c l ). Observe also that, if rd(G c ) = c then rd(G c-1 ) = c-1 since only the colour c j was removed. We will show now that m ′ ≥ (c - Proof. By Lemma 4.1 we can assume that c = 3 and let {r, b, g} be the set of colours. Assume n ≥ 6 as cases n ≤ 5 can be checked by exhaustive methods. The proof is by induction on n. We consider two cases depending on whether G c contains a monochromatic vertex or not.

1)ℓ + 1. Now, if |c j | > ℓ, then clearly m ′ ≥ (c -1)ℓ + 1 edges since for all i, |c i | > ℓ. Otherwise |c j | ≤ ℓ. Now, m = c i=1 |c i | ≥ c ℓ + 1 and therefore c i=1,i =j |c i | ≥ c ℓ -|c j | + 1 = (c-1)ℓ+ℓ-|c j |+1.
(s) = N b G c -{x,y} (z), N r (s) = N r G c -{x,z} (y) and N g (s) = N g G c -{x,z} (y) ∩ N g G c -{x,y} (z)
P = x 1 x 2 . . . x n-1 . Now if c(x 1 x 2 ) = r or c(x n-2 x n-1 ) = r, we are done. Otherwise, c(x 1 x 2 ) = c(x n-2 x n-1 ) = r.
If between x 1 and x 2 there exist the three possible edges then the path xx 1 x 2 . . . x n-1 is a proper Hamiltonian one by appropriately choosing the edge x 1 x 2 such that c(x 1 x 2 ) = c(x 2 x 3 ) and c(x 1 x 2 ) = c(xx 1 ). Otherwise the degree of x 1 in some colour different from r, say b is at most n -3. Then as before, we can make the contraction with x and x 1 removing the edges on colours b and r incident to x 1 . Case B: There is no monochromatic vertex in G c . Suppose first that there exists a vertex x such that |N (x)| = 1. Let y be its unique neighbour. Now by contraction of x and y as in Definition 4.2 and by deleting edges incident to y in two appropriate colours we can complete the argument. Assume therefore that |N (x)| ≥ 2 for all x ∈ G c . Moreover we may suppose that there exists a vertex x such that d(x) ≤ 3n -6. Otherwise, if for all x ∈ G c , d(x) ≥ 3n -5, then

d i (x) ≥ n 2 ∀x ∈ G c , i ∈ {r, g, b}.
Thus by a theorem in [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF], G c has a proper Hamiltonian cycle and so a proper Hamiltonian path. Consider now G c -{x}. This multigraph has at least 3 n-2 2 + 1 edges, then by the inductive hypothesis it has a proper Hamiltonian path P = x 1 x 2 . . . x n-1 . We try to add x to P in order to obtain a proper Hamiltonian path in G c . If x is adjacent to either x 1 or x n-1 in any appropriate colour we are done. Otherwise there are four missing edges incidet to x. If there are at least five edges between x and some pair of vertices {x i , x i+1 }, i = 2, . . . , n -2, then by choosing the appropriate edges xx i and xx i+1 , the path x 1 . . . x i xx i+1 . . . x n-1 is proper Hamiltonian one in G c . Otherwise there are at most four edges between x and every pair of vertices {x i , x i+1 }, for i = 2, . . . , n -2. Therefore there are at least n -3 ≥ 3 missing edges incident to x. It follows that the degree of x is at most 3(n - Notice that in the above theorem there is no condition guaranteeing the connectivity of the underlying graph. In view of Theorem 4.6 that adds this condition, we establish the following lemma. Proof. Let c i denote the colour i and E i the set of edges of G c on colour c i , for i = 1, . . . , c. Suppose first that there is a colour c j such that |E j | ≤ n-2 2 . Then, colour the edges on colour c j with another colour, say c l , and delete (if necessary) parallel edges with the same colour. Call this multigraph G c-1 . Clearly G c-1 is connected and it has at least (c-1) n-2 2 +n edges. Moreover if G c-1 has a proper Hamiltonian path, then it also does G c . Suppose next that for every colour c j , |E j | ≥ n-2 2 + 1. If we proceed as above and we obtain that the multigraph G c-1 has at least (c -1) n-2

2

+ n edges, we are done. Otherwise, for each pair of colours c j , c l we have that |E j ∩ E l | ≥ n-2 2 + 1, that is, after colouring the edges on colour c j with colour c l , there are at least n-2 2

+ 1 parallel edges on colour c l . Now take any two colours c j , c l and consider the uncoloured simple graph G having same vertex set as G c and for each pair of vertices x, y we add the uncoloured edge xy in G if and only if xy ∈ E j and xy ∈ E l in G c . Clearly G has at least n-2 2 + 1 edges. We distinguish between two cases depending on the connectivity of G.

Suppose first that G is connected. Add a new vertex v to G and join it to all the vertices of G. Then G+{v} has at least m ≥ n-1 2 +3 edges. Therefore by [START_REF] Byer | Edge bounds in nonhamiltonian k-connected graphs[END_REF], G + {v} is Hamiltonian-connected, that is, each pair of vertices in G is joined by a Hamiltonian path. In particular we have a Hamiltonian path P that starts at v. Therefore if we remove v from P and we take its edges on alternating colours c j , c l we obtain a proper Hamiltonian path in G + n edges and 2c < n, w has a neighbour, say x, in B -{u, w} on some colour c s . Then we obtain a proper Hamiltonian path in G c as follows. Take the edge vu on colour c k , continue with the edge uw on colour c j or c l (depending on the colour c s ) and the edge wx on colour c s . Last, follow any Hamiltonian path in B -{u, w} starting at x by appropriately alternating the colours c j , c l . Case B: The edge vu exists only on colour c j or c l , say c j , but not both. Now, by a similar argument as in case A, w has a neighbour, say x, in B -{u, w} on some colour c s . Let P be an alternating Hamiltonian path in B -{w} from u to x such that its first edge is on colour c l and its last edge has colour different of c s (this is always possible because of the number of edges of G c ). Now we obtain a proper Hamiltonian path between v and w in G c as follows. Add the edge vu on colour c j to P and complete the path with the edge xw on colour c s .

This completes the argument and the proof. ✷ + n, then G c has a proper Hamiltonian path.

For the extremal example, n ≥ 9, consider a rainbow complete multigraph on n -2 vertices with c colours and add two new vertices x and y. Now add the edge xy and all edges between y and the complete multigraph, all on the same colour. The resulting multigraph, although it has c n-2 2 + n -1 edges, it does not contain a proper Hamiltonian path as x cannot belong to such a path.

Proof. By Lemma 4.5 we can assume that c = 3. Let {r, b, g} be the set of colours. The proof is by induction on n. For n = 9, 10 it can be shown by case analysis that the result holds. Now we have two cases depending on whether G c contains a monochromatic vertex or not. Case A: There exists a monochromatic vertex x ∈ G c . Notice that among all neighbours of x there exists at least one, say y, that is not monochromatic, otherwise we would have a contradiction on the number of edges. Suppose that c(xy) = b. Now we will contract x, y to a new vertex s as in Definition 4.2.

Here the resulting multigraph on n -1 vertices has to be connected (as we will show later) and we need to delete at most 3n -8 edges for the induction hypothesis to hold.

Let us now consider d b (x). Observe that if d b (x) ≤ n -4, we delete at most 3n -8 edges from x and any selected neighbour y of x and we are done. Further, from [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF], if d i (z) ≥ n 2 , ∀z ∈ G c -{x}, i ∈ {r, g, b}, then G c -{x} has a proper Hamiltonian cycle. This would imply a proper Hamiltonian path in G c . Thus, we may assume that there exists some vertex w ∈ G c -{x} such that d i (w) < n 2 for some i ∈ {r, g, b}. Subcase A1: d b (x) = n -1. Observe that w ∈ N b (x). In this case, considering w instead of y, the contraction process deletes n -1 edges from x, and at most n + n 2 -3 from w, which is much less than 3n -8 for n > 10. Subcase A2:

d b (x) = n -2. If there is a vertex y adjacent to x such that d b G c -{x} (y) + d r G c -{x} (y) ≤ 2n -6 or d b G c -{x} (y) + d g G c -{x} ≤ 2n -6
, then we just take x and y for the contraction process. Otherwise for all y adjacent to x we have

d b G c -{x} (y) + d r G c -{x} (y) ≥ 2n -5 and d b G c -{x} (y) + d g G c -{x} (y) ≥ 2n -5. That implies d i (y) ≥ n-2 2
, ∀y ∈ G c -{x, z}, i ∈ {r, g, b}, where z is the unique non-neighbour of x. Then by [START_REF] Abouelaoualim | Cycles and paths in edge-colored graphs with given degrees[END_REF], G c -{x, z} has a proper Hamiltonian cycle. Finally, we can add x and z to the cycle using the fact that x is adjacent to every vertex on it (as it is z) by the degree condition of the vertices of the cycle. By this we obtain a proper Hamiltonian path in G c . Subcase A3: d b (x) = n -3. This case is similar to the previous one but finding a vertex y adjacent to x such that

d b G c -{x} (y) + d r G c -{x} (y) ≤ 2n -5 or d b G c -{x} (y) + d g G c -{x} (y) ≤ 2n -5.
Otherwise the multigraph G c -{x} is rainbow complete (except maybe for the three edges between the two nonneighbours of x), we easily find a proper Hamiltonian cycle in G c -{x} and then adding x, a proper Hamiltonian path in G c . Case B: There is no monochromatic vertex in G c . If there exists a vertex x such that |N (x)| = 1 we proceed as in case B of Theorem 4. [START_REF] Bánkfalvi | Alternating Hamiltonian circuit in two-coloured complete graphs[END_REF]. In what follows we assume that |N (x)| ≥ 2 for all x ∈ G c . Suppose now that there exists a vertex In order to complete the proof, we will show that, either we can find two or three appropriate vertices to contract such that the obtained multigraph G ′c is connected or G c has a proper Hamiltonian path.

x such that d(x) ≤ 3n -8. Otherwise, if for all x ∈ G c , d(x) ≥ 3n -7, then m ≥ n(3n-7) 2 ≥ 3 n-1
Contraction of two vertices: Consider the above contraction of the vertices x, y to s and suppose by contradiction that G ′c is disconnected. It can be easily shown that G ′c has two components with one vertex, say z, and n -2 vertices, respectively. Observe first that if z = s then x and y are both monochromatic, a contradiction with the fact that y was chosen not monochromatic. Consequently z = s.

Suppose first that x is not monochromatic. In this case x has y as its unique neighbour. So, there are 3(n -2) missing edges at x and 3(n -3) missing edges at z since z is isolated in G ′c . This gives us a total of 6n -15 missing edges in G c and this is greater than |E(G c )| = 5n -9 which is a contradiction.

Suppose next that x is monochromatic. In G c there are at least 2(n -1) missing edges at x since it is monochromatic and 3(n -3) missing edges at z since z is isolated in G ′c . Further, there are two more missing edges between y and z since we have the choice of which colours to delete at y. This gives us a total of 5n -9 = |E(G c )| missing edges in G c . Now z must be adjacent to x and y in colour b otherwise we obtain 5n -8 missing edges which is a contradiction. Therefore z is also monochromatic and d(z) = 2. We take then z and y for the contraction (instead of x, y) but in this case we delete just two edges at z which guarantees the connectivity of the contracted multigraph.

Contraction of three vertices: Suppose by contradiction that after the contraction of x, y, z to s, G ′c is disconnected. Then G ′c has exactly two components with one vertex, say u, and n -3 vertices, respectively.

Suppose first that u = s. In G c u must have at least two different neighbours in two different colours among the vertices x, y, z. Otherwise we would be in the case where either u is monochromatic or u has one unique neighbour. Let y ′ and z ′ be two neighbours of u among x, y, z such that c(uy ′ ) = c(uz ′ ). Now we contract the vertices u, y ′ , z ′ (instead of x, y, z). Observe that at u we delete at most six edges since u has only x, y, z as neighbours. In adittion the red edge uy, the blue edge uz and at least one green edge among uy, uz are missing. At y ′ and z ′ we delete 3n -6 edges as usual. With this contraction we delete at most 3n edges and therefore the contracted multigraph has at least 3 n-3 2 + n -9 edges which guarantees not only the inductive hypothesis but also the connectivity for n ≥ 10.

Suppose next that u = s. Then there are no red edges between y and G c -{x, y, z} and no blue edges between z and G c -{x, y, z}. Now, since we are not in the previous cases, y has at least two different neighbours y ′ and z ′ such that c(yy ′ ) = c(yz ′ ). Then we contract the vertices y, y ′ , z ′ (instead of x, y, z). In the contraction process we delete at most 2(n -3) edges between y and G c -{x, y, z} (since there are no red edges), six between y and the vertices x, z, and 3n -6 at y ′ and z ′ . We obtain in total at most 5n -6 deleted edges. Now, this new contracted multigraph has n -2 vertices and at least 3 n-3 2 n -3 edges. Clearly, if the multigraph is connected we are done. Otherwise, as before, it has two components with one vertex and n -3 vertices, respectively. We can suppose that the contracted vertex is the isolated one, otherwise we are done as above. Observe now that the component on n -3 vertices has at least 3 n-3

2

n -3, therefore it is almost rainbow complete. It is easy to prove by induction that it has a proper Hamiltonian cycle. Suppose now without losing generality that c(yy ′ ) = b and c(yz ′ ) = r. Now, in the original multigraph if we cannot add y, y ′ , z ′ to the proper cycle in order to obtain a proper Hamiltonian path (and also using the fact that the contracted multigraph is disconnected), we obtain that there are n -3 red missing edges and n -3 green missing ones at y ′ , n -3 blue and n -3 green at z ′ , and n -3 red at y. We obtain a total of 5n -15 missing edges. If we have any of the edges r, b or g between y ′ and z ′ , either y has no green edges at all to G c -{y, y ′ , z ′ } leading us to a contradiction on the number of edges, or a proper Hamiltonian path can be found. So, these three edges are missing. Similar arguments can be used if we have the edge yy ′ or yz ′ in colour g. Therefore, two more missing edges. Now if we have the edges yy ′ in r and yz ′ in b, we can do the contraction using these colours instead of the originals. Then, either the contracted multigraph is connected and thus we obtain a proper Hamiltonian path, or we obtain a contradiction on the number of edges. We can conclude that at least one between these two edges is missing obtaining a total of 5n -9 = |E(G c )|. That implies that G c -{y, y ′ , z ′ } is rainbow complete and we have all of the green and blue edges between y and G c -{y, y ′ , z ′ }, all of the blue between y ′ and G c -{y, y ′ , z ′ }, and all of the red between z ′ and G c -{y, y ′ , z ′ }. In this last case, it is easy to obtain a proper Hamiltonian path in G c . ✷

In view of Theorem 4.8 we prove the following lemma. Suppose first that n is odd. By Lemma 2.5, if there is a proper cycle C such that V (C) = V (P ), then |P | ≥ n -5. Else, if such a cycle does not exist then |P | ≥ n -7. Otherwise in both cases we obtain a contradiction on the number of edges. Let us consider here the case |P | = n -1 (the other cases are easier to handle, refer to [START_REF] Montero | Graphs and Colors: Edge-colored graphs, edge-colorings and proper connections[END_REF] for more details). Now observe that if there is a proper cycle C such that V (C) = V (P ), then the result easily follows as the unique vertex of G c -C can be appropriately joint to C in order to obtain a proper Hamiltonian path. Assume therefore that there is no proper cycle C such that V (C) = V (P ). Let x be the unique vertex of G c -P . Clearly we cannot have either the edge xx 1 on colours r or g, or the edge xy p on colours r or g, otherwise we easily obtain a proper Hamiltonian path in G c . Now, if there are at least three edges on colours r, g between x and some pair of vertices {y i , x i+1 }, i = 2, . . . , p -1, then by choosing the appropriate edges xy i and xx i+1 , the path x 1 . . . y i xx i+1 . . . y p is a proper Hamiltonian one in G c . Otherwise there are at most two edges on colours r, g between x and every pair of vertices {y i , x i+1 }, for i = 2, . . . , p -1. Therefore d r,g (x) ≤ n -3 and clearly d(x) ≤ 2n -4 as d b (x) ≤ n -1. In addition, if we have two more missing edges incident to x we would obtain that d(x) ≤ 2n -6 as claimed. Now, we can assume the worst case, that is, for each edge y i x i+1 in the path, i = 2, . . . , p -1, we have both edges xy i ,xx i+1 on the same colour of y i x i+1 (that is, r or g). Otherwise, if we suppose without losing generality that c(xy i ) = r and c(y i x i+1 ) = g then we cannot have the blue edge xx i (or we would obtain the proper Hamiltonian path x 1 . . . x i xy i . . . y p ). Therefore, there would be one more missing edge at x. Consider now x 1 . Suppose that we have any edge x 1 y i on colour r or g that is different of the colour of y i x i+1 , for i = 1, . . . , p -1. Taking the blue edge xx i we obtain the proper Hamiltonian path in G c , xx i . . . x 1 y i x i+1 . . . y p . Otherwise we obtain at least p -1 = n-3 2 missing edges x 1 y i on colours r or g. Suppose that we have any edge x 1 x i on at least one colour r or g, for i = 2, . . . , p. Therefore taking the edge xy i-1 on colour r or g (one of both is supposed to exist) we obtain the proper Hamiltonian path xy i-1 . . . x 1 x i y i . . . y p . Otherwise the edges x 1 x i on colours r and g are missing for all i = 2, . . . , p, that is, 2(p -1) = n -3 additional missing edges at x 1 . Finally, summing up and considering that we cannot have the edge x 1 y p on colours r or g (or P would also be a proper cycle), we obtain that d(x) ≤ 3(n -1) -n-3

2 -(n -3) -2 ≤ 2n -6 as claimed. Suppose next that n is even. If there is a proper cycle C such that V (C) = V (P ), then by Lemma 2.5 |P | ≥ n -2. This case is easy since either P is a proper Hamiltonian path or we can connect the unique edge of M b -E(P ) to C in order to obtain a proper Hamiltonian path. Assume therefore that there is no proper cycle C such that V (C) = V (P ). It follows by Lemma 2.5 that |P | ≥ n -4 otherwise we obtain a contradiction on the number of edges. Let us consider just the case |P | = n -2 (|P | = n -4 is easier, refer to [START_REF] Montero | Graphs and Colors: Edge-colored graphs, edge-colorings and proper connections[END_REF] for full details). Let e = xy be the edge of M b -E(P ). Now by similar arguments as in the odd case above, we can prove that, either the edge e can be added to P in order to obtain a proper Hamiltonian path in G c , or one of the vertices x, y, x 1 , y p has degree at most 2n -6 as required. ✷ Let G ′c be the resulting multigraph. In this case, as we delete at most 5n -12 (= 2n -6 + 3(n -3) + 3) edges, it is enough to prove that G ′c is connected to apply Theorem 4.6.

Suppose therefore by contradiction that G ′c is disconnected. Then it has exactly two components with one vertex, say u, and n-3 vertices, respectively, otherwise we arrive to a contradiction on the number of edges.

Assume first that u = s. Then, as in the equivalent case of Theorem 4.6, instead of x, y, z, we may find three other vertices u, y ′ , z ′ to contract to a vertex s ′ just deleting 3n edges. This new obtained multigraph has at least 3 n-3 2 -2 edges. Then, if it is connected we are done, otherwise there is a component with one vertex, say u ′ , and another one on n -3 vertices with at least 3 n-3 2 -2 edges, i.e., almost rainbow complete. Therefore, the biggest component contains a proper Hamiltonian cycle and then we can easily add either the isolated vertex u ′ (if u ′ = s ′ ) or the three u, y ′ , z ′ (if u ′ = s ′ ) vertices to the cycle to obtain a proper Hamiltonian path in G c .

Assume next u = s. If d(x) ≤ n + 1, then the contraction process deletes 4n -5 edges instead of 5n -12. Furthermore as G ′c is disconnected by hypothesis, its component on n -3 vertices has at least 3 n-3 2 n + 3 edges. As in Theorem 4.6, this component is almost rainbow complete and thus it contains a proper Hamiltonian cycle C. This allows us to easily add x, y, z to C in order to obtain a proper Hamiltonian path in G c . In the sequel, we may suppose that d(x) ≥ n + 2. Then x has two different neighbours y ′ and z ′ with

Lemma 2 . 1 2 + 3 , 2 + 5

 212325 Let G be a connected non-coloured simple graph on n vertices, n ≥ 9. If m ≥ n-2 then G has a matching M of size |M | = ⌊ n 2 ⌋. Proof. By a theorem in [6], a 2-connected graph on n ≥ 10 vertices and m ≥ n-2 edges has a Hamiltonian cycle. So if we add a new vertex v to G and we join it to all the vertices of G we have that G+{v} has m ≥ n-1 2 +5 edges. Therefore G + {v} has a Hamiltonian cycle, i.e., G has a Hamiltonian path and this implies that there exists a matching

2 + 4 ,

 24 be a 2-edge-coloured multigraph on n ≥ 14 vertices coloured with {r, b} (red and blue). If rd(G c ) = 2 and m ≥ n 2 + n-3 then G c has two matchings M r and M b of colours red and blue respectively, such that |M r | = ⌊ n 2 ⌋ and |M b | ≥ ⌈ n-2 2 ⌉. Proof. Let E r and E b denote the set of edges coloured in red and blue respectively. Set |E r | = m r and |E b | = m b . Observe that, as for every vertex

2 and

 2 d b (x) ≥ n+1 2

Theorem 3 . 2 2 + 4 ,

 3224 Let G c be a 2-edge-coloured multigraph on n ≥ 14 vertices coloured with {r, b}. If rd(G c ) = 2 and m ≥ n 2 + n-3 then G c has a proper Hamiltonian path.

Definition 4 . 2 Definition 4 . 3

 4243 This last expression is greater than or equal to (c-1)ℓ+1 since ℓ -|c j | ≥ 0. Finally, we have that G c-1 has m ′ ≥ (c -1)ℓ + 1 edges as desired.✷In view of Theorems 4.4,4.6 and 4.8 we need the following definition. Let G c be a 3-edge-coloured multigraph coloured with {r, b, g}. Suppose that there exist two distinct vertices x, y ∈ G c such that y is a neighbour of x and either |N (x)| = 1 or N r (x) = N g (x) = ∅. First remove the vertex x. Then, remove all the edges (if any) in colours either b, r or b, g, incident to y. Finally rename the vertex y to s. We call this process the contraction of x, y to s. Let G c be a 3-edge-coloured multigraph coloured with {r, b, g}. Suppose that there exist three different vertices x, y, z ∈ G c such that c(xy) = b and c(xz) = r. Now the contraction of x, y, z is defined as follows: We replace the vertices x, y, z by a new vertex s such that N b

2 + 1 ,

 21 . Notice that if G ′c is the graph obtained from G c by any of the contractions above, then any proper Hamiltonian path in G ′c can be easily transformed into a proper Hamiltonian one in G c . Theorem 4.4 Let G c be a c-edge-coloured multigraph on n vertices, n ≥ 2 and c ≥ 3. If m ≥ c n-1 then G c has a proper Hamiltonian path. For the extremal case consider a rainbow complete multigraph on n -1 vertices with c colours and add a new isolated vertex x. Although the resulting multigraph has c n-1 2 edges, it contains no proper Hamiltonian path since it is not connected.

Case A : 2 + 1

 :21 There exists a monochromatic vertex x ∈ G c . Assume without loss of generality that all the edges incident to x are on colour r. Suppose first that d(x) ≤ n -2. Consider the multigraph G ′c obtained from G c by contracting x and one of its neighbours, say y, to a vertex s as in Definition 4.2 considering r instead of b. By this, we delete at most 3n -6 edges. This multigraph G ′c has n -1 vertices and at least 3 n-2 edges. Then by inductive hypothesis it has a proper Hamiltonian path. Since s is monochromatic, we easily extend the path with x to obtain a proper Hamiltonian path in G c . Suppose next that d(x) = n -1. Then the multigraph G c -{x} has at least 3 n-2 2 + 1 edges and therefore by inductive hypothesis it has a proper Hamiltonian path

2 + 1 -

 21 1) -4 -(n -3) = 2n -4 ≤ 3n -10. Take now y, z ∈ N (x) and suppose that c(xy) = b and c(xz) = r. Contract x, y, z as in Definition 4.3. By this operation we remove at most 3n-10 edges incident to x and at most 3n-6 edges incident to y and z in G c -{x}. It follows that the obtained multigraph on n -2 vertices has at least c n-1 (3n -10) -(3n -6) ≥ c n-3 2 + 1 edges. Therefore, by the inductive hypothesis it has a proper Hamiltonian path P . Now it is easy to obtain from P a proper Hamiltonian path in G c . ✷

Lemma 4 . 5 2 +

 452 Let G c be a c-edge-coloured multigraph on n vertices fullfilling the conditions of Theorem 4.6 and c ≥ 4. Then either G c has a proper Hamiltonian path or G c contains a connected (c -1)-edge-coloured multigraph G c-1 on n vertices with at least (c -1) n-2 n edges such that if G c-1 has a proper Hamiltonian path then G c has one too.

  c . Suppose next that G is disconnected. By a simple calculation on the number of edges of G we can see that G has two components, say A and B, such that either |A| = 1 and |B| = n -1, or |A| = 2 and |B| = n -2. If |A| = 2 and |B| = n -2, let v, w be the vertices of A. By the condition on the number of edges, both A and B are complete. Now, as G c is connected there exists one edge between v (or w) and some vertex u ∈ B on colour c k . Therefore we obtain a proper Hamiltonian path in G c starting with the edge wv on colour c j (or c l ), then vu on colour c k and following any Hamiltonian path in B alternating the colours c j , c l . If |A| = 1 and |B| = n -1, then let v be the unique vertex of A. Now by [6], B has a Hamiltonian cycle unless it is isomorphic to a complete graph on n -2 vertices plus one vertex, say w, joint to exactly one vertex, say u, of the complete graph B -{w}. Now if B has a Hamiltonian cycle C, then as G c is connected, there exists one edge between v and some vertex in B in some colour, say c k . Therefore we obtain a proper Hamiltonian path in G c starting at v taking this edge on colour c k , then following C alternating the colours c j , c l . Alternatively, if B has no Hamiltonian cycle, then B -{w} has a Hamiltonian path between every pair of vertices. As G c is connected there exists one edge between v and some vertex z ∈ B on some colour c k . If z = u, w, then taking the edge vz on colour c k , following a Hamiltonian path in B -{w} that starts at z and ends at u alternating the colours c j , c l and taking the appropriate edge uw we obtain a proper Hamiltonian path in G c . If z = w, take the edge vw on colour c k , the edge wu on colour either c j , c l and then follow any Hamiltonian path in B starting at u, alternating the colours c j , c l , we obtain a proper Hamiltonian path in G c . If none of the two above cases hold, then v has only one neighbour in B and z = u. Consider the following two cases. Case A: The edge vu exists on colour c k = c j , c l . Then, as G c has at least m ≥ c n-2 2

Theorem 4 . 6

 46 Let G c be a connected c-edge-coloured multigraph on n vertices, n ≥ 9 and 3 ≤ c < n 2 . If m ≥ c n-2 2

2 + 1 2 +

 212 and by Theorem 4.4 the result holds. Consider now G c -{x}. This multigraph has at least 3 n-3 n -1 edges and it is clearly connected. Then by the inductive hypothesis it has a proper Hamiltonian path P . Now we use the same argument as in Theorem 4.4 to add x to P . If we cannot add it, we obtain that d(x) ≤ 3n -15. Finally take y, z ∈ N (x) such that c(xy) = b and c(xz) = r. Contract x, y, z to a new vertex s as in Definition 4.3. By this we delete at most 6n -21 edges, that is, 3n -15 edges incident to x and 3n -6 edges incident to y and z in G c -{x}. Since we can delete at most 6n -19 edges to use the inductive hypothesis, the result holds.

Lemma 4 . 7 2 + 3 ,

 4723 Let G c be a c-edge-coloured multigraph on n vertices fullfilling the conditions of Theorem 4.8. Then either G c has a proper Hamiltonian path or there exists a vertex x ∈ G c such that d(x) ≤ 2n -6. Proof. Let E i be the set of edges of colour i, i ∈ {r, g, b}, and suppose without loss of generality that |E b | ≥ |E r |, |E g |. Then, as the subgraph G b has minimum degree one and |E b | ≥ n-2 it can be easily checked that it is connected. Thus by Lemma 2.1 there is a matching M b such that |M b | = n 2 for n even and |M b | = n-1 2 for n odd. Let P = x 1 y 1 x 2 y 2 . . . x p y p be the longest proper path compatible with M b .

Theorem 4 . 8 2 + 2 + 2 + 7

 482227 Let G c be a c-edge-coloured multigraph on n vertices, n ≥ 11 and c ≥ 3. If rd(G c ) = c and m ≥ c n-2 2c + 1, then G c has a proper Hamiltonian path. For the extremal example, n ≥ 11, consider a rainbow complete multi-graph, say A, on n -2 vertices. Add two new vertices v 1 , v 2 and join them to a vertex v of A with all possible colours. The resulting c-edge-coloured multigraph has c n-2 2c edges and clearly has no proper Hamiltonian path. Proof. By Lemma 4.1 it is enough to prove the theorem for c = 3. Let {r, b, g} be the set of colours. As m ≥ 3 n-2 then |E(G c )| ≤ 6n -16. The proof will be done either by construction of a proper Hamiltonian path or using Theorem 4.6. We will do this by contracting two or three vertices depending on if there exists a vertex x in G c such that |N (x)| = 1 or not. If there exists a vertex x ∈ G c such that |N (x)| = 1 we contract x and its unique neighbour y to a new vertex s as in Definition 4.2. By this we delete at most 2n -1 edges and the resulting multigraph is still connected. Thus the conclusion follows from Theorem 4.6. Suppose next that there is no vertex x ∈ G c such that |N (x)| = 1. It follows that for any vertex x there are two distinct neighbours y,z in G c such that c(xy) = b and c(xz) = r. Now by Lemma 4.7 consider a vertex x such that d(x) ≤ 2n-6. Then contract x, y, z to a new vertex s as in Definition 4.3.

  For the extremal example, n ≥ 8, consider a rainbow complete 2-edgecoloured multigraph on n -2 vertices, n odd. Add two new vertices x 1 and x 2 . Then add a red edge x 1 x 2 and all red edges between {x 1 , x 2 } and the complete graph. Although the resulting graph has n 2 + n-2

	Theorem 3.1 Let G c be a 2-edge-coloured multigraph on n ≥ 8 vertices
	coloured with {r, b}. If m ≥ n 2 + n-2 2 tonian path.	+ 1, then G c has a proper Hamil-
		2

Acknowledgments:

The authors would like to thank N. Narayanan for his valuable corrections and comments.

ANPCyT PICT 1562 Grants and by CONICET, Argentina.

parallel edges. Consider the next two cases: Assume first that the parallel edges are on the same two colours, say c(xy ′ ) = c(xz ′ ) = {b, r} (cases with other two colours are similar). Here we can consider two possible contractions: 1) x, y ′ , z ′ with c(xy ′ ) = b, c(xz ′ ) = r and 2) x, y ′ , z ′ with c(xy ′ ) = r, c(xz ′ ) = b. Now, suppose that in both contractions the multigraph is disconnected and the contracted vertex is always the isolated one, otherwise we are finished. We can observe that G c has n+3 missing edges incident to x (since d(x) ≤ 2n -6), n -3 green edges and 4(n -3) blue and red edges incident to y ′ and z ′ (since in both contractions the multigraph is disconnected). By this we obtain a total of 6n -12 > 6n -16 missing edges, which is a contradiction. Assume next that the parallel edges are not on the same two colours, that is, c(xy ′ ) = {b, r} and c(xz ′ ) = {b, g} (cases with other combinations are similar). Now since we are not in the previous case, we do not have either the green edge xy ′ or the red one xz ′ . Try any of the three possible contractions: 1)

Then, after each of these contractions the multigraph is still disconnected and the contracted vertex is always the isolated one. We can observe that there can exist just the red edges between y ′ and G c -{x, y ′ , z ′ } and the green edges between z ′ and G c -{x, y ′ , z ′ }. Now as rd(G c ) = 3 there must exist the green edge y ′ z ′ and the red edge y ′ z ′ . Since we are not in the previous case, the blue edge y ′ z ′ is not present. We find us in the situation that c(xy ′ ) = {b, r}, c(xz ′ ) = {b, g} and c(y ′ z ′ ) = {r, g}. Now, we have nine different contractions to try, three for each triplet x, y ′ , z ′ , y ′ , x, z ′ and z ′ , x, y ′ . If in all of them we are in this same situation (the contracted multigraph is disconnected and the isolated vertex is the contracted one) we can conclude that in G c there can exist just the blue edges between x and G c -{x, y ′ , z ′ }, the red edges between y ′ and G c -{x, y ′ , z ′ }, and the green edges between z ′ and G c -{x, y ′ , z ′ }. This gives a total of 6(n -3) missing edges in G c . Finally, adding the three missing edges xy ′ in green, xz ′ in red and y ′ z ′ in blue, we obtain 6n -15 missing edges which is a contradiction. ✷