Lisa Chauvet

Flore Gubert

Sandrine Mesplé-Somps

Are Remittances More Effective Than Aid To Reduce Child Mortality? An Empirical Assessment using Inter and Intra-Country Data

Keywords: Child Mortality, Remittances, International Migration, Foreign Aid, Low and Middle Income Countries

This paper analyzes the respective impact of aid, remittances and medical brain drain on child mortality using panel and cross-country quintile-level data on respectively 84 and 46 developing countries. Our results show that remittances reduce child mortality and that the impact of health aid is non-linear, suggesting that health aid is more effective in the poorest countries. By contrast, medical brain drain is found to have a harmful impact on child mortality. Last, remittances seem to be more effective in reducing mortality for children belonging to the richest households, whereas neither pro-poor nor anti-poor effect is found for health aid.

Introduction

Poverty reduction is increasingly put forward as the main objective of official development assistance (ODA) to developing countries. Both national leaders and the international community have indeed pledged to meet by 2015 a series of poverty reduction targets known as the Millennium Development Goals (MDGs). i The pursuit of these MDGs, however, calls for a substantial increase in the provision of basic services to the population of the developing world that ODA alone cannot accomplish. The Monterrey Consensus following the 2002 United Nations International Conference on Financing for Development has thus highlighted The objective of this paper is to analyze the respective impact of aid and remittances on human development as measured by infant or child mortality rates. To what extent do aid and remittances contribute to reduce child mortality disparities between countries? What about their respective impact on child mortality disparities within countries? How do remittances compare to aid when migration costs, namely brain drain, are accounted for? Here is the list of questions this paper seeks to answer.

We choose basic indicators of human welfare instead of a monetary measure of poverty for three reasons. First, comparable cross-country data on monetary poverty over time are extremely scarce. Second, child health figures prominently in the list of MDGs. Donors have indeed committed themselves to reduce by two thirds the mortality rate among children under five (Goal 4). To this end, they have devoted an increasing share of official aid to the health sector. There is however very few empirical evidence on the effectiveness of increased aid flows on health outcomes in recipient countries. Whether donors are right to prioritize the health sector in the intra-country allocation of aid is thus an unanswered question that needs to be addressed. Third, the relationship between migration and health is increasingly emphasized in the microeconomic literature and donor agencies regularly report the success of most of their projects and programs in the health sector. It is therefore interesting to investigate whether successful health interventions from the donors' or the migrants' side at the microlevel translate into improved health outcomes at the macro-level and whether Paul Mosley's micro-macro paradox also applies to the health sector.

Our empirical strategy relies on two econometric exercises. We first examine the respective impact of aid, remittances and medical brain drain on child health indicators using panel data on a sample of 84 developing countries. This first econometric exercise raises substantial methodological issues such as measurement errors and endogeneity of our core explanatory variables, which we try to address in the paper. Keeping in mind the inherent weaknesses of this macro approach, our econometric results suggest that both remittances and health aid significantly reduce infant and child mortality rates. The impact of health aid is non-linear, though, suggesting that aid to the health sector is likely to be more effective in the poorest countries. By contrast, medical brain drain, as measured by the expatriation rate of physicians, is found to have a harmful impact on health outcomes.

We then assess the respective effectiveness of aid and remittances in reducing mortality disparities within countries using cross-country quintile-level data. Results of this second econometric exercise show that remittances are effective in reducing infant and child mortality rates, but much more so for the richest quintiles. This result suggests that while remittances contribute to improve mean health outcomes in recipient countries, they tend to increase intra-country health inequality. The impact of health aid, by contrast, is hardly ever significant in our within-country regressions.

The remainder of the paper is organized as follows. Section 2 reviews the macro-literature on the poverty and inequality impact of aid and remittances. The data, method of estimation and results of the cross-country and intra-country analyses are presented in Section 3 and 4 respectively. Section 5 offers concluding remarks and discusses the policy implications of our findings.

The Impact of Aid and Remittances on Poverty and Inequality: A Literature Review

Poverty and Inequality Impact of Aid

From the early 1960s to the mid 1990s, the literature investigating the macro-impact of aid almost exclusively focused on the link between aid and growth. The emerging picture from this literature is that aid can enhance growth, but that this result is very fragile and highly dependent on the choice of data, sample composition and estimation methods [START_REF] Roodman | Macro Aid Effectiveness Research: A Guide for the Perplexed, Center for Global Development[END_REF]. The adoption of the United Nations Millennium Declaration by UN members in 2000 and the obligation taken up by donors to financially support developing countries' efforts to achieve the eight Millennium Development Goals by 2015 have progressively shifted the focus from the aid-growth nexus to the relationship between aid flows and welfare or poverty indicators.

The few existing studies belonging to this strand of the literature have adopted quite standard cross-country growth regression approaches, and replaced growth with an indicator of welfare or poverty as the dependent variable (see, e.g., [START_REF] Boone | Politics and the Effectiveness of Foreign Aid[END_REF]Mosley, Hudson & Verschoor, 2004;[START_REF] Gomanee | Aid, Government Expenditure, and Aggregate Welfare[END_REF][START_REF] Gomanee | Aid, Public Spending and Human Welfare: Evidence from Quantile Regressions[END_REF]. Since comparable cross-country data on poverty over time are extremely scarce, most studies have concentrated on the effectiveness of aid in improving human development indicators such as infant or under-five mortality rate, life expectancy or primary schooling. In a famous paper, [START_REF] Boone | Politics and the Effectiveness of Foreign Aid[END_REF] finds no evidence that aid succeeds in improving human development indicators in recipient countries. While aid could reduce infant mortality either through an increase in private consumption or through greater provision of public services to the poor, his results suggest that aid increases the size of recipient governments, but that it has no impact on basic measures of human indicators. Boone's paper has been much criticized on two grounds. First, some authors have argued that the welfare impact of aid is not direct but goes through its impact on the amount of government spending allocated to social areas. Mosley, Hudson and Verschoor (2004) estimate a system of three equations with poverty, aid and propoor expenditure as their dependent variables. They find that aid is associated with higher levels of pro-poor spending, and that such spending is associated with lower levels of headcount poverty. Aid is also found to increase health spending which in turn decreases infant mortality. [START_REF] Gomanee | Aid, Public Spending and Human Welfare: Evidence from Quantile Regressions[END_REF] reach the same type of conclusion using quantile regressions. In a companion paper, however, [START_REF] Gomanee | Aid, Government Expenditure, and Aggregate Welfare[END_REF] find evidence that aid improves welfare indicators and this effect is predominantly through direct impacts. Other authors opposed to Boone's conclusions have argued that while it may be true that aggregate aid has not impact on health, particular types of aid among which health aid are effective in improving human development indicators (see, e.g., [START_REF] Masud | Does Foreign Aid Reduce Poverty? Empirical Evidence from Nongovernmental and Bilateral Aid, IMF Working Paper 05/100[END_REF]Dreher, Nunnenkamp & Thiele, 2006;Michaelowa & Weber, 2007;[START_REF] Mishra | Health Aid and Infant Mortality. IMF Working Paper 07[END_REF]. [START_REF] Mishra | Health Aid and Infant Mortality. IMF Working Paper 07[END_REF] in particular rely on a large dataset covering 118 countries over the 1973-2004 period to measure the effect of health aid on infant mortality. They find that increased health aid is associated with a significant reduction in infant mortality. The estimated effect of health aid is small, however, since doubling health aid within a country would reduce infant mortality in the next five-year period by only 2%.

As an additional result, they do not find any significant impact of overall aid. [START_REF] Masud | Does Foreign Aid Reduce Poverty? Empirical Evidence from Nongovernmental and Bilateral Aid, IMF Working Paper 05/100[END_REF] use data on nongovernmental (NGO) and bilateral aid and assess the effectiveness of these financial flows on two social indicators, namely infant mortality and adult illiteracy. Their underlying assumption is that NGOs intervene at the grassroots level and could be more effective to alleviate poverty than other types of aid. Using an unbalanced panel of 58 countries from 1990 to 2001, they find that health expenditure per capita reduces infant mortality as does greater NGO aid per capita. By contrast they do not find any significant impact of total bilateral aid on infant mortality.

Overall, as for the literature examining the aid impact on growth, the few existing papers examining the links between aid and aggregate welfare as measured by human development indicators do not allow to draw clear conclusions. Some papers find no impact at all while some other papers find evidence that aid decreases infant mortality rates, either directly or indirectly through higher levels of pro-poor spending. This lack of consensus in the macro literature is surprising given the number of successful health interventions financially supported by international assistance (Levine & the What Works Working Group, 2004).

Poverty and Inequality Impact of Remittances

Despite the increasing size of remittances, empirical macro-evidence on the poverty or inequality impact of these financial flows is even scarcer than that related to aid. Here again, this lack of evidence stems mainly from the absence of reliable and comparable cross-country data on several relevant variables and the absence of long-series that are required if use is to be made of the latest macroeconometric tools. Consequently, most of the empirical literature is confined largely to a few case-studies on villages or countries based on microeconometric data (see, e.g., [START_REF] Lachaud | Envois de fonds, inégalité et pauvreté au Burkina Faso[END_REF][START_REF] Leliveld | The Effects of Restrictive South African Migrant labor Policy on the Survival of Rural Households in Southern Africa: A Case Study from Rural Swaziland[END_REF][START_REF] Adams | Remittances and Poverty in Guatemala, World Bank Policy Research Working Paper[END_REF][START_REF] Adams | Remittances and Poverty in Ghana, World Bank Policy Research Working Paper[END_REF].

At the cross-national level, there are, to our knowledge, only four recent studies that have looked at the poverty impact of remittances [START_REF] Adams | Do International Migration and Remittances Reduce Poverty in Developing Countries?[END_REF]World Economic Outlook, 2005;Gupta, Patillo & Wagh, 2007;[START_REF] Acosta | What is the Impact of international Remittances on Poverty and Inequality in Latin America?[END_REF]. In addition, despite strong micro-evidence on a positive impact of remittances on education and health (see, e.g., [START_REF] Kanaiaupuni | Migradollars and Mortality: The Effects of Migration on Infant Survival in Mexico[END_REF][START_REF] Cox-Edwards | International Migration, Remittances and Schooling. Evidence from El Salvador[END_REF][START_REF] Hildebrandt | The effects of migration in child health in Mexico[END_REF][START_REF] Hildebrandt | The effects of migration in child health in Mexico[END_REF]Mansuri, 2007), no one has ever investigated the impact of remittances on human development indicators at a macroeconomic level. [START_REF] Adams | Do International Migration and Remittances Reduce Poverty in Developing Countries?[END_REF] use a panel of 71 low-income and middle-income countries to test whether countries producing more international migration or receiving more international remittances have less poverty.

After instrumenting for the potential endogeneity of remittances, they find that a 10% increase in per capita official remittances leads to a 3.5% decline in the share of people living in poverty. Using a broader sample of 101 countries, World Economic Outlook (2005) provides further evidence that remittances have an effect on poverty, even though this effect is rather small: on average, a 2.5 percentage point increase in the remittances to GDP ratio is associated with less than a 0.5 percentage point decrease in poverty. As argued by the authors, this (disappointing) result could be due to the fact that average income and inequality are included as regressors next to remittances. Since these variables are themselves likely to be influenced by remittances, the true impact of remittances on poverty could actually be larger.

Using a sample of 76 countries in which Sub-Saharan countries are substantially represented, Gupta, Patillo and Wagh (2007) adopt the same methodology as that of [START_REF] Adams | Do International Migration and Remittances Reduce Poverty in Developing Countries?[END_REF] and model poverty as a function of mean income, some measures of income distribution and remittances. Their findings indicate that a 10% rise in remittances is associated with about a 1% fall in the incidence of poverty. Last, [START_REF] Acosta | What is the Impact of international Remittances on Poverty and Inequality in Latin America?[END_REF] use both cross-country and household survey data to assess the impact of remittances on growth, poverty and inequality in Latin America. Their crosscountry estimates suggest that remittances have a positive and statistically significant effect on growth on average, but that they tend to increase the level of income inequality. The effect for the average Latin American country is different, however, since an increase in remittances tends to be associated with lower levels of inequality. Turning to their micro-econometric analyses, their findings suggest that the poverty and inequality impact of remittances strongly varies across Latin American countries, depending on whether recipients are concentrated at the bottom or at the top of the distribution of non-remittances income.

In what follows, our aim is to provide additional insights into the question of whether aid and remittances as sources of external financing are effective in improving child health outcomes.

III. The Impact of Aid and Remittances on Child Mortality: a Cross-Country Analysis

The aim of this section is to assess the impact of health aid and remittances on child mortality, using panel data on a sample of 84 countries from 1987 to 2004 (Table A1 in Appendix provides the full list of countries included in the sample). After a brief presentation of the empirical strategy and description of the data, results of our baseline model are discussed. The analysis is then pushed further by testing for non-linearities in the aid-health relationship, and investigating the impact of the medical brain drain on health outcomes.

Model and Data

To explore the relative impacts of aid and migration on child mortality, we estimate a model of the following form:

, , ( 1, 3) ,( 1, 3) ,( 1, 3)
                  (1)
Mortality i,t is either the under-five or the infant mortality rate from the World Development Indicators (WDI, 2006). Under-five mortality rate is the probability (per 1000) that a newborn baby will die before reaching the age of five, if subject to current age-specific mortality rates.

Infant mortality rate is the number of infants dying before reaching one year of age, per 1000 live births in a given year.

Since our dependent variables are bounded, we use a logarithmic transformation. To ease interpretation of our results and account for potential non-linearities, all our independent variables are also log-linearized.

We measure Health aid i,t using aid commitments to the health sector as defined by the Country Reporting System (CRS) of the OECD. ii The main advantage of the CRS is to provide data on aid commitments with a high degree of disaggregation by purpose (sector). Its main disadvantage, though, is that the data is only reliable for recent years, as reflected in Figure 1 by the large underreporting of aid in the CRS data compared to those of the Development Assistance Committee (DAC). As noted by [START_REF] Mishra | Health Aid and Infant Mortality. IMF Working Paper 07[END_REF], the extent of underreporting varies by sector, donor and time period and therefore missing data are omitted from the sample rather than considered as zero health aid. We also restrict our sample to relatively recent observations, starting in the mid-eighties. Figure 1 also shows that the share of aid commitments to the health sector has gradually increased since the eighties: at that time health aid was around 2% of total commitments, while it is now around 5%. This increase in health aid reflects the switch in donors' priorities -notably from aid to infrastructures to aid to social sectors -which goes along with the adoption of the Millennium Development Goals. Health aid i,t is expressed in per capita constant terms (using DAC deflator).

Remittances i,t are defined as current transfers by migrants who are employed for more than a year in another country in which they are considered residents (WDI, 2006). We use the same deflator for remittances as for aid in order to transform this variable into per capita constant terms. As shown by Figure 1, workers' remittances have been increasing both in absolute and in relative terms since the mid-eighties: while they only accounted for around 60% of total aid commitments in the eighties, they have represented more than 200% of aid commitments since 2000, reflecting the growing importance of this financing for developing economies.

This growth in remittances is partly due to the rise in the number of international migrants worldwide. But it also indicates that over the last years people have been shifting from informal to formal channels to send funds. This potentially important source of measurement error is addressed in our econometric analysis. First, we include a time trend,  t , in our list of regressors in order to capture the increasing trend in remittances. Second we control for unobservable heterogeneity among countries ( i ) hoping to account for some omitted variables that could explain simultaneously the increasing trend in remittances and the decreasing trend in child and infant mortality. Finally, this latter issue is also tackled through the instrumentation of remittances (see 3.2).

[Figure 1 about here]

Following the existing literature on cross-country determinants of child health outcomes, equation ( 1) controls for a set of relevant socioeconomic variables, X i,t . Since [START_REF] Ravallion | Human Development in Poor Countries: On the Role of Private Incomes and Public Services[END_REF], and [START_REF] Pritchett | Wealthier is Healthier[END_REF], a consensus has emerged concerning the negative relationship between child mortality and national income. Female education -measured either by educational attainment or illiteracy rates -has also been shown to be negatively correlated with child mortality [START_REF] Filmer | The Impact of Public Spending on Health: Does Money Matter?[END_REF]Anand & Bärnighausen, 2004;[START_REF] Fay | Achieving Child-Health-Related Millenium Development Goals: The Role of Infrastructure[END_REF][START_REF] Mcguire | Basic Health Care Provision and Under-5 Mortality: A Cross-National Study of Developing Countries[END_REF][START_REF] Ravallion | Achieving Child-Health-Related Millenium Development Goals: The Role of Infrastructure -A Comment[END_REF]. We measure income per capita in PPP constant terms (WDI, 2006) and female education using the average years of schooling of the female population aged 15 and over [START_REF] Barro | International Data on Educational Attainment: Updates and Implications[END_REF]. Anand and Bärnighausen (2004) show that the density of human resources in the health sector is significantly correlated with child health indicators. We proxy human resources for health with the number of physicians (per 1000) provided by Bhargava and Docquier (2008).

Other cross-country determinants of child health have been identified in the literature, such as the size of the population [START_REF] Mishra | Health Aid and Infant Mortality. IMF Working Paper 07[END_REF], the share of urban population [START_REF] Masud | Does Foreign Aid Reduce Poverty? Empirical Evidence from Nongovernmental and Bilateral Aid, IMF Working Paper 05/100[END_REF][START_REF] Fay | Achieving Child-Health-Related Millenium Development Goals: The Role of Infrastructure[END_REF][START_REF] Ravallion | Achieving Child-Health-Related Millenium Development Goals: The Role of Infrastructure -A Comment[END_REF], inequality indicators [START_REF] Filmer | The Impact of Public Spending on Health: Does Money Matter?[END_REF][START_REF] Mcguire | Basic Health Care Provision and Under-5 Mortality: A Cross-National Study of Developing Countries[END_REF][START_REF] Fay | Achieving Child-Health-Related Millenium Development Goals: The Role of Infrastructure[END_REF]Ravallion, 2007, Cornia, Rosignoli & Tiberti2008) and poverty rates (Anand & Bärnighausen, 2004), but none were significant in our analysis. Two other variables -ethnic fragmentation and whether the country is predominantly Muslim -were also significantly correlated with infant mortality in Filmer and[START_REF] Filmer | The Impact of Public Spending on Health: Does Money Matter?[END_REF][START_REF] Mcguire | Basic Health Care Provision and Under-5 Mortality: A Cross-National Study of Developing Countries[END_REF]. Both are time invariant and could not be introduced in our fixed effects analysis. iii

Equation ( 1) is estimated on a panel of 84 developing countries, among which 35 African countries, from 1987 to 2004 (the full list of countries included in the sample is provided in Table A1 in Appendix). Child health data is leaping every four or five years (1990, 1995, 2000 and 2004). The right-hand side variables are measured in logarithm and are averaged over three years from t-1 to t-3. This is true for all variables but education, because [START_REF] Barro | International Data on Educational Attainment: Updates and Implications[END_REF] database on education is also leaping every five years and is available only up to 2000. We therefore use the 2000 level of education to explain 2004 mortality, etc. We control for unobservable heterogeneity with country fixed effects,  i . We also include time dummies

 t .

Endogeneity of Aid, Remittances and Income

There are two potential sources of endogeneity of aid and remittances to child and infant mortality rates. First, aid and remittances are given purposively and both donors and migrants are likely to take into account the situation of child health when allocating their flows. Even if aid is determined at the macro-level and remittances are determined at the micro-level both are likely to reflect, to some extent, the chances of survival of children. Second, there could be some omitted variables which affect aid, remittances and child mortality. For example, natural disasters are likely to induce an increase in both child mortality rates and aid and remittances inflows.

We therefore instrument health aid and workers' remittances. iv As instruments for health aid, we use a set of variables that capture historical and cultural relationships between developing countries and donor/destination countries. These variables are more likely to be exogenous to child mortality than any recipient/origin countries' own characteristics. More specifically, we use the total aid budget of the five main donors weighted by cultural distance between receiving and donor/destination countries (whether they have the same religion) and by geographic distance (distance to Washington, Brussels and Tokyo). v As an instrument for health aid, we also use health aid lagged twice. Workers' remittances are instrumented using the ratio of broad money supply (M2) to GDP, as countries that are more financially developed have been found to receive larger remittances. Income per capita is also endogenous to child mortality [START_REF] Pritchett | Wealthier is Healthier[END_REF][START_REF] Filmer | The Impact of Public Spending on Health: Does Money Matter?[END_REF]. It is instrumented using twice lagged income per capita.

We also suspected education to be endogenous to health indicators. We tested this hypothesis.

It turned out that the exogeneity of education could not be rejected by our test, a result which can partly be explained by the fact that education in t-5 (or t-4) is used to explain health outcomes in t.

The excludability and relevance of our instruments being legitimate concerns here, tests for their validity (Sargan test of overidentification, test of underidentification, partial R squared)

have been systematically performed. vi

Estimation of the Baseline Model

Our estimation of the baseline model proceeds in three steps. Equation ( 1) is first estimated with simple OLS. We then introduce country fixed effects to take into account unobservable heterogeneity in our sample. Finally aid, remittances and income are instrumented using 2SLS including country fixed effects and time fixed effects. vii Instrumentation equations are provided in Table A2 in Appendix.

Regressions (1)-( 6) of Table 1 present the estimations of the baseline model when the dependent variable is either the under-five mortality rate or the infant mortality rate. Income per capita is highly significant and tends to decrease child mortality. The impact is quite strong: the coefficients of income in regressions ( 3) and ( 6) suggest that a one percent increase in income decreases child mortality by around 0.56 percent and infant mortality by around 0.49. The coefficients of income per capita are interestingly close to the coefficients found by [START_REF] Pritchett | Wealthier is Healthier[END_REF] in their IV estimations of infant mortality (around 0.3) using a different set of instruments. They are even closer for the fixed effect estimations (0.31 in Pritchett and Summers).

[Table 1 about here] Surprisingly, the number of physicians is not significant in Table 1 except in OLS estimations. When significant, it is negative, suggesting that more doctors imply lower child and infant mortality rates. Anand and Bärnighausen (2004) find a strong impact of doctor and nurse density on various health indicators, which in their case is more robust than in our regressions. Again, only in OLS estimations does female education have a significant impact on child and infant mortality rates. In Table 1, the negative impact of the time dummies -1990 is the omitted time dummy -reflects the decreasing trend in child and infant mortality rates over the last two decades. viii Finally aid and remittances both have a negative coefficient in regressions ( 1)-( 6), but contrary to [START_REF] Mishra | Health Aid and Infant Mortality. IMF Working Paper 07[END_REF], we find no significant impact of health aid, at this stage of our empirical analysis. By contrast, remittances are found to be strongly significant in most regressions, with the expected sign. When instrumented, the coefficient of remittances is multiplied by more than three: a one percent increase in remittances decreases child mortality by 0.12 percent and infant mortality by 0.10 percent.

Non-Linearities in the Aid-Health Relationship

As a next step to our analysis we explore in more detail the relationship between health aid and child health indicators. So far, we find no significant impact of health aid commitments.

However, a relative consensus has emerged in the literature regarding the fact that aggregate aid disbursements impact macro outcomes, such as economic growth, in a non-linear way. ix

Similarly, the impact of health aid on child mortality rates may be non-linear. This nonlinearity may be due to constrained absorptive capacity. A way to proxy constrained absorptive capacity in the health sector is through an interaction of health aid with income per capita: health aid would be relatively more effective in richer countries because they have a higher capacity to absorb aid. The interaction term between health aid and income is introduced into equation (1). It is instrumented using the same set of instruments as those for health aid and income per capita.

Results are presented in columns (1) and ( 2) of Table 2. The absorptive capacity hypothesis is not supported by our results. The impact of health aid is non-linear, but the non-linearity suggests that aid to the health sector is more effective in poorer countries. The threshold in income per capita corresponding to a switch to harmful aid is around 4,600US$ per capita (in PPP). Interestingly, most African countries belong to the decreasing part of the relationship between health aid and health outcomes.

It is worth noting that our baseline specification implies that we capture the direct effects of aid and remittances on child mortality. Another channel through which aid and remittances could impact health outcomes is through their impact on GDP per capita. Since GDP per capita is included among our set of regressors, this indirect impact is not taken into account.

Assuming that both remittances and aid tend to improve income, we therefore probably underestimate the impact of these sources of financing on child health indicators.

[Table 2 about here]

An alternative way of testing the constrained absorptive capacity hypothesis is to introduce the square of health aid into the regression. A quadratic relationship between health aid and child mortality would reflect marginal decreasing return to aid -after a given threshold of aid received, an additional dollar of aid is less effective, because the country no longer has the capacity to absorb it. Aid square is never significant when introduced in any of the regressions.

x Moreover, its sign is negative, as is that of health aid. The absence of a quadratic relationship between health aid and mortality confirms our previous finding of no absorptive capacity constraints of aid to the health sector. Health aid seems to be more effective where the prospects of improvements in mortality indicators are higher i.e. in poorer countries.

Finally, we have explored whether the results using health aid disbursements are similar to those with aid commitments. The CRS does not provide a reliable disaggregation of disbursements by sector. Thus we proxy aid disbursements to the health sector by weighting total net disbursements with the share of health commitments in total commitments. Results are available on request. They suggest that using health aid commitments or disbursements leads to very similar results. xi

Medical Brain-Drain

Our baseline model suggests that migrants' remittances help improving health outcomes such as child mortality rates in developing countries. We now turn to analyzing the counterpart of workers' remittances: the impact of the brain drain induced by migration on child and infant mortality rates in developing countries. More specifically, we explore the impact of the medical brain drain (MDB). Bhargava and Docquier (2008) provide a rich dataset containing information on the expatriation rate of physicians. We therefore introduce this latter variable into our model. It is averaged over three year sub-periods and transformed in logarithm. Child mortality rate and medical brain-drain may be correlated to omitted variables -such as the quality of health infrastructures. We therefore instrument this variable using the same set of instruments as for aid and remittances. xii Regressions (3) and ( 4) of Table 2 present the results when MBD is introduced into the analysis. The coefficient of MBD is highly significant and has the expected positive sign: a one percent increase in the rate of expatriation of physicians increases child and infant mortality rates by around 0.5%. The expatriation of human resources in the health sector has a direct harmful impact on health outcomes in developing countries. xiii Interestingly, the MBD does not really affect the impact of health aid on health outcomes. The threshold of income for which the relationship between aid and child health switches from negative to positive remains similar to that found in regressions (1) and (2) (between 4,600 and 4,800$), and the slope does not change a lot, suggesting that the health improving impact of aid is not altered when the MBD is taken into account.

Impact of total aid on child mortality

In this sub-section, we explore whether health outcomes are only influenced by aid to the health sector or whether the total amount of aid received also matters. There are different alternative routes through which aid may influence health outcomes such as child mortality rates. Education, notably education of mothers, has been shown to be a major determinant of child mortality rates. Thus, aid targeted to education may have an indirect impact on health outcomes. Roads and infrastructures linking rural areas to hospitals may also contribute to decreasing child mortality rates. The same is true for water supply, electricity. Hence aid to infrastructures may also indirectly impact child mortality rates. More generally, the fungibility of aid implies that even if aid is not targeted to the health sector, it relaxes the budget constraint of the government which can choose to spend more to the health sector than it would have without aid. Total aid may therefore be associated with lower child mortality rates.

We explore the impact of total aid in Table A3 in Appendix. More specifically, we distinguish between aid commitments to the health sector and other aid commitments. xiv Other aid is introduced in our baseline model (regressions 1 and 4) as well as in the specifications including the interaction term of aid with income (regressions 2 and 5) and the medical brain drain (regressions 3 and 6). In Table A3 other aid is not instrumented, but the results are very similar when we correct for the potential endogeneity of this variable -using the same set of instruments as for health aid. Table A3 suggests that if any, the impact of aid on health outcome in developing countries goes mainly through providing aid to the health sector. Total aid does not seem to have any impact in Table A3, whereas aid to the health sector and its interaction with income remain significant. The level of income for which the health aid starts to increase child mortality rates is between 4200 and 4800 US$. Introducing other aid into the estimations does not alter the impacts of remittances and of the medical brain drain.

IV. Intra-Country Empirical Assessment

In this section, we investigate the intra-country impact of aid and remittances on child and infant mortality rates, by analyzing to what extent these transfers are targeted or not to the poorest. The discussion begins with a description of the data and of the empirical strategy and ends with comments on our main findings.

Model and Data

We use the World Bank's comprehensive database of Health, Nutrition and Population (HNP) statistics that compile development indicators from Demographic and Health Survey (DHS) by asset quintiles xv within countries [START_REF] Gwatkin | Socio-Economic Differences in Health, Nutrition, and Population Within Developing Countries, An Overview[END_REF]. In what follows, we use an updated HNP database in which some countries have multiple year data (the list of countries and years is provided in Table A1 in Appendix). xvi This temporal dimension of the panel makes it possible to assess the impact of country-specific variables such as GDP per capita, aid, and remittances (that vary over time) in a model including country fixed effects. The dataset covers 46 developing countries among which 26 are in Africa, with five asset quintiles for each country-year, giving a total of 370 country-time-quintile observations.

Table 3 provides summary statistics on mortality rates. It suggests that there are strong mortality disparities within country that are correlated with asset inequality. Households belonging to the poorest asset quintile have the highest mean infant and child mortality rates.

For instance, child mortality is twice as high for the poorest quintile as for the richest one. It is also worth noting that the differences in mean health indicators between the poorest and richest quintiles (within variation) are always smaller than the ranges across countries within each quintile (between variation).

[Table 3 about here]

The intra-country model to be estimated is very similar to the cross-country model presented in the previous section in the sense that control variables are the same and are expressed in log-linear form. The baseline model may therefore be written as follows:

, , ,( 1, 3) ,( 1, 3) ,( 1, 3) Ln Ln Ln Ln

j i t i i t t i t t i t t Mortality X Health aid Remit               15 5 5 ,( 1, 3) ,( 1, 3) , , 2 2 2
*Ln *Ln jt j t j j i t t j j i t t j i t j j j q q Health aid q Remit

                   (2)
where q j are quintile dummy variables and  t are three time dummies (before 1997, between 1997 and 2000, and after 2000).

The set of control variables, X i,(t-1,t-3), includes GDP per capita in PPP constant terms, the number of physicians per 1,000 inhabitants, female education using the average years of schooling of the female population aged 15 and over and the medical brain drain. These variables are averaged over three years from t-1 to t-3 and are transformed in logarithm.

In order to test whether the impact of health aid and remittances differs between quintiles, LnHealth aid and LnRemit are interacted with quintile dummies q 2 to q 5 , the poorest quintile being the reference. The other control variables, such as GDP per capita, are not interacted with quintile dummies in order to limit the number of instruments when the IV specification is used. Finally, we control for country fixed effects as well as for quintile fixed effects and time trend by crossing quintile dummies and time dummies.

As in the cross-country analysis, the potential endogeneity of income, aid, remittances, and medical brain drain variables is controlled for using an IV specification. Instruments include lagged GDP per capita, ratio of lagged broad money supply (M2) to GDP, lagged health aid per capita, and total aid budgets of France, Japan, UK and USA in constant dollars weighted by geographic distance (distance to Washington, Brussels and Tokyo). We also include as instruments lagged GDP per capita and lagged health aid per capita interacted with quintiles q 2 to q 5 .

Estimation Results

Even though controlling for endogeneity and countries' unobserved heterogeneity is likely to provide more reliable results (as in regressions 3 and 6), Table 4 also presents the results of simple OLS and fixed-effects regressions.

[Table 4 about here]

As suggested by Table 4, the impact of our control variables is quite similar to the one found using our cross-country specification. GDP per capita tends to decrease infant and child mortality rates. The coefficient (IV estimator) of this variable suggests that an increase of 1 percent of GDP per capita decreases child and infant mortality by around 0.6 percent. As in the previous specification, the number of physicians per 1,000 inhabitants and female education are found to have no significant impact on mortality rates. This last result is not in accordance with [START_REF] Ravallion | Achieving Child-Health-Related Millenium Development Goals: The Role of Infrastructure -A Comment[END_REF] who finds a significant negative impact of female education whatever the child health indicators chosen (of which the infant and child mortality rates).

This lack of significant impact may result from the fact that the education variable we use is Turning to our variables of interest, our results suggest that migrants' remittances have a significant impact (remittances and remittances interacted with quintile dummies are jointly significant in all estimations). Their impact on mortality rates is found to be greater for the richest quintiles than for the poorest ones. This result suggests that remittances tend to increase health disparities within countries, and is in line with other microeconomic evidence which suggests that remittances may increase within-country inequality [START_REF] Adams | Remittances and Poverty in Ghana, World Bank Policy Research Working Paper[END_REF][START_REF] Barham | Migration, Remittances and Inequality: Estimating the Net Effects of Migration on Income Distribution[END_REF].

By contrast, neither anti-poor nor pro-poor impact is found for health aid. This finding contrasts with that of [START_REF] Fielding | Achieving Health, Wealth and Wisdom: Links Between Aid and the Millennium Development Goals[END_REF] who estimate a system of simultaneous equations on several welfare measures including health outcomes. They find a significantly negative impact of total aid (in percentage of GDP) on child mortality and an increased effectiveness of aid in reducing child mortality of the richest quintile.

Finally, contrary to the inter-country analysis, the medical brain drain does not seem to have a direct significant impact on child mortality.

V. Conclusion

For several years, it has been asserted that achieving Millennium Development Goals by 2015 will require increased external financing coupled with an improved targeting effectiveness in favor of the poorest population. In this context, international migrants' remittances have been increasingly put forward as a promising source of external financing. Nevertheless, empirical assessments of the respective impact of aid and remittances on aggregate welfare as measured either by poverty in monetary terms or human development indicators are rather scarce.

In this paper, we chose to focus on various child health outcomes, namely under-five mortality (Goal 4), and infant mortality to examine the direct impact of aid granted to the health sector and remittances on these human development indicators. Given our primary focus, we have chosen not to enter the debate on the relative importance of direct versus indirect (via government pro-poor expenditure) impact of aid. To complete our diagnosis, we pushed our analysis further and investigated the "net" impact of migration that is to say the effectiveness of migration including the effect of the medical brain drain. We also examined the intra-country allocation of aid and migrants' remittances.

Our results for health aid are in line with the literature examining the welfare impact of aid using cross-country data in the sense that they suggest a non-robust relationship between aid and welfare. While the impact of health aid is found to be significant in our cross-country regressions (but only when aid is interacted with income per capita), this result vanishes when cross-country quintile level data are used.

On the other hand, and for the first time, the trade-off between the gains from migration and its costs is underlined. As suggested by our paper indeed, the global impact of migration is weaker when the negative effect of medical brain drain is accounted for. Moreover, remittances are found to be more beneficial for children belonging to the richest households.

This result is in line with other microeconomic evidence which suggest that remittances may increase within-country inequality. It is different from [START_REF] Chauvet | Impact des financements internationaux sur les inégalités des pays en développement[END_REF], however, who find a pro-poor impact of remittances.

The small estimated impact of health aid and remittances net of "brain drain costs" might well explain why child mortality rates have no substantially improved for three decades as asserted by [START_REF] Murray | Can we achieve Millennium Development Goal 4? New analysis of country trends and forecasts of under-5 mortality to 2015[END_REF], despite the growing volume of health aid and migrants' remittances.

This does not mean that official assistance is inefficient. Nor does it mean that private remittances should substitute for aid. It means that further investigation into the micro-level determinants of child mortality rates is needed to improve our understanding of the bad performances of child health outcomes in most developing countries and in Africa in particular.

References Appendix

[Tables A1, A2 and A3 about here]

i The eight Millennium Development Goals are: 1) to halve extreme income poverty; 2) to achieve universal primary education; 3) to promote gender equality; 4) to reduce by two-thirds the under-five mortality rate; 5) to reduce by three-quarters the maternal mortality rate; 6) to reduce the incidence of AIDS; 7) to promote sustainable development and to halve the percentage of people without access to safe drinking water; 8) to set up a global partnership for development involving more generous, more widespread official development assistance.

ii CRS data is available at: http://www.oecd.org/document/0/0,2340,en_2649_34447_37679488_1_1_1_1,00.html.

iii There has also been an intense debate concerning the impact of public spending on child mortality. Because one of our core independent variable is health aid, and since the impact of health aid goes through the route of public spending, we exclude this variable from our analysis. iv Note that the introduction of country fixed effects contributes to solving, although imperfectly, the omitted variable bias.

v [START_REF] Tavares | Does Foreign Aid Corrupt?[END_REF] and [START_REF] Rajan | What Undermines Aid's Impact on Growth?[END_REF] use similar instruments for aid and/or remittances. vi Tests of overidentification and underidentification are reported in each table. Test for weak instruments, excludability and partial R squared are available upon requests.

vii Following the literature on the determinants of mortality rates and contrary to [START_REF] Mishra | Health Aid and Infant Mortality. IMF Working Paper 07[END_REF], we do not estimate a system of moment equations using Generalized Method of Moments (GMM) with a lagged dependent variable. The main reason is that the number of time periods is too small. viii See Cornia and[START_REF] Cornia | Health Improvements and Health Inequality during the Last 40 Years[END_REF][START_REF] Cornia | Globalization and Health[END_REF][START_REF] Cornia | Globalization and Health[END_REF] for a detail analysis of infant and child mortality trends around the world since the 1960s. ix The kind of non-linearity is still debated, though. Some authors argue that the relationship is quadratic [START_REF] Hansen | Aid and Growth Regressions[END_REF][START_REF] Lensink | Are There Negative Returns to Aid?[END_REF]. Other claim that aid's impact depends on economic policy (Burnside & Dollar, 2000), on the vulnerability to external shocks (Guillaumont & Chauvet, 2001), on export price shocks (Collier & Dehn, 2001), on the fact of being a tropical country [START_REF] Dalgaard | On the Empirics of Foreign Aid and Growth[END_REF]).

x Results are available from authors on request. xi We also re-run all our regressions using aggregate aid disbursements instead of health aid disbursements, but the variable was never significant, suggesting that not all types of aid affect health outcomes. Results are available upon request.

xii It is worth noting that estimations where the medical brain drain is not instrumented lead to very similar results to those of Table 2.

xiii Note that our estimations may under-estimate this impact as the MBD variable provided by Bhargava and Docquier (2008) measures only physicians brain drain but not other medical personnel emigration (nurses, midwife). xiv Other aid is constructed as total aid commitments minus commitments to the health sector (in constant per capita terms). This variable is an average over (t-1, t-3) and is transformed in logarithm.

xv Asset quintiles are computed using the first principal component in an analysis of the correlations between various consumer durables and other household characteristics, following a method proposed by [START_REF] Filmer | Estimating wealth effects without expenditure data or tears: an application to educational enrolments in states of India[END_REF]. xvi Fay, Leipziger, Wodon & Yepes (2005), [START_REF] Ravallion | Achieving Child-Health-Related Millenium Development Goals: The Role of Infrastructure -A Comment[END_REF], and [START_REF] Fielding | Achieving Health, Wealth and Wisdom: Links Between Aid and the Millennium Development Goals[END_REF] have used the HNP database to analyze the determinants of child-health outcomes, but only in cross-section.

Source of the data: OECD-DAC, OECD-CRS, WDI (2006). 1.40E+11

1 9 8 6 1 9 8 7 1 9 8 8 1 9 8 9 1 9 9 0 1 9 9 1 1 9 9 2 1 9 9 3 1 9 9 4 1 9 9 5 1 9 9 6 1 9 9 7 1 9 9 8 1 9 9 9 2 0 0 0 2 0 0 1 2 0 0 2 2 0 0 3 2 0 0 4 Total aid and remittances 0.00E+00 0.000 0.000 Notes: Robust standard errors in parentheses. All variables except the education variable are averages over threeyear periods, from t-1 to t-3, measured in logs. * significant at 10%; ** significant at 5%; *** significant at 1%. In equations 1 and 4, standards errors are clustered by country. (a) Instrumented regressors in equations 3 and 5. Instruments include twice lagged GDP per capita, twice lagged aid, and instruments for aid and remittances in the tradition of [START_REF] Tavares | Does Foreign Aid Corrupt?[END_REF], namely total aid budgets of the five largest donors (USA, Japan, France UK, Germany) in constant dollars weighted by cultural (same religion) and geographical distance variables. The ratio of broad money supply (M2) to GDP is also included as an instrument for remittances. Tests of excludability of the instruments are available upon request. All variables except the education variable are averages over threeyear periods, from t-1 to t-3, measured in logs. * significant at 10%; ** significant at 5%; *** significant at 1%. In equations 1 and 4, standards errors are clustered by country. (a) Instrumented regressors in equations 3 and 5. Instruments include twice lagged GDP per capita, twice lagged aid, and instruments for aid and remittances in the tradition of [START_REF] Tavares | Does Foreign Aid Corrupt?[END_REF], namely total aid budgets of the five largest donors (USA, Japan, France UK, Germany) in constant dollars weighted by cultural (same religion) and geographical distance variables. The ratio of broad money supply (M2) to GDP is also included as an instrument for remittances. Tests of excludability of the instruments are available upon request.

  less precise than the one used by Ravallion: we use the Barro and Lee's indicator (the national average years of schooling of the female population aged 15 and over), whereas[START_REF] Ravallion | Achieving Child-Health-Related Millenium Development Goals: The Role of Infrastructure -A Comment[END_REF] uses the average number of years of female schooling per quintile of the HNP database.

Figure

  Figure 1. Aid and remittances constant dollars (100=2000)

  p.c. x 3 rd quintile (a) -0.0591*** -0.0591*** -0.124*** -0.0543*** -0.0543*** -0.c. x 5 th quintile (a) -0.0827*** -0.0827*** -0.166*** -0.0662*** -0.0662*** -0.134*

Table 1 .

 1 Impact of health aid and remittances on child and infant mortality, baseline model.

	1.00E+10
	9.00E+09
	8.00E+09
	7.00E+09
	4.00E+09 5.00E+09 6.00E+09	Health aid
	3.00E+09
	2.00E+09
	1.00E+09

Table 2 .

 2 Alternative specifications, 2SLS with fixed effects.

	Dependent variable	Child	Infant	Child	Infant
		mortality	mortality	mortality	mortality
	2SLS estimations	(1)	(2)	(3)	(4)
	GDP per capita (a)	-0.191	-0.131	-0.384	-0.296
		(0.295)	(0.271)	(0.313)	(0.272)
	Number of physicians per 1,000	0.0205	0.0264	0.0307	0.0351
		(0.0701)	(0.0645)	(0.0637)	(0.0574)
	Female educational attainment	-0.0993	-0.0816	-0.252	-0.212
		(0.157)	(0.147)	(0.176)	(0.154)
	Dummy for missing education variable	-0.409	-0.354	-0.617**	-0.532*
		(0.298)	(0.278)	(0.311)	(0.275)
	Remittances per capita (a)	-0.137**	-0.119**	-0.142***	-0.123***
		(0.0540)	(0.0506)	(0.0493)	(0.0447)
	Health aid per capita (a)	-1.266**	-1.215**	-1.019**	-1.003**
		(0.541)	(0.509)	(0.516)	(0.468)
	Health aid per capita x Income per capita (a)	0.150**	0.145**	0.120*	0.119**
		(0.0647)	(0.0611)	(0.0617)	(0.0561)
	Medical Brain Drain (a)			0.513**	0.440**
				(0.242)	(0.216)
	Year = 2000	-0.016	-0.023	-0.016	-0.023
		(0.051)	(0.048)	(0.042)	(0.039)
	Year = 2004	-0.063	-0.074	-0.106*	-0.111**
		(0.068)	(0.062)	(0.062)	(0.056)
	Fixed effects

Table 3 .

 3 Summary statistics Infant mortality: number of deaths to children under twelve months of age per 1,000 live births, based on experience during the ten years before the survey. (c) Child mortality: number of deaths to children under five years of age per 1,000 live births, based on experience during the ten years before the survey.

	Variable	Observations (a)	Mean	Std. Dev.	Min	Max
	Infant mortality (b)
	Full sample	370	72.63	34.22	11.90	187.70
	Poorest quintile	74	87.37	31.70	32.00	187.70
	Second quintile	74	83.05	33.22	23.80	152.30
	Third quintile	74	76.92	34.50	19.70	157.20
	Fourth quintile	74	66.42	32.58	11.90	142.00
	Richest quintile	74	49.38	24.97	13.80	97.20
	Child Mortality (c)
	Full sample	370	115.77	67.59	14.20	354.90
	Poorest quintile	74	142.30	63.23	39.10	297.90
	Second quintile	74	135.14	69.65	27.30	354.90
	Third quintile	74	122.72	69.61	23.50	348.30
	Fourth quintile	74	104.44	64.95	14.20	314.90
	Richest quintile	74	74.22	46.46	15.80	183.70
	Notes:
	(a) country-time observations
	(b)

Table 4 .

 4 Intra-country specification with interaction terms.

		Child mortality (CMR)	Infant mortality (IMR)
		(1)	(2)	(3)	(4)	(5)	(6)
		OLS	Within	IV	OLS	Within	IV
	GDP per capita (a)	-0.298***	-0.513***	-0.624***	-0.277***	-0.517***	-0.578**
		(0.0958)	(0.186)	(0.208)	(0.0711)	(0.193)	(0.228)
	Number of physicians per 1,000 -0.175***	0.0128	-0.00526	-0.0856	0.0741	0.0690
		(0.0629)	(0.0699)	(0.0803)	(0.0513)	(0.0727)	(0.0900)
	Female educational atta.	-0.223***	0.0283	-0.579	-0.242***	0.196	-0.384
		(0.0759)	(0.277)	(0.557)	(0.0534)	(0.289)	(0.536)
	Dum. for missing educ. var. (b)	-0.0208			-0.0851
		(0.129)			(0.0929)
	Medical brain drain (a)	0.0180	-0.108	0.295	0.0213	-0.0859	0.323
		(0.0338)	(0.154)	(0.484)	(0.0277)	(0.161)	(0.468)
	Health aid per capita (a)	-0.0277	-0.00738	-0.0266	-0.0307	-0.00541	-0.00369
		(0.0412)	(0.0353)	(0.0762)	(0.0395)	(0.0367)	(0.0734)
	Health aid p.c. x 2 nd quintile(a)	0.0398**	0.0398	0.0489	0.0295	0.0295	0.0543
		(0.0164)	(0.0241)	(0.0454)	(0.0189)	(0.0251)	(0.0472)
	Health aid p.c. x 3 rd quintile (a)	0.0574**	0.0574**	0.0706*	0.0501*	0.0501**	0.0798*
		(0.0261)	(0.0241)	(0.0423)	(0.0267)	(0.0251)	(0.0421)
	Health aid p.c. x 4 th quintile (a)	0.0797**	0.0797***	0.107**	0.0763**	0.0763***	0.0964*
		(0.0318)	(0.0241)	(0.0479)	(0.0321)	(0.0251)	(0.0498)
	Health aid p.c. x 5 th quintile (a)	0.0483	0.0483**	0.103*	0.0541	0.0541**	0.120**
		(0.0375)	(0.0241)	(0.0573)	(0.0379)	(0.0251)	(0.0578)
	Remittances p. c. (a)	0.0405	0.0422	-0.0114	0.0326	0.0537	-0.0161
		(0.0302)	(0.0323)	(0.0718)	(0.0230)	(0.0336)	(0.0700)
	Remit. p.c. x 2 nd quintile (a)	-0.0378*** -0.0378**	-0.0618*	-0.0407*** -0.0407**	-0.0440
		(0.00953)	(0.0151)	(0.0350)	(0.0117)	(0.0157)	(0.0347)
	Remit.

Table A2 .

 A2 Instrumentation equations

			Instrumentation equation for :
		GDP	Health aid	Remittances
		per capita	per capita	per capita
	Number of physicians per 1,000	0.019	-0.647**	0.568*
		(0.023)	(0.317)	(0.305)
	Female educational attainment	0.020	0.713	0.052
		(0.062)	(0.755)	(0.824)
	Dummy for missing education variable	-0.029	1.004	-1.920
		(0.099)	(1.288)	(1.331)
	Year = 2000	0.046	0.579	-0.359
		(0.038)	(0.612)	(0.304)
	Year = 2004	0.159*	-0.051	1.128*
		(0.085)	(0.947)	(0.604)
	Twice lagged health aid per capita	0.007	-0.223*	0.087*
		(0.005)	(0.119)	(0.046)
	Twice lagged GDP per capita	0.338***	-0.070	-0.157
		(0.084)	(0.674)	(0.435)
	M2/GDP	-0.006	0.448	0.139
		(0.041)	(0.385)	(0.330)
	Total aid budget of France x Same religion	0.230	-0.522	3.807***
		(0.147)	(1.344)	(0.901)
	Total aid budget of France x Distance	-0.00002	0.0004	0.00003
		(0.00002)	(0.0003)	(0.0002)
	Total aid budget of UK x Same religion	-0.321**	0.137	-4.328***
		(0.158)	(1.757)	(1.021)
	Total aid budget of UK x Distance	-0.00002	0.0002	0.0001
		(0.00001)	(0.0002)	(0.0001)
	Total aid budget of Germany x Same religion	-0.350	-2.214	-6.710***
		(0.229)	(2.426)	(1.571)
	Total aid budget of USA x Same religion	0.175	0.351	2.189***
		(0.114)	(1.538)	(0.758)
	Total aid budget of USA x Distance	0.000003	0.00005	-0.0001***
		(0.000005)	(0.00007)	(0.00004)
	Total aid budget of Japan x Same religion	-0.125	-4.095	6.815*
		(0.243)	(2.959)	(4.031)
	Total aid budget of Japan x Distance	0.00002	0.00003	0.0003*
		(0.00002)	(0.0002)	(0.0001)
	Fixed effects	Yes	Yes	Yes
	Observations	233	233	233
	F-Statistic (p-value)	0.000	0.061	0.000
	Partial R² of excluded instruments	0.332	0.171	0.178

Table A3 .

 A3 Impact of total aid

	Dependant variable		Child mortality			Infant mortality
	2SLS estimations	(1)	(2)	(3)	(4)	(5)	(6)
	GDP per capita (a)	-0.558**	-0.189	-0.378	-0.485**	-0.128	-0.291
		(0.262)	(0.291)	(0.315)	(0.233)	(0.269)	(0.275)
	Number of physicians per 1,000	0.0448	0.0234	0.0328	0.0499	0.0291	0.0372
		(0.0549)	(0.0690)	(0.0627)	(0.0495)	(0.0635)	(0.0564)
	Female educational attainment	-0.0124	-0.0952	-0.251	0.00251	-0.0777	-0.211
		(0.103)	(0.151)	(0.174)	(0.0954)	(0.141)	(0.152)
	Dum. for missing education var.	-0.232	-0.397	-0.613**	-0.183	-0.343	-0.528**
		(0.189)	(0.284)	(0.305)	(0.175)	(0.264)	(0.268)
	Year = 2000	-0.0333	-0.0156	-0.0151	-0.0398	-0.0227	-0.0222
		(0.0359)	(0.0491)	(0.0420)	(0.0324)	(0.0458)	(0.0384)
	Year = 2004	-0.0675	-0.0655	-0.108*	-0.0784*	-0.0765	-0.113**
		(0.0526)	(0.0653)	(0.0617)	(0.0471)	(0.0600)	(0.0554)
	Remittances per capita (a)	-0.129***	-0.140*** -0.146***	-0.112***	-0.122**	-0.127***
		(0.0459)	(0.0533)	(0.0501)	(0.0418)	(0.0500)	(0.0456)
	Health aid per capita (a)	-0.0204	-1.210**	-0.984**	-0.00995	-1.162**	-0.968**
		(0.0252)	(0.510)	(0.496)	(0.0227)	(0.475)	(0.444)
	Health aid p.c. x Income p.c. (a)		0.143**	0.116*		0.139**	0.115**
			(0.0617)	(0.0599)		(0.0578)	(0.0538)
	Medical Brain Drain (a)			0.517**			0.444**
				(0.244)			(0.217)
	Total aid p.c. -Health aid p.c.	0.0155	0.0303	0.0285	0.0151	0.0295	0.0279
		(0.0274)	(0.0408)	(0.0368)	(0.0254)	(0.0401)	(0.0368)
	Fixed effects	Yes	Yes	Yes	Yes	Yes	Yes
	Observations	233	233	233	233	233	233
	Number of pays	84	84	84	84	84	84
	Sargan (p-value)	0.269	0.534	0.949	0.277	0.542	0.889
	Underidentification test (p-value)	0.099	0.198	0.114	0.099	0.198	0.114
	Notes: Robust standard errors in parentheses.

0.059 0.059 Notes: Robust standard errors in parentheses. All variables except the education variable are averages over threeyear periods, from t-1 to t-3, measured in logs. * significant at 10%; ** significant at 5%; *** significant at 1%. (a) Instrumented regressors. Instruments include twice lagged GDP per capita and aid as well as instruments for aid and remittances in the tradition of [START_REF] Tavares | Does Foreign Aid Corrupt?[END_REF], namely total aid budgets of the five largest donors (USA, Japan, France UK, Germany) in constant dollars weighted by cultural (same religion) and geographic distance variables. The ratio of broad money supply (M2) to GDP is also included as an instrument for remittances. Tests of excludability of the instruments are available upon request. 0.000 0.000 Medical brain drain 0.000 0.000 Notes: Robust standard errors in parentheses. All variables except the education variable are averages over threeyear periods, from t-1 to t-3, measured in logs. * significant at 10%; ** significant at 5%; *** significant at 1%. (a) Instrumented regressors in equations 3, 6. Instruments include lagged GDP per capita, ratio of lagged broad money supply (M2) to GDP, lagged health aid per capita, and total aid budgets of France, Japan, UK and USA in constant dollars weighted by geographic distance (distance to Washington, Brussels and Tokyo). We also include lagged GDP per capita and lagged health aid per capita interacted with quintiles q2 to q5 among the instruments. Tests of excludability of the instruments are available upon request. (b) In within and IV specifications, this variable is dropped due to collinearity with country fixed effects.


Delia Garijo
email: dgarijo@us.es.

Antonio González
email: gonzalezh@us.es.

Alberto Márquez

The resolving number of a graph

Keywords: resolving set, resolving number, metric dimension

We study a graph parameter related to resolving sets and metric dimension, namely the resolving number, introduced by Chartrand, Poisson and Zhang. First, we establish an important difference between the two parameters: while computing the metric dimension of an arbitrary graph is known to be NP-hard, we show that the resolving number can be computed in polynomial time. We then relate the resolving number to classical graph parameters: diameter, girth, clique number, order and maximum degree. With these relations in hand, we characterize the graphs with resolving number 3 extending other studies that provide characterizations for smaller resolving number.

Introduction

Let G = (V (G), E(G)) be a finite, simple, undirected and connected graph of order n = |V (G)|. The distance d (u, v) between two vertices u, v ∈ V (G) is the length of a shortest u-v path in G. A vertex u ∈ V (G) resolves a pair {x, y} ⊂ V (G) if d(u, x) = d(u, y). A set of vertices S ⊆ V (G) is a resolving set of G if every pair of vertices of G is resolved by some vertex in S. The metric dimension of G, denoted by dim(G), is the minimum cardinality of a resolving set of G. The resolving number, written as res(G), is the minimum k such that every k-subset of V (G) is a resolving set of G. Obviously, every set S ⊆ V (G) with |S| ≥ res(G) is a resolving set of G.

Resolving sets and metric dimension were first introduced by [START_REF] Slater | Leaves of trees[END_REF], and independently by [START_REF] Harary | On the metric dimension of a graph[END_REF]. Much latter, Chartrand et al. (2000b) defined the resolving number. There exists by now an extensive literature on resolving sets and the resolving parameters related to them, including applications to several areas such as coin weighing problems, pharmaceutical chemistry, robot navigation, network discovery and verification, and problems of pattern recognition and image processing. See for instance [START_REF] Beerliova | Network discovery and verification[END_REF]; [START_REF] Cáceres | On the metric dimension of cartesian products of graphs[END_REF]; Chartrand et al. (2000a,b); [START_REF] Garijo | On the metric dimension, the upper dimension and the resolving number of graphs[END_REF]; [START_REF] Hernando | Extremal graph theory for metric dimension and diameter[END_REF]; [START_REF] Khuller | Landmarks in graphs[END_REF]; [START_REF] Melter | Metric bases in digital geometry[END_REF].

Although the metric dimension and the resolving number are closely related by their definitions, there are significant differences between them. For instance, one can easily find infinite families of graphs with the same metric dimension, whereas in [START_REF] Garijo | On the metric dimension, the upper dimension and the resolving number of graphs[END_REF] we showed that the set of graphs with fixed resolving number a ≥ 4 is finite. This paper establishes another important difference between these parameters: while computing the metric dimension of an arbitrary graph is NP-hard (see [START_REF] Khuller | Landmarks in graphs[END_REF]), we prove that the resolving number can be computed in polynomial time.

We also deal with two types of problems typically studied for resolving parameters. First, we relate the resolving number to classical graph parameters: diameter, girth, clique number, order and maximum degree. Concretely, we provide bounds (most of which are tight) on the girth, the order, and the maximum degree of a graph in terms of its resolving number. We also determine the graphs G with clique number equal to res(G), and restrict ourselves to trees to give bounds on the diameter, the order and the maximum degree, characterizing also the extremal cases. Our study follows the same spirit as several papers that treat analogous problems for the metric dimension. See Chartrand et al. (2000a); [START_REF] Hernando | Extremal graph theory for metric dimension and diameter[END_REF]; [START_REF] Khuller | Landmarks in graphs[END_REF]; [START_REF] Yushmanov | Estimates for the metric dimension of a graph in terms of the diameter and the number of vertices[END_REF] for relations with the order and the diameter, and [START_REF] Chappell | Bounds on the metric and partition dimensions of a graph[END_REF]; [START_REF] Tomescu | Discrepancies between metric dimension and partition dimension of a connected graph[END_REF] for relations with the chromatic number and the partition dimension. Further, as it will be specified later, most of our results either improve relations obtained in other papers or continue with the studies developed in them.

Our second main problem is to characterize the graphs with given resolving number. As a consequence of some results in Chartrand et al. (2000b) and Jannesari and Omoomi (2011b), one can easily prove that the only graphs G with res(G) ≤ 2 are paths and odd cycles. As a next step, we determine all graphs with resolving number 3 using as main tools our relations between the resolving number and the graph parameters mentioned above. Similar results have been obtained for the metric dimension, and also combining metric dimension with resolving number: Chartrand et al. (2000a) characterized the graphs with metric dimension equal to 1, n -2 and n -1, and the graphs G such that dim(G) = res(G) = k are obtained in [START_REF] Garijo | On the metric dimension, the upper dimension and the resolving number of graphs[END_REF] (see also Jannesari and Omoomi (2011a)).

The paper is organized as follows. Section 2 provides some notation, definitions and a series of technical results. One of these results leads to Corollary 2.2 which states that res(G) can be computed in polynomial time. In Section 3, we present the above described relationships between the resolving number and classical graph parameters. As it was said before, besides their independent interest, these relations are the main tool to characterize the graphs with resolving number 3, which is done in Section 4. We conclude the paper in Section 5 with some remarks and open problems.

Preliminaries. Computational complexity of res(G)

We begin by introducing some more notation and definitions. For u ∈ V (G), we shall denote by N (u) and N [u] the open and closed neighbourhoods of u, respectively. As usual, δ(u) is the degree of u, ∆(G) is the maximum degree of G, and A is the induced subgraph by a subset A ⊆ V (G).

Let P n and C n denote, respectively, the path and the cycle on n vertices. When no confusion can arise, we shall use P (respectively, C or K) to denote a path (respectively, cycle or clique) and also its vertex set.

The girth g(G) is the minimum length of a cycle in G. Note that the girth of a tree is defined to be infinity. The clique number ω(G) is the maximum size of a clique in G, and the diameter of G, written as d(G), is the maximum distance between any two vertices of G. The distance between a vertex u ∈ V (G) and a subset A ⊆ V (G) is d(u, A) = min v∈A d(u, v), and the diameter of A is u, v). The set of pairs of elements of A is denoted by P 2 (A).

d(A) = max u,v∈A d(
Let R(x, y) be the set of vertices of G that resolve the pair {x, y} ⊂ V (G), and let R(x, y) = V (G) \ R(x, y). Note that for every pair {x, y}, the set R(x, y) is not a resolving set of G.

The following proposition is the key tool to obtain the previously mentioned difference on the computational complexity of the resolving number and the metric dimension: res(G) is polynomial-time computable while computing dim(G) is NP-hard (see [START_REF] Khuller | Landmarks in graphs[END_REF]). Proof: First, we preprocess the distance matrix of G in O(n 3 ) time (see [START_REF] Floyd | Algorithm 97: Shortest path[END_REF]). Thus, for each pair {x, y} ∈ P 2 (V (G)) the set R(x, y) can be obtained in O(n) time by comparing the corresponding rows of x and y in the distance matrix. By Proposition 2.1, we can compute res(G) in O(n 3 ) time since

|P 2 (V (G))| is O(n 2 ). ✷
We now provide three results which will be useful in the proofs of this paper.

Lemma 2.3 Let P ⊆ P 2 (V (G)) and let V 1 , V 2 , . . . , V ℓ be a partition of V (G). If every vertex of V i , for i = 1, . . . , ℓ, does not resolve at least k i ≥ 0 pairs of P, then

ℓ i=1 |V i | • k i ≤ |P| • (res(G) -1).
Proof: Every vertex u ∈ V i belongs to at least k i different sets of the form R(x, y) with {x, y} ∈ P. Moreover, by Proposition 2.1, we have

|R(x, y)| ≤ res(G) -1. Hence ℓ i=1 |V i | • k i ≤ {x,y}∈P |R(x, y)| ≤ |P| • (res(G) -1). ✷ Khuller et al. (1996) showed that d(u, w) ∈ {d -1, d, d + 1} for u, v, w ∈ V (G) such that {v, w} ∈ E(G) and d(u, v) = d. The following straightforward lemma provides a version of this result for subsets of V (G). Lemma 2.4 Let u ∈ V (G) and A ⊆ V (G). If d(u, A) = d then d(u, v) ∈ {d, d + 1, . . . , d + d(A)} for every v ∈ A.
A resolving set S of G is minimal if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim + (G) (see Chartrand et al. (2000b)). Clearly, every (n -1)-subset of V (G) is a resolving set and every resolving set contains a minimal resolving set. Hence,

1 ≤ dim(G) ≤ dim + (G) ≤ res(G) ≤ n -1.
This relation and several results in Chartrand et al. (2000b) and Jannesari and Omoomi (2011b) give all graphs G with res(G) ≤ 2. Indeed, by Theorem 1 of Jannesari and Omoomi (2011b), the paths P 1 and P 2 are the only graphs with resolving number equal to 1. By Proposition 2.1 of Chartrand et al. (2000b) we have res( Chartrand et al. (2000b) says that dim + (G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle. If dim + (G) = 1 and res(G) = 2 then dim(G) = 1 and, by Theorem A of Chartrand et al. (2000b), one obtains that G is a path. Thus, we have proved the following result.

P n ) = 2 for n ≥ 3 and res(C n ) = 2 if n is odd. Theorem 2.4 of
Theorem 2.5 res(G) ≤ 2 if and only if G is a path or an odd cycle.

Relationships between res(G) and other graph parameters

Diameter

In [START_REF] Garijo | On the metric dimension, the upper dimension and the resolving number of graphs[END_REF], we showed that d(G) ≤ 3res(G) -5 for a graph G (not being a cycle) with res(G) ≥ 3. Here, we improve this bound for trees characterizing also the extremal case.

For positive integers a, b, c, let S a,b,c be a spider with three legs of lengths a, b, c, respectively (i.e., a tree formed by three paths of lengths a, b, c attached at a single vertex). Proof: For simplicity, let us denote r = res(T ). By Theorem 2.5 we have r ≥ 3. Suppose on the contrary that d(T ) ≥ 2r-3. Assume, without loss of generality, that d(T ) = 2r-3 and let P = (u 1 , u 2 , ..., u 2r-2 ) be a shortest path of length d(T ). Clearly, δ(u 1 ) = δ(u 2r-2 ) = 1. Further, since T is not a path then there is a vertex u ∈ N [u i ] \ P with 1 < i < 2r -2. If i ≥ r (analogous for i < r) then no vertex of S = {u 1 , u 2 , ..., u i } resolves the pair {u, u i+1 } and so S is not a resolving set of G; a contradiction with

|S| = i ≥ r. Therefore, d(T ) ≤ 2r -4.
One can easily check that d(S a,r-2,r-2 ) = 2res(S a,r-2,r-2 ) -4 for a ≤ r -2. Consider now a tree T such that d(T ) = 2r -4, and let P = (u 1 , ..., u 2r-3 ) be a shortest path of length d(T ). Next, we prove that T ∼ = S a,r-2,r-2 with a ≤ r -2.

Arguing as above, we obtain δ(u 1 ) = 1, δ(u 2r-3 ) = 1, and there is a vertex u ∈ N [u i ] \ P with 1 < i < 2r -3. Moreover, the sets {u 1 , ..., u r } and {u r-2 , ..., u 2r-3 } are not resolving sets when i ≥ r and i ≤ r -2, respectively. This implies u i = u r-1 , and so δ(u r-1 ) ≥ 3 and δ(u j ) = 2 for j = 1, r -1, 2r -3. That δ(u r-1 ) = 3 follows from the fact that P is a resolving set, and the same argument shows that the induced subgraph V (T ) \ P is a path. Thus, T ∼ = S a,r-2,r-2 for some positive integer a. Further, no vertex of the set (V (T ) \ P ) ∪ {u r-1 } resolves the pair {u r-2 , u r } and so it is not a resolving set. Hence, a = |V (T )

\ P | ≤ r -2. ✷ K 4 K 2 + K 2 K 1 + P 4 W 1,5 G 1 G 2 G 3 G 4 G 5 G 6 G 7 G 8 G 9 G 10
Fig. 1: The set of graphs F1.

Girth

We now provide a tight bound on the girth of a graph in terms of its resolving number.

Proposition 3.2 If G is neither a tree nor a cycle then g(G) ≤ 2res(G) -1, and this bound is tight.

Proof: Let r = res(G). Suppose on the contrary that g(G) ≥ 2r. Assume, without loss of generality, that g(G) = 2r and consider a cycle of minimum length C = (u 1 , ..., u 2r ). Since G is not a cycle then there is a vertex u adjacent to some vertex of C, say u r . Further, C has minimum length and so (u 1 , u 2 , . . . , u r+1 ) is a shortest u 1 -u r+1 path. Thus, the pair {u, u r+1 } is resolved by no vertex of S = {u 1 , ..., u r }, and so S is not a resolving set; a contradiction with |S| = r.

The graph obtained by attaching a pendant edge to any vertex of an odd cycle C 2a+1 with a ≥ 3 has girth 2a + 1 and resolving number a + 1. This proves that the bound is tight. ✷

Clique number

Jannesari and Omoomi (2011b) proved that ω(G) ≤ res(G)+1 for a graph G such that dim(G) = res(G), and that equality holds only for complete graphs. However, their proof does not use the hypothesis dim(G) = res(G) but only the fact that every set S ⊆ V (G) with |S| ≥ res(G) is a resolving set of G. Thus, their result can be extended to every graph G.

Proposition 3.3 For every graph G, ω(G) ≤ res(G) + 1 and equality holds if and only if G is a complete graph.

As a next step, we determine all graphs G such that ω(G) = res(G). Let F 1 denote the set of 14 graphs depicted in Figure 1. For positive integers a, b with b < a, let G a,b be the graph obtained by attaching a vertex to any b vertices of a complete graph on a vertices (note that res(G a,b ) = a); see Figure 2(right) for a small example. Let G 1 , G 2 , G 3 and G 4 be the other four graphs illustrated in Figure 2.

G 1 G 2 G 3 G 4 G 5,3
Fig. 2: The graphs G 1 , G 2 , G 3 , G 4 and G5,3.

Proposition 3.4 For every graph G, the following statements hold.

(i) ω(G) = res(G) = 1 ⇐⇒ G ∼ = K 1 . (ii) ω(G) = res(G) = 2 ⇐⇒ G ∼ = P n for some n ≥ 3 or G ∼ = C n for some odd n ≥ 5. (iii) ω(G) = res(G) = 3 ⇐⇒ G ∈ F 1 . (iv) ω(G) = res(G) = 4 ⇐⇒ G ∈ {G 1 , G 2 , G 3 , G 4 } or G ∼ = G 4,b for some b < 4. (v) ω(G) = res(G) ≥ 5 ⇐⇒ G ∼ = G a,b
for some b < a and 5 ≤ a = res(G).

Proof: Statement (i) is straightforward, and Statement (ii) follows immediately from Theorem 2.5 (note that res(P 2 ) = 1). As a consequence of the study developed in Section 4 (see Theorem 4.4) one can easily prove Statement (iii). Finally, we prove Statements (iv) and (v) at the same time. If G is isomorphic to either G 1 , G 2 , G 3 , G 4 , or G a,b with res(G) = a ≥ 4 and b < a, then the corresponding statements can be easily checked.

Consider now a graph G such that ω(G) = res(G) = r ≥ 4. Let K be a maximum clique in G. By Proposition 3.3, the graph G is not a complete graph and so there is a vertex u ∈ V (G) \ K adjacent to some vertex of K.

If n = r + 1 then G ∼ = G r,b for some b < r. Otherwise, there is a vertex v ∈ V (G) \ (K ∪ {u}) such that either v ∈ N (u) or v is adjacent to some vertex of K. Let A 1 = (N (u) \ N (v)) ∩ K, A 2 = (N (v) \ N (u)) ∩ K, A 3 = N (u) ∩ N (v) ∩ K and A 4 = K \ (N (u) ∪ N (v)
). Note that any set A i may be empty, and K is the disjoint union of the four sets. We claim that |A i | ≤ 1 for every 1 ≤ i ≤ 4. Indeed, suppose on the contrary that there are two different vertices x, y in, say A 1 . Clearly, d(v, x) = d(v, y) = 2 and so the set S = (K \ {x, y}) ∪ {u, v} is not a resolving set; a contradiction with |S| = r. Hence, |A 1 | ≤ 1 and a similar argument applies to the remaining sets A i . Since

4 i=1 |A i | = |K| = r ≥ 4 and |A i | ≤ 1 then |K| = r = 4 and |A i | = 1 for every 1 ≤ i ≤ 4. Hence, we can assume that N (u) ∩ K = {u 1 , u 2 } and N (v) ∩ K = {u 2 , u 3 } for K = {u 1 , u 2 , u 3 , u 4 }.
Note that, in particular, we have proved that if n = r + 1 then r = 4. Thus, the graphs G obtained in Statement (v) are only those for the case n = r + 1.

If n = 6 then G is isomorphic to either G 1 or G 2 (depending on whether u and v are adjacent or not). Suppose now that n ≥ 7 and let w ∈ V (G) \ (K ∪ {u, v}). Considering the analogous sets A i but for the vertices u, w and v, w, we deduce that either N (w)∩K = {u 1 , u 3 } or N (w)∩K = {u 2 , u 4 }. This implies

n = 7 (otherwise there is a vertex z ∈ V (G) \ (K ∪ {u, v, w}) such that A 3 = N (w) ∩ N (z) ∩ K = ∅ and A 4 = K \ (N (w) ∪ N (z)) = ∅).
We next show that it cannot be the case that N (w)∩K = {u 1 , u 3 } by providing a set S with |S| = 4 that is not a resolving set.

Order

The following proposition gives bounds on the order of a graph in terms of its resolving number, and also provides an alternative proof for Theorem 3.7 of [START_REF] Garijo | On the metric dimension, the upper dimension and the resolving number of graphs[END_REF] which states that the set of graphs with resolving number a ≥ 4 is finite.

Proposition 3.5 If G is neither a path nor a cycle then

res(G) + 1 ≤ n ≤            3res(G) -3 if g(G) = 3, 4res(G) -4 if g(G) = 4, 5res(G) -5 if g(G) = 5, 5res(G) -9 if g(G) > 5 and ∆(G) > 3, 6res(G) -8 if g(G) > 5 and ∆(G) = 3.
Moreover, the lower bound and the upper bounds for g(G) ∈ {3, 5} are tight.

Proof: By definition res(G) + 1 ≤ n for every graph G, and the complete graph K n attains the bound (see Chartrand et al. (2000b)). For the upper bound, we distinguish several cases. Case 1. g(G) = 3: Let C = (u 1 , u 2 , u 3 ) be a 3-cycle in G, and u ∈ V (G). Since d(C) = 1, by Lemma 2.4, d(u, u i ) ∈ {d(u, C), d(u, C) + 1} for every 1 ≤ i ≤ 3. Hence, there is at least one pair {u i , u j } ∈ P 2 (C) which is not resolved by vertex u. Lemma 2.3 gives the expected bound by setting

P = P 2 (C), V 1 = V (G) (ℓ = 1) and k 1 = 1.
The graph consisting of a 3-cycle with one path of length r -2 attached to each vertex of the cycle has resolving number r and 3(r -1) vertices. This shows that the bound is tight.

Case 2. g(G) = 4:

Let C = (u 1 , u 2 , u 3 , u 4 ) be a cycle of minimum length in G, V 1 = R(u 1 , u 3 ) ∩ R(u 2 , u 4 ) and V 2 = V (G) \ V 1 . We now distinguish two cases. Case 2.1. |V 1 | ≤ |V 2 |: Every vertex u ∈ V 2 does not resolve at least one pair of P = {{u 1 , u 3 }, {u 2 , u 4 }}. By Lemma 2.3, taking k 1 = 0 and k 2 = 1 (ℓ = 2) we have 2(res(G) -1) ≥ |V 2 | ≥ n/2. Case 2.2.: |V 1 | > |V 2 |: Let u ∈ V 1 and d(u, C) = d. Assume that d(u, u 1 ) = d. Then d(u, u 2 ), d(u, u 4 ) ∈ {d, d + 1}. Since u ∈ R(u 2 , u 4 ) then either d(u, u 2 ) = d or d(u, u 4 ) = d. Moreover, u ∈ R(u 1 , u 3
) and so d(u, u 3 ) = d+1. Therefore, there are at least two pairs of P = {{u 1 , u 2 }, {u 2 , u 3 }, {u 3 , u 4 }, {u 4 , u 1 }} which are not resolved by vertex u. By Lemma 2.3, setting k 1 = 2 and k 2 = 0 (ℓ = 2) we have

4(res(G) -1) ≥ 2|V 1 | > n.
Case 3. g(G) = 5: A 5-cycle C = (u 1 , u 2 , u 3 , u 4 , u 5 ) has diameter 2 and so Lemma 2.4 gives d(u, u i ) ∈ {d(u, C), d(u, C) + 1, d(u, C) + 2} for every u ∈ V (G) and 1 ≤ i ≤ 5. Hence, there are at least two pairs of P 2 (C) which are not resolved by vertex u. The result follows by Lemma 2.3, taking andk 1 = 2. The graph G 14 depicted in Figure 3 (see Section 4) shows that the bound is tight.

P = P 2 (C), V 1 = V (G) (ℓ = 1)
Case 4. g(G) > 5 and ∆(G) > 3: Let u 0 ∈ V (G) with δ(u 0 ) ≥ 4, and consider four of its neighbours, say u 1 , u 2 , u 3 , u 4 . Let A = {u 0 , u 1 , u 2 , u 3 , u 4 }. Arguing as in Case 3, since d(A) = 2 then every vertex u ∈ V (G) does not resolve at least two pairs of P 2 (A). Moreover, u 0 resolves no pair of P 2 (A \ {u 0 }), and u i resolves no pair of P 2 (A \ {u 0 , u i }) for every 1 ≤ i ≤ 4. By Lemma 2.3, setting

P = P 2 (A), V 1 = V (G) \ A, V 2 = {u 0 }, V 3 = A \ {u 0 } (ℓ = 3), k 1 = 2, k 2 = 6 and k 3 = 3, we have 10(res(G) -1) ≥ 2(n -5) + 6 + 12 = 2n + 8.
Case 5. g(G) > 5 and ∆(G) = 3: Let u 0 ∈ V (G) with δ(u 0 ) = 3 and neighbours u 1 , u 2 , u 3 . Reasoning as above, every vertex u ∈ V (G) does not resolve at least one pair of P 2 (N [u 0 ]). Further, u 0 resolves no pair of P 2 (N (u 0 )). Lemma 2.3 gives the expected bound by taking

P = P 2 (N [u 0 ]), V 1 = V (G) \ {u 0 }, V 2 = {u 0 } (ℓ = 2), k 1 = 1 and k 2 = 3. ✷
We now provide a tight bound for trees, characterizing those that attain the bound.

Proposition 3.6 If T is a tree of order n that is not a path then n ≤ 3res(T ) -5, and equality holds if and only if T ∼ = S a,a,a with a = res(T ) -2 ≥ 1.

Proof: Let u ∈ V (T ) such that δ(u) ≥ 3 and consider three of its neighbours, say u 1 , u 2 , u 3 . We can partition V (T ) into four subsets U, U i with 1 ≤ i ≤ 3, where U i contains all vertices v ∈ V (T ) such that u i belongs to the u-v path, and

U = V (T ) \ ∪ 3 i=1 U i . Note that u i ∈ U i and u ∈ U .
Clearly, no vertex of U i resolves the pair {u j , u k } for i = j = k. Moreover, every vertex of U resolves no pair of P 2 ({u 1 , u 2 , u 3 }). Since every subset of vertices with cardinality at least res(T ) is a resolving set of T we can conclude that for 1 ≤ i ≤ 3,

|U i | + |U | ≤ res(T ) -1. (1)
Hence,

3 i=1 |U i | + 3|U | ≤ 3(res(T ) -1) and so n ≤ 3(res(T ) -1) -2|U | ≤ 3(res(T ) -1) -2. ( 2
)
If T is isomorphic to S a,a,a with a = res(T ) -2 then n = 3res(T ) -5. Consider now a tree T such that n = 3res(T ) -5. Proceeding as above, one can partition V (T ) into the subsets U, U i with 1 ≤ i ≤ 3. Since T satisfies expression (2) then n attains its maximum value when |U | = 1, i.e., U = {u}. Therefore,

3res(T ) -5 = n = 3 i=1 |U i | + 1.

By expression (1) we have |U

i | + 1 ≤ res(T ) -1 which leads to |U i | = res(T ) -2 for 1 ≤ i ≤ 3.
Clearly, the induced subgraph U i is a path in T for every 1 ≤ i ≤ 3. Indeed, if it were the case that two vertices x, y ∈ U i verify that d(u, x) = d(u, y), then the set U j ∪ U k ∪ {u} for i = j = k would not be a resolving set; a contradiction with |U j | + |U k | + 1 = 2res(T ) -3 ≥ res(T ) since, by Theorem 2.5, res(T ) ≥ 3. Hence, T is a tree which consists of three paths of length res(T ) -2 attached at a single vertex, i.e., T ∼ = S a,a,a with a = res(T ) -2 ≥ 1. ✷

Maximum degree

Jannesari and Omoomi (2011a) proved that ∆(G) ≤ 2 r-1 + r + 1 for r = res(G). Here, we improve this exponential bound providing a linear bound.

Proposition 3.7 If G is neither a path nor a cycle then

∆(G) ≤ 3res(G) -4 if g(G) = 3, res(G) if g(G) > 3,
and both bounds are tight.

Proof: Proposition 3.5 gives the bound for g(G) = 3 since ∆(G) ≤ n -1. The wheel graph W 1,5 (see Figure 1) attains the bound. Suppose now that g(G) > 3. Let u 0 be a vertex of degree ∆(G), and u 1 , u 2 ∈ N (u 0 ). Clearly, the induced subgraph N [u 0 ] is a star on ∆(G)+1 vertices (otherwise G would contain a triangle). Then, no vertex of S = N [u 0 ] \ {u 1 , u 2 } resolves the pair {u 1 , u 2 } and so S is not a resolving set of G. Therefore, |S| = ∆(G) -1 ≤ res(G) -1. The star K 1,a on a + 1 vertices proves that the bound is tight since res(K 1,a ) = ∆(K 1,a ) = a.

✷

We now show that only stars attain the bound when restricting the preceding result to trees.

Proposition 3.8 If T is a tree of order n that is not a path then ∆(T ) ≤ res(T ), and equality holds if and only if T is isomorphic to a star K 1,a with a = res(T ) ≥ 3.

Proof: The fact that ∆(T ) ≤ res(T ) follows immediately from Proposition 3.7 since g(T ) is defined to be infinity. Also, as mentioned above res(K 1,a ) = ∆(K 1,a ) = a. Thus, it suffices to prove that a tree T (not being a path) with ∆(T ) = res(T ) is isomorphic to K 1,a with a = res(T ) ≥ 3. Let u 0 be a vertex of degree ∆(T ), and N [u 0 ] = {u 0 , u 1 , ..., u ∆(T ) } its closed neighbourhood. Suppose that there is a vertex u ∈ V (T ) such that d(u, u 0 ) = 2. Assume, without loss of generality, that u ∈ N (u 1 ). Then, the set S = (N [u 0 ] \ {u 2 , u 3 }) ∪ {u} is not a resolving set since the pair {u 2 , u 3 } is resolved by no vertex of S. This contradicts |S| = ∆(T ) = res(T ) and so there does not exist such a vertex u, which implies that T is a star K 1,a with a = ∆(T ) = res(T ) ≥ 3. ✷ 4 Characterization of the graphs G with res(G) = 3

As a natural extension of Theorem 2.5, we now determine all graphs with resolving number 3 using as main tools the relations obtained in Section 3. We begin with three technical lemmas.

Lemma 4.1 If g(G) = ∆(G) = res(G) = 3 then G ∈ F 1 .
Proof: Let C = (u 1 , u 2 , u 3 ) be a cycle in G. Suppose first that δ(u 1 ) = 3 and δ(u 2 ) = δ(u 3 ) = 2, and let u ∈ N (u 1 ) \ {u 2 , u 3 }. Clearly n = 4, since otherwise no vertex v ∈ N (u) \ {u 1 } resolves the pair {u 2 , u 3 } and so the set {u 1 , u, v} is not a resolving set, contradicting res(G) = 3. Therefore, G ∼ = G 1 ∈ F 1 . Recall that the set of graphs F 1 is illustrated in Figure 1. Assume now that δ(u 1 ) = δ(u 2 ) = 3 and δ(u 3 ) = 2. We distinguish two cases.

Assume now that w ∈ N (u) (analogous for w v, w}). Arguing as above, we conclude that x / ∈ N (u i ) for every 1 ≤ i ≤ 3, and so either x ∈ N (w) or x ∈ N (v). In both cases, one reaches a contradiction with res(G) = 3. Indeed, if x ∈ N (w) then d(x, u 1 ) = d(x, v) = 3 since there is no 5-cycle going through u other than C. This implies that {u, w, x} is not a resolving set. A similar reasoning gives that {u, v, x} is not a resolving set when x ∈ N (v).

∈ N (v)). If n = 7 then G ∼ = G 12 ∈ F 2 . When n ≥ 8, there is a vertex x ∈ V (G) \ (N [u 0 ] ∪ {u,
Case 2. Suppose that there are exactly two different 5-cycles through u 0 , say

C 1 = (u 0 , u 1 , u, v, u 2 ) and C 2 = (u 0 , u 2 , u ′ , v ′ , u 3 ). If n = 8 then G ∼ = G 13 ∈ F 2 . Otherwise, there exists a vertex w ∈ V (G) \ (C 1 ∪ C 2 ).
Distinguishing cases according to the adjacencies of w, we next give a set S with |S| = 3 that is not a resolving set; a contradiction with res(G) = 3. One only has to note that: (1) u 0 belongs to exactly two 5-cycles, (2) two 5-cycles share at most one edge, (3) the number of 5-cycles through u 0 is maximum.

If w ∈ N (u 1 ) (analogous for w ∈ N (u 3 )) then no vertex of S = {u 0 , u 1 , u 3 } resolves the pair {u, w}. If w ∈ N (u) (similar for w ∈ N (v ′ )) then the pair {u 0 , u 2 } is resolved by no vertex of S = {u, v ′ , w}. Finally, if w ∈ N (v) (analogous for w ∈ N (u ′ )) then no vertex of S = {u 2 , v, u ′ } resolves {u, w}.

Case 3. There are three different 5-cycles C i , 1 ≤ i ≤ 3, through u 0 : By Proposition 3.5, n = 10. Moreover, arguing as above one can easily prove that the set E(G) contains no edges other than those of the three cycles

C i . Therefore, G ∼ = G 14 ∈ F 2 . ✷ G 11 G 12 G 13 G 14
Fig. 3: The set of graphs F2.

We are now ready for proving the main result in this section.

Theorem 4.4 res(G) = 3 if and only if G is an even cycle, the star K 1,3 or G ∈ F 1 ∪ F 2 .

Proof: It is easy to check that even cycles, K 1,3 and all graphs of F 1 ∪ F 2 have resolving number 3. Consider now a graph G with res(G) = 3. By Theorem 2.5, G is neither a path nor an odd cycle. We can also assume that G is not an even cycle (otherwise the result follows).

Proposition 3.7 yields ∆(G) ≤ 5. Moreover, ∆(G) > 2 since the only connected graphs with maximum degree 2 are paths and cycles.

Suppose first that ∆(G) = 3. If G is a tree, by Proposition 3.8, we have G ∼ = K 1,3 . Otherwise, Proposition 3.2 gives g(G) ≤ 5. Lemmas 4.1 and 4.3 lead to G ∈ F 1 and G ∈ F 2 when g(G) = 3 and g(G) = 5, respectively. Moreover, g(G) = 4. Indeed, suppose on the contrary that g(G) = 4 and let C = (u 1 , u 2 , u 3 , u 4 ) be a minimum cycle in G. Assume that δ(u 1 ) = 3 and so there is a vertex u ∈ N [u 1 ] \ C. Hence, no vertex of the set {u 1 , u 3 , u} resolves the pair {u 2 , u 4 }, which contradicts res(G) = 3.

By Lemma 4.2, we obtain G ∈ F 1 when ∆(G) = 4. Assume, finally, that ∆(G) = 5, and let u ∈ V (G) with δ(u) = 5. Since res(G) = 3, by Lemma 3 of Jannesari and Omoomi (2011a), we have that the induced subgraph N (u) is a 5-cycle. Then g(G) = 3 and, by Proposition 3.5, it follows that n = 6. Therefore, G is isomorphic to the wheel graph W 1,5 ∈ F 1 . ✷

Concluding remarks

In this paper, we have studied a graph parameter related to the metric dimension: the resolving number. We first establish an important difference between both parameters: res(G) is polynomial-time computable while computing dim(G) is NP-hard (see [START_REF] Khuller | Landmarks in graphs[END_REF]). We then relate the resolving number to classical graph parameters, and characterize the graphs with resolving number 3 by using those relations.

As it was said before, our study follows the same vein as several papers on metric dimension, and most of our results either improve relationships obtained in other papers or continue with the studies developed in them.

Although we provide an O(n 3 ) time algorithm for computing the resolving number of an arbitrary graph, it would be interesting to find the exact computational complexity of this parameter, even in specific families of graphs. Also, the non-tight upper bounds of Proposition 3.5 could be improved. Moreover, we use very small examples (the graph G 14 in Figure 3 and the wheel graph W 1,5 in Figure 1) to show the tightness of two bounds given in Propositions 3.5 and 3.7, respectively, and so it appears that they are not tight for large enough values of res(G). Finally, the problem of characterizing the graphs with fixed resolving number a ≥ 4 remains open.

Proposition 2. 1

 1 The resolving number of a graph G is given byres(G) = max x,y∈V (G) |R(x, y)| + 1. Proof: Let us denote m = max x,y∈V (G) |R(x, y)|. Clearly, every set S ⊆ V (G) with |S| > m is a resolving set of G (otherwisethere would be a pair {x, y} such that S ⊆ R(x, y) and so m < |S| ≤ |R(x, y)| ≤ m). Hence, res(G) ≤ m + 1. On the other hand, there is at least one pair {x, y} for which |R(x, y)| = m, and R(x, y) is not a resolving set of G. Then, res(G) ≥ m + 1. ✷ Corollary 2.2 The resolving number res(G) can be computed in polynomial time in the order of G.

Proposition 3. 1

 1 If T is a tree that is not a path then d(T ) ≤ 2res(T ) -4, and equality holds if and only if T ∼ = S a,b,b with b = res(T ) -2 and a ≤ b.

  Consider the induced subgraph H = {u, v, w} . If |E(H)| ∈ {0, 1}, say E(H) = {{u, v}} for |E(H)| = 1, then no vertex of S = {u 1 , u 3 , u, v} resolves the pair {u 4 , w}. If |E(H)| ∈ {2, 3} (assume E(H) = {{u, v}, {v, w}} for |E(H)| = 2) then no vertex of S = {u 2 , u 3 , u, w} resolves the pair {u 1 , v}. When N (w) ∩ K = {u 2 , u 4 }, we obtain the graphs G 3 and G 4 for |E(H)| = 0 and |E(H)| = 3, respectively. If |E(H)| ∈ {1, 2}, say E(H) = {{u, v}} or E(H) = {{u, v}, {v, w}}, then either {u 2 , u 3 , u, w} or {u 1 , u 2 , v, w} is not a resolving set; a contradiction with r = 4. ✷

Partially supported by projects 2009/FQM-164 and 2010/FQM-164. Partially supported by projects 2009/FQM-164 and 2010/FQM-164. § Email: almar@us.es. Partially supported by the ESF EUROCORES programme EuroGIGA ComPoSe IP04 MICINN Project EUI-EURC-2011-4306, and projects 2009/FQM-164 and 2010/FQM-164. 1365-8050

Case 1. N (u 1 )∩N (u 2 ) = {u 3 }: Let N (u 1 ) = {u 2 , u 3 , u} and N (u 2 ) = {u 1 , u 3 , v}. Since g(G) = 3, by Proposition 3.5, we have n ≤ 6. If n = 5 then G is isomorphic to either G 2 or G 3 (both in F 1 ). If n = 6 then there is a vertex w ∈ (N (u) ∪ N (v)) \ {u 1 , u 2 }. Further, w ∈ N (u) ∩ N (v) (otherwise either {u 1 , u, w} or {u 2 , v, w} is not a resolving set). Hence, G is isomorphic to either G 4 or G 5 (both contained in F 1 ).

Case 2. N (u 1 ) ∩ N (u 2 ) = {u 3 , u}: If it were the case that n ≥ 5 then there would be a vertex v ∈ V (G) such that N (u) = {u 1 , u 2 , v}, and the set {u 3 , u, v} would not be a resolving set. Therefore, n = 4 and so

Moreover, arguing as in Case 2 (when n ≥ 5), we deduce that it cannot be the case that two of the u i 's, say

Clearly, the size of the induced subgraph H = {u, v, w} is either 3, 1 or 0. Indeed, if |E(H)| = 2, say E(H) = {{u, v}, {u, w}}, then S = {u 2 , u, w} is not a resolving set since no vertex of S resolves the pair {u 1 , v}.

Proof: Let u 0 ∈ V (G) be a vertex with δ(u 0 ) = 4. By Lemma 4 of Jannesari and Omoomi (2011a), the induced subgraph N (u 0 ) is a path, say (u 1 , u 2 , u 3 , u 4 ). Then g(G) = 3 and, by Proposition 3.5, either n = 5 or n = 6.

Only when δ(u) = 2 and N (u) is either {u 1 , u 4 } or {u 2 , u 3 } we obtain two possible graphs G which are contained in F 1 : the graphs G 9 and G 10 (see Figure 1). In the remaining cases, we next specify a set S with |S| ≥ 3 that is not a resolving set, obtaining a contradiction. If δ(u) = 1, take S = {u 0 , u 1 , u} for N (u) = {u 1 }, and S = {u 0 , u 2 , u} for N (u) = {u 2 } (analogous for N (u) = {u 4 } and N (u) = {u 3 }). If δ(u) = 2, consider S = {u 2 , u 4 , u} for N (u) = {u 1 , u 2 }, and S = {u 0 , u 2 , u} for N (u) = {u 1 , u 3 } (similar for N (u) = {u 3 , u 4 } and N (u) = {u 2 , u 4 }). Finally, if δ(u) ≥ 3 take S = N (u). ✷

Consider now the set of graphs F 2 shown in Figure 3.

Proof: We first observe that any two different 5-cycles in G meet in at most one edge. Indeed, suppose on the contrary that there are two 5-cycles meeting in two edges e, e ′ ∈ E(G). Since g(G) = 5, one can easily check that the edges e, e ′ must be consecutive, and then the set formed by the three end vertices of e, e ′ is not a resolving set, which contradicts res(G) = 3. Consider now a vertex u 0 ∈ V (G) with δ(u 0 ) = 3 and such that the number of 5-cycles through u 0 is maximum. Let N (u 0 ) = {u 1 , u 2 , u 3 }. We distinguish three cases.

Case 1. Suppose that there exists a unique 5-cycle through u 0 , say

Clearly, w / ∈ N (u i ) for 1 ≤ i ≤ 3: the sets {u 0 , u 1 , w}, {u 0 , u 2 , w}, {u 0 , u 3 , w} would not be resolving sets if it were the case that w is adjacent to, respectively, u 1 , u 2 , u 3 (recall that u 0 belongs to exactly one 5-cycle).