Myriam Ababsa

The Evolution of Upgrading Policies in Amman

Keywords: Jordan, Amman, Refugee Camps, Informal Settlements, Upgrading, Participation, Social Disparities

While the Municipality of Amman celebrates its centennial in 2009, highlighting the diversity of its population made up of migrants from across the Bilad al Sham, as well as its modernity, symbolized by the successive development projects (the business district of Shmeissani in the 1980s and the new Abdali downtown planned for 2011), it is clear that social disparities within the city continue to grow stronger between West Amman and East Amman. These disparities tie in with morphological differences between informal housing communities developed near the Palestinian camps of Wahdat and Jabal Hussein, with their self-built buildings; and West Amman neighbourhoods with familyowned four storey buildings, interspersed with villas and office blocks. They appear clearly on maps done at the blok level for Amman city (for density, age structure, sex ratio, type of housing, level of employement and level of litteracy).

This paper outline the different public policies implemented to resolve the gap between East and West within the city of Amman. These policies are all the more important since, from 1980 to 1997, Jordan has gained a following in the field of upgrading poor urban areas in the Arab world as the first country in the region to implement the developmentalist ideology newly promoted by the World Bank in Latin America and Asia, which was to involve the inhabitants of informal areas in all the stages of renovating their home and to enable them to become homeowners through long term loans guaranteed by the State. But from the Arab-Israeli peace process (the Oslo Accord of September 1993 and the Wadi Araba Treaty of January 1994), the Jordanian government changed its methods of intervention in camps and informal areas of the country in order to focus solely on the supply of services, giving clear priority to security issues.

Informal Settlements in Amman

Since its independence in 1946, Jordan's population has increased eleven fold. This is due to both high rates of natural growth (more than 4% in the 1950s-1960s, and 2.2% in 2009), and the country's absorption of four major waves of refugees and migrants: in 1948 (100,000 Palestinian refugees), 1967 (300,000 displaced persons), 1991 (350,000 Palestinian and Jordanian migrants expelled from the Gulf) and 2003-2005 (between 300,000 and 500,000 Iraqis). These waves created high demand on residential land and urban services, as 79% of Jordan's 6 million inhabitants are urban, half of them living in the Amman-Russeifa-Zarqa conurbation.

After the 1948 Naqba and the arrival of 100,000 Palestinian refugees in Amman, four camps were created: in Zarqa (1949), Irbid (1951), Jabal Hussein (1952), and Wahdat (1955). These camps have been administrated by UNRWA since 1950. The 1967 war brought a second wave of Palestinian refugees, generating more informal settlements and leading to the establishment of several nonrecognized camps (areas not recognized as camps but which have access to a basic package of UNRWA services). Huge slums appeared. The aftermath of the war also led to the establishment of six emergency camps for refugees/displaced persons: Husn, Baqaa, Talbieh, Marka, Souf and Jerash were all formally recognized in 1968. Four other official camps are operated under the direct supervision of the Jordanian Department of Palestinian Affairs: Al Nadhif, Madaba, Hanikin and Sukhne.

Defining an Informal Settlement

Because of zoning regulations introduced by the British in the 1930s, residential land in Amman is zoned into four categories A (>1,000 m 2 ), B (>750 m 2 ), C (>500 m 2 ) and D (>250 m 2 ); these plot sizes are too large to be affordable for low-income groups. This is one reason why a variety of informal zones and nonrecognized camps appeared near the official UNRWA camps in East Amman. In Amman, the definition of what constitutes an informal area has been very narrowly defined. In 2006, the Housing and Urban Development Corporation evaluated the number of "squatter areas" throughout Jordan at 40, with a population of only 100,000 inhabitants. One can question this figure, when we compare it with the case in Syria, where nearly 60 % of the city of Damascus is made up of structures built without a permit (ghayr nizami or mukhalafat). In 1986, a study by the Urban Development Department identified 16 informal settlements, covering 1,224 donums and inhabited by 51,145 people (7,320 families). The population densities were around 55 persons per donum (550 persons per ha), but exceeded 100 persons per donum in the Nuzha, Nadhif and Wadi Rimam neighbourhoods (Cities, 1993: 39). Following nearly thirty years of urban upgrading of these informal areas, there are far fewer of them within the city of Amman. However, there are still poor areas, lacking health and education services, and with inadequate road networks and sewerage systems, particularly in the city centre, near the camps and the former informal areas which have been upgraded. There are so many informal areas inhabited by Palestinian refugees that the definition of informality is unique in Jordan. The term sakan `ashwa'i refers almost exclusively to areas inhabited by Palestinian refugees, and is not used for informal habitats with rural or Bedouin populations, which are referred to as "poor areas". However, the definition of 'informal' remains vague. The Housing and Urban Development Corporation follows three criteria for the definition of 'informality': two morphological criteria linked to the structure of the road network (accessibility of the area) and the type of constructions (view from the windows), and sometimes legal criteria concerning types of ownership. Note that the legal status of a property can alone define it as informal, since the lack of inalienable and exclusive rights of transfer renders a property informal.

Physical and legal characteristics of informal settlements

Most of the settlements that appeared in the 1950s and late 60s were built on the edge of hills and in the floodable areas of valleys. Three-quarters of the homes of these informal settlements, generally made up of two rooms, were built in permanent materials (with concrete blocks and bricks) and 70% of them were covered with concrete roofs, while 30% had zinc roofs. The houses were tightly packed onto plots of 150 m² on average, leaving only narrow alleyways between them. The average number of inhabitants per room was 4.2 and this overcrowding was considered an aggravating factor of infant mortality (which was a high 86 per thousand) due to increased domestic risks [START_REF] Daly | Informal Settlements in Jordan. Upgrading Approaches Adopted and Lessons Learned[END_REF]).

Jordan's informal areas have four kinds of land tenure patterns: squats, the hujja contract, ownership (mulk) and tawsiya. In the case of squats, refugees built their shacks on government or private land, with no transaction at all. There is the special case of tribal pastoral land, which is not registered, and considered by the Government as State land [START_REF] Razzaz | Law, Urban Land Tenure, and Property Disputes in Contested Settlements : The Case of Jordan[END_REF]. In the case of a hujja contract, which is very common in the Middle East, a former owner sells his land and makes an oral agreement, the hujja (proof). This transaction is not legal and is not recognized by the Land and Survey Department, but gives a base for asserting ownership in Court. Ownership, mulk, can be private or, as in most cases, collective. Collective ownership is of two kinds: musha'a, where land is coowned with other households by shares, but with only one legal title for all the owners; or musharak, where several associated persons buy a plot of 250m 2 to be divided up. This type of ownership is common in East Amman. The fourth case exists when the Land and Survey Department delivers a document of recognition called tawsiya. According to a survey conducted by the Housing and Urban Development Corporation in 2000, more than half of Amman's informal settlements had land tenure (except in Wadi Abdoun, where it was a third). Generally, this was through musharak contracts (see Table 1). In 1980, a quarter of the city of Amman was occupied by informal settlements inhabited by Palestinian refugees (Client's Record, East Wahdat, 1992). The insecure position of refugee populations living in informal settlements in the heart of the old districts of the capital, which were therefore highly visible, became a national problem which went beyond urban management. In 1980, at the instigation of the World Bank, the Urban Development Department (UDD) was created within the Greater Amman Municipality to develop an urban renewal project of informal settlements located in the east of Amman. From the outset, Jordan implemented very avant-garde policies in terms of urban renewal.

The Jordanian Model of Upgrading with Participation

Before 1980, the Jordanian government had no policy on informal settlements. In 1965, the Housing Corporation was created to build social housing in Amman, intended not for rental but for sale. However, their cost was prohibitive for most refugees who were forced to fall back on rental solutions and illegal construction. Above all, there was no mandate to improve existing buildings.

The impact of the theory of urban renewal designed by John F. C. Turner

During the 1970s, there was a worldwide awareness of the need to address, in ways other than by destruction and displacement, the large informal settlements developed on the outskirts of large cities following rural depopulation and demographic transition. International institutions, particularly the World Bank, began to finance urban renewal programs strongly inspired by theories developed by the town planner John F. C. Turner in Peru in the 1960s. The basic concept of this new developmentalist ideology was to rehabilitate informal areas whilst involving their occupants at all stages of the process: from design to construction, including funding. The idea was to make them pay a nominal fee to acquire ownership of their home through long-term loans, while training them in the construction trades to help them out of unemployment and make them independent. The use of long-term loans was a condition for the replication of upgrading programs.

Within the Greater Amman Municipality, the mandate of the Urban Development Department (UDD) was to build basic infrastructures and develop services and provide housing for the poorest communities. Its slum upgrading program, funded by the World Bank, followed the new ideology of renovation through the participation of target populations. Three major development projects were implemented between 1981 and 1993 (Urban Development Project UDP 1, UDP 2 and UDP 3). The first project (UDP 1) included the upgrading of four informal settlements located in East Wahdat, Jabal Jofeh, Wadi Rimam and Jabal Nozeh, and the creation of three "sites and services" in Marka, Quweisma and Russeifa. The "sites and services" operations developed in Marka, Quweisma and Russeifa consisted for the UDD in acquiring land, subdividing plots and equipping them with basic infrastructure (roads, a water supply, sewers and electricity) and selling them in 150 m² plots, thus introducing a new type of zone (E).

The UDD applied the new concepts of urban renewal advocated by the World Bank: "funding of real-estate ownership" (land was purchased by the UDD and sold to squatters); "cost recovery" to allow the replication of the project; "selfconstruction" by squatters who thus learn building trades; "job opportunity" whereby half the employed labourers must be recruited from the local population concerned; "community involvement" to facilitate the upgrading and adapt it to the real needs of the inhabitants; finally "incremental housing" that develops from a central unit equipped with a sanitation section (a tap with running water and a toilet with a sewer) (interview with D. Khaled Jayousi, june 2006).

The HUDC built a community centre on each of the project sites. The objectives of the community centres were to mobilize and organize local community initiatives, promote income-generating activities and literacy campaigns, increase public awareness and encourage women's involvement in the community development process. Furthermore, women's vocational training centres were built to provide vocational training for women and promote their economic activities through a programme of access to credit [START_REF] Daly | Informal Settlements in Jordan. Upgrading Approaches Adopted and Lessons Learned[END_REF].

The model of the East Wahdat Upgrading programme (Aga Khan Prize 1992)

East Wahdat was chosen for upgrading due to its particularly bad condition. It suffered from high rates of infant mortality (68 ‰), very bad health conditions, a total lack of services and poor housing. East Wahdat was an informal extension of the UNRWA Wahdat camp. It was set up by Palestinian refugees, most of them holders of an UNRWA card, near Wahdat in order to have access to the camp services. But the contrast was huge between the UNRWA camp with its concrete constructions and the poor shacks with zinc roofs of East Wahdat. The main concept behind the effort was twofold: minimum destruction and the participation of the entire population. Walls were created around the lots, and the shanty houses were kept during the construction of the new houses, on the same lot. This is called "incremental housing". The inhabitants were not expelled, but on the contrary kept on their lot. They were asked to build a wall around their houses, following an urban plan. Each lot received a sanitary core (tap water and a sewerage system). This core can still be found at the entrance of each house in most of the camps and upgraded areas in Amman. During the upgrading process, the squatters first constructed a 12 to 20 square metre room into which they moved while their old shacks were being destroyed and a second room was being built (Figure 2).

An office of the UDD was created on the site, and the UDD social team was active in contacting the local population. According to Khaled Jayousi, the success of the East Wahdat upgrading programme was based on the issue of trust between the UDD and the local population. This success was honoured with the award of the Agha Khan Architecture Prize in 1992. The most important aspect of this project was that Palestinian refugees with Jordanian citizenship gained access to legal title deeds.

The aim of the programme was to improve the living conditions of residents of informal settlements by enabling them to secure land tenure and by providing them with basic infrastructure, shelter and community facilities. Funds were raised from the World Bank (31%), the Government of Jordan (25%) and the Housing Bank (44%). The land was bought from the original owners and mortgaged to the tenants with monthly instalments based on 33% of the income of each beneficiary.

After this first success, a total of 13 squatter sites were upgraded by the UDD between 1981 and 1991: the project renovated 11,665 units housing 114,000 inhabitants (Table 2). The UDD bought the land from the government and reallocated it to households. In most cases each household was allocated the plot it was already using. To secure land title deeds, each household had to reimburse the UDD for the cost of the land through long-term mortgages. In this way, most of the households managed to expand their houses or build new dwellings. During the 1980s some residents of informal settlements (such as the area of Jabal Ali, North East of Amman) refused the upgrading programmes. The reason being that, as Palestinian refugees, they still hoped to return to their homes in Palestine. They believed that the upgrading policies were unnecessary as their situation was "temporary". Moreover, they refused to accept Jordan or any other country as an alternative homeland (al-watan al-badil). They feared that the improvement of their informal areas meant converting them into permanent living areas. The same occurred in the 1970s in the UNRWA camps. Another reason for refusing the upgrading of informal areas like Jabal Ali was that people had lived there for a long time without paying taxes or extra costs. If the Government intervened, they would start paying taxes they could not afford.

The reversal of 1997: moving towards the supply of services alone

In 1991, the Housing and Urban Development Corporation was created from the merger of the Housing Corporation and the Urban Development Department.

The upgrading projects then began to include the whole country and no longer only Amman. But after the Oslo peace process in September 1993, the Jordanian government began implementing a completely different policy: aimed at improving only the provision of services in informal areas without addressing issues of access to property or the real-estate status of developed plots. Another major change, all the ten UNRWA camps and all three from the Department of Palestinian Affairs (DPA) were integrated into the work of HUDC.

In The strategies implemented since 1990 only deal with housing. To satisfy needs more cheaply, the HUDC began to organize land areas into small plots with special regulations, with surface areas of 250m² instead of 300m². The HUDC also started to build residential units with a surface area of 80 m²-120m² (the average surface area of residential units in Jordan is 115m²). However, construction costs for these HUDC projects are high (200 JD/m²) when compared to the 120 JD/m² when carried out by the private sector.

The Community Infrastructure Programmes offered opportunities. They provided a set of services while asking for nothing in return, and did not aim for cost recovery at all. They gave very good indemnities and compensations to all families regarding house demolition or displacement. But the fundamental aspect of land tenure was abandoned. The official reason was that land had become so expensive that even the Government could not afford to buy or sell it. Furthermore, the families concerned had become too poor to be able to take out 20-year loans with the Housing Bank, the Islamic Bank or the Government. As Jamal Al Daly explained: "As, far as the land tenure issue in the camps is concerned, the government has no intention to deal with this issue, since the camps are still being considered as a temporary shelter for refugees until their political question is addressed" (Al [START_REF] Daly | Informal Settlements in Jordan. Upgrading Approaches Adopted and Lessons Learned[END_REF].

The Community Infrastructure Programmes work in a completely different way from the old UDD upgrading programmes. They provide services without any financial or even technical participation from the beneficiaries because they concern utility services, and not housing improvements. They involve the local population, which must make up at least half the work force required for the work. Due to high unemployment figures, all the posts are filled. These infrastructure projects are generally well accepted by families in informal areas when compensation levels are high in the case of demolitions for the widening of roads. However, it is now out of the question to aid access to ownership by the regularisation of contracts or registration with the land registry.

In 2006, the HUDC planned several urban upgrading projects in the eastern part of the city, but they were suspended in 2008 because of the royal initiative "Decent Housing for Decent Living" which aimed to build 100,000 homes over five years for the most needy families in the country.

After thirty years of urban upgrading programmes in the poorest neighbourhoods in Amman, pockets of informal settlements have been reduced and the provision of basic services has improved. But social disparities are no less striking between the eastern and western parts of the city.

3 East Amman / West Amman: a cartographic vision of social disparities within Amman

Since 1952, four general censuses of population and habitat have been carried out in Jordan, at the initiative of the Ministry of Interior and the Department of Statistics: 1961Statistics: , 1979Statistics: , 1994Statistics: , 2004. . Surveys were carried out in households and their results were published throughout the governorate. Researchers can obtain the district level (Liwa) and sub-district level (caza), but it is quite exceptional to get the level of communities, neighbourhoods and blocks. In 2009, I had the privilege of working with Geographic Information System GIS engineers from the Municipality of Greater Amman on the 2004 census across 4,808 blocks, in the context of the Atlas of Jordan. First of all I suggested they convert the data, represented in the form of points, into surface areas. Then I was able to analyse various indicators to produce the figures attached.

Amman Density of Population at the block level

In Amman's central neighbourhoods (Wadi Hadadeh, Al Nozha, Al Hashemi Al Shamali, Al Hashemi Al Janubi, Hamza, Jabal Al Nasr, Al Amir Hasan, Jabal Jofeh, Al Manarah, Al Taj, Al Mudarraj, Al Ashrafia, Al Nadhif, Al Akhdar, Al Awdeh and Al Thera), the density of population is over 20,000 inhabitants per square kilometre (with a maximum of 31,240) which is among the highest urban densities in the world (Delhi is between 3,000 and 17,000 inhabitants per km²., London 4,000 to 7,000 inhabitants per km²) (figure 3).

Types of housing inside Greater

Amman at the block level (building, dar and villa).

Figure 5 allows us to understand the morphology of urban Amman. Indeed, the census tells us about the types of buildings: whether they are traditional houses (dar) with a central courtyard and one or two floors, buildings or villas. The mapping of these types of buildings can identify several morphological types: the dominant type in the centre of Amman is collective housing in apartment blocks, either family buildings of four storeys high (with the possibility of building stories below street level, to benefit from hillside slopes) built in the 1970s during the oil boom; or since the 1990s, buildings over eight storeys high. They make up on average more than half of all buildings. Mapping of traditional houses reveals two very different morphological types: that of the rural areas on the fringes of the city where more than two-thirds of houses are "dar" (in the North : Um Shtairat, Um al Orouq, Yajouz, Marj Firas; in the East: Salhiya, Amira Alya, Um Nowwarah; in the South: the former large cereal growing villages of Um al Kundum and Yadouda as well as Jawa Qobaa and Wafaa; finally in the West: Zabda, Waisa, Al Ghrous and Belal) with agricultural activities surviving in the south and west, and poor self-built habitats in the town centre. It is thus quite remarkable to note that both the Wahdat and Jabal Hussein camps had two thirds of their self-built buildings around courtyards statistically recorded as dars, even though they were densified by self construction after 1967. The informal settlements of Jabal Al Qusour and Jabal Akhdar also have a majority of homes classified as "dar" because they are dilapidated. Finally, villas are clearly concentrated in the western part of the city, constituting more than half of housing in the neighbourhoods of Abdoun Shamali and Abdoun Janubi, but also in a small developed area north of Raghadan, called Al Shahid Al Janoubi. On the whole, villas make up one quarter of buildings in Bashir, Tala Ali, Khalda, Um al Summaq and Deir Ghbar. All these neighbourhoods with villas have developed over the years 1990-2000 as shown in figure 1 (in 1994 only one third of them had been built).

The Young and the Elderly in Amman: the real indicator of poverty in the City

Figure 4 (a and b) show very clearly the East and West Amman Division line.

Less than one-third of West Amman's population is under the age of 15, compared to more than 38% of the population of East Amman (Al Nasr, Al Quwaismeh and Kherbet al Suq districts). At the other end of the age range, Figure 10 indicates that the elderly population group (between 75 and 79 years old) makes up less than 1% of the population in East Amman, whereas it sometimes reaches 6.6% in some blocks of West Amman. It is interesting to note that they are not in the neighbourhoods with the richest villas (whose residents are young), but more in the districts west of Amman developed during the 1950s : Badr, Zahran and Um Qusayr. In 2004, life expectancy in Jordan was 71 years for men and 74 years for women. At the national level, 37.3% of the population was under 15 in 2004, and 3.2% was over 65 (DOS, 2007). Jordan started its demographic transition forty years ago. The fertility rate is 3.6 children per woman. These figures allow us to present the different types of families in the city: with more than 4 children per family in the neighbourhoods of the East (informal areas near camps) against those with fewer than 4 children and with elderly people.

Workers and Job Seekers in Amman

Figure 4 (c and d) further confirm the division line between West and East Amman. Figure 9 shows that more than 36% (up to 62% in Abdoun Janoubi, Helal, Yasmin) of West Amman's active population is economically active, whereas only 26 to 36% of East Amman's active population is economically active. In contrast, job seekers represent between 6 and 14% of East Amman's and the rural fringe's population, and between 3 and 9% of West Amman's population.

Conclusion Remarks

After thirty years of urban renewal, Amman continues to be characterized by strong contrasts between poor, highly populated neighbourhoods where unemployment rates are high, and neighbourhoods primarily located in the west but also in the north-west and south west, where the active population is greater, the level of education better and buildings and infrastructure are more developed. Maps produced on the block level allow us to draw a dividing line between East and West neighbourhoods within the city of Amman. West Amman extends from Jabal Amman to Khalda and is bordered in the north by Wadi Hadadeh and in the South by Wadi Deir Ghbar. East Amman covers Amman's historical centre, and more than half of the city with its North and South expansions. One can only regret that the new property developments underway only focus on limited areas within the city: Abdali and the Eastern development belt, leaving large overpopulated areas under-equipped, lacking in social housing and centres of employment.

Figure 1 :

 1 Figure 1 : Location of HUDC Upgrading Programmes in Amman since 1980.

Figure 2 :

 2 Figure 2 : Incremental building in the East Wahdat Upgrading programme.

Table 1 :

 1 Land and Housing Tenure in Upgraded Informal Settlements in Amman, 2000

	Site Name	Population	Land Tenure	Housing Tenure %	Housing * Without Rent %	Housing with Rent %
	Al Nuzha	1 924	Private	50.6	26.5	22.8
	Al-Lawziya	1 756	Private	75.0	13.8	11.2
	Al-Tafayla	6 132	Gov Private		37.8
	Wadi Abdoun	1 686	Gov Private	37.9		15.1
	Abu Sayyah	511	GovPrivate			1.6
	Al-Zawahra	721	Gov Private	80.8	18.2	1
	Al-Qaisya	4 183	Gov Private	56.1	30.0	31.9
	Al-Musdar	388	Private	78.0	8.5	13.6
	Al-Hashemi	1 824	Private	45.3	32.4	22.0
	Wadi-Hadada	1 525	Private	64.4	16.8	18.6
	Al-Nadhif	11 737	Private	47.6	30.4	22.0
	Al-Musherfa	6 797	Gov Private	52.0	22.3	25.7
	Wadi Qattar	962	Gov Private	77.4	9.5	13.1
	Average			59.8 %	21.5 %	16.5 %
	* These units are for relatives or friends of households.
	Source : Base line survey, Final results, HUDC, 2000, Amman.

Table 2 :

 2 Basic information on Squatter settlements included in the upgrading program

	Program	Squatter Settlement Area	Population Completion	Location
			hectare		date
	UDP 1	Wahdat	9,1 ha	5 000	1984	Amman
	UDP 1	Jofeh	2,9 ha	2 500	1982	Amman
	UDP 1	Rimam	3,7 ha	3 500	1984	Amman
	UDP 1	Nuzha	2,4 ha	3 000	1988	Amman
	UDP 2	Hay Amir Hassan	3 ha	2 000	1985	Amman
	UDP 3	Salahadin	7,3 ha	2 000	1985	Aqaba
	UDP 3	Shallaleh North	11,7 ha	5 000	1991	Aqaba

Table 4 :

 4 1997 a new policy to reduce poverty and unemployment, the National Strategic Plan, was implemented by the Jordanian government in the context of structural adjustment policies advocated by the IMF. Its parallel urban policy was a vast infrastructure program for populations (CIP Community Infrastructure Program) both in camps and in informal areas. For the first time in the history of the Jordanian administration, all ten UNRWA camps and all three camps of the Palestinian Affairs Department were integrated into the work of HUDC.There are three types of Community Infrastructure Programme: CIP A, B and C. CIP A aims to renovate the infrastructure of informal habitats and camps. CIP B concerns the improvement of infrastructures in rural areas and small towns, in coordination with the Minister of municipal affairs. Finally, CIP C deals with the internal development of the HUDC through training and technical and computer equipment. The first infrastructure programme (CIP-A) was implemented from March 1998 to February 2002, mainly in Amman but also in Zarqa for informal areas and throughout the country for camps. The services included water supply and sanitation (environmentally sound wastewater and solid waste disposal); drainage systems to minimize property damage and reduce the risk of loss of human lives due to floods; safety measures through accessible roads and lighting; and the provision of schools, health facilities and community centres. Main thoroughfares were widened and lit in informal areas, but only on the periphery of UNRWA camps, in order to preserve their physical integrity. Finally, in informal areas, eight schools, five health centres and eight community centres (where literacy tuition and meetings of associations are held) were built. CIP-A concerned 450,000 people in informal areas and 220,000 in camps. Half of the operating costs (46 million Jordanian Dinars) were covered by the Jordanian government (20 million JD), a quarter by the World Bank (10 million JD), The German development bank KFW (8.5 million), 6 million by Islamic banks and 1.5 million by the Arab Fund. Basic information on Squatter Settlements included in CIP-A Project

	Squatter	Area	Number of	Average	Density	Location
	settlements	hectare	Households	Household Size	Person/ha
	Wadi Abdoun	3.8 ha	280	6	510	Amman
	Al-Hashemi	2.2	282	6	830	Amman
	Al-Musdar	0.7	56	6.1	550	Amman
	Wadi Hadada	1.9	189	6.1	800	Amman
	Al-Lawziya	2.2	340	7	800	Amman
	Al-Zawahra	4.7	102	7.3	150	Amman
	Al-Qaisya	14.7	584	6.9	280	Amman
	Al-Nadhif	8.7	1191	6.3	1350	Amman
	Nuzha	1.8	377	6.1	1070	Amman
	Wadi Qattar	18.0	130	7.4	500	Amman
	Al-Musherfa	20.5	1306	5.8	330	Amman
	Abu Sayyah	12.5	86	7.3	40	Amman
	Jena'a	24.0	1673	5.9	670	Zarqa
	Al-Tafayla	3.9	914	6.5	1570	Amman
	(Source: Main Report: Community Infrastructure Program; CIP Amman 1997 and HUDC
	Report 1999.)


Jean-Luc Fouquet

Henri Thuillier

Jean-Marie Vanherpe

On a family of cubic graphs containing the flower snarks

Keywords: cubic graph, perfect matching, strong matching, counting, hamiltonian cycle, 2-factor hamiltonian

We consider cubic graphs formed with k ≥ 2 disjoint claws C i ∼ K 1,3 (0 ≤ i ≤ k -1) such that for every integer i modulo k the three vertices of degree 1 of C i are joined to the three vertices of degree 1 of C i-1 and joined to the three vertices of degree 1 of C i+1 . Denote by t i the vertex of degree 3 of C i and by T the set {t 1 , t 2 , ..., t k-1 }.

). A strong matching M in a graph G is a matching M such that there is no edge of E(G) connecting any two edges of M . A cubic graph having a perfect matching union of two strong matchings is said to be a Jaeger's graph. We characterize the graphs F S(j, k) that are Jaeger's graphs.

Introduction

The complete bipartite graph K 1,3 is called, as usually, a claw. Let k be an integer ≥ 2 and let G be a cubic graph on 4k vertices formed with k disjoint claws C i = {x i , y i , z i , t i } (0 ≤ i ≤ k -1) where t i (the center of C i ) is joined to the three independent vertices x i , y i and z i (the external vertices of C i ). For every integer i modulo k C i has three neighbours in C i-1 and three neighbours in C i+1 . For any integer k ≥ 2 we shall denote the set of integers modulo k as Z k . In the sequel of this paper indices i of claws C i belong to Z k . By renaming some external vertices of claws we can suppose, without loss of generality, that {x i x i+1 , y i y i+1 , z i z i+1 } are edges for any i distinct from k -1. That is to say the subgraph induced on X = {x 0 , x 1 , . . . , x k-1 } (respectively Y = {y 0 , y 1 , . . . , y k-1 }, Z = {z 0 , z 1 , . . . , z k-1 }) is a path or a cycle (as induced subgraph of G). Denote by T the set of the internal vertices {t 0 , t 1 , . . . , t k-1 }.

Up to isomorphism, the matching joining the external vertices of C k-1 to those of C 0 (also called, for k ≥ 3, edges between C k-1 and C 0 ) determines the graph G. In this way we construct essentially three distinct graphs, namely F S(1, k), F S(2, k) and F S (3, k). The graph F S(j, k) (j ∈ {1, 2, 3}) is the graph where the set of vertices ∪ i=k-1 i=0 {C i \ {t i }} induces j cycles. For k ≥ 3 and any j ∈ {1, 2, 3} the graph F S(j, k) is a simple cubic graph. When k is odd, the F S(2, k) are the graphs known as the flower snarks [START_REF] Isaacs | Infinite families of non-trivial trivalent graphs which are not Tait colorable[END_REF]. We note that F S(3, 2) and F S(2, 2) are multigraphs, and that F S(1, 2) is isomorphic to the cube. For k = 2 the notion of "edge between C k-1 and C 0 " is ambiguous, so we must define it precisely. For two parallel edges having one end in C 0 and the other in C 1 , for instance two parallel edges having x 0 and x 1 as endvertices, we denote one edge by x 0 x 1 and the other by x 1 x 0 . An edge in {x 1 x 0 , x 1 y 0 , x 1 z 0 , y 1 x 0 , y 1 y 0 , y 1 z 0 , z 1 x 0 , z 1 y 0 , z 1 z 0 }, if it exists, is an edge between C 1 and C 0 . We will say that x 0 x 1 , y 0 y 1 and z 0 z 1 are edges between C 0 and C 1 .

By using an ad hoc translation of the indices of claws (and of their vertices) and renaming some external vertices of claws, we see that for any reasoning about a sequence of h ≥ 3 consecutive claws (C i , C i+1 , C i+2 , . . . , C i+h-1 ) there is no loss of generality to suppose that 0 ≤ i < i+h-1 ≤ k -1. For a sequence of claws (C p , ..., C r ) with 0 ≤ p < r ≤ k -1, since 0 is a possible value for subscript p and since k -1 is a possible value for subscript r, it will be useful from time to time to denote by x ′ p-1 the neighbour in C p-1 of the vertex x p of C p (recall that x ′ p-1 ∈ {x k-1 , y k-1 , z k-1 } if p = 0), and to denote by x ′ r+1 the neighbour in C r+1 of the vertex x r of C r (recall that x ′ r+1 ∈ {x 0 , y 0 , z 0 } if r = k -1). We shall make use of analogous notations for neighbours of y p , z p , y r and z r .

We shall prove in the following lemma that there are essentially two types of perfect matchings in F S(j, k).

Lemma 1 Let G ∈ {F S(j, k), j ∈ {1, 2, 3}, k ≥ 2 and let M be a perfect matching of G. Then the 2-factor G \ M induces a path of length 2 and an isolated vertex in each claw C i (i ∈ Z k ) and M fulfils one (and only one) of the three following properties : i) For every i in Z k M contains exactly one edge joining the claw C i to the claw C i+1 , ii) For every even i in Z k M contains exactly two edges between C i and C i+1 and none between C i-1 and C i , iii) For every odd i in Z k M contains exactly two edges between C i and C i+1 and none between C i-1 and C i .

Moreover, when k is odd M satisfies only item i).

Proof Let M be a perfect matching of G = F S(j, k) for some j ∈ {1, 2, 3}.

Since M contains exactly one edge of each claw, it is obvious that G \ M induces a path of length 2 and an isolated vertex in each claw C i .

For each claw C i of G the vertex t i must be saturated by an edge of M whose end (distinct from t i ) is in {x i , y i , z i }. Hence there are exactly two edges of M having one end in C i and the other in

C i-1 ∪ C i+1 .
If there are two edges of M between C i and C i+1 then there is no edge of M between C i-1 and C i . If there are two edges of M between C i-1 and C i then there is no edge of M between C i and C i+1 . Hence, we get ii) or iii) and we must have an even number k of claws in G.

Assume now that there is only one edge of M between C i-1 and C i . Then there exists exactly one edge between C i and C i+1 and, extending this trick to each claw of G, we get i) when k is even or odd.

Definition 2

We say that a perfect matching M of F S(j, k) is of type 1 in Case i) of Lemma 1 and of type 2 in Cases ii) and iii). If neccessary, to distinguish Case ii) from Case iii) we shall say type 2.0 in Case ii) and type 2.1 in Case iii). We note that the numbers of perfect matchings of type 2.0 and of type 2.1 are equal.

Notation : The length of a path P (respectively a cycle Γ) is denoted by l(P ) (respectively l(Γ)).

2 Counting perfect matchings of F S(j, k)

We shall say that a vertex v of a cubic graph G is inflated into a triangle when we construct a new cubic graph G ′ by deleting v and adding three new vertices inducing a triangle and joining each vertex of the neighbourhood N(v) of v to a single vertex of this new triangle. We say also that G ′ is obtained from G by a triangular extension. The converse operation is the contraction or reduction of the triangle. The number of perfect matchings of G is denoted by µ(G).

Lemma 3 Let G be a bipartite cubic graph and let {V 1 , V 2 } be the bipartition of its vertex set. Assume that each vertex in some subset W 1 ⊆ V 1 is inflated into a triangle and let G ′ be the graph obtained in that way. Then µ(G) = µ(G ′ ).

Proof Note that {V 1 , V 2 } is a balanced bipartition and, by Knig's Theorem, the graph G is a cubic 3-edge colourable graph. So, G ′ is also a cubic 3-edge colourable graph (hence, G and G ′ have perfect matchings). Let M be a perfect matching of G ′ . Each vertex of V 1 \ W 1 is saturated by an edge whose second end vertex is in V 2 . Let A ⊆ V 2 be the set of vertices so saturated in V 2 . Assume that some triangle of G ′ is such that the three vertices are saturated by three edges having one end in the triangle and the second one in V 2 . Then we need to have at least

|W 1 | + 2 vertices in V 2 \ A, a contradiction.
Hence, M must have exactly one edge in each triangle and the contraction of each triangle in order to get back G transforms M in a perfect matching of G. Conversely, each perfect matching of G leads to a unique perfect matching of G ′ and we obtain the result.

Let us denote by µ(j, k) the number of perfect matchings of F S(j, k), µ 1 (j, k) its number of perfect matchings of type 1 and µ 2 (j, k) its number of perfect matchings of type 2.

Lemma 4

We have

• µ(1, 3) = µ 1 (1, 3) = 9 • µ(2, 3) = µ 1 (2, 3) = 8 • µ(3, 3) = µ 1 (3, 3) = 6 • µ(1, 2) = 9, µ 1 (1, 2) = 3 • µ(2, 2) = 10, µ 1 (2, 2) = 4 • µ(3, 2) = 12, µ 1 (3, 2) = 6
Proof The cycle containing the external vertices of the claws of the graph F S(1, 3) is x 0 , x 1 , x 2 , y 0 , y 1 , y 2 , z 0 , z 1 , z 2 , x 0 . Consider a perfect matching M containing the edge t 0 x 0 . There are two cases: i) x 1 x 2 ∈ M and ii) x 1 t 1 ∈ M.

In Case i) we must have y 0 y 1 , t 1 z 1 , t 2 z 2 , z 0 y 2 ∈ M. In Case ii) there are two sub-cases: ii).a x 2 y 0 ∈ M and ii).b x 2 t 2 ∈ M. In Case ii).a we must have y 1 y 2 , t 2 z 2 , z 0 z 1 ∈ M and in Case ii).b we must have y 0 y 1 , y 2 z 0 , z 1 z 2 ∈ M. Thus, there are exactly 3 distinct perfect matching containing t 0 x 0 . By symmetry, there are 3 distinct perfect matchings containing t 0 y 0 , and 3 distinct matchings containing t 0 z 0 , therefore µ(1, 3) = 9.

It is well known that the Petersen graph has exactly 6 perfect matchings. Since F S(2, 3) is obtained from the Petersen graph by inflating a vertex into a triangle these 6 perfect matchings lead to 6 perfect matchings of F S(2, 3). We have two new perfect matchings when considering the three edges connected to this triangle (we have two ways to include these edges into a perfect matching). Hence µ(2, 3) = 8.

F S(3, 3) is obtained from K 3,3 by inflating three vertices in the same colour of the bipartition. Since K 3,3 has six perfect matchings, applying Lemma 3 we get immediately the result for µ [START_REF] Fouquet | On linear arboricity of cubic graphs[END_REF][START_REF] Fouquet | On linear arboricity of cubic graphs[END_REF].

Is is a routine matter to obtain the values for F S(j, 2) (j ∈ {1, 2, 3}).

Theorem 5 The numbers µ(i, k) of perfect matchings of F S(i, k) (i ∈ {1, 2, 3}) are given by: When k is odd

• µ(2, k) = 2 k • µ(1, k) = 2 k + 1 • µ(3, k) = 2 k -2
When k is even

• µ(2, k) = 2 × 3 k 2 + 2 k • µ(1, k) = 2 × 3 k 2 + 2 k -1 • µ(3, k) = 2 × 3 k 2 + 2 k + 2
Proof We shall prove this result by induction on k and we distinguish the case "k odd" and the case "k even".

The following trick will be helpful. Let i = 0 and let C i-2 , C i-1 , C i and C i+1 be four consecutive claws of F S(j, k) (j ∈ {1, 2, 3}). We can delete C i-1 and C i and join the three external vertices of C i-2 to the three external vertices of C i+1 by a matching in such a way that the resulting graph is F S(j ′ , k -2). We have three distinct ways to reduce F S(j, k) into F S(j ′ , k -2) when deleting C i-1 and C i .

Case 1: We add the edges {x i-2 x i+1 , y i-2 y i+1 , z i-2 z i+1 } and we get

G 1 = F S(j 1 , k -2)
Case 2: We add the edges {x i-2 y i+1 , y i-2 z i+1 , z i-2 x i+1 } and we get G 2 = F S(j 2 , k -2).

Case 3: We add the edges {x i-2 z i+1 , y i-2 x i+1 , z i-2 y i+1 } and we get G 3 = F S(j 3 , k -2).

Following the cases, we shall precise the values of j 1 , j 2 and j 3 .

It is an easy task to see that each perfect matching of type 1 of F S(j, k) leads to a perfect matching of either G 1 or G 2 or G 3 and, conversely, each perfect matching of type 1 of G 1 allows us to construct 2 distinct perfect matchings of type 1 of F S(j, k), while each perfect matching of type 1 of G 2 and G 3 allows us to construct 1 perfect matching of type 1 of F S(j, k).

We have

µ 1 (j, k) = 2µ 1 (G 1 ) + µ 1 (G 2 ) + µ 1 (G 3 ) (1) Claim 1 µ 1 (2, k) = 2 k
Proof Since the result holds for F S(2, 3) and F S(2, 2) by Lemma 4, in order to prove the result by induction on the number k of claws, we assume that the property holds for

F S(2, k -2) with k -2 ≥ 2.
In that case G 1 , G 2 and G 3 are isomorphic to F S(2, k -2). Using Equation 1we have, as claimed

µ 1 (2, k) = 4µ 1 (2, k -2) = 2 k Claim 2 µ 1 (1, k) = 2 k -(-1) k and µ 1 (3, k) = 2 k + 2(-1) k
Proof Since the result holds for F S(1, 3), F S(1, 2), F S(3, 3), and F S(3, 2), by Lemma 4, in order to prove the result by induction on the number k of claws, we assume that the property holds for F S(1, k -2), and

F S(3, k -2) with k -2 ≥ 2. When considering F S(1, k), G 1 is isomorphic to F S(1, k -2)
, and among G 2 and G 3 one of them is isomorphic to F S(3, k -2) and the other to F S(1, k -2).

In the same way, when considering

F S(3, k), G 1 is isomorphic to F S(3, k -2),
and

G 2 and G 3 are isomorphic to F S(1, k -2).
Using Equation 1 we have,

µ 1 (1, k) = 2µ 1 (1, k -2) + µ 1 (1, k -2) + µ 1 (3, k -2) and µ 1 (1, k) = 2(2 k-2 + 1) + 2 k-2 + 1 + 2 k-2 -2 = 2 k + 1 µ 1 (3, k) = 2(2 k-2 -2) + 2 k-2 + 1 + 2 k-2 + 1 = 2 k -2
When k is odd, we have µ 2 (j, k) = 0 by Lemma 1 and hence µ(j, k) = µ 1 (j, k)

When k is even it remains to count the number of perfect matchings of type 2. From Lemma 1, for every two consecutive claws C i and C i+1 , we have either two edges of M joining the external vertices of C i to those of C i+1 or none. We have 3 ways to choose 2 edges between C i and C i+1 , each choice of these two edges can be completed in a unique way in a perfect matching of the subgraph

C i ∪ C i+1 .
Hence we get easily that the number of perfect matchings of type

2 in F S(j, k) (j ∈ {1, 2, 3}) is µ 2 (j, k) = 2 × 3 k 2 (2)
Using Claims 1 and 2 and Equation 2we get the results for µ(j, k) when k is even.

3 Some structural results about perfect matchings of FS(j, k)

Perfect matchings of type 1

Lemma 6 Let M be a perfect matching of type 1 of G = F S(j, k). Then the 2-factor G \ M has exactly one or two cycles and each cycle of

G \ M has at least one vertex in each claw C i (i ∈ Z k ).
Proof Let M be a perfect matching of type 1 in G. Let us consider the claw

C i for some i in Z k . Assume without loss of generality that the edge of M contained in C i is t i x i . The cycle of G \ M visiting x i comes from C i-1
, crosses C i by using the vertex x i and goes to C i+1 . By Lemma 1, the path

y i t i z i is contained in a cycle of G \ M.
The two edges incident to y i and z i joining C i to C i-1 (as well as those joining C i to C i+1 ) are not contained both in M (since M has type 1). Thus, the cycle of G \ M containing y i t i z i comes from C i-1 , crosses C i and goes to C i+1 . Thus, we have at most two cycles in G \ M, as claimed, and we can note that each claw must be visited by these cycles.

Definition 7 Let us suppose that M is a perfect matching of type 1 in G = F S(j, k) such that the 2-factor G \ M has exactly two cycles Γ 1 and Γ 2 .

A claw C i intersected by three vertices of Γ 1 (respectively Γ 2 ) is said to be Γ 1 -major (respectively Γ 2 -major).

Lemma 8 Let M be a perfect matching of type 1 of G = F S(j, k) such that the 2-factor G \ M has exactly two cycles. Then, the lengths of these two cycles have the same parity as k, and those lengths are distinct when k is odd.

Proof Let Γ 1 and Γ 2 be the two cycles of G \ M. By Lemma 6, for each i in Z k these two cycles must cross the claw C i . Let k 1 be the number of Γ 1 -major claws and let k 2 be the number of Γ 2 -major claws. We have

k 1 + k 2 = k, l(Γ 1 ) = 3k 1 + k 2 and l(Γ 2 ) = 3k 2 + k 1 .
When k is odd, we must have either k 1 odd and k 2 even, or k 1 even and k 2 odd. Then Γ 1 and Γ 2 have distinct odd lengths. When k is even, we must have either k 1 and k 2 even, or k 2 and k 1 odd. Then Γ 1 and Γ 2 have even lengths.

Lemma 9 Let M be a perfect matching of type 1 of G = F S(j, k) such that the 2-factor G \ M has exactly two cycles Γ 1 and Γ 2 . Suppose that there are two consecutive Γ 1 -major claws C j and C j+1 with j ∈ Z k \ {k -1}. Then there is a perfect matching M ′ of type 1 such that the 2-factor G \ M ′ has exactly two cycles Γ ′ 1 and Γ ′ 2 having the following properties:

a) for i ∈ Z k \ {j, j + 1} C i is Γ ′ 2 -major if and only if C i is Γ 2 -major, b) C j and C j+1 are Γ ′ 2 -major, c) l(Γ ′ 1 ) = l(Γ 1 ) -4 and l(Γ ′ 2 ) = l(Γ 2 ) + 4.
Proof Consider the claws C j and C j+1 . Since C j is a Γ 1 -major claw suppose without loss of generality that t j z j belongs to M and that Γ 1 contains the path x ′ j-1 x j t j y j y j+1 where x ′ j-1 denotes the neighbour of x j in C j-1 (then x j x j+1 belongs to M). Since C j+1 is Γ 1 -major and Γ 2 goes through C j and C j+1 , the cycle Γ 1 must contain the path y j+1 t j+1 x j+1 x ′ j+2 where x ′ j+2 denotes the neighbour of x j+1 in C j+2 (then M contains t j+1 z j+1 and y j+1 y ′ j+2 ). Denote by P 1 the path x ′ j-1 x j t j y j y j+1 t j+1 x j+1 x ′ j+2 . Note that Γ 2 contains the path

P 2 = z ′ j-1 z j z j+1 z ′ j+1
where z ′ j-1 and z ′ j+1 are defined similarly. See to the left part of Figure 2.

Let us perform the following local transformation: delete x j x j+1 , t j z j and t j+1 z j+1 from M and add z j z j+1 , t j x j and t j+1 x j+1 . Let M ′ be the resulting perfect matching. Then the subpath P 1 of Γ 1 is replaced by

P ′ 1 = x ′ j-1 x j x j+1 x ′ j+2
and the subpath P 2 of Γ 2 is replaced by P ′ 2 = z ′ j-1 z j t j y j y j+1 t j+1 z j+1 z ′ j+2 (see Figure 2). We obtain a new 2-factor containing two new cycles Γ ′ 1 and Γ ′ 2 . Note that C j and C j+1 are Γ ′ Γ 1 -major). The length of Γ 1 (now Γ ′ 1 ) decreases of 4 units while the length of Γ 2 (now Γ ′

2 ) increases of 4 units. The operation depicted in Lemma 9 above will be called a local transformation of type 1.

Lemma 10 Let M be a perfect matching of type 1 of G = F S(j, k) such that the 2-factor G \ M has exactly two cycles Γ 1 and Γ 2 . Suppose that there are three consecutive claws C j , C j+1 and C j+2 with j in Z k \ {k -1, k -2} such that C j and C j+2 are Γ 1 -major and C j+1 is Γ 2 -major. Then there is a perfect matching M ′ of type 1 such that the 2-factor G \ M ′ has exactly two cycles Γ ′ 1 and Γ ′ 2 having the following properties:

a) for i ∈ Z k \ {j, j + 1, j + 2} C i is Γ ′ 2 -major if and only if C i is Γ 2 -major, b) C j and C j+2 are Γ ′ 2 -major and C j+1 is Γ ′ 1 -major, c) l(Γ ′ 1 ) = l(Γ 1 ) -2 and l(Γ ′ 2 ) = l(Γ 2 ) + 2.
Proof Since C j is Γ 1 -major, as in the proof of Lemma 9 suppose that Γ 1 contains the path x ′ j-1 x j t j y j y j+1 (that is edges t j z j and x j x j+1 belong to M). Since C j+1 is Γ 2 -major the cycle Γ 1 contains the edge y j+1 y j+2 . Then we see that Γ 1 contains the path Q 1 = x ′ j-1 x j t j y j y j+1 y j+2 t j+2 z j+2 z ′ j+3 and that Γ 2 contains the path Q 2 = z ′ j-1 z j z j+1 t j+1 x j+1 x j+2 x ′ j+3 . Note that y j+1 t j+1 , z j+1 z j+2 and t j+2 x j+2 belong to M.

Let us perform the following local transformation: delete t j z j , x j x j+1 , z j+1 z j+2 and x j+2 t j+2 from M and add x j t j , z j z j+1 , x j+1 x j+2 and z j+2 t j+2 to M. Let M ′ be the resulting perfect matching. Then the subpath 3). We obtain a new 2-factor containing two new cycles named Γ ′ 1 and Γ ′ 2 . Note that C j and C j+2 are now Γ ′ 2major claws and C j+1 is Γ ′ 1 -major. The length of Γ 1 decreases of 2 units while the length of Γ 2 increases of 2 units. It is clear that for The operation depicted in Lemma 10 above will be called a local transformation of type 2.

Q 1 of Γ 1 is replaced by Q ′ 1 = x ′ j-1 x j x j+1 t j+1 z j+1 z j+2 z ′ j+3 and the subpath Q 2 of Γ 2 is replaced by Q ′ 2 = z ′ j-1 z j t j y j y j+1 y j+2 t j+2 x j+2 x ′ j+3 (see Figure
i ∈ Z k \ {j, j + 1, j + 2} C i is Γ ′ 2 -major (respectively Γ ′ 1 -major) if and only if C i is Γ 2 -major (respec- tively Γ 1 -major).
Lemma 11 Let M be a perfect matching of type 1 of G = F S(j, k) such that the 2-factor G \ M has exactly two cycles Γ 1 and Γ 2 . Suppose that there are three consecutive claws C j , C j+1 and C j+2 with j in Z k \ {k -1, k -2} such that C j+1 and C j+2 are Γ 2 -major and C j is Γ 1 -major. Then there is a perfect matching M ′ of type 1 such that the 2-factor G \ M ′ has exactly two cycles Γ ′ 1 and Γ ′ 2 having the following properties:

a) for i ∈ Z k \ {j, j + 1, j + 2} C i is Γ ′ 2 -major if and only if C i is Γ 2 -major, b) C j and C j+1 are Γ ′ 2 -major and C j+2 is Γ ′ 1 -major, c) l(Γ ′ 1 ) = l(Γ 1 ) and l(Γ ′ 2 ) = l(Γ 2 ).
Proof Since C j is Γ 1 -major, as in the proof of Lemma 9 suppose that Γ 1 contains the path x ′ j-1 x j t j y j y j+1 (that is edges t j z j and x j x j+1 belong to M). Since C j+1 and C j+2 are Γ 2 -major, the unique vertex of C j+1 (respectively C j+2 ) contained in Γ 1 is y j+1 (respectively y j+2 ). Note that the perfect matching M contains the edges t j z j , x j x j+1 , t j+1 y j+1 , z j+1 z j+2 and t j+2 y j+2 . Then the path R 1 = x ′ j-1 x j t j y j y j+1 y j+2 y ′ j+3 is a subpath of Γ 1 and the path

R 2 = z ′ j-1 z j z j+1 t j+1 x j+1 x j+2 t j+2 z j+2 z ′ j+3 is a subpath of Γ 2 .
See to the left part of Figure 4.

Let us perform the following local transformation: delete t j z j , x j x j+1 , t j+1 y j+1 , z j+1 z j+2 and t j+2 y j+2 from M and add x j t j , z j z j+1 , t j+1 x j+1 , y j+1 y j+2 and t j+2 z j+2 . Let M ′ be the resulting perfect matching. Then the subpath The operation depicted in Lemma 11 above will be called a local transformation of type 3.

R 1 of Γ 1 is replaced by R ′ 1 = x ′ j-1 x j x j+1 x j+2 t j+2 y j+2 y ′ j+3 and the subpath R 2 of Γ 2 is replaced by R ′ 2 = z ′ j-1 z j t j y j y j+1 t j+1 z j+1 z j+2 z ′ j+3 . We obtain a new 2- factor containing two new cycles named Γ ′ 1 and Γ ′ 2 such that l(Γ ′ 1 ) = l(Γ 1 ) and l(Γ ′ 2 ) = l(Γ 2 ) (see Figure 4). It is clear that for i ∈ Z k \ {j, j + 1, j + 2} C i is Γ ′ 2 -major (respectively Γ ′ 1 -major) if and only if C i is Γ 2 -major (respec- tively Γ 1 -major). Note that C j and C j+1 are Γ ′ 2 -major and C j+2 is Γ ′ 1 -major.
Lemma 12 Let M be a perfect matching of type 1 of G = F S(j, k) such that the 2-factor G \ M has exactly two cycles Γ 1 and Γ 2 such that l(Γ 1 ) ≤ l(Γ 2 ) and l(Γ 2 ) is as great as possible. Then there exists at most one Γ 1 -major claw.

Proof Suppose, for the sake of contradiction, that there exist at least two Γ 1 -major claws. Since l(Γ 2 ) is maximum, by Lemma 9 these claws are not consecutive. Then consider two Γ 1 -major claws C i and C i+h+1 (with h ≥ 1) such that the h consecutive claws (C i+1 , . . . , C i+h ) are Γ 2 -major. Since l(Γ 2 ) is maximum, by Lemma 10 the number h is at least 2. Then by applying r = ⌊ h 2 ⌋ consecutive local transformations of type 3 (Lemma 11) we obtain a perfect matching M (r) such that the 2-factor G \ M (r) has exactly two cycles Γ 2 ) is maximum, we can conclude by Lemma 9 and by Lemma 10 that h is neither even nor odd, a contradiction.

Perfect matchings of type 2

We give here a structural result about perfect matchings of type 2 in G = F S(j, k).

Lemma 13 Let M be a perfect matching of type 2 of G = F S(j, k) (with k ≥ 4). Then the 2-factor G \ M has exactly one cycle of even length l ≥ k and a set of p cycles of length 6 where l + 6p = 4k (with 0 ≤ p ≤ k 2 ).

Proof Let M be a perfect matching of type 2 in G. By Lemma 1 the number k of claws is even. Let i in Z k such that there are two edges of M between C i-1 and C i . There are no edges of M between C i and C i+1 and two edges of M between C i+1 and C i+2 . We may consider that 0 ≤ i < k -1. For j ∈ {i, i + 2, i + 4, . . .} we denote by e j the unique edge of G \ M having one end vertex in C j-1 and the other in C j . Let us denote by A the set {e i , e i+2 , e i+4 , . . .}. We note that | A |= k 2 . Assume without loss of generality that the two edges of M between C i-1 and C i have end vertices in C i which are x i and y i (then z i is the end vertex of e i in C i ). Two cases may now occur.

Case 1: The end vertices in C i+1 of the two edges of M between C i+1 and C i+2 are x i+1 and y i+1 (then z i+1 is the end vertex of e i+2 in C i+1 ). In that case the 2-factor G\M contains the cycle of length 6 x i x i+1 t i+1 y i+1 y i t i while the edge z i z i+1 of G \ M relies e i and e i+2 .

Case 2: The end vertices in C i+1 of the two edges of M between C i+1 and C i+2 are y i+1 and z i+1 (respectively x i+1 and z i+1 ). Then x i+1 (respectively y i+1 ) is the end vertex of e i+2 in C i+1 . In that case the edges e i and e i+2 are connected in G \ M by the path z i z i+1 t i+1 y i+1 y i t i x i x i+1 (respectively z i z i+1 t i+1 x i+1 x i t i y i y i+1 ).

The same reasoning can be done for {e i+2 , e i+4 }, {e i+4 , e i+6 }, and so on. Then, we see that the set A is contained in a unique cycle Γ of G \ M which crosses each claw. Thus, the length l of Γ is at least k. More precisely, each e j in A contributes for 1 in l, in Case 1 the edge z i z i+1 contributes for 1 in l and in Case 2 the path z i z i+1 t i+1 y i+1 y i t i x i x i+1 contributes for 7 in l. Let us suppose that Case 1 appears p times (0

≤ p ≤ k 2 ), that is to say G \ M contains p cycles of length 6. Since Case 2 appears k 2 -p times, the length of Γ is l = k 2 + p + 7( k 2 -p) = 4k -6p.
Remark 14 If k is even then by Lemmas 6, 8 and 13 F S(j, k) has an even 2-factor. That is to say F S(j, k) is a cubic 3-edge colourable graph .

4 Perfect matchings and hamiltonian cycles of F (j, k)

Perfect matchings of type 1 and hamiltonicity

Theorem 15 Let M be a perfect matching of type 1 of G = F S(j, k). Then the 2-factor G \ M is a hamiltonian cycle except for k odd and j = 2, and for k even and j = 1 or 3.

Proof Suppose that there exists a perfect matching M of type 1 of G such that G \ M is not a hamiltonian cycle. By Lemma 6 and Lemma 8 the 2factor G \ M is made of exactly two cycles Γ 1 and Γ 2 whose lengths have the same parity as k. Without loss of generality we suppose that l(Γ 1 ) ≤ l(Γ 2 ).

matching M of G the 2-factor G \ M is a hamiltonian cycle).

By Theorem 15 for any odd k ≥ 3 and j ∈ {1, 3} or for any even k and j = 2, and for every perfect matching M of type 1 in F S(j, k) the 2-factor F S(j, k) \ M is a hamiltonian cycle. By Lemma 13 F S(2, k) (k ≥ 4) may have a perfect matching M of type 2 such that the 2-factor F S(2, k) \ M is not a hamiltonian cycle (it may contains cycles of length 6).

Then we have the following.

Corollary 17 A graph G = F S(j, k) is 2-factor hamiltonian if and only if k is odd and j = 1 or 3.

We note that F S(1, 3) is the "Triplex Graph" of Robertson, Seymour and Thomas [START_REF] Robertson | Excluded minor in cubic graphs[END_REF]. We shall examine others known results about 2-factor hamiltonian cubic graphs in Section 5.

Corollary 18

The chromatic index of a graph G = F S(j, k) is 4 if and only if j = 2 and k is odd.

Proof When j = 2 and k is odd, any 2-factor must have at least two cycles, by Theorem 15. Then Lemma 8 implies that any 2-factor is composed of two odd cycles. Hence G has chromatic index 4.

When j = 1 or 3 and k is odd by Theorem 15 F S(j, k) is hamiltonian. If k is even then by Lemmas 6, 8 and 13 F S(j, k) has an even 2-factor.

Perfect matchings of type 2 and hamiltonicity

At this point of the discourse one may ask what happens for perfect matchings of type 2 in F S(j, k) (k even). Can we characterize and count perfect matchings of type 2, complementary 2-factor of which is a hamiltonian cycle ? An affirmative answer shall be given.

Let us consider a perfect matching M of type 2 in F S(j, 2p) with p ≥ 2. Suppose that there are no edges of M between C 2i-1 and C 2i (for any i ≥ 1), that is M is a matching of type 2.0 (see Definition 2). Consider two consecutive claws C 2i and C 2i+1 (0 ≤ i ≤ p -1). There are three cases:

Case (x): {y 2i y 2i+1 , z 2i z 2i+1 } ⊂ M (then, M∩(C 2i ∪C 2i+1 ) = {x 2i t 2i , x 2i+1 t 2i+1 }). Case (y): {x 2i x 2i+1 , z 2i z 2i+1 } ⊂ M (then, M∩(C 2i ∪C 2i+1 ) = {y 2i t 2i , y 2i+1 t 2i+1 }). Case (z): {x 2i x 2i+1 , y 2i y 2i+1 } ⊂ M (then, M∩(C 2i ∪C 2i+1 ) = {z 2i t 2i , z 2i+1 t 2i+1 }).
The subgraph induced on C 2i ∪C 2i+1 is called a block. In Case (x) (respectively Case (y), Case (z)) a block is called a block of type X (respectively block of type Y , block of type Z). Then F S(j, 2p) with a perfect matchings M of type 2.0 can be seen as a sequence of p blocks properly relied. In other words, a perfect matchings M of type 2 in F S(j, 2p) is entirely described by a word of length p on the alphabet of three letters {X, Y, Z}. The block C 0 ∪ C 1 is called initial block and the block C 2p-1 ∪ C 2p is called terminal block. These extremal blocks are not considered here as consecutive blocks.

By Lemma 13, F S(j, 2p) \ M has no 6-cycles if and only if F S(j, 2p) \ M is a unique even cycle. It is an easy matter to prove that two consecutive blocks do not induce a 6-cycle if and only if they are not of the same type. Then the possible configurations for two consecutive blocks are XY , XZ, Y X, Y Z, ZX and ZY . To eliminate a possible 6-cycle in C 0 ∪ C 2p-1 we have to determine for every j ∈ {1, 2, 3} the forbidden extremal configurations. An extremal configuration shall be denoted by a word on two letters in {X, Y, Z} such that the left letter denotes the type of the initial block C 0 ∪ C 1 and the right letter denotes the type of the terminal block C 2p-1 ∪ C 2p . We suppose that the extremal blocks are connected for j = 1 by the edges x 2p-1 z 0 , y 2p-1 x 0 and z 2p-1 y 0 , for j = 2 by the edges x 2p-1 x 0 , y 2p-1 z 0 and z 2p-1 y 0 and for j = 3 by the edges x 2p-1 x 0 , y 2p-1 y 0 and z 2p-1 z 0 . Then, it is easy to verify that we have the following result. Thus, any perfect matching M of type 2.0 of F S(j, 2p) such that the 2-factor G \ M is a hamiltonian cycle is totally characterized by a word of length p on the alphabet {X, Y, Z} having no two identical consecutive letters and such that the sub-word [initial letter][terminal letter] is not a forbidden configuration. Then, we are in position to obtain the number of such perfect matchings in F S(j, 2p). Let us denote by µ ′ 2.0 (j, 2p) (respectively µ ′ 2.1 (j, 2p), µ ′ 2 (j, 2p)) the number of perfect matchings of type 2.0 (respectively type 2.1, type 2) complementary to a hamiltonian cycle in F S(j, 2p). Clearly µ ′ 2 (j, 2p) = µ ′ 2.0 (j, 2p) + µ ′ 2.1 (j, 2p) and µ ′ 2.0 (j, 2p) = µ ′ 2.1 (j, 2p).

Strong matchings and Jaeger's graphs

For a given graph G = (V, E) a strong matching (or induced matching) is a matching S such that no two edges of S are joined by an edge of G. That is, S is the set of edges of the subgraph of G induced by the set V (S). We consider cubic graphs having a perfect matching which is the union of two strong matchings that we call Jaeger's graph (in his thesis [START_REF] Jaeger | Etude de quelques invariants et problèmes d'existence en théorie de graphes[END_REF] Jaeger called these cubic graphs equitable). We call Jaeger's matching a perfect matching M of a cubic graph G which is the union of two strong matchings M B and M R . Set B = V (M B ) (the blue vertices) and R = V (M R ) (the red vertices).

An edge of G is said mixed if its end vertices have distinct colours. Since the set of mixed edges is E(G) \ M, the 2-factor \ M is even and

| B | = | M |.
Thus, every Jaeger's graph G is a cubic 3-edge colourable graph and for any Jaeger's matching

M = M B ∪ M R , | M B | = | M R |.
See, for instance, [START_REF] Fouquet | On linear arboricity of cubic graphs[END_REF] and [START_REF] Fouquet | On isomorphic linear partition in cubic graphs[END_REF] for some properties of these graphs.

In this subsection we determine the values of j and k for which a graph F S(j, k) is a Jaeger's graph.

Lemma 22 If G = F S(j, k) is a Jaeger's graph (with k ≥ 3) and M = M B ∪ M R is a Jaeger's matching of G then M is a perfect matching of type 1.
Proof Suppose that M is of type 2 and suppose without loss of generality that there are two edges of M between C 0 and C 1 , for instance x 0 x 1 and y 0 y 1 . Then C 0 ∩ M = {t 0 z 0 } and C 1 ∩ M = {t 1 z 1 }. Suppose that x 0 x 1 and y 0 y 1 belong to M B . Since M B is a strong matching, t 0 z 0 and t 1 z 1 belong to M \ M B = M R . This is impossible because M R is also a strong matching. By symmetry there are no two edges of M R between C 0 and C 1 . Then there is one edge of M B between C 0 and C 1 , x 0 x 1 for instance, and one edge of M R between C 0 and C 1 , y 0 y 1 for instance. Since M B and M R are strong matchings, there is no edge of M in C 0 ∪ C 1 , a contradiction. Thus, M is a perfect matching of type 1.

Lemma 23 If G = F S(j, k) is a Jaeger's graph (with k ≥ 3) then either (j = 1 and k ≡ 1 or 2 (mod 3)) or (j = 3 and k ≡ 0 (mod 3)).

Proof Let M = M B ∪ M R be a Jaeger's matching of G. By Lemma 22 M is a perfect matching of type 1. Suppose without loss of generality that M B ∩ E(C 0 ) = {x 0 t 0 }. Since M B is a strong matching there is no edge of M B between C 0 and C 1 . Suppose, without loss of generality, that the edge in M R joining C 0 to C 1 is y 0 y 1 . Consider the claws C 0 , C 1 and C 2 . Since M B and M R are strong matchings, we can see that the choices of x 0 t 0 ∈ M B and y 0 y 1 ∈ M R fixes the positions of the other edges of M B and M R . More precisely, {t 1 z 1 , y 2 t 2 } ⊂ M B and {x 1 x 2 , z 2 z ′ 3 } ⊂ M R . This unique configuration is depicted in Figure 5. If k ≥ 4 then we see that z 2 z 3 ∈ M R , x 3 t 3 ∈ M B , and y 3 y ′ 4 ∈ M R . So, the local situation in C 3 is similar to that in C 0 , and we can see that is a unique Jaeger's matching M = M B ∪ M R such that x 0 t 0 ∈ M B and y 0 y 1 ∈ M R in the graph F S(j, k). We have to verify the coherence of the connections between the claws C k-1 and C 0 . We note that M B = M ∩ (∪ i=k-1 i=0 E(C i )) and M R is a strong matching included in the 2-factor induced by ∪ i=k-1 i=0 {V (C i ) \ {t i }}.

Case 1: k = 3p with p ≥ 1.

We have

x 0 t 0 ∈ M B , y k-1 t k-1 ∈ M B , x k-2 x k-1 ∈ M R and z ′ k-1 z 0 = z k-1 z ′ 0 ∈ M R (that is, z k-1 z 0 ∈ M R )
. Thus, z k-1 z 0 , y k-1 y 0 and x k-1 x 0 are edges of F S(j, 3p) and we must have j = 3.

Case 2: k = 3p + 1 with p ≥ 1. We have

x 0 t 0 ∈ M B , x k-1 t k-1 ∈ M B (that is, x k-1 x 0 / ∈ E(G)), z k-2 z k-1 ∈ M R and z ′ k-1 z 0 = y k-1 y ′ 0 ∈ M R (that is, y k-1 z 0 ∈ M R )
. Thus, y k-1 z 0 , x k-1 y 0 and z k-1 x 0 are edges of F S(j, 3p + 1) and we must have j = 1.

Case 3: k = 3p + 2 with p ≥ 1. We have

x 0 t 0 ∈ M B , z k-1 t k-1 ∈ M B , y k-2 y k-1 ∈ M R and z ′ k-1 z 0 = x k-1 x ′ 0 ∈ M R (that is x k-1 z 0 ∈ M R )
. Thus, x k-1 z 0 , y k-1 x 0 and z k-1 y 0 are edges of F S(j, 3p + 2) and we must have j = 1.

Remark 24 It follows from Lemma 23 that for every k ≥ 3 the graph F S(2, k) is not a Jaeger's graph. This is obvious when k is odd, since the flower snarks have chromatic index 4.

Then, we obtain the following.

Theorem 25 For j ∈ {1, 2, 3} and k ≥ 2, the graph G = F S(j, k) is a Jaeger's graph if and only if 5 2-factor hamiltonian cubic graphs Recall that a simple graph of maximum degree d > 1 with edge chromatic number equal to d is said to be a Class 1 graph. For any d-regular simple graph (with d > 1) of even order and of Class 1, for any minimum edgecolouring of such a graph, the set of edges having a given colour is a perfect matching (or 1-factor). Such a regular graph is also called a 1-factorable graph. A Class 1 d-regular graph of even order is strongly hamiltonian or perfectly 1-factorable (or is a Hamilton graph in the Kotzig's terminology [START_REF] Kotzig | Balanced colourings and the four colour conjecture[END_REF]) if it has an edge colouring such that the union of any two colours is a hamiltonian cycle. Such an edge colouring is said to be a Hamilton decomposition in the Kotzig's terminology. In [START_REF] Kotzig | Construction for hamiltonian graphs of degree three (in russian)[END_REF] by using two operations ρ and π (described also in [START_REF] Kotzig | Balanced colourings and the four colour conjecture[END_REF]) and starting from the θ-graph (two vertices joined by three parallel edges) he obtains all strongly hamiltonian cubic graphs, but these operations does not always preserve planarity. In his paper [START_REF] Kotzig | Balanced colourings and the four colour conjecture[END_REF] he describes a method for constructing planar strongly hamiltonian cubic graphs and he deals with the relation between strongly hamiltonian cubic graphs and 4-regular graphs which can be decomposed into two hamiltonian cycles. See also [START_REF] Kotzig | Quelques problmes ouverts concernant les graphes fortement hamiltoniens[END_REF] and a recent work on strongly hamiltonian cubic graphs [START_REF] Bonvicini | On perfectly one-factorable cubic graphs[END_REF] in which the authors give a new construction of strongly hamiltonian graphs.

A Class 1 regular graph such that every edge colouring is a Hamilton decomposition is called a pure Hamilton graph by Kotzig [START_REF] Kotzig | Balanced colourings and the four colour conjecture[END_REF]. Note that K 4 is a pure Hamilton graph and every cubic graph obtained from K 4 by a sequence of triangular extensions is also a pure Hamilton cubic graph. In the paper [START_REF] Kotzig | Balanced colourings and the four colour conjecture[END_REF] of Kotzig, a consequence of his Theorem 9 (p.77) concerning pure Hamilton graphs is that the family of pure Hamilton graphs that he exhibits is precisely the family obtained from K 4 by triangular extensions. Are there others pure Hamilton cubic graphs ? The answer is "yes".

We remark that 2-factor hamiltonian cubic graphs defined above (see Definition 16) are pure Hamilton graphs (in the Kotzig's sense) but the converse is false because K 4 is 2-factor hamiltonian and the pure Hamilton cubic graph on 6 vertices obtained from K 4 by a triangular extension (denoted by P R 3 ) is not 2-factor hamiltonian. Observe that the operation of triangular extension preserves the property "pure Hamilton", but does not preserve the property "2-factor hamiltonian". The Heawood graph H 0 (on 14 vertices) is pure Hamiltonian, more precisely it is 2-factor hamiltonian (see [START_REF] Funk | On minimally one-factorable r-regular bipartite graphs[END_REF] Proposition 1.1 and Remark 2.7). Then, the graphs obtained from the Heawood graph H 0 by triangular extensions are also pure Hamilton graphs.

A minimally 1-factorable graph G is defined by Labbate and Funk [START_REF] Funk | On minimally one-factorable r-regular bipartite graphs[END_REF] as a Class 1 regular graph of even order such that every perfect matching of G is contained in exactly one 1-factorization of G. In their article they study bipartite minimally 1-factorable graphs and prove that such a graph G has necessarily a degree d ≤ 3. If G is a minimally 1-factorable cubic graph then the complementary 2-factor of any perfect matching has a unique decomposition into two perfect matchings, therefore this 2-factor is a hamiltonian cycle of G, that is G is 2-factor hamiltonian. Conversely it is easy to see that any 2-factor hamiltonian cubic graph is minimally 1-factorable. The complete bipartite graph K 3,3 and the Heawood graph H 0 are examples of 2-factor hamiltonian bipartite graph given by Labbate and Funk. Starting from H 0 , from K 1,3 and from three copies of any tree of maximum degree 3 and using three operations called amalgamations the authors exhibit an infinite family of bipartite 2-factor hamiltonian cubic graphs, namely the poly -HB -R -R 2 graphs (see [START_REF] Funk | On minimally one-factorable r-regular bipartite graphs[END_REF] for more details). Except H 0 , these graphs are exactly cyclically 3-edge connected. Others structural results about 2-factor hamiltonian bipartite cubic graph are obtained in [START_REF] Labbate | On 3-cut reductions of minimally 1-factorable cubic bigraphs[END_REF], [START_REF] Labbate | Characterizing minimally 1-factorable r-regular bipartite graphs[END_REF]. These results have been completed and a simple method to generate 2-factor hamiltonian bipartite cubic graphs was given in [START_REF] Funk | 2-factor hamiltonian graphs[END_REF].

Proposition 27 (Lemma 3.3, [START_REF] Funk | 2-factor hamiltonian graphs[END_REF]) Let G be a 2-factor hamiltonian bipartite cubic graph. Then G is 3-connected and | V (G) |≡ 2 (mod 4).

Let G 1 and G 2 be disjoint cubic graphs, x ∈ v(G 1 ), y ∈ v(G 2 ). Let x 1 , x 2 , x 3 (respectively y 1 , y 2 , y 3 ) be the neighbours of x in G 1 (respectively, of y in G 2 ). The cubic graph G such that V (G) = (V (G 1 )\{x})∪(V (G 2 )\{y}) and E(G) = (E(G 1 )\{x 1 x, x 2 x, x 3 x})∪(E(G 2 )\{y 1 y, y 2 y, y 3 y})∪{x 1 y 1 , x 2 y 2 , x 3 y 3 } is said to be a star product and G is denoted by (G 1 , x) * (G 2 , y). Since {x 1 y 1 , x 2 y 2 , x 3 y 3 } is a cyclic edge-cut of G, a star product of two 3-connected cubic graphs has cyclic edge-connectivity 3.

Proposition 28 (Proposition 3.1, [START_REF] Funk | 2-factor hamiltonian graphs[END_REF]) If a bipartite cubic graph G can be represented as a star product G = (G 1 , x) * (G 2 , y), then G is 2-factor hamiltonian if and only if G 1 and G 2 are 2-factor hamiltonian.

Then, taking iterated star products of K 3,3 and the Heawood graph H 0 an infinite family of 2-factor hamiltonian cubic graphs is obtained. These graphs (except K 3,3 and H 0 ) are exactly cyclically 3-edge connected. In [START_REF] Funk | 2-factor hamiltonian graphs[END_REF] the authors conjecture that the process is complete.

Conjecture 29 (Funk, Jackson, Labbate, Sheehan (2003) [START_REF] Funk | 2-factor hamiltonian graphs[END_REF]) Let G be a bipartite 2-factor hamiltonian cubic graph. Then G can be obtained from K 3,3 and the Heawood graph H 0 by repeated star products.

The authors precise that a smallest counterexample to Conjecture 29 is a cyclically 4-edge connected cubic graph of girth at least 6, and that to show this result it would suffice to prove that H 0 is the only 2-factor hamiltonian 21 cyclically 4-edge connected bipartite cubic graph of girth at least 6. Note that some results have been generalized in [START_REF] Abreu | Pseudo 2factor isomorphic regular bipartite graphs[END_REF].

To conclude, we may ask what happens for non bipartite 2-factor hamiltonian cubic graphs. Recall that K 4 and F S(1, 3) (the "Triplex Graph" of Robertson, Seymour and Thomas [START_REF] Robertson | Excluded minor in cubic graphs[END_REF]) are 2-factor hamiltonian cubic graphs. By Corollary 17 the graphs F S(j, k) with k odd and j = 1 or 3 introduced in this paper form a new infinite family of non bipartite 2-factor hamiltonian cubic graphs. We remark that they are cyclically 6-edge connected. Can we generate others families of non bipartite 2-factor hamiltonian cubic graphs ? Since P R 3 (the cubic graph on 6 vertices obtained from K 4 by a triangular extension) is not 2-factor hamiltonian and P R 3 = K 4 * K 4 , the star product operation is surely not a possible tool.

Fig. 1 .

 1 Fig. 1. Four consecutive claws

Fig. 2 .

 2 Fig. 2. Local transformation of type 1

Fig. 3 .

 3 Fig. 3. Local transformation of type 2

Fig. 4 .

 4 Fig. 4. Local transformation of type 3

  l(Γ 1 ) and l(Γ (r)2 ) = l(Γ 2 ) and such that C i+2⌊ h 2 ⌋ and C i+h+1 are Γ

Lemma 19

 19 Let M be a perfect matching of type 2.0 of G = F S(j, 2p) (with p ≥ 2) such that the 2-factor G\M is a hamiltonian cycle. Then the forbidden extremal configurations are XY , Y Z and ZX for F S(1, 2p), XX, Y Z and ZY for F S(2, 2p), and XX, Y Y and ZZ for F S(3, 2p).

Fig. 5 .

 5 Fig. 5. Strong matchings M B (bold edges) and M R (dashed edges)

Preprint submitted to Elsevier

-major claws and for i inZ k \ {j, j + 1} C i is Γ ′ 2 -major (respectively Γ ′ 1 -major) if and only if C i is Γ 2 -major (respectively

Assume moreover that among the perfect matchings of type 1 of G such that the 2-factor G \ M is composed of two cycles, M has been chosen in such a way that the length of the longest cycle Γ 2 is as great as possible. By Lemma 12 there exists at most one Γ 1 -major claw.

Case 1: There exists one Γ 1 -major claw.

Without loss of generality, suppose that C 0 is intersected by Γ 1 in {y 0 , t 0 , x 0 } and that y ′ k-1 y 0 belongs to Γ 1 . Since for every i = 0 the claw C i is Γ 2 -major, Γ 1 contains the vertices y 0 , t 0 , x 0 , x 1 , x 2 , . . . , x k-1 .

• If k = 2r + 1 with r ≥ 1 then Γ 2 contains the path

Case 2: There is no Γ 1 -major claw.

Suppose that x 0 belongs to Γ 1 . Then, Γ 1 contains x 0 , x 1 , ..., x k-1 .

• If k = 2r + 1 with r ≥ 1 then Γ 2 contains the path y 0 t 0 z 0 z 1 t 1 y 1 y 2 ...z 2r-1 t 2r-1 y 2r-1 y 2r t 2r z 2r . Thus, x 0 x k-1 , y 0 z k-1 and z 0 y k-1 are edges of G and the set ∪ i=k-1 i=0 {C i \ {t i }} induces two cycles,that is to say j = 2 and G = F S(2, k).

• If k = 2r + 2 with r ≥ 1 then Γ 2 contains the path

Definition 16 A cubic graph G is said to be 2-factor hamiltonian [START_REF] Funk | 2-factor hamiltonian graphs[END_REF] if every 2-factor of G is a hamiltonian cycle (or equivalently, if for every perfect Theorem 20 The numbers µ ′ 2 (j, 2p) of perfect matchings of type 2 complementary to hamiltonian cycles in F S(j, 2p) (j ∈ {1, 2, 3}) are given by: Clearly, the number of words of length p having no two consecutive identical letters and beginning by α is 2 p-1 . Then a p αβ + b p αβ = 2 p-1 . The deletion of the last β of a word in B p αβ gives a word in A p-1 αβ and the addition of β to the right of a word in A p-1 αβ gives a word in B p αβ .

Thus b p αβ = a p-1 αβ and for every p ≥ 3 a p αβ = 2 p-1a p-1 αβ . We note that a 2 αβ = 2 if α = β, and a 2 αβ = 1 if α = β. If α = β we have to solve the recurrent sequence : u 2 = 2 and u p = 2 p-1u p-1 for p ≥ 3. If α = β we have to solve the recurrent sequence : v 2 = 1 and v p = 2 p-1 -v p-1 for p ≥ 3. Then we obtain u p = 2 3 (2 p-1 + (-1) p ) and v p = 1 3 (2 p + (-1) p+1 ) for p ≥ 2.

By Lemma 19

) we obtain the announced results.

Remark 21 We see that µ ′ 2 (j, 2p) ≃ 2 p+1 and this is to compare with the number µ 2 (j, 2p) = 2 × 3 p of perfect matchings of type 2 in F S(j, 2p) (see backward in Section 2). either k ≡ 1 or 2 (mod 3) and j = 1, or k ≡ 0 (mod 3) and j = 3.

Moreover, F S(1, 2) has 3 Jaeger's matchings and for k ≥ 3 a Jaeger's graph G = F S(j, k) has exactly 6 Jaeger's matchings.

Proof For k = 2 we remark that F S(1, 2) (that is the cube) has exactly three distinct Jaeger's matchings M 1 , M 2 and M 3 . Following our notations:

For k ≥ 3, by Lemma 23, condition ( * ) (j = 1 and k ≡ 1 or 2 (mod 3)) or (j = 3 and k ≡ 0 (mod 3)) is a necessary condition for F S(j, k) to be a Jaeger's graph.

Consider the function Φ

Define similarly Φ X,Z and Φ Y,Z . For j = 1 or 3 these functions are automorphisms of F S(j, k). Thus, the process described in the proof of Lemma 23 is a constructive process of all Jaeger's matchings in a graph F S(j, k) (with k ≥ 3) verifying condition (*).

We remark that for any choice of an edge e of C 0 to be in M B there are two distinct possible choices for an edge f between C 0 and C 1 to be in M R , and such a pair {e, f } corresponds exactly to one Jaeger's matching. Then, a Jaeger's graph F S(j, k) (with k ≥ 3) has exactly 6 Jaeger's matchings.

Remark 26

The Berge-Fulkerson Conjecture states that if G is a bridgeless cubic graph, then there exist six perfect matchings M 1 , . . . , M 6 of G (not necessarily distinct) with the property that every edge of G is contained in exactly two of M 1 , . . . , M 6 (this conjecture is attributed to Berge in [START_REF] Seymour | On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte[END_REF] but appears in [START_REF] Fulkerson | Blocking and anti-blocking pairs of polyhedra[END_REF]). Using each colour of a cubic 3-edge colourable graph twice, we see that such a graph verifies the Berge-Fulkerson Conjecture. Very few is known about this conjecture except that it holds for the Petersen graph and for cubic 3-edge colourable graphs. So, Berge-Fulkerson Conjecture holds for Jaeger's graphs, but generally we do not know if we can find six distinct perfect matchings. We remark that if F S(j, k), with k ≥ 3, is a Jaeger's graph then its six Jaeger's matchings are such that every edge is contained in exactly two of them.