# Interstellar extinction correction in ionised regions using HeI lines

S. Zamora,1,2 Ángeles I. Díaz,1,2, Elena Terlevich3, Vital Fernández4,5
1Departamento de Física Teórica, Universidad Autónoma de Madrid, 28049 Madrid,
Spain
2CIAFF, Universidad Autónoma de Madrid, 28049 Madrid, Spain
3Instituto Nacional de Astrofísica, Óptica y Electrónica (INAOE), Mexico
4Departamento de Astronomía, Universidad de La Serena, Av. Juan Cisternas 1200
Norte, La Serena, Chile
5Instituto de Investigación Multidisciplinar en Ciencia y Tecnología,
Universidad de La Serena, Raúl Bitrán 1305, La Serena, Chile
E-mail<EMAIL_ADDRESS>fellow of Ministerio de Educación y Ciencia,
SpainVisiting Professor, UAM, MadridVisiting Astronomer, IoA, Cambridge, UK

(Accepted 2022 July 28. Received 2022 July 22; in original form 2022 February
7)

###### Abstract

The logarithmic extinction coefficient, c(H$\beta$), is usually derived using
the H$\alpha$/H$\beta$ ratio for case B recombination and assuming standard
values of electron density and temperature. However, the use of strong Balmer
lines can lead to selection biases when studying regions with different
surface brightness, such as extended nebulae, with the use of single integral
field spectroscopy observations, since, in some cases, the H$\alpha$ line can
be saturated in moderate to long exposures. In this work, we present a method
to derive extinction corrections based only on the weaker lines of HeI, taking
into account the presence of triplet states in these atoms and its influence
on recombination lines. We have applied this procedure to calculate the
extinction of different regions of the 30 Doradus nebula from MUSE integral-
field spectroscopy data. The comparison between helium and hydrogen
c(H$\beta$) determinations has been found to yield results fully compatible
within the errors and the use of both sets of lines simultaneously reduces
considerably the error in the derivation.

###### keywords:

H II regions: Interstellar Medium (ISM), Nebulae – galaxies: Magellanic
Clouds, ISM – techniques: imaging spectroscopy, Astronomical instrumentation,
methods, and techniques – ISM: abundances

††pubyear: 2020††pagerange: Interstellar extinction correction in ionised
regions using HeI lines–LABEL:lastpage

##  1 Introduction

The study of the chemical abundances of giant extragalactic HII regions (GEHR)
provides most of our knowledge of these abundances in external galaxies.
However their accurate determination requires the detection and measurement of
temperature dependent weak emission lines. If that is not possible, different
calibrations of mainly oxygen abundances have been proposed, none of them
entirely satisfactory and producing abundance derivations with errors of
0.2-0.3dex (a recent summary of this can be found in Díaz & Zamora (2022) and
a comparison of the different calibrations used is given in Pérez-Montero &
Díaz (2005)). This precludes any spatial study of chemical inhomogeneity
across HII regions.

During many years observations of GEHR regions have been obtained with the use
of long slit spectroscopy and have been focused only in the brightest regions,
hence integrated spectra have been weighted by luminosity and/or surface
brightness. Thus, up to now, HII regions have been usually typified by only
their brightest regions although it is widely recognised that the underlying
assumption that the physical conditions and abundances of the brightest part
of a nebula are representative of the whole entity, still remains
questionable. In fact, low surface brightness regions are rarely observed and
there are few studies of spatially resolved HII regions from long slit
observations (but see, for example NGC 5471 in M101 by Skillman (1985); NGC
604 in M33 by Diaz et al. (1987) and Maíz-Apellániz et al. (2004); and 30
Doradus by Rosa & Mathis (1987)). Now with the use of integral field
spectroscopy (IFS) this can be done much more easily so that we can learn
about variations of physical conditions throughout an entire nebula (García-
Benito et al., 2010; López-Hernández et al., 2013), provided we can obtain all
the elements to do it, for which an essential step is the interstellar
extinction correction of the observed emission line fluxes from which the
gaseous physical conditions, electron density and temperature, and the
elemental abundances are derived.

Interstellar extinction is generated by the scatter and absorption of photons
by the medium between the observer and the radiation source. It is produced by
dust grains and gas present in the interstellar medium and it is proportional
to the gas column in the line of sight. This mechanism, Mie scattering, is
effective in photons with wavelengths comparable to the size of grains and is
less efficient in photons of longer wavelengths. Thus, the effect is dependent
on wavelength and the radiation of the source appears reddened.

The correction of the observed line fluxes for this effect is an indispensable
preliminary step for the physical interpretation of the data. The total
extinction at the corresponding wavelength can be calculated by comparing the
flux of lines with the continuum radio-frequency emission. Another correction
method is to compare known intensity ratios of different emission lines which
have a low dependence on physical conditions, essentially density and
temperature. This procedure provides a differential extinction between the
lines used. Through the years, different methods to determine relative line
extinction affecting observations have been proposed:

(i) Calculating the ratio of two forbidden lines from the same upper set of
levels (e.g. sulphur two forbidden line, Miller, 1968). This procedure has two
main problems: the involved lines are moderately weak and the wavelength range
is very wide, hence it is not usually covered by a simultaneous observation.

(ii) Comparing hydrogen recombination lines from two different series, for
example, Balmer and Paschen, arising from the same upper level. Under this
condition, the line intensity ratios depend mainly on their transition
probabilities, i.e. the Einstein coefficients, and the gas physical conditions
are not relevant. This method is excellent because the involved line ratios
are almost constant for the typical range of nebular temperatures and
densities observed in HII regions (see Tab. 4.4 of Osterbrock & Ferland,
2006), the most important disadvantage being the large difference between the
series intensities, which implies additional errors in the extinction
determinations.

(iii) Comparing two hydrogen recombination lines from the same series, even if
they do not originate from same upper level. This is the case of
H$\alpha$/H$\beta$, H$\beta$/H$\gamma$, etc. The lines are present in all
regions of nebulae and they are sufficiently strong. This method is the most
widely used to correct emission line intensities for interstellar absorption.
Some assumptions about the recombination theory scheme are required, as well
as the previous knowledge of the theoretical line ratios employed. Although
these ratios depend on the density and electron temperature of the nebula,
this dependence is rather weak (see Tab. 4.2 of Osterbrock & Ferland, 2006)
and therefore the method constitutes an acceptable approach.

However, due to the fact that some of the already existing spectrographs and
others coming up in the future, encompass a wavelength range not including
hydrogen Balmer lines other than H$\beta$ and H$\alpha$, the reddening
constant determination relies only on the ratio between these two lines with
the former one being, in many cases, heavily affected by underlying stellar
absorption, and thus producing a very uncertain extinction correction. In this
case adding the HeI recombination lines to the analysis can provide a much
more reliable determination.

Also in the case of extended nebulae IFS provides images showing a very large
dynamical range of surface brightness hence, in many cases, it is not possible
to analyse the region in its full extent using a single exposure: a shorter
one has a good S/N in the strong nebular emission lines, including both
H$\alpha$ and H$\beta$, but the weak emission lines, as for example the
auroral electron temperature sensitive lines crucially needed for the
determination of the physical conditions of the gas, can be measured with a
reasonable S/N only for the brightest filaments. On the other hand, in longer
exposures, these weak lines can be detected and measured easily, but the
strongest lines, including H$\alpha$, are often saturated, not allowing the
determination of the extinction if only the hydrogen lines are used. In this
second case, we propose the use of HeI lines to derive the reddening constan
despite the fact that the HeI lines are weaker, since it circumvents
saturation effects.

In this work we present a method to derive the logarithmic extinction
coefficient at optical wavelengths using the emission lines of HeI checking
for consistency between the proposed method and the commonly used procedure of
using HI Balmer recombination lines and showing that, in fact, both sets of
lines can be used jointly providing a reliable determination. Section 2
addresses the theoretical aspects involved in the methodologyand is included
for the benefit of the reader not familiar with the atomic physics involved.
Section 3 provides an application of the method based on observations of the
central part of the very well studied GEHR 30Dor in the Large Magellanic Cloud
(LMC) obtained with the MUSE spectrograph attached to the VLT telescope. Our
results are presented and discussed in Section 4 and finally the summary and
conclusions are presented in Section 5.

##  2 Theoretical analysis

###  2.1 Theoretical context

Fig. 1 shows the energy level structure of the HeI atom. It is similar to that
of hydrogen except that there are no sub-level degeneracies with different
angular momentum for HeI.

Figure 1: Levels’ structure of HeI. The left diagram is to singlet states and
the right is to triplet stages. We have highlighted lines that we have
analysed in this study.

The He atom is a two-electron system and it has singlet and triplet levels.
For singlet states, radiative recombination transitions cascade down to the
21P and 21S levels. These are the characteristics of the produced transitions:
(i) The 21P level involves $\lambda\lambda$4922, 5048, 6678 and 7281 Å lines.
Its deexcitation can occur by two mechanisms: the emission of an infrared
photon (21P$\rightarrow$21S transition) or the emission of a L$\alpha$ photon
( 21P$\rightarrow$11S transition) with their relative probabilities being
given by the ratio of their Einstein coefficients, A($2^{1}P,\
1^{1}S$)/A($2^{1}P,\ 2^{1}S)$ $\sim$ 1000, i. e. for every 1000 Ly$\alpha$
photons, 1 infrared photon is generated. In addition, since the cross-section
of hydrogen atoms at the energy of the HeI Ly$\alpha$ photon is large,
(a21.3eV(H) $\sim$ 1.5$\cdot$10-18 cm-2) its absorption by an HI atom is more
probable than 1000 Ly$\alpha$ absorptions and re-emissions. We can therefore
assume that this last one is the dominant process, it is optically thick and
the case B recombination is an appropriate approximation. (ii) The
21S$\rightarrow$11S transition producing the $\lambda$5016 Å line occurs
through the emission of two continuum photons (20.7 eV) with the relative
probability of one of them having an energy equal to or higher than 13.6 eV
being 0.56. Therefore, it would be able to ionize H and contribute to the
diffuse radiation field.

For triplet states, radiative recombination cascades down to the 23S
metastable level. The decay of these electrons to the fundamental level 11S is
forbidden, with probability of A(23S, 21S) = 1.26$\cdot$10-4s-1 (Osterbrock &
Ferland, 2006). The 23S level can be collisionally depopulated to the singlet
levels 21S and 21P, with a high probability (and with a spin change). The
depopulation to the 11S level is also possible but with very low probability.
The critical electron density for this process to occur, nc(23S), is defined
as the balance between the probability of radiative and collisional
transitions:

$n_{c}(2^{3}S)=\frac{A(2^{3}S,\ 1^{3}S)}{C(2^{3}S,\ 2^{1}S)+C(2^{3}S,\
2^{1}P)}$ (1)

where A and C are the corresponding Einstein and collisional coefficients
respectively. Values of C(23S, 21S) and C(23S, 21P) range from 1.95$\cdot$10-8
cm3s-1 to 2.68$\cdot$10-8 cm3s-1 and 2.34$\cdot$10-9 cm3s-1 to 9.81$\cdot$10-9
cm3s-1 respectively for temperatures between 6000 and 25000 K (see Tab. 2.5 of
Osterbrock & Ferland, 2006). Therefore the critical electron density ranges
from 6.2 $\times$ 103 cm-3 to 3.34 $\times$ 103 cm-3. In HII regions, the
electron density is usually of the order of 102cm-3 and lower than nc, thus
radiative transitions dominate.

However, even at lower densities, ne < nc(23S), the collisional contribution
can play a significant role for several lines. This is the case of the
$\lambda$7065 Å line for which the ratio of collisional to recombination
contributions is 0.152 as compared to the value of 0.054 found for the
$\lambda$5876 Å line. For singlet lines, collisional corrections are 0.013,
0.015, <0.01, 0.016 and 0.054 for the $\lambda\lambda$ 4922, 5016, 5048, 6678
and 7281 Å lines respectively (Benjamin et al., 1999, T = 20000K and ne =
100cm-3) calculated using the radiative cascade rates of Smits (1996) and the
collisional rates of Sawey & Berrington (1993).

Additionally, since 23S is a metastable level, the effect of radiative
transfer can also be important in this study. A large population of electrons
in this level can generate a significant optical depth, particularly in
n3P$\rightarrow$23S transitions, and the revision of the assumption of Case B
recombination is necessary. For instance, members of the n3P series can be
transformed into members of other series (n3S and n3D). This effect increases
with the number of electrons in the 23S level, which depends directly on the
probability of their transition to levels 21S and 21P, requiring threshold
energies of 0.9 eV and 1.5 eV respectively. We can define the optical depth
factor to radiative transfer for a given line, fline(T, ne, $\tau$), as the
ratio between the emissivity of the line for given values of T, ne and $\tau$
and the emissivity for the same T and n but with $\tau$ = 0. Even for
densities as high as ne = 108 cm-3, the optical depth factor on singlet lines
is less than 0.4% at worst and for the $\lambda$5876 Å line (T = 10000 K, ne =
100 cm-3, $\tau$ = 100) takes an accepted value of 1%. Nevertheless, the
$\lambda$7065 Å line shows a strong dependence on this effect, of almost 4%
(Benjamin et al., 2002).

###  2.2 Interstellar extinction correction using the ratio of two
recombination lines

Light is absorbed as it travels through the interstellar medium in such a way
that the observed flux of each spectral emission line follows the equation:

$F_{\lambda}=I_{\lambda}\cdot 10^{-0.4\cdot A_{\lambda}}$ (2)

where Fλ and Iλ are the observed and emitted fluxes at wavelength $\lambda$
and Aλ is the corresponding extinction in magnitudes along the observing path.
Written as a function of the optical depth, $\tau_{\lambda}$:

$F_{\lambda}=I_{\lambda}\cdot e^{-\tau_{\lambda}}$ (3)

where $\tau_{\lambda}$ depends on wavelength and the physical properties of
the medium, i. e. the column density of absorbing dust grains and the
extinction cross-section per particle. This is expressed by means of an
extinction curve which gives $\tau_{\lambda}=C\cdot f(\lambda)$.

The observed flux can be normalised to the flux of a reference line. For
extinction corrections derived from HI lines, the reference line is usually
H$\beta$ and therefore the value of the logarithmic extinction curve at this
wavelength is null, f(H$\beta$) = 0. With this normalisation, equation 3 is
written as:

$\frac{F_{\lambda}}{F_{H\beta}}=\frac{I_{\lambda}}{I_{H\beta}}\cdot
10^{-0.434\cdot C(f(\lambda)-f(H\beta))}$ (4)

For extinction corrections derived from HeI lines we propose to use as
reference line the HeI $\lambda$6678 Å line, the most prominent of the singlet
levels. In this case, for equation 3 we obtain:

$\frac{F_{\lambda}}{F_{HeI\lambda 6678}}=\frac{I_{\lambda}}{I_{HeI\lambda
6678}}\cdot 10^{-0.434\cdot C(f(\lambda)-f(HeI\lambda 6678))}$ (5)

The logarithmic extinction coefficient, c(H$\beta$), is the reddening constant
defined as c(H$\beta$) = 0.434$\cdot$ C. With this definition, equations 4 and
5 are given by:

$\frac{F_{\lambda}}{F_{H\beta}}=\frac{I_{\lambda}}{I_{H\beta}}\cdot
10^{-c(H\beta)(f(\lambda)-f(H\beta))}$ (6) $\frac{F_{\lambda}}{F_{HeI\lambda
6678}}=\frac{I_{\lambda}}{I_{HeI\lambda 6678}}\cdot
10^{-c(H\beta)(f(\lambda)-f(HeI\lambda 6678))}$ (7)

The final logarithmic extinction coefficient can be calculated as:

$c(H\beta)=-\frac{1}{f(\lambda)-f(H\beta)}\cdot\left[log\left(\frac{F_{\lambda}}{F_{H\beta}}\right)-log\left(\frac{I_{\lambda}}{I_{H\beta}}\right)\right]$
(8)

for the hydrogen, with f(H$\beta$) = 0, and

$\begin{split}c(H\beta)=&-\frac{1}{f(\lambda)-f(HeI\lambda 6678)}\cdot\\\
&\cdot\left[log\left(\frac{F_{\lambda}}{F_{HeI\lambda
6678}}\right)-log\left(\frac{I_{\lambda}}{I_{HeI\lambda
6678}}\right)\right]\end{split}$ (9)

for the helium correction method.

Line | f($\lambda$)a | Iλ/Iref b
---|---|---
H$\beta$ | 0 | 1.000
HeI $\lambda$4922 Å | -0.014 | 0.345
HeI $\lambda$5875 Å | -0.209 | 3.518
H$\alpha$ | -0.313 | 2.863
HeI $\lambda$6678 Å | -0.329 | 1.000
HeI $\lambda$7065 Å | -0.377 | 0.621
HeI $\lambda$7281 Å | -0.402 | 0.187
Pa17 | -0.514 | 0.004
Pa16 | -0.518 | 0.004
Pa15 | -0.521 | 0.005
Pa14 | -0.525 | 0.007
Pa13 | -0.531 | 0.008
Pa12 | -0.537 | 0.011
Pa11 | -0.546 | 0.014
Pa10 | -0.557 | 0.018
Pa9 | -0.572 | 0.025

  * •

a Miller & Mathews (1972), Rv = 3.2 .

  * •

b Luridiana et al. (2015), ne(cm-3) = 102, T(K) = 104.

Table 1: Empirical values of the normalised logarithmic extinction at the
wavelengths of the different HeI emission lines from Miller & Mathews (1972),
and the ratio of these lines to the $\lambda$ 6678 Å reference line as
calculated by the PyNeb (Luridiana et al., 2015) tool for T= 104 K and ne= 102
cm-3, using Storey & Hummer (1995) and Porter et al. (2012) atomic data for
hydrogen and helium respectively.

The values of f($\lambda$) and the theoretical ratios between the different
helium and hydrogen lines and the reference ones at $\lambda$ 6678 Å and
H$\beta$ respectively are given in Tab. 1.

###  2.3 Interstellar extinction correction using a linear regression

Equations 6 and 7 can be edited as:

$log_{10}\left(\frac{F_{\lambda}}{F_{H\beta}}\right)-log_{10}\left(\frac{I_{\lambda}}{I_{H\beta}}\right)=-c(H\beta)(f(\lambda)-f(H\beta))$
(10)

$\begin{split}log_{10}\left(\frac{F_{\lambda}}{F_{HeI\lambda
6678}}\right)&-log_{10}\left(\frac{I_{\lambda}}{I_{HeI\lambda
6678}}\right)=\\\ &=-c(H\beta)(f(\lambda)-f(HeI\lambda 6678))\end{split}$ (11)

These equations are equivalent for the same reddening curve normalisation (in
this case, f(H$\beta$) = 0). The difference between the observed and
theoretical logarithmic ratios constitutes the dependent variable, the
normalised logarithmic extinction at each wavelength represents the
independent variable and the logarithmic extinction coefficient, c(H$\beta$)
is the slope of the fitting.

##  3 Observations and measurements

Field ID |  | RA
---
(hh:mm:ss)
| Dec
---
(dd:mm:ss)
Exp. time (s) | ESO project ID |  | Observation date
---
(yy-mm-dd, hh:mm:ss)
Seeing (”)
30Dor-A | 05:38:36.75 | -69:06:32.8 | 240 | 60.A-9351 | 2014-08-19, 08:54:50 | 1.240
30Dor-A | 05:38:36.73 | -69:06:32.8 | 2400 | 60.A-9351 | 2014-08-19, 09:10:05 | 1.262
30Dor-B | 05:38:47.37 | -69:06:32.8 | 240 | 60.A-9351 | 2014-08-22, 08:57:44 | 1.507
30Dor-B | 05:38:47.36 | -69:06:32.8 | 2400 | 60.A-9351 | 2014-08-22, 09:07:05 | 1.343
30Dor-C | 05:38:36.67 | -69:05:34.8 | 240 | 60.A-9351 | 2014-08-24, 08:46:09 | 1.499
30Dor-C | 05:38:36.66 | -69:05:34.8 | 2400 | 60.A-9351 | 2014-08-24, 08:55:31 | 1.415
30Dor-D | 05:38:47.44 | -69:05:34.8 | 240 | 60.A-9351 | 2014-08-25, 08:55:04 | 1.252
30Dor-D | 05:38:47.43 | -69:05:34.7 | 2400 | 60.A-9351 | 2014-08-25, 09:04:20 | 1.188
Table 2: Description of the observations.

We have used observations of the central part of 30 Dor obtained with the MUSE
spectrograph (Multi-Unit Spectroscopic Explorer Bacon et al., 2010, Program
ID: 60.A-93) to test the proposed method. Four fields have been analysed, each
of them having exposure times of 240 s and 2400 s, a Field of View (FoV) close
to 1.52’ and a pixel scale of 0.2". The observations were made on the 19th,
22nd, 24th, and 25th of August 2014 (see Tab. 2).

The IFU observations of this nebula provide simultaneously areas with very
different surface brightness. While in long slit observations high surface
brightness regions are preferentially observed and aperture effects are
important, the use of IFU data can circumvent these disadvantages.
Additionally, the extremely high quality of the chosen two sets of MUSE
observations makes them ideal for the purpose of comparing the two methods
described here for extinction derivation. The high S/N obtained in the weakest
lines from the long exposure cubes is comparable to the typical S/N of data
employed for the study of extinction in emission nebulae using strong
recombination lines. Also, the high spectral resolution of MUSE data (R $\sim$
1770 at 4800 Å and R $\sim$ 3590 at 9300) contributes to this critical aspect
increasing the S/N ratio linearly with the resolution.

We have made the region selection measuring the fluxes of strong and weak
emission lines in spectra extracted from the short (240 s) and long (2400 s)
exposure cubes respectively. These two approaches are complementary since in
the short exposure spectra the faint emission lines are almost undetectable in
low surface brightness regions, while strong lines are saturated in the long
exposure spectra of high surface brightness ones. Thus, H$\alpha$ and H$\beta$
emission lines have been measured from cubes with 240s of exposure time while
HeI and Paschen HI lines have been measured from 2400 s exposure cubes. Random
spectra have been extracted simulating a circular aperture of 1.5" diameter
that corresponds to the largest seeing value of the observations (see 2). The
area covered by the selected data amounts to more than 35% of the total area
covered by the 4 data cubes. To guarantee the star formation origin of the
extracted spectra we have imposed the requirements: EW(H$\alpha$) > 6 Å (Cid
Fernandes et al., 2010; Sánchez et al., 2015) and 2.7 < H$\alpha$/H$\beta$ < 6
(Osterbrock & Ferland, 2006, ne = 100 cm-3, Te = 104 K).

Figure 2: HeI and Paschen emission lines in the optical spectrum from data in
the 2400 s exposure. Upper panel is a zoom of the bottom panel to see weak
lines.

Fig.2 shows a typical spectrum extracted from the analysed cubes, marking the
HeI emission lines present in the wavelength range covered by the data (from
4800 to 9300 Å). Three lines have been discarded for the analysis: $\lambda$
5016 Å overlaps with [OIII]$\lambda$ 5007 Å, $\lambda$ 5048 Å is too weak, and
$\lambda$ 7065 Å suffers from optical depth and collisional excitation
effects. Finally, we have used the lines $\lambda$4922, $\lambda$5876,
$\lambda$6678, $\lambda$7281 Å of HeI, and H$\alpha$, H$\beta$ and Paschen
lines of HI, these latter ones for comparison purposes.

The line flux measurements have been performed as described next: (i) the
emission lines present in the spectrum have been masked with a width of $\pm$8
Å around the central wavelength of the line; (ii) a global continuum has been
adjusted fitting a second-order polynomial and the statistical dispersion of
the continuum, $\sigma_{c}$, has been calculated; (iii) we have assigned a
local continuum to each emission line to be measured, taking into account the
dispersion of the global continuum fitting,
$F_{c}(line)=F_{c}(\lambda)\pm\sigma_{c}$; (iv) finally, we have fitted a
Gaussian function according to the local continuum level. The stellar
absorption underlying the H$\alpha$, H$\beta$ and HeI lines has been corrected
using, in step (iv), a two-component Gaussian fit to reproduce simultaneously
emission and absorption in each line (see Díaz et al., 2007).

Flux errors have been calculated from the expression given in Gonzalez-Delgado
et al. (1994):

$\Delta[F_{\lambda}]=\sigma_{l}\cdot N^{1/2}[1+EW/(N\Delta)]^{1/2}$ (12)

where $\Delta[F]$ is the error in the line flux, $\sigma_{l}$ represents the
standard deviation in the continuum near each line, N is the number of pixels
used in the measurement of the line flux, EW is the line equivalent width and
$\Delta$ is the spectral dispersion (1.25 Å/pix). This expression takes into
account the photon statistics and the error in the continuum of each line. The
calculated errors have been propagated in quadrature for the rest of the
derived quantities.

We have assumed the Miller & Mathews (1972) law with a specific attenuation of
Rv = 3.2, case B of recombination and a simple screen distribution of dust.
The ratio of helium and hydrogen lines have been selected from the Tab. 1 and
references explained in the table.

##  4 Results and discussion

Table 3: Extraction parameters for emission line maps.

Line |  $\lambda_{c}$ (Å) |  $\Delta\lambda$ (Å) |  $\Delta\lambda_{left}$ (Å) |  $\Delta\lambda_{right}$ (Å)
---|---|---|---|---
H$\alpha$ | 6563 | 8 | 6523.0 - 6542.0 | 6596.0 - 6612.0
H$\beta$ | 4861 | 8 | 4827.5 - 4843.5 | 4892.4 - 4908.4
$[SIII]$ | 6312 | 8 | 6236.2 - 6252.2 | 6406.0 - 6422.0
HeI | 6678 | 8 | 6645.8 - 6661.8 | 6681.8 - 6697.8

  * •

All wavelengths are in rest frame.

We have constructed 2D maps from the observed data cubes. For the different
emission lines we have assumed a linear behavior of the continuum emission in
the region of interest choosing side-bands around each line of a given width.
Table 3 give the identification of each line in column 1, its central
wavelength, $\lambda_{c}$ in Å in column 2, its width, $\Delta\lambda$, in Å
in column 3, and the wavelength range of the two continuum side-bands, in Å in
columns 4 and 5. We have not taken into account the underlying stellar
absorption in HeI and HI lines since, in theis case,their contribution is
negligible.

Figure 3: H$\alpha$ (upper panels) and [SIII] $\lambda$ 6312 Å (lower panels)
line maps obtained from short (left) and long (right) exposure MUSE data.
Fluxes are given in units of $10^{-20}$ $erg/s/cm^{2}$. The white areas in the
upper right panel show the saturation effects in the H$\alpha$ line in the
long exposure frame. The lower left panel shows the practically non detection
of the [SIII] $\lambda$ 6312 Å (at the noise level) in the low surface
brightness region in the short exposure one.

Fig. 3 shows the selection effect due to the large dynamical range of
luminosity and surface brightness of GEHR in the two sets of constructed maps.
The images in the upper panels correspond to short (left) and long (right)
exposure images in the H$\alpha$ lines. The white colour indicates the areas
where the H$\alpha$ line is completely saturated and thus the value of the
extinction cannot be obtained, hence the emission line ratios cannot be
corrected for reddening. One might think the left image is good enough to
allow a good nebular analysis. However, the images in the lower panel, that
correspond to the weak auroral line of [SIII] at $\lambda$ 6312 Å, show a S/N
so low in the short exposure one (left) that, in many regions, the line cannot
even be detected, and so only the brighter regions can be fully analysed. On
the other hand, in the long exposure image (right) the S/N is more than
reasonable all across the frame showing that a complete characterization of
the gas can be made using only relatively weak emission lines if extinction
can be calculated without the use of the H$\alpha$ line, that is using HeI
lines instead.

Figure 4: Reference line maps for hydrogen and helium. Left: observed HeI
$\lambda$6678 Å flux. Right: observed H$\beta$ flux. All images are in
logarithmic scale. North is up and East is to the left. Fluxes are given in
units of $10^{-20}$ $erg/s/cm^{2}$. Figure 5: Linear regression of c(H$\beta$)
values from hydrogen lines, helium lines and both sets of lines together.
H$\alpha$ and HeI $\lambda$5875 Å errors are inside the symbols in the graph.

We have checked the spatial distribution of the H$\beta$ and HeI $\lambda$
6678 Å lines used for normalisation in the extinction derivation method (see
Fig. 4). Both maps show the same spatial distribution across the nebula and
very similar S/N. The pixel-by-pixel ratio of H$\beta$ to HeI $\lambda$6678 Å
calculated from the maps has a mean value of $\sim$ 20 with a standard
deviation of 5 which corresponds to a 0.113% and a 0.006% of the mean values
of the HeI $\lambda$6678 Å and H$\beta$ intensity maps respectively.

For short exposure spectra (240 s), we have used the ratio of the H$\alpha$
and H$\beta$ lines to derive the mean extinction (Eq. 8). The estimated mean
errors in the line fluxes are 0.92% for H$\beta$ and 0.15% for H$\alpha$,
producing values of c(H$\beta$) with an absolute mean error of 0.02. In the
case of the helium lines, the long exposure data (2400 s) have been used
choosing the two strongest HeI lines: $\lambda\lambda$ 5875 and 6678 Å with
associated mean errors of 0.37% and 1.37% respectively which yield values of
c(H$\beta$) with an absolute mean error of 0.05 (Eq. 9).

Fit | c(H$\beta$)
---|---
Hydrogen | 0.619 $\pm$ 0.018
Helium | 0.650 $\pm$ 0.050
Hydrogen and Helium | 0.632 $\pm$ 0.010
Table 4: Reddening constant values obtained from the fitting shown in Fig. 5
for a randomly selected emission region.

In order to minimise errors in the reddening constant determination, we have
fitted a linear regression using all the available H and HeI lines in Eqs. 10
and 11, following Díaz et al. (2007) for hydrogen. Fig. 5 shows an example of
the application of this method to the spectra of one selected emission region
extracted from two cubes of different exposure times (240 s and 2400 s). The
fits obtained for hydrogen lines, helium lines and all the lines together are
consistent with each other and the intercept is compatible with zero, with the
fit using all the lines yielding the smaller error for the c(H$\beta$)
determination (see Tab. 4). Although the error found using only the HeI lines
is larger than that using the HI lines, it should be taken into account that
the underlying stellar absorption is less important than in the case of
hydrogen analysis (see González Delgado et al., 2005; Aver et al., 2021). If
the underlying absorption were a critical issue in our work, a simultaneous
fit of decrements and stellar absorption could be done (see, for example
Izotov et al., 1994).

Also, in order to check the reliability of our results, we have introduced the
derived methodology in the Bayesian algorithm described in Fernández et al.
(2019) which simultaneously fits a 14 parameters chemical model, obtaining
results which are fully compatible with those reported here.

Finally, we have run a bootstrap model using random temperatures and densities
in order to evaluate the effect of these physical parameters on the HeI lines.
The bootstrap method is a statistic procedure that can be used to estimate
characteristics of a calculated parameter, like the mean or standard
deviation, resampling with replacement the involved variables. In this work we
have used 106 repeats and we have assumed a Gaussian distribution of density
with $\mu$ = 275.5 cm-3 and $\sigma$ = 75.16 cm-3, that correspond to
densities in a range from 50 to 500 cm-3 considering a 3$\sigma$ width. In the
case of temperatures, we have assumed a Gaussian distribution with $\mu$ =
11000 K and $\sigma$ = 1000 K, that correspond to a temperature range from
8000 K and 14000 K. We have computed the ratio of H$\alpha$/H$\beta$ and
$\lambda$5876 Å /$\lambda$6678 Å lines using PyNeb (Luridiana et al., 2015)
and atomic data from Storey & Hummer (1995) and Porter et al. (2012) for
hydrogen and helium respectively. The standard deviations for hydrogen and
helium results are 0.0185 and 0.0041 respectively and the lines ratio
distributions seem to be approximately gaussians. From these results, we can
conclude that the ratio of HeI lines are less affected by temperature and
density variations than the H$\alpha$/H$\beta$ ratio which represents another
important advantage of the proposed method.

On the other hand, as mentioned in section 2 there are some effects that need
to be taken into account, in particular collisional de-excitation, radiative
transfer and optical depth of some levels. Regarding the first, the
collisional contribution, before discarding the $\lambda$7065 Å line, is
within measurement errors and their effect is minimised in the fitting
procedure. This is also the case for the other two considered effects.

##  5 Summary and conclusions

In this article we have presented a method to derive the logarithmic
extinction coefficient at optical wavelengths using the emission lines of HeI.
The aim of this work has been two-folding. Firstly, due to the fact that some
of the already existing spectrographs and others coming up in the future,
encompass a wavelength range not including hydrogen Balmer lines other than
H$\beta$ and H$\alpha$, the reddening determination relies only on the ratio
between these two lines with the first of them being, in many cases, heavily
affected by underlying stellar absorption. In this case we propose adding the
HeI lines to the analysis in order to obtain a more reliable determination.
Secondly, IFS provides images of extended gaseous nebulae with a very large
dynamical range of surface brightness hence,in many cases, it is not possible
to analyse the region in its full extent using a single exposure since a short
one has a good S/N in strong nebular emission lines, including both H$\alpha$
and H$\beta$, but the weak emission lines needed for the determination of the
physical conditions of the gas can be measured only for the brightest regions.
On the other hand, in long exposures, these weak lines can be detected and
measured easily, thus providing a very complete characterisation of the gas,
but the strongest lines,including H$\alpha$, are saturated thus precluding the
determination of the extinction if only HI lines are used. In this case we
propose the use of HeI lines to obtain a good derivation of the reddening
constant.

The method has been tested on archive MUSE data of the 30 Doradus nebula
obtained with both short (240s) and long (2400s) exposure times. The reddening
curve has been normalised to HeI $\lambda$ 6678 Å and the calculations have
been done assuming Case B recombination, a simple screen distribution of dust
and the Miller & Mathews (1972) reddening law. We have compare the extinction
derived for randomly selected regions using the weaker lines at
$\lambda\lambda$ 4922, 5876, 6678, 7065 and 7281 Å from the long exposure data
and the ratio of the strong lines H$\alpha$ over H$\beta$ from the short
exposure ones.

The comparison of the logarithmic extinction at H$\beta$ obtained using HI and
HeI lines independently has proved both methods to be fully compatible within
the errors although, as expected, these are slightly larger when using the
weaker HeI lines. The errors in c(H$\beta$) get considerably reduced when both
sets of lines are jointly used. The proposed methodology has been easily
introduced into a Bayesian algorithm yielding results which are also
compatible with those obtained by traditional computations.The fact that HeI
and HI agree in the case of giant HII regions shows that none of the
complexities related to line optical depth effects, departures from Case B
recombination, or collisional excitation that might exist are important and
the situation is classical and simple.

The results presented here will allow to study spatially resolved nebulae in
their full extent, analysing both high and low surface brightness regions
simultaneously in a single moderate-to-long exposure pointing.

## Acknowledgements

Based on data products from observations made with ESO Telescopes at the La
Silla Paranal Observatory under programme ID 60.A-93. This research has been
supported by the former Spanish Ministry of Economy, Industry and
Competitiveness through the MINECO-FEDER research grant AYA2016-79724-C4-1-P,
and the present Spanish Ministry of Science and Innovation through research
grant PID2019-107408GB-C42. S.Z. acknowledges financial support from contract
BES-2017-080509 associated to grant AYA2016-79724-C4-1-P. V. F. acknowledges
support from FONDECYT Postdoc 2020 project 3200473 from the National Agency
for Research and Development (ANID). We would like to thank Roberto Terlevich
for the careful reading of this manuscript and his improvement suggestions and
also an anonymous referee who, with his/her comments, has helped to clarify
the aims of this work.

## Data Availability

The original data on which this article is based can be found in the ESO
Science Archive Facility from ESO telescopes at La Silla Paranal Observatory.

## References

  * Aver et al. (2021) Aver E., Berg D. A., Olive K. A., Pogge R. W., Salzer J. J., Skillman E. D., 2021, J. Cosmology Astropart. Phys., 2021, 027
  * Bacon et al. (2010) Bacon R., et al., 2010, The MUSE second-generation VLT instrument. p. 773508, doi:10.1117/12.856027
  * Benjamin et al. (1999) Benjamin R. A., Skillman E. D., Smits D. P., 1999, ApJ, 514, 307
  * Benjamin et al. (2002) Benjamin R. A., Skillman E. D., Smits D. P., 2002, ApJ, 569, 288
  * Cid Fernandes et al. (2010) Cid Fernandes R., Stasińska G., Schlickmann M. S., Mateus A., Vale Asari N., Schoenell W., Sodré L., 2010, MNRAS, 403, 1036
  * Díaz & Zamora (2022) Díaz Á. I., Zamora S., 2022, MNRAS, 511, 4377
  * Diaz et al. (1987) Diaz A. I., Terlevich E., Pagel B. E. J., Vilchez J. M., Edmunds M. G., 1987, MNRAS, 226, 19
  * Díaz et al. (2007) Díaz Á. I., Terlevich E., Castellanos M., Hägele G. F., 2007, MNRAS, 382, 251
  * Fernández et al. (2019) Fernández V., Terlevich E., Díaz A. I., Terlevich R., 2019, MNRAS, 487, 3221
  * García-Benito et al. (2010) García-Benito R., et al., 2010, MNRAS, 408, 2234
  * Gonzalez-Delgado et al. (1994) Gonzalez-Delgado R. M., et al., 1994, ApJ, 437, 239
  * González Delgado et al. (2005) González Delgado R. M., Cerviño M., Martins L. P., Leitherer C., Hauschildt P. H., 2005, MNRAS, 357, 945
  * Izotov et al. (1994) Izotov Y. I., Thuan T. X., Lipovetsky V. A., 1994, ApJ, 435, 647
  * López-Hernández et al. (2013) López-Hernández J., Terlevich E., Terlevich R., Rosa-González D., Díaz Á., García-Benito R., Vílchez J., Hägele G., 2013, MNRAS, 430, 472
  * Luridiana et al. (2015) Luridiana V., Morisset C., Shaw R. A., 2015, A&A, 573, A42
  * Maíz-Apellániz et al. (2004) Maíz-Apellániz J., Pérez E., Mas-Hesse J. M., 2004, AJ, 128, 1196
  * Miller (1968) Miller J. S., 1968, ApJ, 154, L57
  * Miller & Mathews (1972) Miller J. S., Mathews W. G., 1972, ApJ, 172, 593
  * Osterbrock & Ferland (2006) Osterbrock D. E., Ferland G. J., 2006, Astrophysics of gaseous nebulae and active galactic nuclei
  * Pérez-Montero & Díaz (2005) Pérez-Montero E., Díaz A. I., 2005, MNRAS, 361, 1063
  * Porter et al. (2012) Porter R. L., Ferland G. J., Storey P. J., Detisch M. J., 2012, MNRAS, 425, L28
  * Rosa & Mathis (1987) Rosa M., Mathis J. S., 1987, ApJ, 317, 163
  * Sánchez et al. (2015) Sánchez S. F., et al., 2015, A&A, 574, A47
  * Sawey & Berrington (1993) Sawey P. M. J., Berrington K. A., 1993, Atomic Data and Nuclear Data Tables, 55, 81
  * Skillman (1985) Skillman E. D., 1985, ApJ, 290, 449
  * Smits (1996) Smits D. P., 1996, MNRAS, 278, 683
  * Storey & Hummer (1995) Storey P. J., Hummer D. G., 1995, MNRAS, 272, 41


# Tree Embeddings and Tree-Star Ramsey Numbers

Zilong Yan  School of Mathematics, Hunan University, Changsha 410082, P.R.
China. Email<EMAIL_ADDRESS>Yuejian Peng  Corresponding author. School
of Mathematics, Hunan University, Changsha, 410082, P.R. China. Email:
<EMAIL_ADDRESS>Supported in part by National Natural Science Foundation of
China (No. 11931002). Zilong Yan  School of Mathematics, Hunan University,
Changsha 410082, P.R. China. Email<EMAIL_ADDRESS>Yuejian Peng
Corresponding author. School of Mathematics, Hunan University, Changsha,
410082, P.R. China. Email<EMAIL_ADDRESS>Supported in part by National
Natural Science Foundation of China (No. 11931002).

# Tree Embeddings and Tree-Star Ramsey Numbers

Zilong Yan  School of Mathematics, Hunan University, Changsha 410082, P.R.
China. Email<EMAIL_ADDRESS>Yuejian Peng  Corresponding author. School
of Mathematics, Hunan University, Changsha, 410082, P.R. China. Email:
<EMAIL_ADDRESS>Supported in part by National Natural Science Foundation of
China (No. 11931002). Zilong Yan  School of Mathematics, Hunan University,
Changsha 410082, P.R. China. Email<EMAIL_ADDRESS>Yuejian Peng
Corresponding author. School of Mathematics, Hunan University, Changsha,
410082, P.R. China. Email<EMAIL_ADDRESS>Supported in part by National
Natural Science Foundation of China (No. 11931002).

###### Abstract

We say that a graph $F$ can be embedded into a graph $G$ if $G$ contains an
isomorphic copy of $F$ as a subgraph. Guo and Volkmann [6] conjectured that if
$G$ is a connected graph with at least $n$ vertices and minimum degree at
least $n-3$, then any tree with $n$ vertices and maximum degree at most $n-4$
can be embedded into $G$. In this paper, we give a result slightly stronger
than this conjecture and obtain a sufficient and necessary condition that a
tree with $n$ vertices and maximum degree at most $n-3$ can be embedded into a
connected graph G with at least $n$ vertices and minimum degree at least
$n-3$. Our result implies that the conjecture of Guo and Volkmann is true with
one exception. We also give an application to the Ramsey number of a tree
versus a star.

Keywords: Tree, Embedding, Ramsey number, Tree-Star Ramsey number.

##  1 Introduction

All graphs considered throughout the paper are simple graphs, i.e. without
loops and multiple edges. Let $V(G)$ denote the vertex set of $G$ and let
$E(G)$ denote the edge set of $G$. For $v\in V(G)$, let $N(v)=\\{u\in
V(G)|uv\in E(G)\\}$, $N[v]=N(v)\cup\\{v\\}$, and $d(v)=|N(v)|$. For
$S\subseteq V(G)$, denote $N(S)=\cup_{v\in S}N(v)$ and $N[S]=N(S)\cup S$. Let
$\delta(G)=min\\{d(v)|v\in V(G)\\}$ and $\Delta(G)=max\\{d(v)|v\in V(G)\\}$.
Let $K_{n}$ denote the complete graph on n vertices and $K_{1,m}$ denote the
star with $m+1$ vertices. For graphs $G$ and $H$, the Ramsey Number $R(G,H)$
is the smallest integer $N$ such that any red-blue-coloring of $E(K_{N})$
yields a red $G$ or a blue $H$. For graphs $F$ and $G$, we say that an
injection $\phi:V(F)\rightarrow V(G)$ is an embedding of $F$ into $G$ if for
any edge $xy$ in $F$, $\phi(x)\phi(y)$ is an edge in $G$. We say that $F$ can
be embedded into $G$ if there is an embedding of $F$ into $G$.

Degree conditions for tree embedding have been studied actively. A well-known
conjecture of Erdős-Sós states that any tree with $n$ vertices can be embedded
into a simple graph with average degree exceeding $n-2$. In [7], Havet, Reed,
Stein and Wood studied the conditions on the maximum degree and the minimum
degree of a graph to embed any tree with $n$ vertices, they proposed an
interesting conjecture that any tree with $n$ vertices can be embedded into a
simple graph with maximum degree more than $n+1$ and minimum degree at least
$\lfloor{2(n+1)\over 3}\rfloor$. The Loebl-Komlós-Sós conjecture [5] states
that any tree with $n$ vertices can be embedded into a simple graph with
median degree at least $n+1$. We study minimum degree conditions to embed
trees, and it has natural applications on tree-star Ramsey numbers.

In [8], Parson determined the path-star Ramsey numbers. A key ingredient in
the proof is that $P_{n}$, a path with $n$ vertices, can be embedded into a
graph with minimum degree $n-1$. This is generalized to the following well-
known result (see [3]).

###### Lemma 1.1

If $G$ is a graph with minimum degree $n-1$, then any tree with $n$ vertices
can be embedded into $G$.

This lemma implies the Ramsey result of Burr [2]: $R(T_{n},K_{1,m})\leq
m+n-1$, where $T_{n}$ is a tree with $n$ vertices and $K_{1,m}$ is the star
with $m+1$ vertices. Applying Lemma 1.1, Cockayne [3] improved the upper bound
of $R(T_{n},K_{1,m})$ to $m+n-2$ for a special class of trees with $n$
vertices and some values of $m$ and $n$. Further, Guo and Volkmann [6]
generalized the result of Cockayne to any tree with $n$ vertices. A key making
the generalization possible is that Guo and Volkmann showed that any tree with
$n$ vertices other than $K_{1,n-1}$ can be embedded into a connected graph
with at least $n$ vertices and minimum degree $n-2$. They remarked that there
are connected graphs $G$ with at least $n$ vertices and minimum degree $n-3$,
and trees with $n$ vertices and maximum degree $n-3$ which cannot be embedded
into $G$. And they proposed the following conjecture.

###### Conjecture 1

([6]) If $G$ is a connected graph with at least $n$ vertices and minimum
degree at least $n-3$, then any tree with $n$ vertices and maximum degree at
most $n-4$ can be embedded into $G$.

We show a result slightly stronger than this conjecture and obtain a
sufficient and necessary condition that trees with $n$ vertices and maximum
degree at most $n-3$ can be embedded into a graph $G$ with minimum degree at
least $n-3$.

Let $p$ and $q$ be positive integers. Let $T(p,q)$ be a tree with a longest
path $v_{1}v_{2}v_{3}v_{4}v_{5}$ satisfying that $d(v_{3})=2$, and $v_{2}$ and
$v_{4}$ have $p$ and $q$ leaves respectively (see Figure 1).

Figure 1: $T(p,q)$

The following is the main result in this paper.

###### Theorem 1.2

Let $G$ be a connected graph with at least $n$ vertices and minimum degree at
least $n-3$. Let $T_{n}$ be a tree with $n$ vertices and $\Delta(T_{n})\leq
n-3$. Then $T_{n}$ can be embedded into $G$ if and only if the following
situations do not happen.
(i) $G=K_{n-3,n-3}$ and $T_{n}=T(p,n-3-p)$, where $p\geq 1$.
(ii) $G$ is a balanced complete $(k+1)$-partite graph with $a$ vertices in
each part and $ka=n-3$, and $T_{n}=T(1,n-4)$, where $k\geq 2$ is a positive
integer.

This result implies that Conjecture 1 holds except in situation (i) in Theorem
1.2. A non-negative integer $N$ is called a linear combination of two positive
integers $p$ and $q$ if there exist non-negative integers $k$ and $l$ such
that $N=kp+lq$. Applying Theorem 1.2, we are going to prove the following
tree-star Ramsey numbers in Section 4.

###### Theorem 1.3

Let $T_{n}$ be a tree with $n$ vertices, $\Delta(T_{n})\leq n-3$, and
$T_{n}\not=T(p,n-3-p)$. If $m+n-3$ is not a linear combination of $n-1$ and
$n-2$, then $R(T_{n},K_{1,m})\leq m+n-3$.

###### Theorem 1.4

Let $T_{n}$ be a tree with $n$ vertices and $\Delta(T_{n})\leq n-3$. Let
$m=k(n-1)+3$ and $0\leq k\leq n-5$.
(i) If $T_{n}\not=T(p,n-3-p)$, then $R(T_{n},K_{1,m})=m+n-3$.
(ii) If $m+n-3$ is not a linear combination of $n-1$, $n-2$, $n-3+a_{1}$, …,
$n-3+a_{d}$, where $a_{1},a_{2},...,a_{d}$ are positive divisors of $n-3$ no
less than $3$, then $R(T(1,n-4),K_{1,m})=m+n-3$. Otherwise
$R(T(1,n-4),K_{1,m})=m+n-2$.
(iii) Let $p\geq 2$. If $m+n-3$ is not a linear combination of $2n-6$, $n-1$
and $n-2$, then $R(T(p,n-3-p),K_{1,m})=m+n-3$. Otherwise
$R(T(p,n-3-p),K_{1,m})=m+n-2$.

The conjecture of Erdős-Sós states that any tree with $n$ vertices can be
embedded into a graph with average degree exceeding $n-2$. It is easy to show
that a connected graph with average degree greater than $n-2$ contains a
connected subgraph with minimum degree greater than $\frac{1}{2}(n-2)$. So if
one can characterize what kind of trees with $n$ vertices can be embedded into
a connected graph $G$ with at least $n$ vertices and
$\delta(G)\geq\frac{1}{2}(n-1)$, then these trees will satisfy the conjecture.
In general, it is interesting to study what kind of $T_{n}$ can be embedded
into a connected graph $G$ with at least $n$ vertices and $\delta(G)\geq t$.

In Section 2, we give some crucial lemmas in the proof of Theorem 1.2. The
proof of Theorem 1.2 will be given in Section 3. In Section 4, we prove
Theorems 1.3 to 1.4.

##  2 Preparations

###### Definition 2.1

A labelling $\\{v_{1},v_{2},...,v_{n}\\}$ of vertices of a tree with $n$
vertices is called a conventional labelling if for each $j\in[2,n]$,
$|N(v_{j})\cap\\{v_{1},...,v_{j-1}\\}|=1$. To simplify the notation, we always
denote the unique vertex in $N(v_{j})\cap\\{v_{1},...,v_{j-1}\\}$ by
$v_{j^{\prime}}$ for a conventional labelling.

Note that a tree $T$ always has a conventional labelling. We may take any
vertex in $V(T)$ as $v_{1}$ and order the other vertices as $v_{2},...,v_{n}$
in increasing order of the distances to $v_{1}$.

For given graphs $F$ and $G$, we say that a subset $U\subseteq V(F)$ has been
embedded into $G$ (or $\phi$ is an embedding of $U$ to G) if an embedding
$\phi$ of $F[U]$ into $G$ has been established. If $U\subseteq V(F)$ has been
embedded to $G$ via an embedding $\phi$, we say that $\phi$ can be extended to
a vertex $v\in V(F)\setminus U$ if there exists $v^{\prime}\in V(G)$ such that
the extension function $\hat{\phi}:U\cup\\{v\\}\rightarrow V(G)$ defined by
$\hat{\phi}(u)=\phi(u)$ for $u\in U$ and $\hat{\phi}(v)=v^{\prime}$ is an
embedding of $F[U\cup\\{v\\}]$ into $G$.

###### Lemma 2.2

Let $G$ be a connected graph with at least $n$ vertices. Let
$\\{v_{1},v_{2},...,v_{n}\\}$ be a conventional labelling of $T_{n}$. Let
$j\in\\{2,...,n\\}$. Let $\phi$ be an embedding of $\\{v_{1},...,v_{j-1}\\}$
into $G$.
(i) If

$|N(\phi(v_{j^{\prime}}))\setminus\\{\phi(v_{1}),...,\phi(v_{j-1})\\}|\geq 1,$
(1)

then $\phi$ can be extended to $v_{j}$.
(ii) If $\delta(G)\geq n-1$, then $\phi$ can be extended to $v_{j}$.
(iii) Let $\delta(G)\geq n-2$. If $2\leq j\leq n-1$, then $\phi$ can be
extended to $v_{j}$. If $j=n$ and there exists
$k\in\\{1,2,...,n-1\\}\setminus\\{n^{\prime}\\}$ such that $\phi(v_{k})\notin
N(\phi(v_{n^{\prime}}))$, then $\phi$ can be extended to $v_{j}$.
(iv) Let $\delta(G)\geq n-3$. If $2\leq j\leq n-2$, then $\phi$ can be
extended to $v_{j}$. If $j=n-1$ and
$|\\{\phi(v_{1}),...,\phi(v_{n-2})\\}\setminus
N(\phi(v_{(n-1)^{\prime}}))|\geq 2$, then $\phi$ can be extended to $v_{j}$.
If $j=n$ and $|\\{\phi(v_{1}),...,\phi(v_{n-1})\\}\setminus
N(\phi(v_{n^{\prime}}))|\geq 3$, then $\phi$ can be extended to $v_{j}$.

Proof of Lemma 2.2. The condition in (i) guarantees that there is a free
vertex in $N(\phi(v_{j^{\prime}}))$ to embed $v_{j}$, therefore $v_{j}$ can be
embedded to a vertex in $N(\phi(v_{j^{\prime}}))$, and this proves (i). (ii),
(iii) and (iv) are direct implications of (i). $\Box$

###### Lemma 2.3

([4]) Let $G$ be a connected graph with minimum degree $\delta(G)$. Then $G$
contains a path of length $min\\{n,2\delta(G)+1\\}$.

###### Lemma 2.4

Let $G$ be a connected graph with minimum degree $\delta$. Let $S_{0}\subseteq
V(G)$ and let $S_{1}$ be a proper subset of $S_{0}$ such that
$N(S_{1})\subseteq S_{0}$. If there exists $\alpha\in S_{0}$ such that
$N(\alpha)\not\subset S_{0}$, then there exists a path of length at least
$|S_{1}|+\delta-|S_{0}|+1$ starting from a neighbor $\alpha$ outside $S_{0}$.

Proof of Lemma 2.4. Let $\alpha_{1}\in N(\alpha)\setminus S_{0}$. Let
$\alpha_{1}\alpha_{2}...\alpha_{g}$ be a maximum path outside $S_{0}$. Since
$N(S_{1})\subseteq S_{0}$, $N(\alpha_{g})\subseteq
S_{0}\cup\\{\alpha_{1},\alpha_{2},...,\alpha_{g-1}\\}\setminus S_{1}$. Since
$|N(a_{g})|\geq\delta$, $|S_{0}|+g-1-|S_{1}|\geq\delta$. So
$g\geq|S_{1}|+\delta-|S_{0}|+1$. $\Box$

###### Lemma 2.5

Let $G$ be a non-complete and connected graph, then there exist
$\alpha,\beta,\gamma\in V(G)$ such that $\alpha\beta,\alpha\gamma\in E(G)$ and
$\beta\gamma\notin E(G)$.

Proof of Lemma 2.5. Take a shortest path between two non-adjacent vertices,
then three consecutive vertices in this path satisfy the condition. $\Box$

##  3 Embedding trees

We give the proof of Theorem 1.2 below.

Proof of Theorem 1.2. Let $T_{n}$ be a tree with $n$ vertices. Let $P$ be a
longest path of $T_{n}$. Let $|P|$ be the number of vertices of path $P$ and
$i=|P|-2$. Since $|P|=3$ implies that $T_{n}=K_{1,n-1}$, it contradicts
$\Delta(T_{n})\leq n-3$. So $|P|\geq 4.$ For $|P|\geq 5$, we label the two end
vertices as $v_{n-1}$ and $v_{n}$, all other vertices in $P$ as
$v_{1},v_{2},...,v_{i}$ such that $P=v_{n-1}v_{1}v_{2}...v_{i}v_{n}$, i.e.
$v_{n-1}$ is connected to $v_{1}$, $v_{1}$ is connected to $v_{2}$, $\cdots$,
$v_{i-1}$ is connected to $v_{i}$, and $v_{i}$ is connected to $v_{n}$. We
order the vertices outside $P$ as $\\{v_{i+1},...,v_{n-2}\\}$ in non-
decreasing order of the distances to $P$. For example, $v_{i+1}$ is connected
to a vertex in $P$. Note that $\\{v_{1},v_{2},...,v_{n-1},v_{n}\\}$ is a
conventional labelling. We will show that there is no embedding
$\phi:V(T_{n})\rightarrow V(G)$ if and only if situation (i) or (ii) in
Theorem 1.2 happens.

By Lemma 1.1, we can easily embed $\\{v_{1},...,v_{n-2}\\}$ into $G$. So what
we need to work on is to embed $v_{1}$ and $v_{i}$ properly so that there is a
free vertex for us to embed $v_{n-1}$ in the neighborhood of the vertex
$v_{1}$ embedded to, and there is a free vertex for us to embed $v_{n}$ in the
neighborhood of the vertex $v_{i}$ embedded to.

By Lemma 2.5, there exist $u_{1}$, $u_{2}$ and $u_{3}$ in $G$ satisfying that
$u_{2}\in N(u_{1})$ and $u_{3}\in N(u_{2})\setminus N(u_{1})$. Let
$\phi(v_{j})=u_{j}$ for $j\in[3]$. By Lemma 2.2 (iv), $\phi$ can be extended
to $\\{v_{4},...,v_{i-1}\\}$. Denote $\phi(v_{j})=u_{j}$ for $j\in[i-1]$.
Denote $K_{i}=\\{\phi(v_{1}),...,\phi(v_{i-1})\\}$.

Case 1. $|P|\geq 6$.

Case 1.1. There exists a vertex, denoted by $u_{i}$, in $N(u_{i-1})\setminus
K_{i}$ such that $|K_{i}\setminus N(u_{i})|\geq 2$.

In this case, let $\phi(v_{i})=u_{i}$. Since $\delta(G)\geq n-3$,
$u_{1},u_{3}\notin N(u_{1})$, by Lemma 2.2 (iv), $\phi$ can be extended to
$\\{v_{1},...,v_{n-1}\\}$. Further $|K_{i}\setminus N(u_{i})|\geq 2$ implies
that $|\\{\phi(v_{1}),...,\phi(v_{n-1})\\}\setminus N(u_{i})|\geq 3$, by Lemma
2.2 (iv), there exists an embedding from $T_{n}$ into $G$.

Case 1.2. There exists a vertex, denoted by $u_{i}$, in $N(u_{i-1})\setminus
K_{i}$ such that $|K_{i}\setminus N(u_{i})|=1$, and $|K_{i}\setminus N(u)|\leq
1$ for any $u\in N(u_{i-1})\setminus K_{i}$.

Note that $|K_{i}\setminus N(u_{i})|=1$ implies that there exists a vertex
$u_{x}$ in $K_{i}$ such that $u_{x}u_{i}\notin E(G)$.

If $d(u_{i})\geq n-2$, let $\phi(v_{i})=u_{i}$. Since $u_{3}\notin N(u_{1})$,
by Lemma 2.2 (iv), $\phi$ can be extended to $\\{v_{i+1},...,v_{n-1}\\}$.
Since $u_{x},u_{i}\notin N(u_{i})$,
$|N(u_{i})\setminus\\{\phi(v_{1}),...,\phi(v_{n-1})\\}|\geq 1$ and there is at
least one free vertex in $N(u_{i})$ to embed $v_{n}$. So it is sufficient to
consider $d(u_{i})=n-3$. Let $K=K_{i}\cup N[u_{i}]$, then $|K|=n-1$.

###### Claim 3.1

$N(u_{1})\subseteq K$ if $T_{n}$ cannot be embedded into G.

Proof of Claim 3.1. Suppose that there exists a vertex denoted by $u_{n-1}$ in
$N(u_{1})\setminus K$. Since $u_{3}\notin N(u_{1})$, by Lemma 2.2 (iv), $\phi$
can be extended to $\\{v_{1},...,v_{n-1}\\}$. Furthermore, we can guarantee
that some vertex $v_{a}\in T_{n}\setminus\\{v_{n}\\}$ is embedded to
$u_{n-1}$, where $a\in[i+1,n-1]$ (This is always possible since we can always
embed $v_{n-1}$ to $u_{n-1}$ if $u_{n-1}$ is not previously used). Now
$u_{x},u_{i},u_{n-1}\notin N(u_{i})$, then there exists a free vertex in
$N(u_{i})\setminus\\{\phi(v_{1}),...,\phi(v_{n-2}),\phi(v_{n-1})\\}$ to embed
$v_{n}$ and $T_{n}$ can be embedded into $G$. $\Box$

###### Claim 3.2

$N(u_{2})\subseteq K$ if $T_{n}$ cannot be embedded into G.

Proof of Claim 3.2. If there exists a vertex $u_{1}^{\prime}\in
N(u_{2})\setminus K$, then reassign $\phi(v_{1})=u_{1}^{\prime}$ and let
$\phi(v_{i})=u_{i}$. By the choice of $u_{1}^{\prime}$, we know that
$u_{i}\notin N(\phi(v_{1}))$. By Lemma 2.2 (iv), $\phi$ can be extended to
$\\{v_{1},...,v_{n-1}\\}$. Recall that there exists a vertex $u_{x}\in K_{i}$
such that $u_{x}u_{i}\notin E(G)$. We claim that $u_{x}\not=u_{1}$. Since
$d(u_{1})\geq n-3$, $u_{1},u_{3}\notin N(u_{1})$, $N(u_{1})\subseteq K$ and
$|K|=n-1$, $u_{1}u_{i}\in E(G)$. Since $u_{x},u_{1}^{\prime}\notin N(u_{i})$,
there is at least one free vertex in
$N(u_{i})\setminus\\{\phi(v_{1}),...,\phi(v_{n-1})\\}$ to embed $v_{n}$. A
contradiction. $\Box$

###### Claim 3.3

$N(u_{t})\subseteq K$ for $1\leq t\leq i-1$ if $T_{n}$ cannot be embedded into
G.

Proof of Claim 3.3. Use induction on t. For $t=1$ or 2, it is guaranteed by
Claim 3.2. Let $3\leq t\leq i-1.$ We assume that $N(u_{s})\subseteq K$ for
$1\leq s\leq t-1$. If $N(u_{t})\not\subset K$, then there exists a vertex
$u_{t-1}^{\prime}\in N(u_{t})\setminus K$. By Lemma 2.4, there exists a path
$u_{t-1}^{\prime}u_{t-2}^{\prime}...u_{1}^{\prime}$ outside K. Reassign
$\phi(v_{\alpha})=u_{\alpha}^{\prime}$ for $1\leq\alpha\leq t-1$ and let
$\phi(v_{i})=u_{i}$. Since $u_{\alpha}^{\prime}\notin N(u_{i})$ for
$1\leq\alpha\leq t-1$ and $t\geq 3$, by Lemma 2.2 (iv), $\phi$ can be extended
to $\\{v_{i+1},...,v_{n}\\}$. $\Box$

###### Claim 3.4

$N(K)\subseteq K$ if $T_{n}$ cannot be embedded into G.

Proof of Claim 3.4. If there exists a vertex $u_{i-1}^{\prime}\in
N(u_{i})\setminus K_{i}$ such that there exists a vertex $u_{i-2}^{\prime}\in
N(u_{i-1}^{\prime})\setminus K$, by Lemma 2.4, there exists a path
$u_{i-2}^{\prime}u_{i-3}^{\prime}...u_{1}^{\prime}$ outside K. Reassign
$\phi(v_{\alpha})=u_{\alpha}^{\prime}$ for $1\leq\alpha\leq i-1$ and let
$\phi(v_{i})=u_{i}$. Since $i\geq 4$ guarantees that
$u_{1}^{\prime},u_{2}^{\prime}\notin N(u_{i})$, by Lemma 2.2 (iv), $\phi$ can
be extended to $\\{v_{i+1},...,v_{n}\\}$. $\Box$

By Claim 3.4, if $T_{n}$ cannot be embedded into $G$, then $K$ is a component
with $n-1$ vertices, contradicting that $G$ is a connected graph with at least
$n$ vertices. So $T_{n}$ can be embedded into $G$ in this case.

Case 1.3. For each vertex $u$ in $N(u_{i-1})\setminus K_{i}$, $|K_{i}\setminus
N(u)|=0$.

Take a vertex, denote by $u_{i}$, in $N(u_{i-1})\setminus K_{i}$, and let
$\phi(v_{i})=u_{i}$.

If $d(u_{i})\geq n-1$, since $u_{1},u_{3}\notin N(u_{1})$, by Lemma 2.2 (iv),
$\phi$ can be extended to an embedding on $\\{v_{1},...,v_{n-1}\\}$. Since
$d(u_{i})\geq n-1$ and $\phi(v_{i})=u_{i}\notin N(u_{i})$, there is at least
one free vertex in $N(u_{i})\setminus\\{\phi(v_{1}),...,\phi(v_{n-1})\\}$ to
embed $v_{n}$.

If $d(u_{i})=n-2$, then $|N[u_{i}]|=n-1$. We claim that $\cup_{u\in
N[u_{i}]}N[u]=N[u_{i}]$ if $T_{n}$ cannot be embedded into $G$. If there
exists a vertex, denote by $u_{n-1}$, in $N(u_{1})\setminus N[u_{i}]$, let
$\phi(v_{i})=u_{i}$ and extend $\phi$ to an embedding on
$\\{v_{1},...,v_{n-1}\\}$ such that we embed some
$v_{a}\in\\{v_{i+1},...,v_{n-1}\\}$ to $u_{n-1}$ (This is always possible
since we can always embed $v_{n-1}$ to $u_{n-1}$ if $u_{n-1}$ is not
previously used). Now $u_{i},u_{n-1}\notin N(u_{i})$, therefore there exists
one free vertex in $N(u_{i})$ to embedded $v_{n}$ and $T_{n}$ can be embedded
into $G$. So we have shown that $N[u_{1}]\subseteq N[u_{i}]$. Assume that
$\cup_{i=1}^{t}N[u_{i}]\subseteq N[u_{i}]$ for $1\leq t\leq i-1$, we show that
$N[u_{t+1}]\subseteq N[u_{i}]$. If there exists a vertex $u_{t}^{\prime}\in
N[u_{t+1}]\setminus N[u_{i}]$, by Lemma 2.4, there exists a path
$u_{t}^{\prime}u_{t-1}^{\prime}...u_{1}^{\prime}$ outside $N[u_{i}]$. Reassign
$\phi(v_{\alpha})=u_{\alpha}^{\prime}$ for $1\leq\alpha\leq t$. Since
$u_{i}\notin N(\phi(v_{1}))$, by Lemma 2.2 (iv), $\phi$ can be extended to an
embedding on $\\{v_{1},...,v_{n-1}\\}$. Since $d(u_{i})=n-2$ and
$\phi(v_{i})=u_{i}$, $\phi(v_{a})\notin N(u_{i})$ for $1\leq a\leq t$, there
is at least one free vertex in
$N(u_{i})\setminus\\{\phi(v_{1}),...,\phi(v_{n-1})\\}$ to embed $v_{n}$.
Therefore we have shown that $N[K_{i}]\subseteq N[u_{i}]$. If there exist
vertices $u^{\prime},u^{\prime\prime}$ such that $u^{\prime}\in
N(u_{i})\setminus K_{i}$ and $u^{\prime\prime}\in N[u^{\prime}]\setminus
N[u_{i}]$, since $d(u_{3})\geq n-3$, $|N[u_{i}]|=n-1$ and $u_{1},u_{3}\notin
N(u_{3})$ and $N(u_{3})\subseteq N[u_{i}]$, $u_{3}u^{\prime}\in E(G)$.
Reassign $\phi(v_{2})=u^{\prime}$ and $\phi(v_{1})=u^{\prime\prime}$. Since
$u_{i}\notin N(\phi(v_{1}))$, by Lemma 2.2 (iv), $\phi$ can be extended to
$\\{v_{1},v_{2},...,v_{n-1}\\}$. Since $u^{\prime\prime}u_{i}\notin E(G)$ and
$d(u_{i})=n-2$, there exists a free vertex in
$N(u_{i})\setminus\\{\phi(v_{1}),...,\phi(v_{n-1})\\}$ to embed $v_{n}$ and
$T_{n}$ can be embedded into $G$. So we have shown that $\cup_{u\in
N[u_{i}]}N[u]=N[u_{i}]$ if $T_{n}$ cannot be embedded into $G$. Therefore
$N[u_{i}]$ is a component of $n-1$ vertices, contradicting that $G$ is a
connected graph with at least $n$ vertices.

Now we discuss $d(u_{i})=n-3$. Since $u_{1}u_{3}\notin E(G)$ and $d(u_{3})\geq
n-3$, there exists a vertex, denoted by $u_{2}^{\prime}$, in
$N(u_{3})\setminus N[u_{i}]$. If there exists a vertex $u_{1}^{\prime}\in
N(u_{2}^{\prime})\setminus N[u_{i}]$, then reassign
$\phi(v_{2})=u_{2}^{\prime}$ and $\phi(v_{1})=u_{1}^{\prime}$. Since
$\phi(v_{1}),\phi(v_{2})\notin N(\phi(v_{i}))$, by Lemma 2.2 (iv), $\phi$ can
be extended to $\\{v_{1},...,v_{n}\\}$ and $T_{n}$ can be embedded into $G$.
So $N(u_{2}^{\prime})\subseteq N[u_{i}]$. Since $u_{2}^{\prime}u_{i}\notin
E(G)$ and $d(u_{2}^{\prime})\geq n-3$, $N(u_{2}^{\prime})=N(u_{i})$. Since
$u_{2}^{\prime}u_{1},u_{2}^{\prime}u_{3}\in E(G)$, we can reassign
$\phi(v_{2})=u_{2}^{\prime}$. Now $u_{i}$ has a non-neighbor in $K_{i}$. Note
that $u_{3}\notin N(\phi(v_{1}))$ still holds. This situation is exactly Case
1.2 we have proved.

Case 2. $|P|=5$.

Figure 2: Case $d_{T_{n}}(v_{2})\geq 3$

Figure 3: Case $d_{T_{n}}(v_{2})=2$

In this case, $P=v_{n-1}v_{1}v_{2}v_{3}v_{n}$. If $d_{T_{n}}(v_{2})\geq 3$,
then there exists a vertex $v_{4}$ connected to $v_{2}$ (see Figure 3). If
$d_{T_{n}}(v_{2})=2$, then $N_{T_{n}}(v_{2})=\\{v_{1},v_{3}\\}$. If $T_{n}=P$,
since $|V(G)|\geq 5$ and $\delta(G)\geq 2$, by Lemma 2.3, $P=T_{n}$ can be
embedded in $G$. So if $d_{T_{n}}(v_{2})=2$, we may assume that
$d_{T_{n}}(v_{1})\geq 3$ or $d_{T_{n}}(v_{3})\geq 3$ (see Figure 3).

Let $u_{3}^{\prime}$ be a vertex with maximum degree in $V(G)$. If
$d(u_{3}^{\prime})\geq n-2$, if there exists a vertex $u_{2}^{\prime}\in
N(u_{3}^{\prime})$ such that there exists a vertex $u_{1}^{\prime}\in
N(u_{2}^{\prime})\setminus N[u_{3}^{\prime}]$, then let
$\phi(v_{1})=u_{1}^{\prime}$, $\phi(v_{2})=u_{2}^{\prime}$ and
$\phi(v_{3})=u_{3}^{\prime}$. Since $u_{1}^{\prime},u_{3}^{\prime}\notin
N(u_{1}^{\prime})$ and $\delta(G)\geq n-3$ and $d(u_{3}^{\prime})\geq n-2$, by
Lemma 2.2 (iv), $\phi$ can be extended to $\\{v_{4},...,v_{n}\\}$. If there is
no such vertex $u_{2}^{\prime}$ in $N(u_{3}^{\prime})$, then
$N[u_{3}^{\prime}]$ is a component, so $d(u_{3}^{\prime})\geq n-1$. If there
exists a vertex $u_{1}^{\prime}\in N(u_{3}^{\prime})$ such that
$d(u_{1}^{\prime})\geq n-2$, let $\phi(v_{1})=u_{1}^{\prime}$ and
$\phi(v_{3})=u_{3}^{\prime}$ and $\phi(v_{2})\in N(u_{1}^{\prime})$, then by
Lemma 2.2 (iv), $\phi$ can be extended to $\\{v_{4},...,v_{n}\\}$. So we may
assume that $d(u_{x})=n-3$ for all $u_{x}\in N(u_{3}^{\prime})$. Since
$|N[u_{3}^{\prime}]|\geq n$, for any vertex $u_{3}^{\prime\prime}\in
N(u_{3}^{\prime})$, we can find vertices
$u_{1}^{\prime\prime},u_{4}^{\prime\prime}\in N(u_{3}^{\prime})\setminus
N[u_{3}^{\prime\prime}]$. Let $\phi(v_{1})=u_{1}^{\prime\prime}$ and
$\phi(v_{2})=u_{3}^{\prime}$ and $\phi(v_{3})=u_{3}^{\prime\prime}$ and
$\phi(v_{4})=u_{4}^{\prime\prime}$. Since $\phi(v_{1}),\phi(v_{3})\notin
N(\phi(v_{1}))$, $d(\phi(v_{1}))\geq n-3$ and
$\phi(v_{1}),\phi(v_{3}),\phi(v_{4})\notin N(\phi(v_{3}))$, by Lemma 2.2 (iv),
$\phi$ can be extended to $\\{v_{4},...,v_{n}\\}$ and $T_{n}$ can be embedded
into $G$. Therefore, it is sufficient to consider that $G$ is an
($n-3$)-regular connected graph.

Case 2.1. $G$ is an ($n-3$)-regular connected graph with at least $n$ vertices
and $d_{T_{n}}(v_{2})\geq 3$ (see Figure 3).

###### Claim 3.5

Let $G$ be ($n-3$)-regular and $d_{T_{n}}(v_{2})\geq 3$ (see Figure 3). If
there exist vertices $u_{x},u_{y},u_{a},u_{b}\in V(G)$ such that
$u_{x}u_{y}\in E(G)$ and $u_{a},u_{b}\in N(u_{y})\setminus N[u_{x}]$ (see
Figure 5), then $T_{n}$ can be embedded into G.

Proof. Let $\phi(v_{1})=u_{a}$, $\phi(v_{2})=u_{y}$, $\phi(v_{3})=u_{x}$ and
$\phi(v_{4})=u_{b}$. Since $G$ is ($n-3$)-regular,
$\phi(v_{1}),\phi(v_{2})\notin N(\phi(v_{1}))$, and
$\phi(v_{1}),\phi(v_{4}),\phi(v_{3})\notin N(\phi(v_{3}))$, by Lemma 2.2 (iv),
$\phi$ can be extended to $\\{v_{5},...,v_{n}\\}$. $\Box$

Figure 4: Figure for Claim 3.5

Figure 5: Figure for Case 2.1

Take a vertex $u_{3}^{\prime}\in V(G)$. Since $|N[u_{3}^{\prime}]|=n-2$,
$N[u_{3}^{\prime}]$ is not a component. So there exists vertices
$u_{1}^{\prime},u_{2}^{\prime}$ such that $u_{2}^{\prime}\in
N(u_{3}^{\prime})$ and $u_{1}^{\prime}\in N(u_{2}^{\prime})\setminus
N[u_{3}^{\prime}]$ (see Figure 5). By Claim 3.5, $N[u_{2}^{\prime}]\subseteq
N[u_{3}^{\prime}]\cup\\{u_{1}^{\prime}\\}$. If $u_{1}^{\prime}$ has two
neighbors outside $N[u_{3}^{\prime}]$, then these two neighbors are outside
$N[u_{2}^{\prime}]$. By Claim 3.5, $T_{n}$ can be embedded into $G$. If
$N(u_{1}^{\prime})\subseteq N[u_{3}^{\prime}]$, then
$N(u_{1}^{\prime})=N(u_{3}^{\prime})$. If $T_{n}$ cannot be embedded into $G$,
Claim 3.5 implies that $\cup_{u\in N[u_{3}^{\prime}]}N(u)\cup
N(u_{1}^{\prime})=N[u_{3}^{\prime}]\cup\\{u_{1}^{\prime}\\}$. Otherwise there
exists a vertex $u\in N(u_{3}^{\prime})$ such that $u$ has a neighbor $w$
outside $N[u_{3}^{\prime}]\cup\\{u_{1}^{\prime}\\}$, then $u$ has two
neighbors $w$ and $u_{1}^{\prime}$ outside $N[u_{3}^{\prime}]$, contradicting
Claim 3.5. Thus $N[u_{3}^{\prime}]\cup\\{u_{1}^{\prime}\\}$ is a component on
$n-1$ vertices, contradicting that $G$ is a connected graph with at least $n$
vertices. Therefore, there exists exactly one vertex $u_{a}\in
N(u_{1}^{\prime})\setminus N[u_{3}^{\prime}]$. By Claim 3.5,
$N(u_{1}^{\prime})$ and $N(u_{a})$ differ by at most one vertex. So
$N(u_{1}^{\prime})\subseteq N(u_{3}^{\prime})\cup\\{u_{a}\\}$. If there exists
a vertex $u\in N(u_{3}^{\prime})\cap N(u_{1}^{\prime})$ connected to $u_{a}$,
then both $u_{a}$ and $u_{1}^{\prime}$ are in $N(u)\setminus
N(u_{3}^{\prime})$, contradicting Claim 3.5. So $N(u_{1}^{\prime})$ and
$N(u_{a})$ have no common neighbor in $N[u_{3}^{\prime}]$, contradicting Claim
3.5 again. So $T_{n}$ can be embedded into $G$.

Case 2.2. $G$ is ($n-3$)-regular and $d_{T_{n}}(v_{2})=2$ (see Figure 3), i.e.
$T_{n}=T(p,n-3-p)$ for some $p$.

###### Claim 3.6

Let G be an (n-3)-regular connected graph on at least $n$ vertices. If there
exists $u_{1}^{\prime},u_{2}^{\prime},u_{3}^{\prime}\in V(G)$ such that
$u_{1}^{\prime}u_{2}^{\prime},u_{2}^{\prime}u_{3}^{\prime}\in E(G)$ and
$u_{1}^{\prime}u_{3}^{\prime}\notin E(G)$. Then $T_{n}$ can be embedded into G
or $N(u_{1}^{\prime})=N(u_{3}^{\prime})$.

Proof. Suppose that $N(u_{1}^{\prime})\not=N(u_{3}^{\prime})$. Since $G$ is
regular, there exists a vertex $u_{4}\in N(u_{1}^{\prime})\setminus
N[u_{3}^{\prime}]$. Let $\phi(v_{1})=u_{1}^{\prime}$,
$\phi(v_{2})=u_{2}^{\prime}$, $\phi(v_{3})=u_{3}^{\prime}$ and
$\phi(v_{4})=u_{4}$. Since $u_{1}^{\prime}u_{3}^{\prime}\notin E(G)$, and
$u_{1}^{\prime},u_{3}^{\prime},u_{4}\notin N(u_{3}^{\prime})$, by Lemma 2.2
(iv), $\phi$ can be extended to an embedding of $T_{n}$. $\Box$

Assume that $T_{n}$ cannot be embedded into $G$. Let $A_{1}$ be a maximal set
in $G$ satisfying that it is an independent set and its any two vertices have
a common neighbor. By Claim 3.6, all vertices in $A_{1}$ have the same set of
neighbors, say $B$. Then $|B|=n-3$. We claim that $V(G)=A_{1}\cup B$.
Otherwise, there exists a vertex $u_{x}\in V(G)\setminus(A_{1}\cup B)$ such
that $u_{x}$ is connected to a vertex in $B$ and none of the vertices in
$A_{1}$ is adjacent to $u_{x}$. By Claim 3.6, $N(u_{x})=B$. This contradicts
the maximality of $A_{1}$. Since it holds for all such maximal sets, we can
divide $B$ into $k$ sets $B_{1},B_{2},...,B_{k}$ such that $B_{j}$ is such a
maximal set for each $j\in[k]$. Since $G$ is regular,
$|A_{1}|=|B_{1}|=...=|B_{k}|=a$, $n-3=ak$ and $|V(G)|=n-3+a$ (See Figure 6).
Since $|V(G)|\geq n$, $a\geq 3$.

Figure 6: $K_{a,a,\dots,a}$

If $k=1$, since $G$ is ($n-3$)-regular, $G=K_{n-3,n-3}$, and in this case,
$T(p,n-3-p)$ cannot be embedded into $K_{n-3,n-3}$. This is because that
$T(p,n-3-p)$ is a bipartite graph with 2 and $n-2$ vertices in each of the two
parts. This is situation (i) in Theorem 1.2.

If $k\geq 2$, then let $\phi(v_{1})\in B_{1}$, $\phi(v_{2})\in B_{2}$ and
$\phi(v_{3})\in A_{1}$.

Figure 7: $T(p,n-3-p)(2\leq p\leq n-5)$

Figure 8: $T(1,n-4)$

If $d(v_{1})\geq 3$ and $d(v_{3})\geq 3$ (see Figure 8), let
$\phi(v_{k}),\phi(v_{j})\in A_{1}$ and $\phi(v_{s}),\phi(v_{t})\in B_{1}$,
then the other leaves can be embedded in $A\cup B$ since $G$ is a balanced
complete $(k+1)$-partite graph, and $T_{n}$ can be embedded into $G$. Now
consider $d(v_{1})=2$ or $d(v_{3})=2$, i.e. $T_{n}=T(1,n-4)$. We claim that
$T(1,n-4)$ cannot be embedded into $G$. Without loss of generality, assume
that $d(v_{1})=2$ (see Figure 8). Suppose that $T(1,n-4)$ can be embedded into
$G$ and $v_{3}$ is embedded into $A_{1}$ (without loss of generality). Then
all $n-3$ vertices connected to $v_{3}$ should be embedded outside $A_{1}$.
Since $|V(G)\setminus A_{1}|=n-3$, $\phi(v_{1})$ must be in $A_{1}$. Since all
vertices of $T(1,n-4)\setminus\\{v_{1},v_{3}\\}$ are connected to $v_{1}$ or
$v_{3}$, then every vertex in $T(1,n-4)\setminus\\{v_{1},v_{3}\\}$ must be
embedded outside $A_{1}$, i.e. there are $n-2$ vertices should be embedded
outside $A_{1}$, but $|V(G)\setminus A_{1}|=n-3$. This is impossible. So in
this case $T(1,n-4)$ cannot be embedded into $G$. This is situation (ii) in
Theorem 1.2.

Case 3. $|P|=4$.

In this case we label the vertices of $T_{n}$ as in Figure 9. Note that
$\\{v_{1},v_{2},...,v_{n}\\}$ is a conventional labelling. Since
$d(v_{1})+d(v_{2})=n$ and $\Delta(T_{n})\leq n-3$, $d(v_{1}),d(v_{2})\geq 3$.

Figure 9: $T_{n}$ has n-2 leaves

Case 3.1. $\Delta(G)\geq n-1$.

Let $u,v\in V(G)$ such that $d(u)=\Delta(G)$ and $uv\in E(G)$. Embed
$\phi(v_{2})=u$ and $\phi(v_{1})=v$. By Lemma 2.2 (iv), $\phi$ can be extended
to $\\{v_{1},...,v_{n-2}\\}$. Recall that $v_{n-1}$ and $v_{n}$ have the same
parent (see Figure 9). Since $d(u)\geq n-1$, there are two free vertices in
$N(u)\setminus\\{\phi(v_{1}),...,\phi(v_{n-2})\\}$ to embed $v_{n-1}$ and
$v_{n}$. So $T_{n}$ can be embedded in $G$.

Case 3.2. $\Delta(G)=n-2$.

Let $\phi(v_{2})=u_{2}^{\prime}$ such that $d(u_{2}^{\prime})=n-2$. We claim
that there exists a vertex $u_{1}^{\prime}\in N(u_{2}^{\prime})$ such that
there exists a vertex $u_{3}^{\prime}\in N(u_{1}^{\prime})\setminus
N[u_{2}^{\prime}]$. Otherwise $\cup_{u\in
N[u_{2}^{\prime}]}=N[u_{2}^{\prime}]$. So $N[u_{2}^{\prime}]$ is a component
with $n-1$ vertices, contradicting that $G$ is a connected graph on at least
$n$ vertices. Let $\phi(v_{1})=u_{1}^{\prime}$ and
$\phi(v_{3})=u_{3}^{\prime}$. By Lemma 2.2 (iv), $\phi$ can be extended to
$\\{v_{1},...,v_{n-2}\\}$. Since $d(u_{2}^{\prime})=n-2$ and
$u_{3}^{\prime}\notin N(u_{2}^{\prime})$, there are two free vertices in
$N(u_{2}^{\prime})\setminus\\{\phi(v_{1}),...,\phi(v_{n-2})\\}$ to embed
$v_{n-1}$ and $v_{n}$. So $T_{n}$ can be embedded into $G$.

Case 3.3. $G$ is $(n-3)$-regular.

###### Claim 3.7

If there exists a vertex $u_{2}^{\prime}\in V(G)$ such that there exists a
vertex $u_{1}^{\prime}\in N(u_{2}^{\prime})$ with two neighbors
$u_{x},u_{y}\in N(u_{1}^{\prime})\setminus N[u_{2}^{\prime}]$, then $T_{n}$
can be embedded into $G$.

Proof. Let $\phi(v_{1})=u_{1}^{\prime}$, $\phi(v_{2})=u_{2}^{\prime}$,
$\phi(v_{3})=u_{x}$ and $\phi(v_{4})=u_{y}$. By Lemma 2.2 (iv), $\phi$ can be
extended to $\\{v_{1},...,v_{n-2}\\}$. Since $u_{2}^{\prime},u_{x},u_{y}\notin
N(u_{2}^{\prime})$ and $d(u_{2}^{\prime})=n-3$, there are two free vertices in
$N(u_{2}^{\prime})\setminus\\{\phi(v_{1}),...,\phi(v_{n-2})\\}$ to embed
$v_{n-1}$ and $v_{n}$. So $T_{n}$ can be embedded into $G$. $\Box$

###### Claim 3.8

If $T_{n}$ cannot be embedded into $G$, then for any vertex $u_{x}\in V(G)$,
there exists a vertex $u_{y}\in N(u_{x})$ such that $u_{y}$ has exactly one
neighbor outside $N[u_{x}]$.

Proof. By Claim 3.7, any vertex in $N(u_{x})$ has at most one neighbor outside
$N[u_{x}]$. If $\cup_{u\in N[u_{x}]}N[u]\subseteq N[u_{x}]$, then $N[u_{x}]$
is a component on $n-2$ vertices, a contradiction. $\Box$

If $T_{n}$ cannot be embedded into $G$, let $u_{x}\in V(G)$ and $u_{y}\in
N(u_{x})$ such that $u_{z}\in N(u_{y})\setminus N[u_{x}]$. Since $G$ is
(n-3)-regular and $u_{z}\in N(u_{y})\setminus N[u_{x}]$, there is exactly one
vertex $u_{a}\in N(u_{x})\setminus N(u_{y})$ and
$N(u_{y})=N[u_{x}]\cup\\{u_{z}\\}\setminus\\{u_{y},u_{a}\\}$. By Claim 3.7,
$N[u_{y}]\setminus\\{u_{x}\\}\subseteq N[u_{z}]$. Since $u_{y}u_{a}\notin
E(G)$, $|d(u_{a})|=n-3$ and $|N[u_{x}]|=n-2$, there is exactly one vertex
$u_{b}\in N(u_{a})\setminus N(u_{x})$. If $u_{b}=u_{z}$, then
$N(u_{z})=N(u_{x})$. For any vertex $u\in N(u_{x})$, $u_{z}\in N(u)\setminus
N(u_{x})$. Then by Claim 3.7, $N[u_{x}]\cup\\{u_{z}\\}$ is a component on
$n-1$ vertices, a contradiction. So $u_{b}\not=u_{z}$. Since $u_{a}$ has
exactly one neighbor outside $N(u_{x})$,
$N[u_{a}]=N[u_{x}]\cup\\{u_{b}\\}\setminus\\{u_{y}\\}$. Since all vertices in
$N(u_{x})$ have at most one neighbor outside $N(u_{x})$ and $u_{z}$ is a
neighbor of all vertices in
$N(u_{x})\setminus\\{u_{a}\\}=N(u_{a})\setminus\\{u_{b},u_{x}\\}\cup\\{u_{y}\\}$,
by Claim 3.7, $u_{b}$ is not adjacent to any of these vertices, i.e, $u_{b}$
has no neighbor in $N(u_{a})\setminus\\{u_{b}\\}$, contradicting Claim 3.7
again. So $T_{n}$ can be embedded into $G$ in this case. $\Box$

##  4 Tree-star Ramsey number

In this section, we apply Theorem 1.2 to obtain the Ramsey number of a tree
versus a star for some cases.

Proof of Theorem 1.3. For any red-blue-coloring of $E(K_{m+n-3})$, let $G_{R}$
and $G_{B}$ be the red graph and the blue graph respectively. If
$\Delta(G_{B})\geq m$, then there is a blue $K_{1,m}$. So we may assume that
$\Delta(G_{B})\leq m-1$. Hence $\delta(G_{R})\geq(m+n-4)-(m-1)=n-3$. Since
$m+n-3$ is not a linear combination of $n-1$ and $n-2$, then $G_{R}$ contains
a component with order at least $n$. By Theorem 1.2, $T_{n}$ can be embedded
into $G_{R}$. $\Box$

###### Fact 4.1

For positive integers $m$ and $n$, $m+n-4$ is a linear combination of $n-1$
and $n-2$ and $m+n-3$ is not a linear combination of $n-1$ and $n-2$ if and
only if $m=k(n-1)+3$ and $0\leq k\leq n-5$.

Proof of Fact 4.1. Necessity: If $m+n-4=k(n-1)+l(n-2)$, $k\geq 0$ and $l\geq
1$, then

$m+n-3=k(n-1)+l(n-2)+(n-1)-(n-2)=(k+1)(n-1)+(l-1)(n-2),$

contradicting that $m+n-3$ is not a linear combination of $n-1$ and $n-2$.
Therefore $l=0$ and $m=(k-1)(n-1)+3$, where $k\geq 1$. Let us rewrite
$m=k(n-1)+3$, where $k\geq 0$. If $k\geq n-4$, then

$m+n-3=k(n-1)+n=(k-n+4)(n-1)+(n-2)(n-2),$

and $m+n-3$ is a linear combination of n-1 and n-2. So $0\leq k\leq n-5$.

Sufficiency: If $m=k(n-1)+3$ and $0\leq k\leq n-5$, then $m+n-4=(k+1)(n-1)$ is
a linear combination of $n-1$ and $n-2$. If $m+n-3$ is a linear combination of
$n-1$ and $n-2$, then $m+n-3=k(n-1)+n=k^{\prime}(n-1)+l^{\prime}(n-2)$
($k^{\prime},l^{\prime}\geq 0$). So
$(k+2-k^{\prime})(n-1)=(l^{\prime}+1)(n-2)$. Since $n-1$ is relatively prime
to $n-2$, $k+2-k^{\prime}=c(n-2)$ for $c\geq 1$. Therefore
$k\geq(n-2)-2+k^{\prime}\geq n-4$, a contradiction. $\Box$

For a positive integer $a$ dividing $n-3$, let $B(n-3+a)$ be the balanced
complete $\frac{n-3+a}{a}$-partite graph on $n-3+a$ vertices.

Proof of Theorem 1.4. Since $m+n-4=(k+1)(n-1)$, we can partition
$V(K_{m+n-4})$ into $k+1$ disjoint equal parts with $n-1$ vertices in each
part. Color edges in each part red and other edges blue. Then
$\Delta(G_{B})\leq m+n-4-(n-1)=m-3$. So this coloring yields neither a red
$T_{n}$ nor a blue $K_{1,m}$. Therefore $R(T_{n},K_{1,m})\geq m+n-3$.

(i). By Fact 4.1 and Theorem 1.3, $R(T_{n},K_{1,m})\leq m+n-3$. Therefore
$R(T_{n},K_{1,m})=m+n-3$.

(ii). For any red-blue-coloring of $E(K_{m+n-3})$, let $G_{R}$ and $G_{B}$ be
the red graph and the blue graph respectively. If $\Delta(G_{B})\geq m$, then
there is a blue $K_{1,m}$. So we may assume that $\Delta(G_{B})\leq m-1$.
Hence $\delta(G_{R})\geq(m+n-4)-(m-1)=n-3$. By Fact 4.1, $G_{R}$ contains a
component with at least $n$ vertices. By Theorem 1.2, if $m+n-3$ is not a
linear combination of $n-1$, $n-2$, $n-3+a_{1}$, …, $n-3+a_{d}$, then
$T(1,n-4)$ can be embedded into $G_{R}$. So $R(T(1,n-4),K_{1,m})\leq m+n-3$.
Therefore $R(T(1,n-4),K_{1,m})=m+n-3$.

If $m+n-3=k_{1}(n-1)+l_{1}(n-2)+s_{1}(n-3+a_{1})+...+s_{d}(n-3+a_{d})$, for
red-blue-coloring of $E(K_{m+n-3})$, let $G_{R}$ and $G_{B}$ be the red graph
and the blue graph respectively. Let $G_{R}=k_{1}K_{n-1}\cup l_{1}K_{n-2}\cup
s_{1}B(n-3+a_{1})\cup...\cup s_{d}B(n-3+a_{d})$ and $G_{B}=G_{R}^{c}$. By
Theorem 1.2, $T(1,n-4)$ cannot be embedded into $G_{R}$. Since
$\delta(G_{R})\geq n-3$, then $\Delta(G_{B})\leq(m+n-4)-(n-3)=m-1$. So there
is neither a red $T_{n}$ nor a blue $K_{1,m}$. Therefore
$R(T(1,n-4),K_{1,m})\geq m+n-2$. The same lower bound was given in [6]. So
$R(T(1,n-4),K_{1,m})=m+n-2$.

(iii). For any red-blue-coloring of $E(K_{m+n-3})$, let $G_{R}$ and $G_{B}$ be
the red graph and the blue graph respectively. If $\Delta(G_{B})\geq m$, then
there is a blue $K_{1,m}$. So we may assume that $\Delta(G_{B})\leq m-1$.
Hence $\delta(G_{R})\geq n-3$. By Fact 4.1 and $m+n-3$ is not a linear
combination of $2n-6$, $n-1$ and $n-2$, there exists a component $G^{\prime}$
such that $n\leq|V(G^{\prime})|\not=2n-5$. By Theorem 1.2, $T(p,n-3-p)$ can be
embedded into $G^{\prime}$. Therefore $R(T(p,n-3-p),K_{1,m})=m+n-3$. If
$m+n-3=r(2n-6)+s(n-1)+t(n-2)$, then we can partition $K_{m+n-3}$ into $r+s+t$
disjoint parts such that $r$ parts have order $2n-6$ and $s$ parts have order
$n-1$ and $t$ parts have order $n-2$. Let $G_{R}=rK_{n-3,n-3}\cup sK_{n-1}\cup
tK_{n-2}$ and $G_{B}=G_{R}^{c}$. Then $\Delta(G_{B})\leq m+n-4-(n-3)=m-1$ and
$T(p,n-3-p)$ cannot be embedded into $G$. Therefore $R(T(p,n-3-p),K_{1,m})\geq
m+n-2$. The same lower bound was given in [6]. So $R(T(1,n-4),K_{1,m})=m+n-2$.
$\Box$

Acknowledgement The research is supported in part by National Natural Science
Foundation of China (No. 11931002).

## References

  * [1] J. A. Bondy and U. S. R. Murty, Graph theory with applications, The Macmillan Press Ltd., 1976.
  * [2] S. A. Burr: Generalized Ramsey theory for graphs - a survey, Graphs and Combinatorics, Lecture Notes in Mathematics, 406(1974), 52-75.
  * [3] E. J. Cockayne: Some tree-star ramsey numbers, J. Combinatorial Theory, Ser. B, 17(1974), 183-187.
  * [4] G. A. Dirac: Some theorems on abstract graphs, Proc. London Math. Soc., 2(1952), 69-81.
  * [5] P. Erdős, Z. Füredi, M. Loebl, and V. T. Sós: Discrepency of trees, Studia Sci. Math. Hungra, 30(1995), 47-57.
  * [6] Y. Guo and L. Volkmann: Tree-Ramsey numbers, Australasian J. Combin., 11(1995), 169-175.
  * [7] F. Havet, B. Reed, M. Stein, and D. Wood: A variant of the Erdős and Sós conjecture, Journal of Graph Theory, 94(2019), 131-158.
  * [8] T. D. Parsons: Path-star ramsey numbers, J. Combinatorial Theory, Ser. B, 17(1974), 51-58.