# Assessing ASR Model Quality on Disordered Speech using BERTScore

###### Abstract

Word Error Rate (WER) is the primary metric used to assess automatic speech
recognition (ASR) model quality. It has been shown that ASR models tend to
have much higher WER on speakers with speech impairments than typical English
speakers. It is hard to determine if models can be be useful at such high
error rates. This study investigates the use of BERTScore, an evaluation
metric for text generation, to provide a more informative measure of ASR model
quality and usefulness. Both BERTScore and WER were compared to prediction
errors manually annotated by Speech Language Pathologists for error type and
assessment. BERTScore was found to be more correlated with human assessment of
error type and assessment. BERTScore was specifically more robust to
orthographic changes (contraction and normalization errors) where meaning was
preserved. Furthermore, BERTScore was a better fit of error assessment than
WER, as measured using an ordinal logistic regression and the Akaike’s
Information Criterion (AIC). Overall, our findings suggest that BERTScore can
complement WER when assessing ASR model performance from a practical
perspective, especially for accessibility applications where models are useful
even at lower accuracy than for typical speech.

##  1 Introduction

Automatic Speech Recognition (ASR) model quality is most often measured by
Word Error Rate (WER), the aggregate score of word deletions, substitutions
and insertions. WER is the de facto metric for benchmarking models’
improvements and regressions. Most state-of-the-art (SOTA) ASR models trained
and evaluated on typical English speech report single digit WERs on standard
test corpora [1]. However, models trained only on typical speech perform worse
on disordered speech, reporting a median WER of 31.5 on short phrases [2]. In
these situations where WER is high, it is difficult to assess how useful a
model will be for the end user. In particular, WER doesn’t capture semantic
closeness or the assessment of the error. For instance, misrecognizing the
suffix ‘s’ in a plural and missing the negation of a word can have the same
error rate but missing the negation can fail to capture the user’s intent (see
examples in Table 4). Thus, looking at word error rate alone may not convey
the utility of the model in some practical settings where errors are
tolerated. An example being video call captioning for a person with a speech
impairment, which can ensure that the conversation partner will understand the
speaker better.

Green et al. show that, for individuals with disordered speech, personalizing
ASR models with the individual’s speech can lead to on average 75% relative
WER improvements over unadapted models trained for typical speech [2]. The
personalized models, although having WERs in the range of 15 or 20 (which
would be considered high for typical speech), provided utility to the users in
certain domains such as home automation, spoken transactions (asking for
something), and conversations [3]. Their work demonstrates that transcriptions
do not need to be perfect to communicate a speaker’s intent or meaning. Errors
such as normalization (one hundred percent vs. 100%) or contraction expansion
(I’m vs I am) can be considered a combination of deletions, insertions and
substitutions, but to a human or a SOTA natural language understanding (NLU)
system, the meaning is conveyed the same.

Alternatives to WER have been investigated, aiming to address the limitations
when applied to conversations [4, 5]. There are several metrics in natural
language understanding applications that aim to measure similarity of
generated text with a human truth e.g. BLEU [6] and METEOR [7] are popular in
machine translation, ROUGE [8] is used the context of summarization, SPICE [9]
is used in image-captioning, and more recently BLEURT [10] and BERTScore [11]
which are based on pre-trained language models have been proposed for text
generation. Even for speech applications, recent work [12, 13] proposed
metrics utilizing pre-trained language models. In Kim et al. [12], the
proposed alternate metric is based on semantic distance between the predicted
and ground truth transcripts. Our work is motivated similarly, though we
utilize BERTScore111BERTScore is available open source at
https://github.com/Tiiiger/bert_score., an existing semantic distance based
metric popular in language generation and adapt it to our task.

In this work, we specifically investigate BERTScore and WER for measuring the
utility of personalized ASR models. We worked with Speech Language
Pathologists (SLPs) to perform a detailed analysis of the errors, including
error type and assessment assessments, based on the model predictions from
personalized ASR models. We then compared both BERTScore and WER in terms of
how well they aligned with the SLP assessments. Our findings showed that while
both metrics are well correlated with SLP judgements, BERTScore was a better
fit to the assessments overall. Further, BERTScore was a better indicator of
utility in the presence of simple contraction and normalization errors than
WER.

##  2 Data and Approach

We first describe the model and data used in our analysis and then describe
the metric and comparison approach.

###  2.1 Personalized ASR Models and utility

The ASR models used in our study are based on work from Green et. al. [2]
which developed personalized models for 432 speakers with impairments who
contributed to Project Euphonia [14]. This corpus consists of over 1 million
samples (over 1300 hours) of more than 1000 anonymized speakers with different
types and severity levels of speech impairments. Following the same approach
in [2], we fine-tuned models on a subset of 15 individuals from the Euphonia
corpus [14] by tuning most of the initial encoder layers while keeping the
decoder frozen. This included speakers having varying degrees of speech
impairment described in Table 1. Speaker etiologies include Amyotrophic
Lateral Sclerosis (ALS), Cerebral Palsy, Down Syndrome, Multiple Sclerosis,
and other long tail etiologies that have less representation in the overall
Euphonia dataset, including Brain Injury, Vocal Chord Paralysis and Cleft
Palate. This approach showed huge improvements in WER, from average WER of
66.3 $\pm$ 10.0 before adaptation to a WERs in the range of 15-20 after
personalization. These WERs though, are still much higher than the original
model’s WER of 6-8 on typical speech [15].

Severity | # Speakers | Avg. Adapted WER
---|---|---
(rel. improvement)
Mild | 2 |  16.5 (62%)222Mild speech severity models having a higher average WER than moderate speech severity is an artifact of the small sample size. Green et al. (2021) showed that Mild WER was significantly lower than Moderate in the Euphonia dataset.
Moderate | 7 | 14.3 (76%)
Severe | 6 | 21.6 (72%)
Table 1: Distribution of speakers, severity of speech impairment, and average
WER after adaptation with relative improvement.

To validate the utility of the models beyond the WER improvements,
particularly for overall user experience, we solicited feedback from 15
speakers who used personalized ASR models to dictate their speech through a
mobile app for several months. The feedback suggested that in several
scenarios, the models were indeed useful. Specifically, users were able to (1)
perform home automation through voice controlled assistants, (2) use it for
face to face and video conversations with friends and family, (3) long-form
dictation and email, and (4) even for short transactional interactions with
individuals unfamiliar with the impaired speaker’s voice. These user success
stories suggested that despite high WERs, users experienced benefits across
several domains and situations.

###  2.2 Error Analysis

To understand and measure the utility of the models and track improvements and
regressions, we sought more detailed analysis of the errors from SLPs on the
per-speaker test set produced by each speaker’s personalized model. SLPs
assessed a total of 3473 transcription errors and determined (1) error type
and (2) assigned an assessment rating of the error severity. They categorized
the errors into 8 types including deletion, contraction, normalization,
homophone, spelling, proper noun, repetition, and other word errors. These are
described in Table 2. The error severity assessment was rated on a scale of 0,
1 or 2 depending on whether or not an error preserved meaning. This is
described in Table 3. An error severity assessed at levels 0 and 1 are
considered to be “recoverable,” i.e., a communication partner would be able to
understand what a speaker meant to say. An error level 2 represents a
communication breakdown, where the perceived meaning is lost or drastically
altered from a speaker’s intent.

Type | Description | # Errors (%)
---|---|---
Deletion | One or more spoken words | 413 (12%)
| do not appear in prediction. |
Contraction | Words either contracted | 17 (0.5%)
| or a contraction expanded |
Normalization | Non-canonical transcription | 404 (12%)
| (e.g. ”four o’clock” vs ”4:00”) |
Homophone | Word has same pronunciation | 34 (1%)
| but different meaning. |
Spelling | Different spelling, beyond | 30 (1%)
| what’s covered above. |
| (e.g. “color” vs “colour”) |
Proper noun | Misrecognized named entity | 386 (11%)
| or technical term. |
Repetition | Non-spoken repetitions. | 21 (1%)
Word Error | A word is misrecognized. | 2168 (62%)
| (no above errors apply) |
Table 2: Description of error types with counts and proportion of 3473 errors. Assessment | Description | # Errors (%)
---|---|---
0 | Meaning is completely | 861 (25%)
| preserved. |
1 | Some errors, but meaning | 786 (23%)
| is mostly preserved. |
2 | Major errors, significant | 1826 (53%)
| changes to the meaning. |
Table 3: Error severity assessment response scale, descriptions, counts and
proportion of total 3473 errors.

Dataset. We consolidated the errors and assessments into a dataset. Table 1
shows the distribution of the speakers and the severity of their speech
impairment, Table 2 shows distribution over error types and Table 3 includes
the assessment at different severity levels. As shown in Table 3, 53% the
errors were assessed as Level 2 errors, 25% of the transcription errors were
marked as Level 0 (meaning completely preserved) and another 23% as Level 1
(minor errors): in almost half of the cases, the meaning was preserved. The
majority of errors were the most general category Word Error. There were,
however, a significant amount of normalization errors, which are typically
meaning preserving (Levels 0 or 1). Examples of different error types and the
associated SLP assessments are shown in Table 4.

Error Type | Predicted Transcript | Actual Transcript | Word Acc. |  FBERT | Assessment
---|---|---|---|---|---
Deletion | Come right back _ | Come right back please | 0.75 | 0.86 | 0
|  I have a head_ | I have a headache | 0.75 | 0.69 | 2
Contraction |  I’m a bit overwhelmed | I am a bit overwhelmed. | 0.60 | 0.89 | 0
Normalization |  play Beyoncé | play Beyonce | 0.50 | 1.00 | 0
|  Okay 9:30 five | Okay, nine thirty five. | 0.50 | 0.75 | 1
Proper Noun |  Here are TV shows by Hugh Griffiths | Here are TV shows by Hugh Griffith | 0.86 | 0.96 | 0
|  First do you know how the story ends | Faust, do you know how the story ends? | 0.88 | 0.79 | 2
Repetition |  What are you are you trying to say to me | What are you trying to say to me? | 0.75 | 0.92 | 1

Table 4: Examples of errors with associated Word Accuracy, FBERT and Error
Assessment metrics.

####  2.2.1 Overview of transcript error assessment task

For completeness, we also detail the specific instructions provided to the
SLPs here. SLPs were given the following instructions when assessing an error.
To prevent bias and better simulate being a conversational partner, SLPs were
asked to look at ground truth transcripts only after making a mental guess at
the phrase meaning.

  1. 1.

Read the model prediction without looking at the original transcript.

  2. 2.

Make a mental guess at the intended meaning of the text.

  3. 3.

Read the ground-truth transcript and compare to the prediction; assign an
error assessment according to the scale in table.

To assess Inter-Annotator Agreement, measured with Cohen’s kappa [16], 5% of
the errors were annotated by two SLPs. Raters were in substantial agreement
for both error assessment ($\kappa=0.64$) and error types ($\kappa=0.69$)
based on the scale in [17].

###  2.3 Word Accuracy and FBERT

BERTScore [11] is a text evaluation metric based on a pretrained BERT model’s
[18] contextual embedding. It measures the similarity of two sentences as the
sum of the cosine similarities of the token embeddings of the sentences as
follows. Let the ground truth transcript ($x$) with pre-normalized token
embeddings ($x_{i}$), be represented as $x=\langle x_{1},\cdots,x_{k}\rangle$,
and a similarly tokenized predicted sentence be represented as $y=\langle
y_{1},\cdots,y_{l}\rangle$, and the cosine similarity between two tokens
$x_{i}$ and $y_{j}$ be denoted as $x_{i}\cdot y_{j}$. We use the version of
BertScore where the cosine similarity is weighted by the inverse document
frequency (idf) computed on the test set of ground truth transcripts. Then,
BERTScore maximizes the cosine similarity of each token in $x$ with each token
in $y$ to compute the recall, precision, and F1 measure as:

$\displaystyle R=\frac{1}{|x|}\sum_{x_{i}\in x}\max_{y_{j}\in y}(x_{i}\cdot
y_{j})\quad P=\frac{1}{|y|}\sum_{y_{j}\in y}\max_{x_{i}\in x}(x_{i}\cdot
y_{j})$ $\displaystyle F_{BERT}=2\frac{P\times R}{P+R}$ (1)

We use the BERT-base model [18] for the token embeddings to compute cosine
similarity. BERTScore[11] was evaluated on several hundred machine translation
and captioning systems and was shown to be robust to syntax changes and
provide a metric of semantic similarity that aligned well with human
judgements. In this analysis we use the F1 measure, denoted FBERT (Eqn. 2.3),
combining the sentence level precision and recall returned from BERTScore. The
ranges of FBERT and WER333WER is capped at 100 in this analysis. are [0,1] and
[0,100] respectively. A transcript with an exact match would have FBERT = 1
and WER = 0. In order to make analysis more comparable, we match ranges by
reporting Word Accuracy (Eqn. 2) instead of WER in the subsequent sections.

$\displaystyle\text{Word Accuracy}=1-\frac{WER}{100}$ (2)

###  2.4 Ordinal Logistic Regression

We examine how well WER and FBERT as metrics are aligned with expert-annotated
error assessments. Since error assessments were graded on a Likert Scale from
0 to 2 and are inherently ordinal, we ran a series of ordinal logistic
regression (OLR) models with error assessments as the dependent variable, and
Word Accuracy and/or FBERT as the independent variables.

To further determine model quality with Word Accuracy and FBERT as parameters,
we rank each models’ associated Akaike Information Criterion (AIC)[19], a
lower AIC indicating a better model for the data.

Figure 1: Distribution of Word Accuracy (left) and FBERT (right) broken out by
error assessment.

Figure 2: Distribution of Word Accuracy (left) and FBERT (right) broken out by
error type.

##  3 Results

BERTScore distinguishes error severity better. Figure 1 shows the summary
statistics of Word Accuracy and FBERT for the three levels of error
assessment. We can clearly see that 1) FBERT distinguishes different error
assessment levels better than Word Accuracy, especially between 0 and 1; and
2) FBERT has overall smaller variance ($SD=0.142$) than Word Accuracy
($SD=0.274$). A one-way ANOVA test also confirms that FBERT
($F=684.38,p<0.001$) could differentiate different assessment levels better
than Word Accuracy ($F=209.01,p<0.001$).

BERTScore distinguishes error types better. Leveraging the expert-annotated
error types for all data, we then compare how Word Accuracy and FBERT
differentiate between different error types, with results shown in Figure 2.
For instance, FBERT differentiates contraction errors better than Word
Accuracy (i.e. they should have higher scores because these errors typically
do not impact the semantic meanings of the speech), similarly for
normalization errors. One-way ANOVA tests again confirm that FBERT
($F=41.75,p<0.001$) outperforms Word Accuracy ($F=9.45,p<0.001$) when
distinguishing different error types on impaired speech.

BERTScore fits SLP assessments better. Our results of ordinal logistic
regressions show that both Word Accuracy and FBERT are significant predictors
for error assessment, but FBERT has a larger absolute value of coefficient
($\text{coeff}=-10.87,t=-28.6,p<0.001$) than Word Accuracy
($\text{coeff}=-2.52,t=-17.4,p<0.001$), which means FBERT is more predictive
of error assessment: a decrease in FBERT is more likely to result in a higher
error assessment score (i.e. more severe error). This is also confirmed by AIC
scores where $AIC=5854$ for OLR with FBERT as the parameter and $AIC=6733$
with Word Accuracy. The OLR model with FBERT as the parameter fits better with
the error assessment data, than with Word Accuracy as the parameter.

BERTScore is more useful when measuring semantic similarity. Models based on
WER and BERTScore both significantly fit the data, but there are situations
where BERTScore is more robust to transcription errors that do not affect the
semantic meanings. Table 4 shows transcription error examples with their
associated Word Accuracy and FBERT. For instance, both “Deletion” examples
(see row 1 in Table 4) have a word accuracy of 0.75. However, one (Come right
back _) has an assessment score of 0 because the original meaning of the
utterance is persevered, while the other example (I have a head_) has an
assessment score of 2 because of the significant change to the intended
meaning. Using Word Accuracy in this case fails to distinguish the quality of
the predicted transcripts. FBERT, instead, performs better in measuring the
quality of the predictions (0.86 vs. 0.69). Similarly, normalization errors
often result in low Word Accuracy, especially for short phrases, even though
the meaning is not affected. E.g. play Beyoncé vs. play Beyonce has an Word
Accuracy of 0.50 while an FBERT of 1.00.

BERTScore is however more expensive and less flexible than WER. WER is useful
in many applications regardless of language or phrase domain. BERTScore on the
other hand is more computationally expensive and relies on a pre-trained BERT
model that can run into issues with multilingual data and out of vocabulary
words.

##  4 Conclusion

ASR models exhibit higher word error rates when measured on non-typical
speech, relative to rates typically reported in SOTA research. When making
product decisions, it can be difficult to assess the quality of a model with a
large WER. Models that could provide utility to people with impaired speech
may be gated from release unnecessarily. To our knowledge, this is the largest
user study validating the usefulness of personalized models despite models
having WERs larger than products made for typical speakers.

In this study we discussed a separate metric for determining model quality
based on loss of semantic meaning in transcription errors using BERTScore, a
semantic embedding metric. We found that BERTScore was more robust to several
types of transcription errors including normalization and contraction errors.

In future studies, we aim to investigate further metrics, such as Character
Error Rate (CER) and BLEURT, that can give insight into when a model will be
useful for speakers with disordered speech, especially when a speaker may have
a condition that causes their voice to become more severely impaired over
time. WER and BERTScore, when used together as parameters, fit the data better
than either parameter alone. Future studies should also look at utilizing both
signals together to assess model usefulness. It would also be good to a domain
specific threshold of WER and FBERT that can help predict success rate,
proportion of speakers that will have a usable ASR model after
personalization, similar to the home automation domain WER of 15 discussed in
Tobin and Tomanek(2022).

Future studies can also investigate applications of BERTScore for estimating
ASR model quality beyond disordered speech. ASR models with higher WER may
still be useful for speakers with accented speech or non-ideal acoustic
settings for example.

## References

  * [1] G. Synnaeve, “Wer are we?” github.com/syhw/wer_are_we, 2022, accessed: 2022-04-09. [Online]. Available: https://github.com/syhw/wer_are_we
  * [2] J. R. Green, R. L. MacDonald, P.-P. Jiang, J. Cattiau, R. Heywood, R. Cave, K. Seaver, M. A. Ladewig, J. Tobin, M. P. Brenner, P. C. Nelson, and K. Tomanek, “Automatic Speech Recognition of Disordered Speech: Personalized Models Outperforming Human Listeners on Short Phrases,” in _Proc. Interspeech 2021_ , 2021, pp. 4778–4782.
  * [3] J. Tobin and K. Tomanek, “Personalized automatic speech recognition trained on small disordered speech datasets,” in _ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2022, pp. 6637–6641.
  * [4] Y.-Y. Wang, A. Acero, and C. Chelba, “Is word error rate a good indicator for spoken language understanding accuracy,” in _2003 IEEE Workshop on Automatic Speech Recognition and Understanding (IEEE Cat. No.03EX721)_ , 2003, pp. 577–582.
  * [5] A. C. Morris, V. Maier, and P. Green, “From WER and RIL to MER and WIL: improved evaluation measures for connected speech recognition,” in _Proc. Interspeech 2004_ , 2004, pp. 2765–2768.
  * [6] K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu, “Bleu: A method for automatic evaluation of machine translation,” in _Proceedings of the 40th Annual Meeting on Association for Computational Linguistics_ , ser. ACL ’02. USA: Association for Computational Linguistics, 2002, p. 311–318. [Online]. Available: https://doi.org/10.3115/1073083.1073135
  * [7] S. Banerjee and A. Lavie, “METEOR: An automatic metric for MT evaluation with improved correlation with human judgments,” in _Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization_. Ann Arbor, Michigan: Association for Computational Linguistics, Jun. 2005, pp. 65–72. [Online]. Available: https://aclanthology.org/W05-0909
  * [8] C.-Y. Lin, “ROUGE: A package for automatic evaluation of summaries,” in _Text Summarization Branches Out_. Barcelona, Spain: Association for Computational Linguistics, Jul. 2004, pp. 74–81. [Online]. Available: https://aclanthology.org/W04-1013
  * [9] P. Anderson, B. Fernando, M. Johnson, and S. Gould, “Spice: Semantic propositional image caption evaluation,” in _Computer Vision – ECCV 2016_ , B. Leibe, J. Matas, N. Sebe, and M. Welling, Eds. Cham: Springer International Publishing, 2016, pp. 382–398.
  * [10] T. Sellam, D. Das, and A. Parikh, “BLEURT: Learning robust metrics for text generation,” in _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Online: Association for Computational Linguistics, Jul. 2020, pp. 7881–7892. [Online]. Available: https://aclanthology.org/2020.acl-main.704
  * [11] T. Zhang*, V. Kishore*, F. Wu*, K. Q. Weinberger, and Y. Artzi, “Bertscore: Evaluating text generation with bert,” in _International Conference on Learning Representations_ , 2020.
  * [12] S. Kim, A. Arora, D. Le, C.-F. Yeh, C. Fuegen, O. Kalinli, and M. L. Seltzer, “Semantic Distance: A New Metric for ASR Performance Analysis Towards Spoken Language Understanding,” in _Proc. Interspeech 2021_ , 2021, pp. 1977–1981.
  * [13] R. Sharma, S. Palaskar, A. W. Black, and F. Metze, “End-to-end speech summarization using restricted self-attention,” in _ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 8072–8076.
  * [14] R. L. MacDonald, P.-P. Jiang, J. Cattiau, R. Heywood, R. Cave, K. Seaver, M. A. Ladewig, J. Tobin, M. P. Brenner, P. C. Nelson, J. R. Green, and K. Tomanek, “Disordered Speech Data Collection: Lessons Learned at 1 Million Utterances from Project Euphonia,” in _Proc. Interspeech 2021_ , 2021, pp. 4833–4837.
  * [15] R. Prabhavalkar, T. N. Sainath, Y. Wu, P. Nguyen, Z. Chen, C.-C. Chiu, and A. Kannan, “Minimum word error rate training for attention-based sequence-to-sequence models,” in _2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE Press, 2018, p. 4839–4843. [Online]. Available: https://doi.org/10.1109/ICASSP.2018.8461809
  * [16] J. Cohen, “A coefficient of agreement for nominal scales,” _Educational and Psychological Measurement_ , vol. 20, no. 1, pp. 37–46, 1960.
  * [17] J. R. Landis and G. G. Koch, “The measurement of observer agreement for categorical data,” _Biometrics_ , vol. 33, no. 1, pp. 159–174, 1977. [Online]. Available: http://www.jstor.org/stable/2529310
  * [18] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [19] H. Akaike, “Information theory and an extension of the maximum likelihood principle,” in _Selected papers of hirotugu akaike_. Springer, 1998, pp. 199–213.


# Rainbow Connection Number and
Connected Dominating Sets

L. Sunil Chandran  Department of Computer Science and Automation,
Indian Institute of Science,
Bangalore -560012, India.
{sunil, anita<EMAIL_ADDRESS>Anita Das  Department of Computer
Science and Automation,
Indian Institute of Science,
Bangalore -560012, India.
{sunil, anita<EMAIL_ADDRESS>Deepak Rajendraprasad  Department
of Computer Science and Automation,
Indian Institute of Science,
Bangalore -560012, India.
{sunil, anita<EMAIL_ADDRESS>Nithin M. Varma  Department of
Computer Science and Engineering,
National Institute of Technology,
Calicut - 673 601, India.
<EMAIL_ADDRESS>
###### Abstract

Rainbow connection number $rc(G)$ of a connected graph $G$ is the minimum
number of colours needed to colour the edges of $G$, so that every pair of
vertices is connected by at least one path in which no two edges are coloured
the same. In this paper we show that for every connected graph $G$, with
minimum degree at least $2$, the rainbow connection number is upper bounded by
$\gamma_{c}(G)+2$, where $\gamma_{c}(G)$ is the connected domination number of
$G$. Bounds of the form $diameter(G)\leq rc(G)\leq diameter(G)+c$, $1\leq
c\leq 4$, for many special graph classes follow as easy corollaries from this
result. This includes interval graphs, AT-free graphs, circular arc graphs,
threshold graphs, and chain graphs all with minimum degree at least $2$ and
connected. We also show that every bridge-less chordal graph $G$ has
$rc(G)\leq 3.radius(G)$. In most of these cases, we also demonstrate the
tightness of the bounds.

An extension of this idea to two-step dominating sets is used to show that for
every connected graph on $n$ vertices with minimum degree $\delta$, the
rainbow connection number is upper bounded by $3n/(\delta+1)+3$. This solves
an open problem from [Schiermeyer, 2009], improving the previously best known
bound of $20n/\delta$ [Krivelevich and Yuster, 2010]. Moreover, this bound is
seen to be tight up to additive factors by a construction mentioned in [Caro
et al., 2008].

Keywords: rainbow connectivity, rainbow colouring, connected dominating set,
connected two-step dominating set, radius, minimum degree.

##  1 Introduction

Edge colouring of a graph is a function from its edge set to the set of
natural numbers. A path in an edge coloured graph with no two edges sharing
the same colour is called a rainbow path. An edge coloured graph is said to be
rainbow connected if every pair of vertices is connected by at least one
rainbow path. Such a colouring is called a rainbow colouring of the graph. The
minimum number of colours required to rainbow colour a connected graph is
called its rainbow connection number, denoted by $rc(G)$. For example, the
rainbow connection number of a complete graph is $1$, that of a path is its
length, that of an even cycle is its diameter, that of an odd cycle is one
more than its diameter, and that of a star is its number of leaves. Note that
disconnected graphs cannot be rainbow coloured and hence the rainbow
connection number for them is left undefined. For a basic introduction to the
topic, see Chapter $11$ in [Chartrand and Zhang, 2008].

The concept of rainbow colouring was introduced in [Chartrand et al., 2008].
Precise values of rainbow connection number for many special graphs like
complete multi-partite graphs, Peterson graph and wheel graphs were also
determined there. It was shown in [Chakraborty et al., 2009] that computing
the rainbow connection number of an arbitrary graph is NP-Hard. To rainbow
colour a graph, it is enough to ensure that every edge of some spanning tree
in the graph gets a distinct colour. Hence order of the graph minus one is an
upper bound for rainbow connection number. There have been attempts to find
better upper bounds for the same in terms of other graph parameters like
connectivity, minimum degree etc.

In the search towards good upper bounds for rainbow connection number, an idea
that turned out to be successful more than once is a “strengthened” notion of
connected $k$-step dominating set (Definition 2 in Section 1.1): a
strengthening so that a rainbow colouring of the induced graph on such a set
can be extended to the whole graph using a constant number of additional
colours. Theorem $1.4$ in [Caro et al., 2008] was proved using a strengthened
connected $1$-step dominating set and Theorem $1.1$ in [Krivelevich and
Yuster, 2010] was proved using a strengthened connected $2$-step dominating
set. A closer examination revealed to us that the additional requirements
imposed on the connected dominating sets in both those cases were far more
restrictive than what was essential. This led us to the investigation of what
is the weakest possible strengthening of a connected dominating set which can
achieve the same. Since every edge incident on a pendant vertex will need a
different colour, it is easy to see that such a dominating set should
necessarily include all the pendant vertices in the graph. Quite surprisingly,
it turns out that this obvious necessary condition is also sufficient!
(Theorem 1 in Section 2). For rainbow connection number of many special graph
classes, the above result gives tight upper bounds which were otherwise
difficult to obtain (Theorem 4 in Section 2). The farthest we could get with
the idea was a curious theorem about chordal graphs (Theorem 5 in Section 2).

A similar inquiry for the weakest strengthening a connected two-step
dominating set (Theorem 7 in Section 2) led us to the solution of an important
open problem in this area regarding the optimal upper bound of rainbow
connection number in terms of minimum degree. (See Theorem 10 in Section 2 and
the remarks therein). As an intermediate step in solving the above problem, we
also discovered a tight upper bound on the size of a minimum connected two-
step dominating set of a graph in terms of its minimum degree (Theorem 8 in
Section 2). To the best of our knowledge, this bound is not yet reported in
literature. It may have applications beyond the realm of rainbow colouring.
For instance, Theorem 8 immediately gives an upper bound on radius of every
graph in terms of its minimum degree (Corollary 9 in Section 2) which
marginally improves the one reported in [Erdős et al., 1989].

###  1.1 Preliminaries

See Table 1 for the notations employed throughout the paper.

Table 1: Notations. $G$ is a graph, $v$ a vertex in $G$ and $S$ a subset of vertices in $G$. $k$ is a non-negative integer. $V(G)$ |  Vertex set of $G$.
---|---
$E(G)$ |  Edge set of $G$.
$|G|$ |  Number of vertices in $G$ or order of $G$.
$\delta(G)$ |  Minimum degree of $G$
$pen(G)$ |  Number of pendant vertices in $G$
$rc(G)$ |  Rainbow connection number of $G$
$d(u,v)$ |  Distance between vertices $u$ and $v$
$ecc(v)$ |  Eccentricity of $v$
$diam(G)$ |  Diameter of $G$
$rad(G)$ |  Radius of $G$
$\gamma_{c}^{k}(G)$ |  Connected $k$-step domination number of $G$
$\gamma_{c}(G)$ |  $\gamma^{1}_{c}(G)$, Connected domination number of $G$
$N^{k}(S)$ |  Set of all vertices at distance exactly $k$ from set $S$
$N^{k}(v)$ | $N^{k}(\\{v\\})$
$N(S)$ |  $N^{1}(S)$, Neighbourhood of $S$
$N(v)$ |  $N^{1}(\\{v\\})$, Neighbourhood of $v$
$G[S]$ |  Induced subgraph of $G$ on $S$

All graphs considered in this article are finite, simple and undirected. The
length of a path is its number of edges. An edge in a connected graph is
called a bridge, if its removal disconnects the graph. A graph with no bridges
is called a bridge-less graph.

######  Definition 1.

Let $G$ be a connected graph. The distance between two vertices $u$ and $v$ in
$G$, denoted by $d(u,v)$ is the length of a shortest path between them in $G$.
The eccentricity of a vertex $v$ is $ecc(v):=\max_{x\in V(G)}{d(v,x)}$. The
diameter of $G$ is $diam(G):=\max_{x\in V(G)}{ecc(x)}$. The radius of $G$ is
$rad(G):=\min_{x\in V(G)}{ecc(x)}$. Distance between a vertex $v$ and a set
$S\subseteq V(G)$ is $d(v,S):=\min_{x\in S}{d(v,x)}$. The $k$-step open
neighbourhood of a set $S\subseteq V(G)$ is $N^{k}(S):=\\{x\in
V(G)|d(x,S)=k\\}$, $k\in\\{0,1,2,\cdots\\}$. The degree of a vertex $v$ is
$degree(v):=|N^{1}(\\{v\\})|$. The minimum degree of $G$ is
$\delta(G):=\min_{x\in V(G)}{degree(x)}$. A vertex is called pendant if its
degree is $1$ and isolated if its degree is $0$.

######  Definition 2.

Given a graph $G$, a set $D\subseteq V(G)$ is called a $k$-step dominating set
of $G$, if every vertex in $G$ is at a distance at most $k$ from $D$. Further,
if $D$ induces a connected sub-graph of $G$, it is called a connected $k$-step
dominating set of $G$. The cardinality of a minimum connected $k$-step
dominating set in $G$ is called its connected $k$-step domination number
$\gamma^{k}_{c}(G)$. When $k=1$, we may omit the qualifier “$1$-step” in the
above names and the superscript $1$ in the notation.

Note that connected $k$-step dominating sets exist only for connected graphs.
Connected $k$-step domination number is left undefined otherwise.

######  Definition 3.

An intersection graph of a family of sets $\mathcal{F}$, is a graph whose
vertices can be mapped to sets in $\mathcal{F}$ such that there is an edge
between two vertices in the graph if and only if the corresponding two sets in
$\mathcal{F}$ have a non-empty intersection. An interval graph is an
intersection graph of intervals on the real line. A unit interval graph is an
intersection graph of unit length intervals on the real line. A circular arc
graph is an intersection graph of arcs on a circle.

######  Definition 4.

An independent triple of vertices $x$, $y$, $z$ in a graph $G$ is an
asteroidal triple $($AT$)$, if between every pair of vertices in the triple,
there is a path that does not contain any neighbour of the third. A graph
without asteroidal triples is called an AT-free graph.

######  Definition 5.

A graph $G$ is a threshold graph, if there exists a weight function
$w:V(G)\rightarrow\mathbb{R}$ and a real constant $t$ such that two vertices
$u,v\in V(G)$ are adjacent if and only if $w(u)+w(v)\geq t$.

######  Definition 6.

A bipartite graph $G(A,B)$ is called a chain graph if the vertices of $A$ can
be ordered as $A=(a_{1},a_{2},\cdots,a_{k})$ such that $N(a_{1})\subseteq
N(a_{2})\subseteq\cdots\subseteq N(a_{k})$ [Yannakakis, 1982].

######  Definition 7.

A graph $G$ is called chordal, if there is no induced cycle of length greater
than $3$.

##  2 Our Results

The main ideas in this paper are captured in Theorem 1, Theorem 7 and Theorem
8. The other results are consequences of them. Among the results, Theorem 10
demands a special mention due to the prominence of the question it answers in
the area of rainbow colouring. To state Theorem 1 in its full generality, we
need to make one new definition.

######  Definition 8 (Two-way dominating set).

A dominating set $D$ in a graph $G$ is called a two-way dominating set if
every pendant vertex of $G$ is included in $D$. In addition, if $G[D]$ is
connected, we call $D$ a connected two-way dominating set.

######  Remark 1.

If $\delta(G)\geq 2$, then every (connected) dominating set in $G$ is a
(connected) two-way dominating set. We use the name “two-way domination” since
the definition implies that every vertex in $V(G)\backslash D$ has at least
two edge disjoint paths to $D$.

######  Theorem 1.

If $D$ is a connected two-way dominating set in a graph $G$, then

$rc(G)\leq rc(G[D])+3.$

Proof is given in Section 3.1

######  Remark 2.

The reader may wonder why the pendant vertices had to be included in the
dominating set $D$. Our strategy is to colour $G[D]$ first and then colour all
the edges outside using a constant number (in this case $3$) of additional
colours ensuring rainbow connectivity. Pendent vertices are always a
bottleneck for rainbow colouring since no two pendant edges (edges incident on
pendant vertices) can share the same colour. Hence the restriction.

######  Corollary 2.

For every connected graph $G$, with $\delta(G)\geq 2$,

$rc(G)\leq\gamma_{c}(G)+2.$

###### Proof.

This follows from Theorem 1 since (i) in this case, every connected dominating
set in $G$ is a connected two-way dominating set and (ii)
$rc(G[D])\leq|D|-1=\gamma_{c}(G)-1$ for a minimum connected dominating set $D$
in $G$. ∎

######  Corollary 3.

For every connected graph $G$,

$rc(G)\leq\gamma_{c}(G)+pen(G)+2.$

###### Proof.

This follows from Theorem 1 since adding all the pendant vertices to a minimum
connected dominating set gives a connected two-way dominating set of size at
most $\gamma_{c}(G)+pen(G)$. ∎

Diameter of a graph is a trivial lower bound for its rainbow connection
number. Theorem 1 gives upper bounds which are only a small additive constant
above the diameter for many special graph classes.

######  Theorem 4.

Let $G$ be a connected graph with $\delta(G)\geq 2$. Then,

  1. $(i)$

if $G$ is an interval graph, $diam(G)\leq rc(G)\leq diam(G)+1$,

  2. $(ii)$

if $G$ is AT-free, $diam(G)\leq rc(G)\leq diam(G)+3$,

  3. $(iii)$

if $G$ is a threshold graph, $diam(G)\leq rc(G)\leq 3$,

  4. $(iv)$

if $G$ is a chain graph, $diam(G)\leq rc(G)\leq 4$,

  5. $(v)$

if $G$ is a circular arc graph, $diam(G)\leq rc(G)\leq diam(G)+4$.

Moreover, there exist interval graphs, threshold graphs and chain graphs with
minimum degree at least $2$ and rainbow connection number equal to the
corresponding upper bound above. There exists an AT-free graph $G$ with
minimum degree at least $2$ and $rc(G)=diam(G)+2$, which is $1$ less than the
upper bound above.

######  Remark 3.

The upper bounds follow from Theorem 1 since (i) every interval graph $G$
which is not isomorphic to a complete graph has a dominating path of length at
most $diam(G)-2$, (ii) every AT-free graph $G$ has a dominating path of length
at most $diam(G)$, (iii) a maximum weight vertex in a connected threshold
graph $G$ is a dominating vertex, (iv) every connected chain graph $G$ has a
dominating edge, and (v) every circular arc graph $G$, which is not an
interval graph, has a dominating cycle of diameter at most $diam(G)$.

Tight examples and proofs for non-trivial claims made in the above remark are
given in Section 3.4. We could not find tight examples for AT-free and
circular arc graphs. It may be interesting to see whether those two upper
bounds can be improved.

Another interesting application of Theorem 1 is the following result on
chordal graphs. It is curious since chordal graphs, unlike interval graphs or
AT-free graphs, can grow in more than two directions and hence they need not
contain dominating paths in general.

######  Theorem 5.

If $G$ is a bridge-less chordal graph, then $rc(G)\leq 3.rad(G)$. Moreover,
there exists a bridge-less chordal graph with $rc(G)=3.rad(G)$.

Proof is given in Section 3.6. The main idea is that we can induct on the
radius of the graph and use Theorem 1 to prove the induction step.

Theorem 4$(i)$ gives $rc(G)\leq diam(G)+1$ for every unit interval graph $G$.
We have a stronger result, using a different approach.

######  Theorem 6.

If $G$ is a unit interval graph such that $\delta(G)\geq 2$, then
$rc(G)=diam(G)$.

Proof is given in Section 3.6

The extension of the idea of two-way domination to two-way two-step domination
is what gives the remaining results. We need to make one more definition to
state the next major theorem (Theorem 7) in its full generality.

######  Definition 9 (Two-way two-step dominating set).

A (connected) two-step dominating set $D$ of vertices in a graph $G$ is called
a $($connected$)$ two-way two-step dominating set if (i) every pendant vertex
of $G$ is included in $D$ and (ii) every vertex in $N^{2}(D)$ has at least two
neighbours in $N^{1}(D)$.

######  Remark 4.

As in the two-way ($1$-step) dominating set, here too every vertex $v\in
V(G)\backslash D$ has two edge disjoint paths into $D$. Hence the adjective
“two-way”. It may be noted that, just like pendant edges, no two bridges in a
graph can be coloured the same in any rainbow colouring. Hence the restriction
of two-way domination is in some sense necessary to obtain colouring
strategies which use only a constant number of extra colours outside the
dominating set.

######  Theorem 7.

If $D$ is a connected two-way two-step dominating set in a graph $G$, then

$rc(G)\leq rc(G[D])+6.$

Proof is given in Section 3.2

######  Theorem 8.

(i) Every connected graph $G$ of order $n$ and minimum degree $\delta$ has a
connected two-step dominating set $D$ of size at most
$\frac{3(n-|N^{2}(D)|)}{\delta+1}-2$. (ii) Every connected graph $G$ of order
$n\geq 4$ and minimum degree $\delta$ has a connected two-way two-step
dominating set $D^{\prime}$ of size at most $\frac{3n}{\delta+1}-2$. Moreover,
for every $\delta\geq 2$, there exist infinitely many connected graphs $G$
such that $\gamma^{2}_{c}(G)\geq\frac{3(n-2)}{\delta+1}-4$.

Proof is given in Section 3.3

It is easy to see that the radius of any connected graph is at most $k$ more
than the radius of its $k$-step connected dominating set. Moreover, the radius
of any graph $H$ is at most $|H|/2$. Hence the following corollary is also
immediate.

######  Corollary 9.

For every connected graph $G$ of order $n$ and minimum degree $\delta$,

$rad(G)\leq\frac{3n}{2(\delta+1)}+1.$

This bound marginally improves the one reported in [Erdős et al., 1989],
namely $\frac{3(n-3)}{2(\delta+1)}+5$ and the proof is shorter. Note that we
can similarly upper bound the diameter of $G$ by $\frac{3n}{\delta+1}+1$. But
the corresponding bound reported in [Erdős et al., 1989] is better, namely
$\frac{3n}{\delta+1}-1$.

######  Theorem 10.

For every connected graph $G$ of order $n$ and minimum degree $\delta$,

$rc(G)\leq\frac{3n}{\delta+1}+3.$

Moreover, for every $\delta\geq 2$, there exist infinitely many graphs $G$
such that $rc(G)\geq\frac{3(n-2)}{\delta+1}-1$.

###### Proof.

Observe that the connected (two-way two-step dominating) set $D$ can be
rainbow coloured using $|D|-1$ colours by ensuring that every edge of some
spanning tree gets distinct colours. So the upper bound follows immediately
from Theorems 7 and 8(ii). The family of tight examples is demonstrated in
[Caro et al., 2008]. ∎

######  Remark 5.

Theorem 10 nearly settles the investigation for an optimal upper bound of
rainbow connection number in terms of minimum degree which was initiated in
[Caro et al., 2008]. There it was shown that, if $\delta(G)\geq 3$, then
$rc(G)<5n/6$. For general $\delta$, they had given two upper bounds viz.,
$(1+o_{\delta}(1))n\ln(\delta)/\delta$ and $(4\ln(\delta)+3)n/\delta$. They
had also shown a construction for a family of graphs with
$diam(G)=\frac{3(n-2)}{\delta+1}-1$, leaving a gap of $\ln(\delta)$ factor
between the bound and the construction. They remarked that the problem of
finding an optimum bound for $rc(G)$ in terms of $\delta$ is an intriguing
problem and conjectured that for $\delta(G)\geq 3$, $rc(G)<3n/4$. Schiermeyer
proved the above conjecture and raised the question whether $rc(G)\leq
3n/(\delta+1)$ for all values of $\delta$ [Schiermeyer, 2009]. If the answer
is yes, then for graphs with linear minimum degree $\epsilon n$, the rainbow
connection number is bounded by a constant. This was indeed shown to be the
case in [Chakraborty et al., 2009]. But their proof employed Szemerédi’s
Regularity Lemma and hence the bound was a tower function in $1/\epsilon$.
This was considerably improved in [Krivelevich and Yuster, 2010], where it was
shown that $rc(G)\leq 20n/\delta$ for any connected graph. This is the best
known bound for the problem till date. Theorem 10 improves it and answers the
question from [Schiermeyer, 2009] in affirmative but up to an additive
constant of $3$. Moreover, this bound is seen to be tight up to additive
factors by the construction mentioned in [Caro et al., 2008].

##  3 Proofs

###  3.1 Proof of Theorem 1

Statement. If $D$ is a connected two-way dominating set in a graph $G$, then
$rc(G)\leq rc(G[D])+3$.

###### Proof.

We prove the theorem by demonstrating a rainbow colouring that uses at most
$rc(G[D])+3$ colours. For $x\in N^{1}(D)$, its neighbours in $D$ will be
called foots of $x$, and the corresponding edges will be called legs of $x$.
Any rainbow path whose edge colours are contained in $\\{1,2,\cdots,k\\}$ will
be called a $k$-rainbow path.

Rainbow colour $G[D]$ using colours $\\{1,2,\cdots,k:=rc(G[D])\\}$. Let
$H:=G[V(G)\backslash D]$. Partition $V(H)$ into sets $X$, $Y$ and $Z$ as
follows. $Z$ is the set of all isolated vertices of $H$. In every non-
singleton connected component of $H$, choose a spanning tree. This gives a
spanning forest on $V(H)\backslash Z$ with no isolated vertices. Choose $X$
and $Y$ as any one of the bipartitions defined by this forest. Colour every
$X\mbox{--}D$ edge with $k+1$, every $Y\mbox{--}D$ edge with $k+2$ and every
edge in $H$ with $k+3$. Since $D$ is a two-way dominating set, there are no
pendant vertices outside $D$. Therefore, every vertex in $Z$ will have at
least two legs. Colour one of them with $k+1$ and all the others with $k+2$.

We show that the above colouring is a rainbow colouring of $G$. For pairs in
$D\times D$, there is already a $k$-rainbow path connecting them in $G[D]$.
For a pair $(x,y)\in N^{1}(D)\times D$, join any leg of $x$ (coloured $k+1$ or
$k+2$) with the $k$-rainbow path from the corresponding foot to $y$ in $G[D]$.
For a pair $(x,y)\in(X\cup Z)\times(Y\cup Z)$ join a $k+1$ leg of $x$ and a
$k+2$ leg of $y$ with a $k$-rainbow path between the corresponding foots in
$G[D]$. For a pair in $(x,x^{\prime})\in X\times X$, $x$ has a neighbour
$y(x)\in Y$ from the spanning forest. Join the corresponding $x\mbox{--}y(x)$
edge (coloured $k+3$) with the $y(x)\mbox{--}x^{\prime}$ $(k+2)$-rainbow path
mentioned earlier. Similarly every pair $(y,y^{\prime})\in Y\times Y$ is also
rainbow connected. ∎

###  3.2 Proof of Theorem 7

Statement. If $D$ is a connected two-way two-step dominating set in a graph
$G$, then $rc(G)\leq rc(G[D])+6$.

###### Proof.

We prove the theorem by demonstrating a rainbow colouring that uses at most
$rc(G[D])+6$ colours. For $x\in N^{k}(D)$, its neighbours in $N^{k-1}(D)$,
$k=1,2$ will be called foots of $x$ and the corresponding edges will be called
legs. Any rainbow path whose edge colours are contained in
$\\{1,2,\cdots,k\\}$ will be called a $k$-rainbow path.

Rainbow colour $G[D]$ using colours $\\{1,2,\cdots,k:=rc(G[D])\\}$. Construct
a new graph $H$ on $N^{1}(D)$ with the edge set

$\displaystyle E(H)$ $\displaystyle=$ $\displaystyle\\{\\{x,y\\}|x,y\in
N^{1}(D),\\{x,y\\}\in E(G)\textnormal{ or }$ $\displaystyle\exists z\in
N^{2}(D)\textnormal{ such that }\\{x,z\\},\\{y,z\\}\in E(G)\\}.$

Recall that, in a two-way two-step dominating set $D$, there are no pendant
vertices outside $D$ and every vertex in $N^{2}(D)$ has at least two
neighbours in $N^{1}(D)$. Hence in the above graph $H$, the isolated vertices
are only those which have all their neighbours (at least $2$) in $D$. Call
their collection $Z$. Choose a spanning tree in every non-singleton connected
component of $H$. This gives a spanning forest of $V(H)\backslash Z$ with no
isolated vertices. Let $X$ and $Y$ be any bipartition defined by this forest.
Colour every $X\mbox{--}D$ edge with $(k+1)$ and every $Y\mbox{--}D$ edge with
$(k+2)$. For every vertex in $Z$, colour one of its legs with $(k+1)$ and the
remaining with $(k+2)$. Colour every edge of $G$ within $N^{1}(D)$ by $k+3$.
Partition the vertices of $N^{2}(D)$ into $A$ and $B$ as follows. $A=\\{x\in
N^{2}(D)|N(x)\cap X\neq\emptyset\textnormal{ and }N(x)\cap Y\neq\emptyset\\}$
and $B=N^{2}(D)\backslash A$. Colour every $A\mbox{--}X$ edge with $(k+3)$ and
every $A\mbox{--}Y$ edge with $(k+4)$. First we claim that
$G^{\prime}:=G[D\cup N^{1}(D)\cup A]$ is rainbow connected.

By following the same arguments as in proof of Theorem 1, it can be easily
seen that every pair in $D\times D$, is connected by a $k$-rainbow path and
every pair in $N^{1}(D)\times D$ and $(X\cup Z)\times(Y\cup Z)$ is connected
by a $(k+2)$-rainbow path. Notice that for every vertex $x\in X$, there exists
$y(x)\in Y$ such that $x\mbox{--}y(x)$ is an edge in the spanning forest.
Vertices $x$ and $y(x)$ are connected either by a single $(k+3)$ edge or a
$(k+3,k+4)$ path. Hence between any pair $(x,x^{\prime})\in X\times X$, we can
find a rainbow path by joining the $x\mbox{--}y(x)$ path with the
$y(x)\mbox{--}x^{\prime}$ $(k+2)$-rainbow path. Similarly any pair in $Y\times
Y$ is also rainbow connected. Any pair $(a,a^{\prime})\in A\times A$ can be
rainbow connected by joining the $(k+3)$ leg of $a$ whose foot will be in $X$
and $(k+4)$ leg of $a^{\prime}$ whose foot will be in $Y$ with the
$(k+2)$-rainbow path between the two foots. Similarly we can connect any
vertex $a\in A$ with any vertex in $x\in D\cup N^{1}(D)$ by using the $(k+3)$
leg of $a$ if $x\in Y$ and the $(k+4)$ leg of $a$ otherwise. Hence
$G^{\prime}$ is rainbow coloured using colours $1$ to $k+4$.

Now only the vertices of $B$ remain. All of them have at least two neighbours
in $G^{\prime}$. Colour one edge to $G^{\prime}$ with $k+5$ and all the other
edges with $k+6$. It is easily seen that we now have a rainbow colouring of
entire $G$. ∎

###  3.3 Proof of Theorem 8

Statement. (i) Every connected graph $G$ of order $n$ and minimum degree
$\delta$ has a connected two-step dominating set $D$ of size at most
$\frac{3(n-|N^{2}(D)|)}{\delta+1}-2$. (ii) Every connected graph $G$ of order
$n\geq 4$ and minimum degree $\delta$ has a connected two-way two-step
dominating set $D^{\prime}$ of size at most $\frac{3n}{\delta+1}-2$. Moreover,
for every $\delta\geq 2$, there exist infinitely many connected graphs $G$
such that $\gamma^{2}_{c}(G)\geq\frac{3(n-2)}{\delta+1}-4$.

###### Proof.

The case when $\delta\leq 1$ can be checked easily. So we assume $\delta\geq
2$ and execute the following two stage procedure.

  1. Stage $1$.

$D=\\{u\\}$, for some $u\in V(G)$.
While $N^{3}(D)\neq\emptyset$,
{
Pick any $v\in N^{3}(D)$. Let $(v,x_{2},x_{1},x_{0})$, $x_{0}\in D$ be a
shortest $v\mbox{--}D$ path.
$D=D\cup\\{x_{1},x_{2},v\\}$.
}

  2. Stage $2$.

$D^{\prime}=D$.
While $\exists v\in N^{2}(D^{\prime})$ such that $|N(v)\cap
N^{2}(D^{\prime})|\geq\delta-1$,
{
$D^{\prime}=D^{\prime}\cup\\{x_{1},v\\}$ where $(v,x_{1},x_{0})$, $x_{0}\in
D^{\prime}$ is a shortest $v\mbox{--}D^{\prime}$ path.
}

Clearly $D$ remains connected after every iteration in Stage $1$. Since Stage
$1$ ends only when $N^{3}(D)=\emptyset$, the final $D$ is a two step
dominating set. Let $k_{1}$ be the number of iterations executed in Stage $1$.
$|D\cup N^{1}(D)|\geq\delta+1$ when Stage $1$ starts. Since a new vertex from
$N^{3}(D)$ is added to $D$, $|D\cup N^{1}(D)|$ increases by at least
$\delta+1$ in every iteration. Therefore, when Stage $1$ ends,
$k_{1}+1\leq\frac{|D\cup N^{1}(D)|}{\delta+1}=\frac{n-|N^{2}(D)|}{\delta+1}$.
Since $D$ starts as a singleton set and each iteration adds $3$ more vertices,
$|D|=3k_{1}+1\leq\frac{3(n-|N^{2}(D)|)}{\delta+1}-2$. This proves Part (i) of
the theorem.

$D^{\prime}$ remains a connected two-step dominating set throughout Stage $2$.
Stage $2$ ends only when every vertex $v\in N^{2}(D^{\prime})$ has at most
$\delta-2$ neighbours in $N^{2}(D^{\prime})$. Hence at least two neighbours of
$v$ are in $N^{1}(D^{\prime})$. Moreover, since $\delta\geq 2$, there are no
pendant vertices in $G$. So the final $D^{\prime}$ is a connected two-way two-
step dominating set. Let $k_{2}$ be the number of iterations executed in Stage
$2$. Since we add to $D^{\prime}$ a vertex who has at least $\delta-1$
neighbours in $N^{2}(D^{\prime})$, $|N^{2}(D^{\prime})|$ reduces by at least
$\delta$ in every iteration. Since we started with $|N^{2}(D)|$ vertices,
$k_{2}\leq\frac{|N^{2}(D)|}{\delta}$. Since we add $2$ vertices to
$D^{\prime}$ in each iteration,
$|D^{\prime}|=|D|+2k_{2}\leq\frac{3(n-|N^{2}(D)|)}{\delta+1}-2+\frac{2|N^{2}(D)|}{\delta}\leq\frac{3n}{\delta+1}-2$
for $\delta\geq 2$. This proves Part (ii).

For every $\delta>2$, construction for infinitely many graphs $G$ with
$diam(G)=\frac{3(n-2)}{\delta+1}-1$ is reported in [Erdős et al., 1989] and
[Caro et al., 2008]. It is easy to see that for every graph $G$,
$diam(G)\leq\gamma^{2}_{c}(G)+3$. Hence
$\gamma^{2}_{c}(G)\geq\frac{3(n-2)}{\delta+1}-4$ for every graph in that
family. ∎

###  3.4 Proof of Theorem 4

Among the remarks made below Theorem 4, only (i), (ii) and (v) are non-
trivial. Proof of (ii) can be found in [Corneil et al., 1997]. We give proofs
of (i) and (v) below.

Statement (i). Every interval graph $G$ which is not isomorphic to a complete
graph has a dominating path of length at most $diam(G)-2$.

###### Proof.

Consider an interval representation of $G=(V,E)$. For $u\in V$ let $l(u)$ and
$r(u)$ represent the left end point and the right end point of $u$,
respectively. Let $A=\min_{u\in V}r(u)$ and $B=\max_{u\in V}l(u)$. Let $a$ and
$b$ be vertices such that $r(a)=A$ and $l(b)=B$. Let $S_{1}=\\{u\in V|l(u)\leq
A\\}$ and $S_{2}=\\{u\in V|r(u)\geq b\\}$. Clearly $S_{1}$ and $S_{2}$ induce
cliques in $G$ and thus we can assume that for each $u\in S_{1}$, $l(u)=A$ and
for each $u\in S_{2}$, $r(u)=B$. Thus the intervals corresponding to $a$ and
$b$ are point intervals. Since $G$ is not a complete graph, $A\neq B$.
Moreover, since $G$ is connected, there exists $u\in S_{1}$ and $v\in S_{2}$
such that $u,v$ are not point intervals. Let $x\in S_{1}$ and $y\in S_{2}$ be
two not necessarily distinct vertices such that the distance from $x$ to $y$
is minimum among all such pairs. Clearly $x\neq a$, $y\neq b$ and the shortest
path $P$ between $x$ and $y$ is a dominating path in $G$. Moreover, since $a$
and $b$ are point intervals, $d(a,b)\geq d(x,y)+2$. Hence length of $P$ is at
most $d(a,b)-2\leq diam(G)-2$ as required. ∎

Statement (v). Every circular arc graph $G$, which is not an interval graph,
has a dominating cycle of diameter at most $diam(G)$.

###### Proof.

Let $\mathcal{C}$ denote the circle in the circular arc representation of $G$.
We will use the same symbol to denote a vertex of $G$ and its corresponding
arc if there is no chance of confusion. Let $C_{k}=(c_{1},c_{2},\cdots,c_{k})$
be a minimum collection of arcs that cover $\mathcal{C}$. It is easy to see
that $C_{k}$ is a dominating cycle of $G$. We claim that $diam(C_{k})\leq
diam(G)$.

For contradiction, let us assume $diam(C_{k})>diam(G)$. Hence there exists
$c_{i},c_{j}\in V(C_{k}),\;i<j$, such that their distance in $G$ is less than
their distance in $C_{k}$. Let $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ denote
the two disjoint segments of $\mathcal{C}\backslash(c_{i}\cup c_{j})$. Let
$(c_{i}=x_{0},x_{1},\cdots,x_{l},x_{l+1}=c_{j})$ be a shortest
$c_{i}\mbox{--}c_{j}$ path in $G$. The set of arcs
$X=(x_{1},x_{2},\cdots,x_{l})$ will surely cover at least one of
$\mathcal{S}_{1}$ or $\mathcal{S}_{2}$. Let $R:=(c_{i+1},c_{i+2},\cdots
c_{j-1})$ and $L:=C_{k}\mbox{--}(R\cup\\{c_{i},c_{j}\\})$. Since arcs
corresponding to $C_{k}$ cover the circle, the arcs corresponding one of them,
say $L$ will cover the $\mathcal{S}_{i}$ not covered by $X$. By assumption
$|L|,|R|>|X|=l$. So we can get a smaller collection of arcs covering
$\mathcal{C}$ by replacing $R$ with $X$ in $C_{k}$ contradicting the
minimality of $C_{k}$. ∎

#### Tight Examples

We give examples to show that the upper bounds in $(i)$, $(iii)$ and $(iv)$ of
Theorem 4 are tight. We also give an example to show that the upper bound in
$(ii)$ is nearly tight.

$x_{1}$$x_{2}$$x_{3}$$x_{d-3}$$x_{d-2}$$x_{d-1}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$z_{1}$$z_{2}$$z_{3}$$z_{4}$
Figure 1: Example of an interval graph with minimum degree $2$, diameter $d$
and rainbow connection number $d+1$.

######  Example 1 (An interval graph $G$ with $\delta(G)\geq 2$ and $rc(G)\geq
d+1$ for any given diameter $d$).

Consider the graph in Figure 1. It is an interval graph with minimum degree
$2$ and diameter $d$. We claim that it cannot be rainbow coloured using $d$
colours.

Let $Y=\\{y_{1},y_{2},y_{3},y_{4}\\}$ and $Z=\\{z_{1},z_{2},z_{3},z_{4}\\}$.
Every pair $(y,z)\in Y\times Z$ is at a distance $d$ apart and they have only
one $d$-length path between them. Hence every shortest $Y\mbox{--}Z$ path
should be rainbow coloured. So in any rainbow colouring which used only $d$
colours, every $Y\mbox{--}x_{1}$ edge is forced to share the same colour.
Hence there is no rainbow path between $y_{1}$ and $y_{3}$.

######  Example 2 (An AT-free graph $G$ with $\delta(G)\geq 2$ and
$rc(G)=diam(G)+2$).

$K_{2,n}$, the complete bipartite graph with $2$ vertices in one part and $n$
in the other, is an AT-free graph with minimum degree $2$ and diameter $2$.
For $n\geq 10$, its rainbow connection number is known to be $4$ (Theorem
$2.6$ in [Chartrand et al., 2008]).

$e$$y_{1}$$y_{2}$$x_{1}$$x_{2}$$x_{3}$$x_{n-3}$$x_{n-2}$$x_{n-1}$ Figure 2:
Example of a threshold graph with minimum degree $2$ and rainbow connection
number $3$. Also an example of a bridge-less chordal graph with
$rc(G)=3.rad(G)$.

######  Example 3 (A threshold graph $G$ with $\delta(G)\geq 2$ and $rc(G)\geq
3$).

Consider the graph $G$ in Figure 2 which can be obtained by adding an edge $e$
between the two vertices in the smaller part of $K_{2,n-1}$, $n\geq 10$. It is
easily seen to be a threshold graph (Two dominating vertices, $y_{1}$ and
$y_{2}$, can be given a weight $1$, others a weight $0$ and threshold being
$1$). For contradiction let us assume that $G$ can be coloured using $2$
colours. Subdividing $e$ gives a $K_{2,n}$. It is easy to see that by
retaining the colour of $e$ to one of the two new edges and giving a third
colour to the other is a rainbow colouring of $K_{2,n}$. This is a
contradiction to the fact that $rc(K_{2,n})=4$ for $n\geq 10$. (Theorem $2.6$
in [Chartrand et al., 2008]).

######  Example 4 (A chain graph $G$ with $\delta(G)\geq 2$ and $rc(G)\geq
4$).

$K_{2,n}$ is a chain graph with minimum degree $2$ and diameter $2$. For
$n\geq 10$, it is known to have a rainbow connection number of $4$ (Theorem
$2.6$ in [Chartrand et al., 2008]).

###  3.5 Proof of Theorem 5

######  Lemma 11.

If $v$ is a vertex of eccentricity $r$ in a bridge-less chordal graph $G$,
then $G[\bigcup_{i=0}^{l}{N^{i}(v)}]$ is a bridge-less chordal graph for all
$l\in\\{0,1,\cdots,r\\}$.

###### Proof.

It is enough to show that $G^{\prime}=G[\bigcup_{i=0}^{r-1}{N^{i}(v)}]$ is a
bridge-less chordal graph. The general result will follow by repeated
application of the above. Every induced subgraph of a chordal graph is also
chordal. Hence it suffices to show that $G^{\prime}$ is bridge-less.

For contradiction, let us assume that $b=(x,y)\in E(G^{\prime})$ is a bridge
of $G^{\prime}$. Consider a BFS tree $T^{\prime}$ of $G^{\prime}$ rooted on
$v$. Since $b$ is a bridge, $b\in E(T^{\prime})$ (else $G^{\prime}\backslash
b$ will be connected). Without loss of generality let $x\in N^{i-1}(v)$ and
$y\in N^{i}(v)$, $i\leq r-1$. Since $G$ is bridge-less by assumption, there
exists a path from $x$ to $y$ in $G\backslash b$. Consider a shortest such
path $P$. Since $P$ is a shortest path, $P\cup b$ is an induced cycle in $G$.
Since $G^{\prime}\backslash b$ is disconnected, $P$ has to contain at least
one vertex $z$ from $N^{r}(v)$. Further, since $x\in N^{i-1}(v),\;i-1\leq r-2$
cannot be adjacent to $z$, $P$ should contain at least one more vertex $w$
from $G^{\prime}$. Hence $P\cup\\{b\\}$ is an induced cycle of length at least
$4$ in $G$ which contradicts the assumption that $G$ is chordal. ∎

With the above lemma, now we can easily give the proof of Theorem 5

Statement. If $G$ is a bridge-less chordal graph, then $rc(G)\leq 3.rad(G)$.
Moreover, there exists a bridge-less chordal graph with $rc(G)=3.rad(G)$.

###### Proof.

We will prove the statement by an induction on radius. Any graph with radius
zero is a singleton vertex which can be rainbow coloured using zero colours.
Hence the statement is true for radius zero. Let the statement be true up till
a radius of $r-1$.

Now, let $G$ be any bridge-less chordal graph with radius $r$. Let $v$ be a
central vertex of $G$, i.e., a vertex with eccentricity $r$. By Lemma 11,
$G^{\prime}=G[\bigcup_{i=0}^{r-1}{N^{i}(v)}]$ is also a bridge-less chordal
graph and its radius is at most $r-1$. Hence by induction hypothesis
$rc(G^{\prime})\leq 3(r-1)$. Since minimum degree is at least two for any
bridge-less graph, $V(G^{\prime})$ is a connected two-way dominating set for
$G$. Hence by Theorem 1, $rc(G)\leq rc(G^{\prime})+3\leq 3r$. Thus the
statement is true for all values of radius.

Consider the graph $G$ in Figure 2. It is a bridge-less chordal graph with
radius $1$ and rainbow connection number is $3$. (See the argument under
Example 3 in Section 3.4.)

∎

###  3.6 Proof of Theorem 6

Statement. If $G$ is a unit interval graph such that $\delta(G)\geq 2$, then
$rc(G)=diam(G)$.

###### Proof.

Let $G$ be a unit interval graph with $\delta(G)\geq 2$. Consider a unit
interval representation of $G$. For $u\in V(G)$, let $l(u)$ and $r(u)$
represent the left and right end points of $u$ respectively. Let $x$ and $y$
be the vertices corresponding to the intervals with leftmost left end and
rightmost right end respectively. Consider a shortest path $P$ between $x$ and
$y$, say $P=(x=x_{1},x_{2},\ldots,x_{k}=y)$. Clearly $k\leq diam(G)+1$ and $P$
is a dominating path in $G$. Let $S_{i}=\\{u\in V(G)|l(u)\leq r(x_{i})\leq
r(u)\\}$, $i=1,2,\cdots,k-1$. It is easily seen that each $S_{i}$ induces a
clique in $G$. Let $H$ be a subgraph of $G$ with
$V(H)=\bigcup_{i=1}^{k-1}{S_{i}}$ and $E(H)=\bigcup_{i=1}^{k-1}E(G[S_{i}])$.
Since $G$ is a unit interval graph, $H$ contains all edges incident on $P$
(including those in $P$). Hence $H$ is a spanning subgraph of $G$. Colour
every edge in $E(G[S_{i}])\backslash\bigcup_{j=1}^{i-1}{E(G[S_{j}])}$ with
colour $i$ for $i=1,2,\cdots,k-1$. This colours every edge of $H$ using at
most $k-1$ colours. Colour the remaining edges of $G$ using colour $1$. We
claim that this is a rainbow colouring of $G$.

For any pair of vertices, $u$ and $v$ in $V(G)$, consider any shortest path
$R$ between them in $H$. Clearly $R$ does not contain more than one edge from
a single clique. In the above colouring, two edges of $H$ will get the same
colour only if they belong to the same clique. Hence $R$ is a rainbow path. So
$rc(G)\leq k-1\leq diam(G)$. Since diameter is a lower bound for rainbow
connection number, $rc(G)=diam(G)$. ∎

## References

  * [Caro et al., 2008] Caro, Y., Lev, A., Roditty, Y., Tuza, Z., and Yuster, R. (2008).  On rainbow connection.  the electronic journal of combinatorics, 15(R57):1.
  * [Chakraborty et al., 2009] Chakraborty, S., Fischer, E., Matsliah, A., and Yuster, R. (2009).  Hardness and algorithms for rainbow connection.  Journal of Combinatorial Optimization, pages 1–18.
  * [Chartrand et al., 2008] Chartrand, G., Johns, G., McKeon, K., and Zhang, P. (2008).  Rainbow connection in graphs.  Math. Bohem, 133(1):85–98.
  * [Chartrand and Zhang, 2008] Chartrand, G. and Zhang, P. (2008).  Chromatic graph theory.  Chapman & Hall.
  * [Corneil et al., 1997] Corneil, D., Olariu, S., and Stewart, L. (1997).  Asteroidal triple-free graphs.  SIAM journal on discrete mathematics, 10(3):399–430.
  * [Erdős et al., 1989] Erdős, P., Pach, J., Pollack, R., and Tuza, Z. (1989).  Radius, diameter, and minimum degree.  Journal of Combinatorial Theory, Series B, 47(1):73–79.
  * [Krivelevich and Yuster, 2010] Krivelevich, M. and Yuster, R. (2010).  The rainbow connection of a graph is (at most) reciprocal to its minimum degree.  Journal of Graph Theory, 63(3):185–191.
  * [Schiermeyer, 2009] Schiermeyer, I. (2009).  Rainbow connection in graphs with minimum degree three.  In Fiala, J., Kratochvíl, J., and Miller, M., editors, Combinatorial Algorithms, volume 5874 of Lecture Notes in Computer Science, pages 432–437. Springer Berlin / Heidelberg.
  * [Yannakakis, 1982] Yannakakis, M. (1982).  The complexity of the partial order dimension problem.  SIAM Journal on Algebraic and Discrete Methods, 3(3):351–358.