# Syntax Customized Video Captioning by Imitating Exemplar Sentences

Yitian Yuan, Lin Ma, and Wenwu Zhu  Y. Yuan is with Meituan, Beijing, China.
This work was done when Yitian Yuan was at Tsinghua University, Beijing,
China. E-mail<EMAIL_ADDRESS>L. Ma is with Meituan, Beijing, China.
E-mail<EMAIL_ADDRESS>W. Zhu is with the Department of Computer
Science and Technology, Tsinghua University, Beijing, China. W. Zhu is the
corresponding author. E-mail<EMAIL_ADDRESS>Manuscript received XXXX;
revised XXXX.

###### Abstract

Enhancing the diversity of sentences to describe video contents is an
important problem arising in recent video captioning research. In this paper,
we explore this problem from a novel perspective of customizing video captions
by imitating exemplar sentence syntaxes. Specifically, given a video and any
syntax-valid exemplar sentence, we introduce a new task of Syntax Customized
Video Captioning (SCVC) aiming to generate one caption which not only
semantically describes the video contents but also syntactically imitates the
given exemplar sentence. To tackle the SCVC task, we propose a novel video
captioning model, where a hierarchical sentence syntax encoder is firstly
designed to extract the syntactic structure of the exemplar sentence, then a
syntax conditioned caption decoder is devised to generate the syntactically
structured caption expressing video semantics. As there is no available syntax
customized groundtruth video captions, we tackle such a challenge by proposing
a new training strategy, which leverages the traditional pairwise video
captioning data and our collected exemplar sentences to accomplish the model
learning. Extensive experiments, in terms of semantic, syntactic, fluency, and
diversity evaluations, clearly demonstrate our model capability to generate
syntax-varied and semantics-coherent video captions that well imitate
different exemplar sentences with enriched diversities. Code is available at
{https://github.com/yytzsy/Syntax-Customized-Video-Captioning}.

###### Index Terms:

Video captioning, sentence syntax customization, recurrent neural network.

##  1 Introduction

Figure 1: The syntax customized video captioning task by imitating different
exemplar sentences. It can be observed that the generated syntax customized
video captions by our model can not only precisely depict the video contents,
but also highly resemble the syntactic structures of the given exemplar
sentences.

Video captioning [1, 2, 3], which aims to automatically generate natural
language sentences to describe video contents, has aroused great interest
recent years. Inspired by the success of the sequence-to-sequence model [4] in
neural machine translation, the encoder-decoder architecture [5] leveraging
CNNs and RNNs to encode video semantics and utilizing RNNs to decode sentences
has become a common and effective configuration for most video captioning
approaches.

Previous methods [6, 7, 3, 8, 9, 10] are mostly trained with the (conditional)
maximum likelihood objective, which encourages the use of the $n$-grams that
appeared in the training samples. Consequently, the generated sentences will
bear high resemblance to training sentences in detailed wording [11]. For
example, the generated sentences by the captioning models trained on MSRVTT
[12] often present similar syntactic structures like “A is doing B at/on/when
C”. Although such generated captions can describe the video contents, the
monotonous and plain sentence forms are of very limited linguistic diversity
and expression variability. Compared with those captioning models, people can
express things more freely and vividly in daily life. Such an ability, on the
one hand, is due to that we have the basic syntactic knowledge about sentence
organization. On the other hand, we can acquire abundant corpora during daily
reading and talking, and learn how to express things. Therefore, is it
possible to learn and leverage sentence syntactic information to guide the
video caption generation? Or, more intuitively, can we use the human-edited
sentences to customize video captions so as to strengthen the captioning
variability in expression?

To answer the above questions, we propose a novel task, namely Syntax
Customized Video Captioning (SCVC) in this paper. As shown in Figure 1, given
a video and any syntax-valid exemplar sentence, we aim to generate one
caption, which should not only express the video semantics but also follow the
syntactic structure of the given exemplar sentence. Since exemplar sentences
are easy to acquire with no restrictions, our proposed task provides a
promising way to strengthen the diversity and expressiveness of video
captioning.

In order to solve the SCVC task, our proposed video captioning model consists
of three fully coupled components. Firstly, one hierarchical sentence syntax
encoder is proposed to capture the syntactic information of the exemplar
sentence, in specific a character-level LSTM and a word-level LSTM are stacked
to characterize the local lexical features and the global syntactic
structures, respectively. Then, one video semantic encoder is introduced to
represent the video semantics. Finally, we design a syntax conditioned caption
decoder realized in a two-layer LSTM, in which one layer relies on the
exemplar syntactic information to modulate the LSTM for customizing the
caption syntax, and the subsequent layer relies on the video features to
modulate the LSTM for generating the syntactically structured caption
describing video semantics. As we do not have the syntax customized
groundtruth captions, we propose a new training strategy, which fully
leverages the syntactic and semantic information residing in both conventional
video captioning data and our collected auxiliary exemplar sentences to train
the overall model, thus enabling the generation of video captions with
customized syntaxes.

Our main contributions are summarized as follows.

  * •

A novel Syntax Customized Video Captioning (SCVC) task is proposed to enrich
the diversity and expressiveness of video descriptions.

  * •

A novel video captioning model is designed, with a hierarchical sentence
syntax encoder and a syntax conditioned caption decoder effectively encoding
the exemplar sentence syntaxes and controlling the syntactic structures of the
generated video captions, respectively.

  * •

A new training strategy is proposed to fully utilize both the public video
captioning data and the collected exemplar sentences to train our overall
model. Extensive experiments also verify our model capability to generate
various syntax customized video captions with enriched diversities.

##  2 Related Works

Video captioning has been extensively studied in the past few years. From
pioneering template-based methods [13, 14, 2, 15] which defined special
grammar rules to compose captions, to recent sequence-to-sequence
architectures which leveraged RNNs to encode videos and then decode captions
sequentially [6, 7, 16, 3, 8, 9, 10], numerous improvements have been
achieved. However, most of these previous approaches are trained to select
words with the maximum probability sampled from the learned distribution of
the training corpus, resulting in a monotonous set of generated captions
bearing high resemblance to the training data.

The above works mainly aim at generating precise captions to describe visual
contents for keeping fidelity, inspired by the research of text style transfer
[17, 18, 19, 20, 21] in the natural language processing community, some recent
works for video captioning further put more emphasis on improving the
expressiveness or diversity of the predicted video descriptive sentences [22,
11, 23, 24, 25, 26, 27, 28, 29]. Specifically, Gan et al. proposed a StyleNet
to control the style in the captioning process so as to produce attractive
captions with the desired style like romantic or humorous [25]. You et al.
supplied the sentiment label as one additional dimension of the input feature,
so as to make the model learn to control the injection of sentiment words in
captions for sentiment-conveying [29]. Wang et al. proposed to sample a Part-
of-Speech (POS) sequence based on the video representation. By manually
altering the sampled POS, the subsequently predicted captions can also be
modified [27]. Chen et al. proposed fine-grained control of image caption
generation with an abstract scene graph, which makes the level of details such
as attributes or relationships can be captured in the caption generation
process [22].

Compared with using the style label/sentiment label/POS tag/scene graph to
control caption generation, directly leveraging the exemplar sentences to
customize the generated captions is more intuitive and natural. Moreover,
since the exemplar sentences are easy to obtain and of various syntactic
structures, the expressiveness and diversity of video captions can thereby be
enriched through imitating those syntax-varied exemplars.

Figure 2:  Framework of our proposed model for the syntax customized video
captioning task, which consists of three fully coupled components, i.e., a
hierarchical sentence syntax encoder extracting the syntactic structure of the
exemplar sentence, a video semantic encoder yielding the video semantic
representation, and a syntax conditioned caption decoder relying on the
encoded syntactic and semantic information to produce the syntax customized
video caption. Best viewed in color.

##  3 The Proposed Model

In this section, we propose one novel model to tackle the SCVC task, with the
model overview illustrated in Figure 2. Concretely, the proposed model
consists of three components, namely the hierarchical sentence syntax encoder,
the video semantic encoder and the syntax conditioned caption decoder. We will
detail the model and demonstrate our training strategy in the following.

###  3.1 Hierarchical Sentence Syntax Encoder

To make one video caption imitate the syntactic structure of the given
exemplar sentence, how to extract the exemplar sentence syntaxes rather than
its semantics is an essential problem. Hence, as shown in the top-right part
of Figure 2, we propose a hierarchical sentence syntax encoder as follows.

Specifically, suppose an exemplar sentence $S=[w_{1},...,w_{n},...,w_{N}]$
with $N$ words, in which the $n$-th word consists of $L$ characters
$w_{n}=[w_{n,1},...,w_{n,l},...,w_{n,L}]$. A character-level LSTM, namely
${\rm{LSTM}}^{c}$, is first performed on the sequential characters of each
word:

$\mathbf{h}^{c}_{n,l},\mathbf{c}^{c}_{n,l}={\rm{LSTM}}^{c}(\mathbf{w}^{c}_{n,l},\mathbf{h}^{c}_{n,l-1},\mathbf{c}^{c}_{n,l-1}).$
(1)

Here $\mathbf{w}^{c}_{n,l}$ is the embedding of the character $w_{n,l}$ in the
word $w_{n}$, and the corresponding hidden vector $\mathbf{h}^{c}_{n,l}$ will
encode the context in the word to characterize the subword features of
$w_{n}$. We average the $L$ character-level hidden vectors, and obtain the
syntactic word feature
$\mathbf{w}_{n}=\rm{Avg}(\mathbf{h}^{c}_{n,1},...,\mathbf{h}^{c}_{n,L})$. As
words with similar syntactic behaviors, such as part-of-speech (POS), often
have similar subword characteristics like suffix or prefix [30], our
character-based word feature $\mathbf{w}_{n}$ will capture the local lexical
features to support the sentence level syntax encoding. Subsequently, another
word-level LSTM, namely ${\rm{LSTM}}^{w}$, is stacked on ${\rm{LSTM}}^{c}$ to
aggregate the syntactic word features:

$\mathbf{h}^{w}_{n},\mathbf{c}^{w}_{n}={\rm{LSTM}}^{w}(\mathbf{w}_{n},\mathbf{h}^{w}_{n-1},\mathbf{c}^{w}_{n-1}).$
(2)

With such a hierarchical encoding strategy, the syntactic representation
$\mathbf{H}^{s}=[\mathbf{h}^{w}_{1},...,\mathbf{h}^{w}_{n},...,\mathbf{h}^{w}_{N}]$
of the exemplar sentence $S$ is obtained, which will be used to control the
sentence syntax of the predicted video caption.

Word Replacement Mechanism based on POS Tags. When conducting experiments, we
observe that the sentence syntax encoder often tends to remember the exact
words instead of learning the sentence syntactic structure. In order to make
the syntax encoder put more emphasis on the sentence syntaxes and lexical word
features, we propose a word replacement mechanism based on their POS tags.
Specifically, we firstly use the Stanford NLP toolkit [31] to get the POS tag
of each word in the sentence. Then, when feeding the sentence in the syntax
encoder, we randomly replace the word in the sentence with the word of the
same POS tag, and thus discourage the syntax encoder from memorizing the exact
word in the exemplar sentence.

###  3.2 Video Semantic Encoder

For encoding video semantic features, we follow the conventional approaches
which first use one pretrained CNN to encode each video frame in the input
video $V$, and get a video feature sequence
$\mathbf{V}=[\mathbf{v}_{1},...,\mathbf{v}_{m},...,\mathbf{v}_{M}]$. Then, an
LSTM is leveraged to encode the video contexts, with the aggregated hidden
vectors
$\mathbf{H}^{v}=[\mathbf{h}^{v}_{1},...,\mathbf{h}^{v}_{m},...,\mathbf{h}^{v}_{M}]$
denoting the video semantic representation, which will further be utilized to
provide semantic meanings of the generated video caption.

###  3.3 Syntax Conditioned Caption Decoder

In this section, we propose to condition the caption generation process on the
encoded exemplar sentence syntaxes to achieve the caption syntax
customization. The prediction of each word in the caption is on the basis of
the global syntax “backbone”, and the video semantics are taken as the “flesh”
to replenish the caption with semantic meanings. Based on this consideration,
we establish a two-layer LSTM to decode the caption, with the first layer
modeling sentence syntaxes while the second layer fulfilling sentence
semantics.

When decoding the $t$-th word in the caption, the first layer decoding LSTM,
which we denote as ${\rm LSTM}^{syn}$, takes the concatenation of the
embedding of the previous word $\mathbf{e}_{t-1}$ and the attentively
summarized syntactic representation
$\mathbf{a}^{s}_{t}={\rm{Att}}(\mathbf{h}^{syn}_{t-1},\mathbf{H}^{s})$ as
input, outputting the hidden vector $\mathbf{h}^{syn}_{t}$ to control the
sentence syntax at this timestep:

$\mathbf{h}^{syn}_{t},\mathbf{c}^{syn}_{t}={\rm{LSTM}}^{syn}([\mathbf{e}_{t-1},\mathbf{a}^{s}_{t}],\mathbf{h}^{syn}_{t-1},\mathbf{c}^{syn}_{t-1}\;\big{|}\;\mathbf{a}^{s}_{t}).$
(3)

In order to incorporate the syntactic information $\mathbf{a}^{s}_{t}$ and
make it better control the recurrent word decoding procedure, we propose a new
Conditional Layer Normalization (CLN) mechanism to modulate $\rm{LSTM}^{syn}$
as shown in the bottom-left part of Figure 2. Specifically, taking
$\mathbf{a}_{t}^{s}$ as the conditional guidance signal, the computation flow
of Eq. (3) proceeds as:

$\begin{split}[\mathbf{f}_{t}^{syn},\mathbf{i}_{t}^{syn},&\mathbf{o}_{t}^{syn},\mathbf{g}_{t}^{syn}]={\rm\textbf{CLN}}(\mathbf{W}_{h}^{syn}\mathbf{h}^{syn}_{t-1}\;\big{|}\;\mathbf{a}_{t}^{s})\\\
&+{\rm\textbf{CLN}}(\mathbf{W}_{i}^{syn}[\mathbf{e}_{t-1},\mathbf{a}^{s}_{t}]\;\big{|}\;\mathbf{a}_{t}^{s})+\mathbf{b}^{syn},\\\
\mathbf{c}_{t}^{syn}&=\sigma(\mathbf{f}_{t}^{syn})\odot\mathbf{c}_{t-1}^{syn}+\sigma({\mathbf{i}_{t}^{syn}})\odot{\rm
tanh}(\mathbf{g}_{t}^{syn}),\\\
\mathbf{h}_{t}^{syn}&=\sigma(\mathbf{o}_{t}^{syn})\odot{\rm
tanh}\left({\rm\textbf{CLN}}(\mathbf{c}_{t}^{syn}\;\big{|}\;\mathbf{a}_{t}^{s})\right).\end{split}$
(4)

Here CLN performs the modulation on the LSTM gates
$\\{\mathbf{f}_{t}^{syn},\mathbf{i}_{t}^{syn},\mathbf{o}_{t}^{syn},\mathbf{g}_{t}^{syn}\\}$
and cell $\mathbf{c}_{t}^{syn}$, which leverages $\mathbf{a}_{t}^{s}$ to
conditionally scale and shift the layer normalized vectors:

${\rm\textbf{CLN}}(\mathbf{x}\;\big{|}\;\mathbf{a}^{s}_{t})=f_{\gamma}(\mathbf{a}_{t}^{s})\cdot\frac{\mathbf{x}-\bm{\mu}(\mathbf{x})}{\bm{\sigma}(\mathbf{x})}+f_{\beta}(\mathbf{a}_{t}^{s}).$
(5)

The scaling and shifting vectors $f_{\gamma}(\mathbf{a}_{t}^{s})$ and
$f_{\beta}(\mathbf{a}_{t}^{s})$ are generated by two independent multi-layer
perceptrons (MLPs) with $\mathbf{a}_{t}^{s}$ as the input, and the three CLNs
in Eq. (4) are independent with each other and do not share weights. By
equipping CLNs, the syntactic representation $\mathbf{a}_{t}^{s}$ is expected
to affect the update procedure of ${\rm LSTM}^{syn}$, thereby achieving the
caption syntax customization.

The second layer LSTM in our syntax conditioned caption decoder, which we
denote as ${\rm LSTM}^{sem}$, has the same architecture as ${\rm LSTM}^{syn}$.
Specifically, ${\rm LSTM}^{sem}$ takes the concatenation of the syntax hidden
vector $\mathbf{h}^{syn}_{t}$ and the attentively summarized video semantic
representation
$\mathbf{a}^{v}_{t}={\rm{Att}}(\mathbf{h}^{sem}_{t-1},\mathbf{H}^{v})$ as
inputs, and is conditionally controlled under the video semantics:

$\mathbf{h}^{sem}_{t},\mathbf{c}^{sem}_{t}={\rm{LSTM}}^{sem}([\mathbf{h}_{t}^{syn},\mathbf{a}^{v}_{t}],\mathbf{h}^{sem}_{t-1},\mathbf{c}^{sem}_{t-1}\;\big{|}\;\mathbf{a}^{v}_{t}).$
(6)

Here, $\mathbf{a}^{v}_{t}$ is taken as the condition guidance signal to
intensify the video contents in the word decoding procedure, making the
predicted caption better preserve the video semantics. Through the above two-
layer LSTM modeling, the words in the caption will be sequentially predicted
based on the hidden vectors
$\mathbf{H}^{sem}=[\mathbf{h}^{sem}_{1},..,\mathbf{h}^{sem}_{t},...,\mathbf{h}^{sem}_{T}]$.

###  3.4 Training Strategy

As we do not have the syntax customized groundtruth video captions, we propose
to leverage the pairwise video captioning data in available datasets as well
as our collected auxiliary exemplar sentence corpus to train our proposed
model.

####  3.4.1 Training with Pairwise Video Captioning Data

As illustrated in Figure 3(a), the pairwise video captioning data is utilized
for training the proposed model, with the groundtruth caption also being taken
as the exemplar sentence. As such, the sentence syntax of the caption is
extracted and then coupled with the video semantics to predict the caption.
For the training of this syntax customized video captioning procedure, two
loss terms are introduced as the learning objective, i.e., the syntactic loss
and the semantic loss.

Figure 3:  Our proposed training strategy leverages (a) the pairwise video
captioning data and (b) our collected auxiliary exemplar sentences to train
our proposed model. The shadowed blocks are shared when training.

Syntactic Loss. In our syntax customized video captioning, the syntactic
structure of the generated caption should resemble that of the exemplar
sentence. We use the Stanford NLP toolkit [32] to extract the constituency
parse tree of the exemplar sentence (here is the input video caption), which
is presented as a bracket syntactic token sequence. Then we collect the hidden
state vectors of the $\rm{LSTM}^{syn}$ as
$\mathbf{H}^{syn}$=$[\mathbf{h}^{syn}_{1},...,\mathbf{h}^{syn}_{t},...,\mathbf{h}^{syn}_{T}]$,
feed them into a basic decoding model such as [10], and predict the
corresponding syntactic token sequence of the input exemplar sentence.
Accordingly, the syntactic loss can be defined as:

$L_{v,c}^{syn}=-{\rm log}P(C^{syn}|\mathbf{H}^{syn};V,C).$ (7)

$L_{v,c}^{syn}$ is realized by the typical negative log-likelihood loss. $V$
denotes the input video, and $C$ denotes its accompanying caption in the
dataset, which is also used as the exemplar sentence. $C^{syn}$ indicates the
extracted syntactic token sequence of the input caption $C$.

Semantic Loss. Since the generated caption should express the semantic meaning
of the video, we collect the hidden vectors
$\mathbf{H}^{sem}=[\mathbf{h}^{sem}_{1},...,\mathbf{h}^{sem}_{t},...,\mathbf{h}^{sem}_{T}]$
of the $\rm{LSTM}^{sem}$ that directly serves for caption decoding, and adopt
the negative log-likelihood loss for semantic supervision with $C$:

$L_{v,c}^{sem}=-{\rm log}P(C|\mathbf{H}^{sem};V,C).$ (8)

####  3.4.2 Training with An Exemplar Sentence Corpus

Since the syntactic structures of the captions in existing video captioning
datasets are simple and monotonous, only relying on them to train our model
will limit its ability on expression variability. To this end, we collect a
large number of syntax-varied exemplar sentences to enhance our model’s
learning ability. Meanwhile, as shown in Figure 3(b), we propose a sentence
semantic encoder to replace the video semantic encoder in our model. Doing so
will make one single sentence can also be autoencoded with the yielded
architecture, and further help the training of the shared hierarchical
sentence syntax encoder and syntax conditioned caption decoder.

Concretely, the sentence semantic encoder relies on one fully-connected layer
to encode the glove embedding [33] of each word, and the obtained word feature
sequence will be taken as the sentence semantic representation. By feeding the
semantic and syntactic representations of the sentence to the syntax
conditioned caption decoder, we follow the same procedure in Sec. 3.3 to
reconstruct the input sentence. The corresponding syntactic and semantic
losses can also be defined:

$\begin{split}L_{s,s}^{syn}&=-{\rm log}P(S^{syn}|\mathbf{H}^{syn};S,S),\\\
L_{s,s}^{sem}&=-{\rm log}P(S|\mathbf{H}^{sem};S,S).\end{split}$ (9)

Here $S$ denotes the sentence we feed to the sentence autoencoding procedure,
which can be our collected exemplar sentence $E$ or the caption $C$ in the
existing video captioning datasets. $S^{syn}$ denotes the parse tree token
sequence of $S$.

####  3.4.3 Overall Training Objective

The above training objective considers either feeding a (video, caption) pair
or one single sentence to our model. However, there is also one case of taking
one exemplar sentence $E$ and one video $V$ as the inputs to our model.
Although we do not have groundtruth caption to support the $L^{sem}$ loss in
this case, the $L^{syn}$ loss can still be involved in training since the
parse tree sequence $E^{syn}$ of the exemplar sentence can be pre-extracted.
Hence, we can obtain an additional syntactic loss as follows:

$L^{syn}_{v,e}=-{\rm log}P(E^{syn}|\mathbf{H}^{syn};V,E).$ (10)

Summing up the above terms, the overall training objective of our model is
defined as:

$L=L_{v,c}^{syn}+L_{v,c}^{sem}+L_{s,s}^{syn}+L_{s,s}^{sem}+L^{syn}_{v,e}.$
(11)

##  4 Experiments

TABLE I: Performance comparisons on MSRVTT and ActivityNet Captions. Method | MSRVTT | ActivityNet Captions
---|---|---
| TED$\downarrow$
---
| COS$\uparrow$
---
| perplexity$\downarrow$
---
| TED$\downarrow$
---
| COS$\uparrow$
---
| perplexity$\downarrow$
---
ExemplarOnly | 0.00 | 0.5238 | 4.92 | 0.00 | 0.5784 | 4.91
Seq2Seq | 15.91 | 0.6949 | 3.51 | 20.12 | 0.7317 | 2.58
Template | 4.88 | 0.6595 | 7.75 | 2.97 | 0.6945 | 7.58
GFN | 16.08 | 0.6963 | 3.86 | 20.86 | 0.7467 | 2.80
Ours | 5.44 | 0.6892 | 5.64 | 5.52 | 0.7113 | 6.61

###  4.1 Dataset and Exemplar Sentence Collection

We conduct our syntax customized video captioning experiments on the MSRVTT
[12] and ActivityNet Captions [34] datasets. We pair each video in these two
datasets with 20 different syntax-varied exemplar sentences that are
originally collected in the Shutterstock Image Description Corpus [35].
Accordingly, 20 different syntax customized video captions will be generated
by our proposed model. The details of the datasets and our exemplar sentence
collection are as follows.

MSRVTT [12]. The MSRVTT is a large-scale dataset for video captioning. It
contains 10k video clips and each video clip is accompanied with 20 human-
edited English sentence descriptions, resulting in 200K video-caption pairs in
total. Following the existing works, we use the public data split in our
experiments, i.e., 6513 videos for training, 497 for validation, and 2990 for
testing.

ActivityNet Captions [34]. The ActivityNet Captions is a benchmark dataset
proposed for dense video captioning. There are 20K untrimmed videos in total,
and each video has several annotated segments with starting and ending times
as well as the associated captions. Overall it contains 10,024 videos for
training, 4,926 videos for validation and 5,044 for testing. Since we do not
perform dense video captioning in this work, we split the caption-paired
segments from the training and validation videos, and perform video captioning
on them. In this way, 54,926 segment-caption pairs are collected, where 37,421
segments from the public training set are used for training, and 17,505
segments from the validation set are used for testing.

Exemplar Sentence Collection. The exemplar sentences in our work should meet
the following two requirements. (1) The sentences should be human-edited. (2)
The sentences should have various syntactic structures with no other
restrictions. We find that the recently collected Shutterstock Image
Description Corpus [35] is quite appropriate. Specifically, the Shutterstock
Image Description Corpus is collected by crawling the image descriptions from
Shutterstock for the unsupervised image captioning research. Shutterstock is
an online stock photography website, which provides hundreds of millions of
royalty-free stock images. All the image descriptions are written by image
composers, and have diverse sentence syntactic forms. We download the
collected 2,322,628 image descriptions in the Shutterstock Image Description
Corpus, and filter the descriptions that are less than 8 words or longer than
30 words, obtaining a total of 761,582 exemplar sentences. For each
video/segment in the MSRVTT and ActivityNet Captions, we randomly choose 20
descriptions as its exemplar sentences for our syntax customized video
captioning task.

###  4.2 Evaluation Metrics

To comprehensively evaluate the predicted syntax customized video captions, we
refer to the research in the relating text style transfer task [17, 18] and
conduct the objective evaluation from the syntactic, semantic and fluency
aspects as follows.

Syntactic Evaluation. To evaluate whether our generated captions comply with
the syntactic structures of the exemplar sentences, we directly compare their
constituency parse tree by computing the syntactic Tree Edit Distance (TED)
[36] between them after removing word tokens. Smaller TED value means higher
syntactic similarity.

Semantic Evaluation. For each sentence, we first remove the stop words and
then take the average glove word embeddings of the remaining words as its
sentence semantic features. In the semantic feature space, the average cosine
similarity (COS) between the syntax customized video caption and all the
originally groundtruth video captions in the dataset is used to evaluate their
semantic coherence.

Sentence Fluency.  Besides syntactic and semantic evaluation, another
important aspect is the sentence fluency of the generated syntax customized
video captions. We use a pre-trained language model to measure the perplexity
of generated captions as the fluency score. A state-of-the-art BERT model [37]
trained on a large scale lower case English dataset is used for the
evaluation.

###  4.3 Implementation Details

To represent videos, we leverage the Inception-Resnet-v2 network [38]
pretrained on the ILSVRC-2012-CLS image classification dataset [39] to extract
a 1,536 dimensional feature vector for each frame. Videos in the MSRVTT and
ActivityNet Captions datasets are represented with evenly spaced 30 and 100
features, respectively. Shorter videos of less than 30 or 100 features are
padded with zero vectors. The word embedding size and all the LSTMs’ hidden
sizes are set as 256. Adam [40] optimizer is used for training. For the word
replacement mechanism, the probability to replace the word with their same
POS-tagged word is 0.7. The model is implemented with PyTorch [41].

For getting the syntactic token sequence, we first extract the constituency
parse tree of the input exemplar sentence with Stanford NLP parser [32]. For
example, the parse tree of the sentence “ a short clip of news on a white
background” is “ (ROOT (NP (NP (NP (DT) (JJ) (NN)) (PP (IN) (NP (NN)))) (PP
(IN) (NP (DT) (JJ) (NN)))))”. We regard the sentence parse as a syntactic
token sequence, where each element such as “ROOT”, “NN” or “(” is an
independent token in the sequence. Such a syntactic token sequence will be
used for the syntactic loss as stated in Sec. 3.4.

###  4.4 Compared Methods

Since the proposed syntax customized video captioning is a new task, there is
no baseline method for direct comparisons. In this section, we compare our
proposed model with the following methods:

  * •

The ExemplarOnly method which directly outputs the given exemplar sentence as
the video caption while does not consider the video contents.

  * •

The conventional sequence-to-sequence (Seq2Seq) video captioning method [10],
which only predicts one single caption for one video while does not consider
the sentence syntax.

  * •

The Template method, which firstly detects visual concepts [42] from each
video to generate a bag of video-related words. Then every content word in the
exemplar sentence is simply replaced by one video-related word from the bag
that has the same part-of-speech as the removed word.

  * •

The Gated Fusion Network (GFN) for video captioning with POS sequence guidance
[27]. We replace their intermediately sampled POS sequences from videos with
the POS sequences of the given exemplar sentences, and attain the
corresponding syntax customized video captions.

###  4.5 Performance Comparison

####  4.5.1 Quantitative Evaluation

Table I compares our proposed model with the baseline methods in terms of the
objective evaluation metrics introduced above. The ExemplarOnly method
directly outputs exemplar sentences without considering video contents, making
the exemplar and output sentence structures exactly the same and TED scores as
0.0, whereas the semantic coherence to the video is much lower. The Seq2Seq
model mainly focuses on describing video contents while neglecting the given
exemplar sentence syntaxes, so it gets higher semantic COS scores but inferior
TED scores. The Template method simply fills the detected content words from
videos in the exemplar sentences while does not consider the global sentence
meanings. Doing so makes the generated captions fit the original exemplar
syntaxes very well but the captions are not fluent and get high (poor)
perplexity scores. Meanwhile, the semantic scores are also lower. Although GFN
attempts to leverage POS features to guide video captioning, its
controllability of caption syntax is weak and results in high TEDs between
exemplar sentences and captions. The main focus of GFN is still to improve the
semantic accuracy of video captions and keep their fidelity with the training
corpus. Since the Seq2Seq and GFN models often generate simple sentence
descriptions with common sentence forms, their perplexity scores are
correspondingly lower. The collected exemplar sentences are human-edited,
which often take more various and complex syntaxes and are free in grammar.
Thus, the perplexity scores of the ExemplarOnly method are relatively higher.
Based on these complicated exemplars, the yielded Template and Ours method
will also inevitably present higher perplexity scores.

Our proposed model achieves much better TED scores and comparable COS scores
than the Seq2Seq and GFN models, which shows that our method can comply with
the exemplar sentence syntaxes while describing the video semantics. Also,
imitating the complex exemplar sentences does not significantly affect the
sentence fluency of our generated captions, with the perplexity scores
increasing in a reasonable range compared to the ExemplarOnly method.

TABLE II:  Human evaluation of captioning. Method |  | Syntactic
---
Score
| Semantic
---
Score
| Fluency
---
Score
ExemplarOnly | 1.0000 | 0.0040 | 0.9260
Seq2Seq | 0.0043 | 0.5945 | 0.9938
Template | 0.9205 | 0.5322 | 0.6530
GFN | 0.0058 | 0.6153 | 0.9753
Ours | 0.8895 | 0.5773 | 0.8560
TABLE III:  Captioning diversity evaluation.

Method | MSRVTT | ActivityNet Captions
---|---|---
| LSA
---
| Self-CIDER
---
| LSA
---
| Self-CIDER
---
ExemplarOnly | 0.7437 | 0.9737 | 0.7431 | 0.9741
Seq2Seq [10] | 0.0000 | 0.0000 | 0.0000 | 0.0000
Template | 0.5073 | 0.7940 | 0.5067 | 0.7943
GFN [27] | 0.2194 | 0.3225 | 0.2553 | 0.4241
Ours | 0.6150 | 0.8814 | 0.6973 | 0.9365

TABLE IV: Evaluation results in the conventional captioning metrics (%).

Method | MSRVTT | ActivityNet Captions
---|---|---
| B@4
---
| CIDEr
---
| ROUGE∗
---
| METEOR
---
| B@4
---
| CIDEr
---
| ROUGE∗
---
| METEOR
---
Seq2Seq [10] | 37.20 | 40.24 | 58.64 | 26.39 | 3.36 | 23.92 | 20.44 | 8.93
Template | 0.86 | 4.87 | 23.81 | 12.59 | 0.11 | 6.26 | 10.15 | 4.71
GFN [27] | 38.74 | 43.90 | 59.42 | 27.11 | 4.65 | 32.87 | 21.65 | 10.24
Ours | 3.29 | 11.45 | 28.45 | 15.33 | 0.20 | 8.18 | 9.73 | 4.50

  * •

*: Here ROUGE indicates ROUGE_L.

Figure 4:  Qualitative results for the syntax customized video captioning. For
each case, we provide the video, the groundtruth caption, and the caption
generated by the Seq2Seq model. Two exemplar sentences are given to each
video. The Template, GFN, and our predicted syntax customized video captions
are also present correspondingly.

####  4.5.2 Qualitative Evaluation

Figure 4 shows the qualitative results for the syntax customized video
captioning task. The Seq2Seq model can generate only one simple caption for
one video, which is monotonous and bears high resemblance to the training
corpus. The Template method which simply replaces main content words in the
exemplar sentences make the generated captions lack of fluency. The GFN model
cannot capture sentence syntaxes and produces similar or the same captions for
different exemplar sentences. Our generated captions comply with the exemplar
sentence syntaxes well, and more concrete video contents like “snow helmet”
and “green grass” can also be described in the captions more expressively.
Meanwhile, the two different syntax customized video captions further provide
us the intuition of diverse video captioning.

To better demonstrate the effectiveness of our proposed method on syntax
customized video captioning, we further provide more qualitative results of
Ours method in Figure 7 and Figure 8 at the end of the paper. It can be
observed that on different types and contents of videos, our generated
captions can not only present the video semantics accurately, but also well
imitate the syntaxes of the given exemplar sentences.

####  4.5.3 Human Evaluation

Besides the quantitative and qualitative evaluations, we also conduct a human
assessment of the generated captions. The human evaluators were asked to rate
the three aspects of the generated captions — syntax similarity with the
exemplar sentence, semantic coherence with the video, and sentence fluency.
Each rating aspect is graded in three scales {0.0, 0.5, 1.0}, and the higher,
the better. We randomly chose 200 captions generated by each compared method
from the test set and invited 10 evaluators (5 males and 5 females) to grade
them. The average rating scores are presented in Table 2. These scores are in
agreement with the above quantitative evaluation. Although the complex
exemplar sentence syntaxes may influence the sentence fluency of our generated
captions, they are still realistic and can describe the video semantic
contents meanwhile imitating the exemplar sentence syntaxes.

####  4.5.4 Captioning Diversity Evaluation

Since we collect 20 different exemplar sentences for each video, we will
accordingly get 20 different syntax customized captions with the proposed
model. To measure the diversity among these generated captions, we follow the
evaluation metrics introduced in [43], and report the LSA and Self-CIDEr based
diversity scores in Table 3. The collected exemplar sentences are independent
of each other, and it is evident that the diversity scores of the ExemplarOnly
method are fairly high and can be seen as upper bounds in this diversity
evaluation experiment. The conventional Seq2Seq model can only generate one
single caption for one video, and thus it cannot achieve diverse video
captioning and gets all the scores as 0.0. The GFN method can vary the video
captions to some extent, while the captioning diversity remains limited. The
Template method and Ours model can generate diverse captions to describe the
video contents, and Ours model even gets comparable LSA and Self-CIDER scores
to other state-of-the-art methods reported in [43]. Hence, the results verify
that our proposed model can indeed strengthen the diversity of video
captioning.

Figure 5: The illustration of correlation between the number of object (verb,
noun) words in captions and the exemplar sentence lengths. In each scatter
map, the x-axis indicates the lengths of exemplar sentences, and the y-axes
indicate the number of noun, verb, and noun+verb words in our generated syntax
customized video captions, respectively.

###  4.6 The Influence of Exemplar Sentence Length

In our experiments, we find that given different exemplar sentences, there can
be different object descriptions coming from the video. Therefore, it is also
interesting to study the effect of exemplar sentence length to the number of
different object words in the generated captions. Therefore, we first count
the different verb and noun words in each generated syntax customized video
caption of our model. Then, we plot 6 scatter maps in Fig. 5, where the top
three scatters are for MSRVTT dataset and the bottom three are for ActivityNet
Captions dataset. The x coordinate of each point in the scatter map means the
length of the given exemplar sentence, and the y coordinate means the number
of different noun, verb, and noun+verb words (we call them objects in general)
in the corresponding syntax customized video caption, respectively. The
pearson correlation coefficient between the exemplar sentence length and the
object number is also presented in the top-right part of each subfigure. It
can be observed that the object number is positively correlated to the
exemplar sentence length, no matter for verbs, nouns or their union. Such
results indicate that when we provide longer exemplar sentences, more objects
will be incorporated in the generated syntax customized captions, making more
representative and diverse video descriptions.

###  4.7 Discussions on the Conventional Metrics

The generated syntax customized video captions one the one hand should
semantically describe the video contents, on the other hand should
syntactically follow the given exemplar sentences, thus making the caption
syntactic structures be greatly changed in the syntax imitation procedure. As
such, our generated syntax customized video captions will be greatly different
from the original groundtruth captions (in the MSRVTT and ActivityNet Captions
datasets) on n-gram characteristics and detail wording. Since conventional
captioning evaluation metrics, such as BLEU, take the n-gram similarity
between the predicted and groundtruth captions as a basic measurement, they
are not very appropriate for evaluating our syntax customized video captioning
task.

In this section, we still provide the evaluation results in the conventional
video captioning metrics in Table IV for reference. As expected, our proposed
model does not achieve high performances in these metrics, while the Seq2Seq
and GFN models get good results because they are still focusing on fitting the
detail wording patterns in the training corpus. The different evaluation
results between the conventional captioning metrics and our human ratings in
the main paper also indicate the limitation of the conventional metrics in
evaluating syntax-varied captions.

Figure 6: In this figure, we present the ablation studies of the proposed
model by examining the contributions on (a) the loss components, (b) the
sentence syntax encoding, and (c) the caption decoding.

###  4.8 Ablation Studies

####  4.8.1 Model Contribution Examination

In this section, we perform three groups of ablation studies on the MSRVTT
dataset to examine the contributions of our proposed model, with the results
shown in Figure 6. Each point in this figure represents the performance of the
model on the validation set during the training process. The x-axis indicates
the 10/TED scores, and the y-axis denotes the COS scores. Since lower TED and
higher COS means better performance, models at the top right are more
desirable.

Loss Components. Comparing the model with only the
$L_{v,c}$=$L_{v,c}^{syn}$+$L_{v,c}^{sem}$ loss and the model additionally
considering the $L_{s,s}$=$L_{s,s}^{syn}$+$L_{s,s}^{sem}$ loss in Figure 6(a),
we can observe that training with an exemplar sentence corpus as introduced in
Sec. 3.4.2 can augment the training data and thereby improve the model
performance. By considering both $L_{v,c}$ and $L_{v,e}^{syn}$ terms, the
performance curve rises steadily without fierce fluctuation. It shows that
even without paired groundtruth syntax customized captions, merely providing
supervision on sentence syntaxes can also help the model imitate the syntactic
structures of the given exemplar sentences. By combining all the above terms,
our proposed model achieves the best performances.

Sentence Syntax Encoding. Ours-WordSyntaxEmbed model in Figure 6(b) drops the
character-level LSTM, and only keeps the word-level LSTM to encode the
sentence syntactic structure. Ours-NoWordReplace model does not adopt the word
replacement mechanism as we stated in Sec. 3.1. The performance superiority of
the full model (Ours) over these two ablation models verifies the benefits of
the character-level LSTM in encoding subword features and the word replacement
mechanism. These designs can help our model capture exemplar sentence syntaxes
effectively and filter out unnecessary sentence semantics, which is very
crucial for syntax customized video captioning.

Caption Decoding. Ours-Concate model in Figure 6(c) simply concatenates
sentence syntactic and video semantic representations and takes them as the
inputs to the decoding LSTM without the proposed CLN processing. We can
observe that the full model (Ours) achieves higher COS scores than Ours-
Concate, which shows that equipping CLN in the decoding LSTM is beneficial to
video semantic preservation when performing syntax customization. In Ours-
Semantic1Syntax2 model, we feed video semantic representation to the first
layer LSTM and sentence syntactic representation to the second. Such a
semantic-first syntax-follow architecture is significantly inferior to our
proposed model. The reason mainly dues to that using syntactic information to
guide the word prediction in the second layer LSTM will hinder it from
choosing appropriate words coherent to the video semantics.

####  4.8.2 The Influence of Word Replacement Probability

TABLE V: Model performance with different word replacement probability. Method | TED$\downarrow$ | COS$\uparrow$ | perplexity$\downarrow$
---|---|---|---
Ours-0.1 | 4.28 | 0.6535 | 6.82
Ours-0.3 | 4.81 | 0.6643 | 6.65
Ours-0.5 | 4.72 | 0.6724 | 6.44
Ours-0.7 | 5.44 | 0.6892 | 5.64
Ours-0.9 | 6.14 | 0.6878 | 5.61

For the word replacement mechanism proposed in Sec. 3.1, we have mentioned
that we will randomly replace the word in the exemplar sentence with the word
of the same POS tag with specific probability. In this section, we further
investigate the influence of the word replacement probability to the model
performance, by setting the probability value to {0.1, 0.3, 0.5, 0.7, 0.9} and
evaluating the corresponding models in the MSRVTT dataset. The model
performances are shown in Table V.

It can be observed from Table V that if the replacement probability is small
(e.g., 0.1, 0.3, 0.5), the models get lower COS semantic scores and smaller
TED scores. The reason is that in these cases, the models tend to remember the
exact words in the exemplar sentences instead of learning their POS tag
information and sentence syntaxes, and thus causes the output captions just
copy the words from the exemplar sentences. If we increase the replacement
probability to higher value (e.g., 0.9), the TED score increases and the COS
score decreases a little compared to those of Ours-0.7, while these two
settings are comparable to each other in perplexity. Considering the overall
better performance of Ours-0.7 in balancing the three metrics, setting
replacement probability as 0.7 is suitable for our proposed model.

##  5 Conclusion

In this paper, we proposed a novel syntax customized video captioning task by
imitating different exemplar sentences to strengthen the diversity and
expressiveness of video captioning. To solve this task, a hierarchical
sentence syntax encoder was proposed to capture both the local subword
features and global sentence syntaxes of the exemplar sentence, based on which
a two-layer syntax conditioned caption decoder was devised to generate the
syntax customized caption expressing video semantic meanings. Comprehensive
experiments verify that the generated captions by our model can vividly
describe video contents while complying with different exemplar sentence
syntaxes, thus indicating our contributions to enrich the video captioning
diversity.

Figure 7: More qualitative results on the MSRVTT dataset. For each video, we
provide one groundtruth caption, one exemplar sentence, and the syntax
customized video caption predicted by our proposed model.  Figure 8: More
qualitative results on the ActivityNet Captions dataset. For each video, we
provide one groundtruth caption, one exemplar sentence, and the syntax
customized video caption predicted by our proposed model.

## Acknowledgments

This work was supported by the National Key Research and Development Program
of China (No. 2020AAA0106300, 2018AAA0102000), National Natural Science
Foundation of China Key Project (No. 62050110) and Shenzhen Nanshan District
Ling-Hang Team Grant under No.LHTD20170005.

## References

  * [1] S. Chen, T. Yao, and Y.-G. Jiang, “Deep learning for video captioning: a review,” in _Proceedings of the 28th International Joint Conference on Artificial Intelligence. AAAI Press_ , 2019.
  * [2] M. Rohrbach, W. Qiu, I. Titov, S. Thater, M. Pinkal, and B. Schiele, “Translating video content to natural language descriptions,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2013, pp. 433–440.
  * [3] S. Venugopalan, M. Rohrbach, J. Donahue, R. Mooney, T. Darrell, and K. Saenko, “Sequence to sequence-video to text,” in _Proceedings of the IEEE international conference on computer vision_ , 2015, pp. 4534–4542.
  * [4] I. Sutskever, O. Vinyals, and Q. V. Le, “Sequence to sequence learning with neural networks,” in _Advances in neural information processing systems_ , 2014, pp. 3104–3112.
  * [5] S. Venugopalan, H. Xu, J. Donahue, M. Rohrbach, R. Mooney, and K. Saenko, “Translating videos to natural language using deep recurrent neural networks,” _arXiv preprint arXiv:1412.4729_ , 2014.
  * [6] L. Baraldi, C. Grana, and R. Cucchiara, “Hierarchical boundary-aware neural encoder for video captioning,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 1657–1666.
  * [7] Y. Pan, T. Mei, T. Yao, H. Li, and Y. Rui, “Jointly modeling embedding and translation to bridge video and language,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 4594–4602.
  * [8] B. Wang, L. Ma, W. Zhang, and W. Liu, “Reconstruction network for video captioning,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 7622–7631.
  * [9] J. Xu, T. Yao, Y. Zhang, and T. Mei, “Learning multimodal attention lstm networks for video captioning,” in _Proceedings of the 25th ACM international conference on Multimedia_. ACM, 2017, pp. 537–545.
  * [10] L. Yao, A. Torabi, K. Cho, N. Ballas, C. Pal, H. Larochelle, and A. Courville, “Describing videos by exploiting temporal structure,” in _Proceedings of the IEEE international conference on computer vision_ , 2015, pp. 4507–4515.
  * [11] B. Dai, S. Fidler, R. Urtasun, and D. Lin, “Towards diverse and natural image descriptions via a conditional GAN,” in _ICCV_ , 2017.
  * [12] J. Xu, T. Mei, T. Yao, and Y. Rui, “Msr-vtt: A large video description dataset for bridging video and language,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 5288–5296.
  * [13] S. Guadarrama, N. Krishnamoorthy, G. Malkarnenkar, S. Venugopalan, R. Mooney, T. Darrell, and K. Saenko, “Youtube2text: Recognizing and describing arbitrary activities using semantic hierarchies and zero-shot recognition,” in _Proceedings of the IEEE international conference on computer vision_ , 2013, pp. 2712–2719.
  * [14] A. Rohrbach, M. Rohrbach, W. Qiu, A. Friedrich, M. Pinkal, and B. Schiele, “Coherent multi-sentence video description with variable level of detail,” in _German conference on pattern recognition_. Springer, 2014, pp. 184–195.
  * [15] R. Xu, C. Xiong, W. Chen, and J. J. Corso, “Jointly modeling deep video and compositional text to bridge vision and language in a unified framework,” in _Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence_. AAAI Press, 2015, pp. 2346–2352.
  * [16] R. Pasunuru and M. Bansal, “Reinforced video captioning with entailment rewards,” _arXiv preprint arXiv:1708.02300_ , 2017.
  * [17] Z. Fu, X. Tan, N. Peng, D. Zhao, and R. Yan, “Style transfer in text: Exploration and evaluation,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 32, no. 1, 2018.
  * [18] D. Jin, Z. Jin, Z. Hu, O. Vechtomova, and R. Mihalcea, “Deep learning for text style transfer: A survey,” _arXiv preprint arXiv:2011.00416_ , 2020.
  * [19] C. Wu, X. Chen, and X. Li, “Mask transformer: Unpaired text style transfer based on masked language,” _Applied Sciences_ , vol. 10, no. 18, p. 6196, 2020.
  * [20] C. dos Santos, I. Melnyk, and I. Padhi, “Fighting offensive language on social media with unsupervised text style transfer,” in _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , 2018, pp. 189–194.
  * [21] Y. Cheng, Z. Gan, Y. Zhang, O. Elachqar, D. Li, and J. Liu, “Contextual text style transfer,” in _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings_ , 2020, pp. 2915–2924.
  * [22] S. Chen, Q. Jin, P. Wang, and Q. Wu, “Say as you wish: Fine-grained control of image caption generation with abstract scene graphs,” _arXiv preprint arXiv:2003.00387_ , 2020.
  * [23] A. Deshpande, J. Aneja, L. Wang, A. G. Schwing, and D. Forsyth, “Fast, diverse and accurate image captioning guided by part-of-speech,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 10 695–10 704.
  * [24] X. Duan, W. Huang, C. Gan, J. Wang, W. Zhu, and J. Huang, “Weakly supervised dense event captioning in videos,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 3059–3069.
  * [25] C. Gan, Z. Gan, X. He, J. Gao, and L. Deng, “Stylenet: Generating attractive visual captions with styles,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 3137–3146.
  * [26] A. Mathews, L. Xie, and X. He, “Semstyle: Learning to generate stylised image captions using unaligned text,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 8591–8600.
  * [27] B. Wang, L. Ma, W. Zhang, W. Jiang, J. Wang, and W. Liu, “Controllable video captioning with pos sequence guidance based on gated fusion network,” _arXiv preprint arXiv:1908.10072_ , 2019.
  * [28] H. Xiao and J. Shi, “Diverse video captioning through latent variable expansion with conditional gan,” _arXiv preprint arXiv:1910.12019_ , 2019\.
  * [29] Q. You, H. Jin, and J. Luo, “Image captioning at will: A versatile scheme for effectively injecting sentiments into image descriptions,” _arXiv preprint arXiv:1801.10121_ , 2018.
  * [30] D. Hall, G. Durrett, and D. Klein, “Less grammar, more features,” in _Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 2014, pp. 228–237.
  * [31] C. D. Manning, M. Surdeanu, J. Bauer, J. R. Finkel, S. Bethard, and D. McClosky, “The stanford corenlp natural language processing toolkit,” in _Proceedings of 52nd annual meeting of the association for computational linguistics: system demonstrations_ , 2014, pp. 55–60.
  * [32] C. Manning, M. Surdeanu, J. Bauer, J. Finkel, S. Bethard, and D. McClosky, “The stanford corenlp natural language processing toolkit,” in _Proceedings of 52nd annual meeting of the association for computational linguistics: system demonstrations_ , 2014, pp. 55–60.
  * [33] J. Pennington, R. Socher, and C. Manning, “Glove: Global vectors for word representation,” in _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , 2014, pp. 1532–1543.
  * [34] R. Krishna, K. Hata, F. Ren, L. Fei-Fei, and J. Carlos Niebles, “Dense-captioning events in videos,” in _Proceedings of the IEEE international conference on computer vision_ , 2017, pp. 706–715.
  * [35] Y. Feng, L. Ma, W. Liu, and J. Luo, “Unsupervised image captioning,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019.
  * [36] K. Zhang and D. Shasha, “Simple fast algorithms for the editing distance between trees and related problems,” _SIAM journal on computing_ , vol. 18, no. 6, pp. 1245–1262, 1989.
  * [37] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, and J. Brew, “Huggingface’s transformers: State-of-the-art natural language processing,” _ArXiv_ , vol. abs/1910.03771, 2019.
  * [38] C. Szegedy, S. Ioffe, V. Vanhoucke, and A. A. Alemi, “Inception-v4, inception-resnet and the impact of residual connections on learning,” in _Thirty-First AAAI Conference on Artificial Intelligence_ , 2017.
  * [39] O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, and M. Bernstein, “Imagenet large scale visual recognition challenge,” _International Journal of Computer Vision_ , vol. 115, no. 3, pp. 211–252, 2015.
  * [40] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [41] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” in _Advances in Neural Information Processing Systems_ , 2019, pp. 8024–8035.
  * [42] H. Fang, S. Gupta, F. Iandola, R. K. Srivastava, L. Deng, P. Dollar, J. Gao, X. He, M. Mitchell, J. C. Platt, C. Lawrence Zitnick, and G. Zweig, “From captions to visual concepts and back,” in _The IEEE Conference on Computer Vision and Pattern Recognition_ , June 2015.
  * [43] Q. Wang and A. B. Chan, “Describing like humans: on diversity in image captioning,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 4195–4203.

|  Yitian Yuan received her Ph.D. degree in computer science and technology
from Tsinghua University in 2021. She got her B.E. degree in computer science
from Beijing Jiaotong University in 2016. Her main research interests include
multimedia analysis, computer vision and deep learning. She is currently a
researcher in Meituan, Beijing, China.
---|---
|  Lin Ma received the Ph.D. degree from the Department of Electronic
Engineering, The Chinese University of Hong Kong, in 2013, the B.E. and M.E.
degrees in computer science from the Harbin Institute of Technology, Harbin,
China, in 2006 and 2008, respectively. He is now a Researcher with Meituan,
Beijing, China. Previously, he was a Principal Researcher with Tencent AI
Laboratory, Shenzhen, China from Sept. 2016 to Jun. 2020. He was a Researcher
with the Huawei Noah’Ark Laboratory, Hong Kong, from 2013 to 2016. His current
research interests lie in the areas of computer vision, multimodal deep
learning, specifically for image and language, image/video understanding, and
quality assessment. Dr. Ma received the Best Paper Award from the Pacific-Rim
Conference on Multimedia in 2008. He was a recipient of the Microsoft Research
Asia Fellowship in 2011. He was a finalist in HKIS Young Scientist Award in
engineering science in 2012.
---|---
|  Wenwu Zhu is currently a Professor of Computer Science Department of
Tsinghua University and Vice Dean of National Research Center on Information
Science and Technology, Prior to his current post, he was a Senior Researcher
and Research Manager at Microsoft Research Asia. He was the Chief Scientist
and Director at Intel Research China from 2004 to 2008. He worked at Bell Labs
New Jersey as a Member of Technical Staff during 1996-1999. He served as the
Editor-in-Chief for the IEEE Transactions on Multimedia (T-MM) from January 1,
2017 to December 31, 2019. He has been serving as the chair of the steering
committee for IEEE T-MM and Vice EiC for IEEE Transactions on Circuits and
Systems for Video Technology (TCSVT) since January 1, 2020. His current
research interests are in the areas of multimedia big data and intelligence,
and multimedia networking including edge computing. He received nine Best
Paper Awards. He is an IEEE Fellow, AAAS Fellow, SPIE Fellow, and a member of
Academia Europaea.
---|---


# The Rainbow Connection Number of The Commuting Graph of a Finite Nonabelian
Group

Rian Febrian Umbara1,3, A.N.M. Salman2†, Pritta Etriana Putri2‡ 1 Doctoral
Program in Mathematics, Faculty of Mathematics and Natural Sciences, Institut
Teknologi Bandung, Bandung, Indonesia<EMAIL_ADDRESS>2
Combinatorial Mathematics Research Group, Faculty of Mathematics and Natural
Sciences, Institut Teknologi Bandung, Indonesia
†msalman<EMAIL_ADDRESS>3 School of Computing, Telkom
University, Bandung, Indonesia<EMAIL_ADDRESS>
###### Abstract.

A path in an edge-colored graph is called a rainbow path if every two distinct
edges of the path have different colors. A graph whose every pair of vertices
are linked by a rainbow path is called a rainbow-connected graph. The rainbow
connection number of a graph is the minimum number of colors that are needed
to color the edges of the graph such that the graph is rainbow-connected. In
this paper, we determine the rainbow connection number of the commuting graph
of a finite nonabelian group, which is a graph whose vertex set is a
nonabelian group of finite order and two distinct elements of the group is
adjacent in the graph if they commute. We also show that the rainbow
connection number of the commuting graph of a finite group is related to the
number of maximal abelian subgroups or the number of involutions that do not
commute with any other nonidentity element of the group.

###### Key words and phrases:

rainbow connection number, commuting graph, finite nonabelian group

###### 2010 Mathematics Subject Classification:

Primary 05C15; Secondary 05C25.

##  1\. Introduction

Let $G=(V(G),E(G))$ be a graph with $V(G)$ and $E(G)$ are its set of vertices
and set of edges, respectively. Let $c$ be an edge coloring on $G$ which
allows the adjacent edges of $G$ have the same color. A path $P$ betwen two
vertices of $G$ is a rainbow path under the coloring $c$ if every pair of
edges of the path have different colors. If every two vertices of $G$ are
connected by a raibow path, then $G$ is rainbow-conneted. The minimum number
of colors that are needed to color the edges of $G$ such that $G$ is rainbow-
connected is called the rainbow connection number of $G$, denoted by $rc(G)$.
A rainbow coloring of $G$ that uses $rc(G)$ colors is called a minimum rainbow
coloring of $G$.

The study of rainbow connection number of a graph was initiated by Chartrand
et al. in 2008 [8]. The concept of rainbow connection number was proposed to
solve the problem of communication security between two agencies of US
Government after the terrorist attack on September 11, 2001. The rainbow
connection number of a graph serves as a metric to assess the security of a
communication or computer network represented by the graph. Besides defining
rainbow connection number of a graph, Chartrand et al. also determined the
rainbow connection numbers of some graphs, such as complete graphs, trees,
wheel graphs, bipartite graphs, and multipartite graphs [8]. Other researchers
have also studied the rainbow connection numbers of other graph families. Some
of them are Fitriani et al. who studied the rainbow connection number of
amalgamation of some graphs [12] and comb product of graphs [13] .

Over the last decade, some researchers have studied the rainbow connection
numbers of some graphs of finite groups. A graph of a finite group is a graph
whose vertex set is the elements of a finite group and two elements of the
group are adjacent if they meet a certain condition. Some example of graphs of
finite groups are Cayley graphs [6], non-commuting graph of a group [2],
commuting graph of a group [4], undirected power graphs of semigroups [7], the
enhanced power graph of a group [1], and the inverse graph of a finite group
[3]. Some studies have been conducted to study rainbow connection numbers of
some graphs of finite groups, such as the (strong) rainbow connection numbers
of Cayley graphs on abelian groups [14], rainbow 2-connection numbers of
Cayley graphs [15], rainbow connection number of the power graph of a finite
group [16], rainbow connectivity of the non-commuting graph of a finite group
[20], rainbow connection numbers of Cayley graphs [17], rainbow connectivity
in some Cayley graphs [5], and rainbow connection number of the inverse graph
of a finite group ([18],[19]).

Motivated by those studies, we study the rainbow connection number of the
commuting graph of a finite nonabelian group. The commuting graph
$CG(\Gamma,X)$, where $\Gamma$ is a finite group and $X$ is a nonempty subset
of $\Gamma$, is a graph with $X$ as its set of vertices and $u,v\in X$ are
adjacent if $u$ and $v$ commute in $\Gamma$ [4]. If $X=\Gamma$, then
$CG(\Gamma,X)$ is written as $CG(\Gamma)$. In this paper, we discuss
$CG(\Gamma)$, where $\Gamma$ is a finite nonabelian group. We show that for a
finite nonabelian group $\Gamma$ with a nontrivial center, the rainbow
connection number of $CG(\Gamma)$ is related to the number of maximal abelian
subgroups of $\Gamma$. We also show that if $\Gamma$ is a finite nonabelian
group with a trivial center, the rainbow connection number of $CG(\Gamma)$
determines the number of involutions of $\Gamma$ that do not commute with any
other nonidentity element of $\Gamma$.

##  2\. Preliminaries

###  2.1. Some terminologies in Graph Theory

We refer to [9] for definitions and notations in Graph Theory that are not
described in this text. A graph is a pair $G=(V(G),E(G))$ of sets, where the
elements of $E(G)$ are 2-element subsets of $V(G)$. An element of $V(G)$ is
called a vertex of $G$ and an element of $E(G)$ is called an edge of $G$. A
graph $G=(V(G),E(G))$ is finite if $|V(G)|$ is finite. If $|V(G)|=0$ of $1$,
then $G$ is called a trivial graph. An edge $\epsilon=\\{x,y\\}$ is written as
$\epsilon=xy$ or $\epsilon=yx$. Two vertices $x$ and $y$ of a graph $G$ are
adjacent if $xy$ is an edge of $G$. An edge $xy$ is incident with both $x$ and
$y$. Both $x$ and $y$ are the ends of the edge $xy$. A vertex of a graph $G$
which is adjacent to one and only one vertex of $G$ is called a pendant
vertex. An edge that incidents with a pendant vertex is called a pendant edge.
If every two distinct vertices of a graph $G$ is adjacent, then $G$ is a
complete graph. Let $k\geq 1$ be an integer. A path between two vertices
$x_{0}$ and $x_{k}$ is a graph with a set of vertices
$\\{x_{0},x_{1},\dots,x_{k}\\}$ and a set of edges
$\\{x_{0}x_{1},x_{1}x_{2},\dots,x_{k-1}x_{k}\\}$, where $x_{i}\neq x_{j}$ for
every distinct $i,j\in\\{0,1,\dots,k\\}$. If there is a path between every two
distinct vertices of a graph, then the graph is connected. All graphs in this
paper are nontrivial and connected.

The length of a path is the number of edges in the path. The distance between
two vertices $x$ and $y$, denoted by $d(x,y)$, in a graph $G$ is the length of
the shortest path between $x$ and $y$ in $G$. The largest distance between any
two vertices of a graph $G$ is called the diameter of $G$, denoted by
$diam(G)$. Let $r\geq 2$ be an integer. A graph $G=(V(G),E(G))$ is called an
$r$-partite graph if $V(G)$ can be partitioned into $r$ classes such that
every member of $E(G)$ has it ends in different classes.

###  2.2. Some properties of the rainbow connection number of a graph

Let $G$ be a connected graph with at least two vertices. Chartrand et al. [8]
have determined some properties of the rainbow connection number of $G$. For a
connected graph $G$, $diam(G)\leq rc(G)\leq m$, where $diam(G)$ is the
diameter of $G$ and $m$ is the number of edges of $G$. For a natural number
$t$, if a connected graph $G$ with $|G|\geq 3$ has $t$ pendant vertices, then
$rc(G)\geq t$. The rainbow connection number of a complete graph and a
$k$-partite graph, where $k\geq 3$, have also been determined.

######  Theorem 2.1.

[8] Let $G$ be a connected graph. The rainbow connection number of $G$ is 1 if
and only if $G$ is a complete graph.

######  Theorem 2.2.

[8] Let $G=K_{n_{1},n_{2},\dots,n_{k}}$ be a complete $k$-partite graph, with
$k\geq 3$ and $n_{1}\leq n_{2}\leq\dots\leq n_{k}$, such that
$s=\sum_{1}^{k-1}n_{i}$ and $t=n_{k}$. Then

$rc(G)=\begin{cases}1&\text{if }n_{k}=1\\\ 2&\text{if }n_{k}\geq 2,s>t\\\
min\\{3,\lceil\sqrt[s]{t}\rceil\\}&\text{if }s\leq t\end{cases}$

###  2.3. Group and the commuting graph of a group

We refer to [10] for definitions and notations in Group Theory that are not
described in this paper. A group is an ordered pair $(\Gamma,*)$, where
$\Gamma$ is a set and $*$ is a binary operation, which satisfies the following
axioms:

  1. (1)

$(a*b)*c=a*(b*c)$ for all $a,b,c\in\Gamma$,

  2. (2)

there exists an element $e\in\Gamma$, which is called the identity element of
$\Gamma$, such that $a*e=e*a=a$ for all $a\in\Gamma$,

  3. (3)

for each $a\in\Gamma$ there is an element $a^{-1}\in\Gamma$, which is called
the inverse of $a$, such that $a*a^{-1}=a^{-1}*a=e$.

For simplicity, the group notation $(\Gamma,*)$ will be written as $\Gamma$.
Let $\Gamma$ be a group. Two members $a,b\in\Gamma$ commute if $a*b=b*a$. A
group $\Gamma$ is called an abelian group if every two members of $\Gamma$
commute. The center of a group $\Gamma$ is $Z(\Gamma)=\\{z\in\Gamma|z*a=a*z$
for every $a\in\Gamma\\}$. If $Z(\Gamma)=\\{e\\}$, where $e$ is the identity
element of $\Gamma$, then $Z(\Gamma)$ is called trivial. A group $\Gamma$ is
called a finite group if $|\Gamma|$ (the cardinality of the set $\Gamma$) is
finite. An element $a\in\Gamma$ is called an involution if $a\neq e$ and
$a*a=e$. If $\Gamma$ is a group and $\Lambda$ is a nonempty subset of $\Gamma$
such that for all $h,k\in\Lambda$, $h*k\in\Lambda$ and $h^{-1}\in\Lambda$,
then $\Lambda$ is called a subgroup of $\Gamma$. If $\Lambda$ is a subgroup of
$\Gamma$ such that every two elements of $\Lambda$ commute, then $\Lambda$ is
an abelian subgroup of $\Gamma$. If $\Lambda$ is an abelian subgroup of a
group $\Gamma$ and there is no other abelian subgroup of $\Gamma$ that
contains $\Lambda$, then $\Lambda$ is called a maximal abelian subgroup of
$\Gamma$.

The identity element of a finite group is a member of every maximal abelian
subgroup of the group. Hence, the cardinality of any maximal abelian subgroup
of a finite nontrivial group is at least 2. A maximal abelian subgroup of
cardinality 2 consists of the identity element of the group and an involution
that do not commute with any other nonidentity element of the group. If $a$
and $b$ are any two elements that do not commute in a finite nonabelian group,
then $a$ and $b$ are not in the same maximal abelian subgroup of the group and
the subset $\\{a,b,a*b\\}$ is noncommuting. Therefore, a finite nonabelian
group must have at least three maximal abelian subgroups. It is obvious that
if $\\{\Lambda_{1},\Lambda_{2},\dots,\Lambda_{m}\\}$ is the collection of all
maximal abelian subgroups of a finite nonabelian group $\Gamma$, where $m\geq
3$, then $\Gamma=\bigcup\limits_{i=1}^{m}\Lambda_{i}$. A finite group $\Gamma$
has only one maximal abelian subgroup if and only if $\Gamma$ is abelian. In
this case, the maximal abelian subgroup is the group itself.

The commuting graph $CG(\Gamma,X)$, where $\Gamma$ is a finite group and $X$
is a nonempty subset of $\Gamma$, is a graph whose set of vertices is $X$ and
two members $a,b\in X$ are adjacent if $a*b=b*a$ in $\Gamma$ [4]. If
$X=\Gamma$, then $CG(\Gamma,X)$ is written as $CG(\Gamma)$. Obviously,
$CG(\Gamma)$ is connected, since the identity element of any group $\Gamma$
comumutes with all elements of the group. Figure 1 shows the commuting graph
of group $SD_{24}$, the semidihedral group with 24 members. The presentation
of the group is $SD_{24}=\langle a,b:a^{12}=b^{2}=1,ba=a^{5}b\rangle$.

Figure 1. The commuting graph of group $SD_{24}$.

Every two elements of a maximal abelian subgroup of a finite group $\Gamma$
are adjacent in $CG(\Gamma)$. Hence, a maximal abelian subgroup of $\Gamma$
forms a maximal clique in $CG(\Gamma)$, and a maximal abelian subgroup of
order 2 forms a pendant edge in $CG(\Gamma)$. Since a finite abelian group has
only one maximal abelian subgroup, which is the group itself, the commuting
graph the group is a complete graph, and hence its rainbow connection number
is 1. If $\Gamma$ is a finite nonabelian group, then $\Gamma$ has more than
one maximal commuting subsets and its commuting graph is not a complete
graph..

##  3\. Main results

Throughout this section, we discuss rainbow connection numbers of the
commuting graphs of finite nonabelian groups. If $\Gamma$ is a finite
nonabelian group, then $CG(\Gamma)$ is not a complete graph and hence
$rc(CG(\Gamma))\geq 2$. We start the discussion with finite nonabelian groups
whose commuting graphs have rainbow connection numbers at most 3.

######  Theorem 3.1.

Let $\Gamma$ be a finite nonabelian group. The rainbow connection number of
$CG(\Gamma)$ is at most $3$ if and only if $\Gamma$ has a nontrivial center or
$\Gamma$ is a group with a trivial center and has at most three maximal
abelian subgroups of order $2$.

###### Proof.

Let $\Gamma$ be a finite nonabelian group with a nontrivial center and
$Z(\Gamma)$ be the center of $\Gamma$. Since any member of $Z(\Gamma)$
commutes with all members of $\Gamma$, any member of $Z(\Gamma)$ is adjacent
with all vertices in $V(CG(\Gamma))$. Choose any two members $z_{1}$ and
$z_{2}$ from $Z(\Gamma)$. For every element $x\in\Gamma\setminus Z(\Gamma$),
the edge $xz_{1}$ is colored with color 1 and the edge $xz_{2}$ is colored
with color 2. The edge $z_{1}z_{2}$ is colored with color 3. The other edges
of $CG(\Gamma)$ are colored with color 1. With this edge coloring, every two
distinct elements $x,y\in\Gamma\setminus Z(\Gamma)$ are connected by the path
$xz_{1}z_{2}y$ which has 3 edges with 3 distinct colors. Hence,
$rc(CG(\Gamma))\leq 3$.

Now let $\Gamma$ be a finite nonabelian group with a trivial center and has at
most three maximal abelian subgroups of order 2. Let $e$ be the identity
element of $\Gamma$, $\mathscr{C}=\\{C_{1},\dots,C_{m}\\}$ be the collection
of all maximal abelian subgroups of $\Gamma$ with $m\geq 3$ (since $\Gamma$ is
nonabelian), and let $\mathscr{C}$ has exactly $t$ members of order 2, where
$0\leq t\leq 3$. Construct a set
$\bar{\mathscr{C}}=\\{\bar{C}_{1},\dots,\bar{C}_{t}\\}$, which is the
collection of all maximal abelian subgroups of order 2 and
$\hat{C}=(\Gamma\setminus\bigcup\limits_{i=1}^{t}\bar{C}_{i})\cup\\{e\\}$.
Write $\bar{C}_{i}=\\{e,\bar{c}_{i}\\}$ for every $i\in\\{1,\dots,t\\}$ and
write $\hat{C}=\\{e,\hat{c}_{1},\hat{c}_{2},\dots,\hat{c}_{s}\\}$ in an order
such that $\hat{c}_{i}$ commutes with $\hat{c}_{i-1}$ or with $\hat{c}_{i+1}$
for every $i\in\\{1,\dots,s\\}$, where $s=|\Gamma|-t-1$.

If $t=0$, then $\bar{\mathscr{C}}=\emptyset$, $\hat{C}=\Gamma$, and we can
color the edges of $CG(\Gamma)$ with three colors as follows:

  1. (1)

the edge $e\hat{c}_{i}$ is colored with color 1 if $i$ is odd or color 2 if
$i$ is even for every $i\in\\{1,2,\dots,s\\}$,

  2. (2)

the other edges are colored with color 3.

With this coloring, the rainbow paths between two vertices of $CG(\Gamma)$ are
as follows:

  1. (1)

$\hat{c}_{i}\hat{c}_{j}$ if $\hat{c}_{i}$ and $\hat{c}_{j}$ are adjacent,
where $i,j\in\\{1,2,\dots,s\\}$,

  2. (2)

$\hat{c}_{i}e\hat{c}_{j}$ if $\hat{c}_{i}$ and $\hat{c}_{j}$ are not adjacent
and the parities of $i$ and $j$ are different, where
$i,j\in\\{1,2,\dots,s\\}$,

  3. (3)

if $\hat{c}_{i}$ and $\hat{c}_{j}$ are not adjacent and the parities of $i$
and $j$ are the same, where $i,j\in\\{1,2,\dots,s\\}$, then the rainbow path
between $\hat{c}_{i}$ and $\hat{c}_{j}$ is
$\hat{c}_{i}e\hat{c}_{j-1}\hat{c}_{j}$ if $\hat{c}_{j-1}$ is adjacent to
$\hat{c}_{j}$ and $j\neq 1$, or $\hat{c}_{i}e\hat{c}_{j+1}\hat{c}_{j}$ if
$\hat{c}_{j+1}$ is adjacent to $\hat{c}_{j}$ and $j\neq s$.

Since every two vertices of $CG(\Gamma)$ are connected by a rainbow path under
this edge coloring, we have $rc(CG(\Gamma))\leq 3$.

If $1\leq t\leq 3$, the edge $e\bar{c}_{i}$ is a pendant edge of $CG(\Gamma)$
for every $i\in\\{1,\dots,t\\}$ and we can color the edges of $CG(\Gamma)$
with three colors as follows:

  1. (1)

the edge $e\bar{c}_{i}$ is colored with color $i$ for every
$i\in\\{1,\dots,t\\}$,

  2. (2)

the edge $e\hat{c}_{i}$ is colored with color 1 if $i$ is odd or color 2 if
$i$ is even for every $i\in\\{1,2,\dots,s\\}$,

  3. (3)

the other edges are colored with color 3.

The rainbow paths between two vertices of $CG(\Gamma)$ under this edge
coloring are as follows.

  1. (1)

The rainbow paths between $\hat{c}_{i}$ and $\hat{c}_{j}$, where
$i,j\in\\{1,2,\dots,s\\}$ and $i\neq j$, are the same as the paths in the case
of $t=0$.

  2. (2)

For $i,j\in\\{1,\dots,t\\}$, where $i\neq j$, the rainbow path between
$\bar{c}_{i}$ and $\bar{c}_{j}$ is $\bar{c}_{i}e\bar{c}_{j}$.

  3. (3)

For $j\in\\{1,2,\dots,s\\}$, the rainbow path between $\bar{c}_{1}$ and
$\hat{c}_{j}$ is $\bar{c}_{1}e\hat{c}_{j}$ if $j$ is even,
$\bar{c}_{1}e\hat{c}_{j-1}\hat{c}_{j}$ if $j$ is odd, $\hat{c}_{j-1}$ is
adjacent to $\hat{c}_{j}$, and $j\neq 1$, or
$\bar{c}_{1}e\hat{c}_{j+1}\hat{c}_{j}$ if $j$ is odd, $\hat{c}_{j+1}$ and
$\hat{c}_{j}$ are adjacent, and $j\neq s$.

  4. (4)

If $t=2$ and $j\in\\{1,2,\dots,s\\}$, the rainbow path between $\bar{c}_{2}$
and $\hat{c}_{j}$ is $\bar{c}_{2}e\hat{c}_{j}$ if $j$ is odd,
$\bar{c}_{2}e\hat{c}_{j-1}\hat{c}_{j}$ if $j$ is even and $\hat{c}_{j-1}$ is
adjacent to $\hat{c}_{j}$, or $\bar{c}_{2}e\hat{c}_{j+1}\hat{c}_{j}$ if $j$ is
even, $\hat{c}_{j+1}$ is adjacent to $\hat{c}_{j}$, and $j\neq s$. The rainbow
paths between $\bar{c}_{1}$ and $\hat{c}_{j}$ are the same as the paths in
point 3.

  5. (5)

If $t=3$ and $j\in\\{1,2,\dots,s\\}$, the rainbow path between $\bar{c}_{3}$
and $\hat{c}_{j}$ is $\bar{c}_{3}e\hat{c}_{j}$ . The rainbow paths between
$\bar{c}_{1}$ and $\hat{c}_{j}$, and between $\bar{c}_{2}$ and $\hat{c}_{j}$,
are the same as the paths in point 3 and 4, respectively.

Since every two distinct vertices of $CG(\Gamma)$ are connected by a rainbow
path under this edge coloring, we get $rc(CG(\Gamma))\leq 3$. From the above
explanations, we conclude that if $\Gamma$ has a nontrivial center or if
$\Gamma$ is a group with a trivial center and has at most three maximal
abelian subgroups of order 2, then $rc(CG(\Gamma))\leq 3$.

Now suppose that $\Gamma$ is a finite nonabelian group with a trivial center
and has at least $4$ maximal abelian subgroups of order 2. Therefore,
$CG(\Gamma)$ has at least $4$ pendant edges and $rc(CG(\Gamma))\geq 4$. Thus,
if $rc(CG(\Gamma))\leq 3$, then $\Gamma$ has a nontrivial center or $\Gamma$
is a group with a trivial center and has at most three maximal abelian
subgroups of order 2. ∎

Theorem 3.1 characterizes all finite nonabelian groups whose rainbow
connection numbers of their commuting graphs do not exceed 3. The theorem
states that the rainbow connection number of a finite nonabelian groups with
nontrivial center cannot be greater than 3. In Theorem 4, we discuss a finite
nonabelian group with nontrivial center whose rainbow connection number of its
inverse graph equals 2.

######  Theorem 3.2.

Let $\Gamma$ be a finite nonabelian group with $|Z(\Gamma)|\geq 2$ and
$\mathscr{C}$ be the collection of all maximal abelian subgroups of $\Gamma$.
If $|\mathscr{C}|\leq 2^{|Z(\Gamma)|}$, then $rc(CG(\Gamma))=2$.

###### Proof.

Let $\Gamma$ be a finite nonabelian group with $|Z(\Gamma)|\geq 2$ and
$\mathscr{C}=\\{C_{1},\dots,C_{m}\\}$ be the collection all maximal abelian
subgroups of $\Gamma$, where $m\geq 3$. Since $\Gamma$ is nonabelian,
$rc(CG(\Gamma))\geq 2$. Choose any $u_{i}$ from $C_{i}$ for every
$i\in\\{1,\dots,m\\}$ such that $u_{i}$ and $u_{j}$ are not adjacent in
$CG(\Gamma)$ if $i\neq j$. Form a subset $U=\\{u_{1},\dots,u_{m}\\}$. Consider
an induced subgraph of $CG(\Gamma)$ whose set of vertices is $Z(\Gamma)\cup
U$. Since every two distinct elements of $Z(\Gamma)$ are adjacent and each
element of $U$ is adjacent to each element of $Z(\Gamma)$, the induced
subgraph is a complete $(|Z(\Gamma)|+1)$-partite graph $K_{1,\dots,1,|m|}$
whose partite sets are $\\{z_{1}\\},\dots,\\{z_{|Z(\Gamma)|}\\}$, and $U$. If
$m\leq 2^{|Z(\Gamma)|}$, according to Theorem 2.2, the rainbow connection
number of the induced subgraph is 2. Hence, if $m\leq 2^{|Z(\Gamma)|}$, then
we only need 2 colors for coloring the edges of $CG(\Gamma)$ such that any two
nonadjacent vertices are linked by a rainbow path, and we get
$rc(CG(\Gamma))=2$. ∎

The semidihedral group $SD_{8n}$, which is a group of order $8n$ with $n\geq
2$, is an example of a group that meet the condition of Theorem 3.2. The
presentation of the group is $SD_{8n}=\langle
a,b:a^{4n}=b^{2}=e,ba=a^{2n-1}b\rangle$. The set of elements of the group is
$\\{e,a,a^{2},\dots,a^{4n-1},b,ab,a^{2}b,\dots,a^{4n-1}b\\}$. The center of
$SD_{8n}$ is $Z(SD_{8n})=\\{e,a^{2n}\\}$ if $n$ is even, and
$Z(SD_{8n})=\\{e,a^{n},a^{2n},a^{3n}\\}$ if $n$ is odd. For an even $n$, the
maximal abelian subgroups of $SD_{8n}$ are
$H_{i}=\\{e,a^{2n},a^{i}b,a^{2n+i}b\\}$ for $i\in\\{1,2,\dots,3n-1\\}$ and
$H_{3n}=\\{e,a,a^{2},\dots,a^{4n-1}\\}$. For an odd $n$, the maximal abelian
subgroups of $SD_{8n}$ are
$H_{i}=\\{e,a^{n},a^{2n},a^{3n},a^{i}b,a^{n+i}b,a^{2n+i}b,a^{3n+i}b\\}$ for
$i\in\\{1,2,\dots,n\\}$ and $H_{n+1}=\\{e,a,a^{2},\dots,a^{4n-1}\\}$. If $n=$
3, $SD_{8n}=SD_{24}$ and has four maximal abelian subgroups. Hence,
$rc(CG(SD_{24}))=2$. Figure 2 shows the minimum rainbow coloring of the
commuting graph of the group $SD_{24}$.

Figure 2. The minimum rainbow coloring of the commuting graph of group
$SD_{24}$ with two colors. The edges whose color numbers are not written are
colored with color 1.

From Theorem 3.2, we directly get the fact that for a finite nonabelian group
$\Gamma$ with $|Z(\Gamma)|\geq 2$, if $rc(CG(\Gamma))=3$, then $\Gamma$ has
more than $2^{|Z(\Gamma)|}$ maximal abelian subgroups. In order to obtain some
finite nonabelian groups whose rainbow connection numbers of their commuting
graphs equal 3, we need the following theorem.

######  Theorem 3.3.

Let $\Gamma$ be a finite nonabelian group and $H\subset\Gamma$, with $|H|\geq
2$. If $\Gamma$ has a collection $\mathscr{T}$ of at least two maximal abelian
subgroups such that the intersection of every two subgroups in $\mathscr{T}$
equals $H$, then

  1. (1)

$rc(CG(\Gamma,X))=2$ if and only if $|\mathscr{T}|\leq 2^{|H|}$,

  2. (2)

$rc(CG(\Gamma,X))=3$ if and only if $|\mathscr{T}|>2^{|H|}$,

where $X$ is the union of all subgroups in $\mathscr{T}$.

###### Proof.

Let $\Gamma$ be a finite nonabelian group and $H$ be a subset of $\Gamma$ with
$|H|\geq 2$. Let $m\geq 2$, $\mathscr{T}=\\{\Theta_{1},\dots,\Theta_{m}\\}$ be
a collection of some maximal abelian subgroups of $\Gamma$ such that
$H=\Theta_{i}\cap\Theta_{j}$ for every distinct $i$ and $j$ in
$\\{1,\dots,m\\}$, and $X=\bigcup\limits_{i=1}^{m}\Theta_{i}$. Since $\Gamma$
is nonabelian and $m\geq 2$, $CG(\Gamma,X)$ is not a complete graph.
Therefore, $rc(CG(\Gamma,X))\geq 2$ (according to Theorem 2.1). Every two
distinct elements of $\Theta_{i}$ are adjacent in $CG(\Gamma,X)$ for each
$\\{1,\dots,m\\}$. In particular, every two distinct elements of $H$ are
adjacent in $CG(\Gamma,X)$. Since $\Theta_{i}\cap\Theta_{j}=H$ for every
$i,j\in\\{1,\dots,m\\}$, where $i\neq j$, every $a\in\Theta_{i}\setminus H$ is
not adjacent to every $b\in\Theta_{j}\setminus H$ in $CG(\Gamma,X)$ if $i\neq
j$. Hence, the shortest path (of length 2) in $CG(\Gamma,X)$ that connects
$a\in\Theta_{i}\setminus H$ and $b\in\Theta_{j}\setminus H$, where $i\neq j$,
is the path $ah_{k}b$, where $h_{k}\in H$ and $k$ in $\\{1,\dots,|H|\\}$.

Pick one member $w_{i}$ from $\Theta_{i}\setminus H$ for every
$i\in\\{1,\dots,m\\}$, then form a subset $W=\\{w_{1},\dots,w_{m}\\}$.
Obviously, every two distinct members of $W$ are not adjacent in
$CG(\Gamma,X)$. Consider an induced subgraph of $CG(\Gamma,X)$ with $H\cup W$
as its set of vertices. We name the subgraph as $T$. Since every two distinct
vertices of $H$ are adjacent and each vertex of $H$ is adjacent to every
vertex of $W$, $T$ is a complete $(|H|+1)$-partite graph $K_{1,\dots,1,|m|}$,
where its partite sets are $\\{h_{1}\\},\dots,\\{h_{|H|}\\}$, and $W$. If
$|H|\geq 2$, then the number of partite sets of $V(T)$ is at least 3 and the
rainbow connection number of $T$ is 2 or 3 (according to Theorem 2.2). Let
$c_{T}$ be a minimum rainbow coloring of $T$. Then, the number of colors of
$c_{T}$ is 2 or 3. Since $H=\Theta_{i}\cap\Theta_{j}$ for every distinct $i$
and $j$ in $\\{1,\dots,m\\}$, the paths $w_{i}h_{k}w_{j}$ in $T$ for all
$k\in\\{1,\dots,|H|\\}$ are the shortest paths (of length 2) in $CG(\Gamma,X)$
which connect $w_{i}$ and $w_{j}$. The other paths in $CG(\Gamma,X)$ which
connect $w_{i}$ and $w_{j}$ have length at least 3.

Next, choose any member $\hat{w}_{i}$ from $\Theta_{i}\setminus H$ for every
$i\in\\{1,\dots,m\\}$ such that $\hat{w}_{i}\neq w_{i}$ for at least one
$i\in\\{1,\dots,m\\}$ and form a subset
$\hat{W}=\\{\hat{w}_{1},\dots,\hat{w}_{m}\\}$. Then we get another
$(|H|+1)$-partite induced subgraph of $CG(\Gamma,X)$, namely $\hat{T}$, with
partites sets are $\\{h_{1}\\},\dots,\\{h_{|H|}\\}$, and $\hat{W}$. Similar to
$T$, for every distinct $i$ and $j$ in $\\{1,\dots,m\\}$, the paths
$\hat{w}_{i}h_{k}\hat{w}_{j}$ in $\hat{T}$ for all $k\in\\{1,\dots,|H|\\}$ are
the shortest paths (of length 2) in $CG(\Gamma,X)$ which connect $\hat{w}_{i}$
and $\hat{w}_{j}$. The other paths in $CG(\Gamma,X)$ which connect
$\hat{w}_{i}$ and $\hat{w}_{j}$ have length at least 3. Obviously, $T$ and
$\hat{T}$ are isomorphic. Hence, $c_{T}$ can also be a minimum rainbow
coloring of $\hat{T}$, where the edge $\hat{w}_{i}h_{j}$ in $\hat{T}$ is
colored with the same color that we use to color the edge $w_{i}h_{j}$ in $T$
and the color of the edge $h_{j}h_{k}$ in $\hat{T}$ is also the same as the
color of the edge $h_{j}h_{k}$ in $T$ for every $i\in\\{1,\dots,m\\}$ and
every $j,k\in\\{1,\dots,|H|\\}$. Therefore, the rainbow connection number of
$\hat{T}$ is also 2 or 3. In fact, the number of such $(|H|+1)$-partite
induced subgraphs in $CG(\Gamma,X)$ is $\prod_{i=1}^{m}|\Theta_{i}\setminus
H|$ and $c_{T}$ can be used as the minimum rainbow coloring for each of them.
All edges of $CG(\Gamma,X)$ outside the union of these subgraphs are the edges
between two adjacent vertices in $\Theta_{i}\setminus H$ for all
$i\in\\{1,\dots,m\\}$. If we use $c_{T}$ as the edge coloring for each of the
$(|H|+1)$-partite induced subgraphs and all edges of $CG(\Gamma,X)$ outside
the union of these subgraphs are colored with one of the colors of $c_{T}$,
then every two ertices of $CG(\Gamma,X)$ are connected by a rainbow path. If
we use less than the number of colors of $c_{T}$ to color the edges of
$CG(\Gamma,X)$, then there exists a pair of nonadjacent vertices of $T$ that
are not connected by a rainbow path, and $CG(\Gamma,X)$ is not rainbow-
connected. Therefore, the number of colors of $c_{T}$ is also the number of
colors of the minimum rainbow coloring of $CG(\Gamma,X)$. Thus, the rainbow
connection number of $CG(\Gamma,X)$ is the same as the rainbow connection
number of $T$, which is 2 or 3.

Next, we determine $rc(CG(\Gamma,X))$ based on the value of $m$ and $|H|$.

  1. (1)

Let $m\leq 2^{|H|}$ . If $m<|H|$, then according to Theorem 2.2, the rainbow
connection number of $T$ is 2. If $|H|\leq m\leq 2^{|H|}$, then
$\lceil\sqrt[|H|]{m}\rceil=2$. Thus, according to Theorem 2.2, the rainbow
connection number of $T$ is 2.

Now suppose that $m>2^{|H|}$. We get $\lceil\sqrt[|H|]{m}\rceil>2$. According
to Theorem 2.2, the rainbow connection number of $T$ is 3. Hence, if the
rainbow connection number of $T$ is 2, then $m\leq 2^{|H|}$. Thus, the rainbow
connection number of $T$ is 2 if and only if $m\leq 2^{|H|}$. Since the
rainbow connection number of $CG(\Gamma,X)$ is the same as the rainbow
connection number of $T$, we can conclude that the rainbow connection number
of $CG(\Gamma,X)$ is 2 if and only if $m\leq 2^{|H|}$

  2. (2)

According to point 1, the rainbow connection number of $CG(\Gamma,X)$ is 2 if
and only if $m\leq 2^{|H|}$ . Thus, we can conclude that the rainbow
connection number of $CG(\Gamma,X)$ is 3 if and only if $m>2^{|H|}$.

.∎

Using Theorem 3.3, we obtain some finite nonabelian groups whose rainbow
connection numbers of their commuting graphs equal 3.

######  Theorem 3.4.

Let $\Gamma$ be a finite nonabelian group with $|Z(\Gamma)|\geq 2$, or with
$|Z(\Gamma)|=1$ and has at most three maximal abelian subgroups of order $2$.
Let $m\geq 2$ be an integer, $H\subset\Gamma$ with $|H|\geq 1$, and $\Gamma$
has a collection of maximal abelian subgroups
$\mathscr{T}=\\{\Theta_{1},\dots,\Theta_{m}\\}$ such that
$\Theta_{i}\cap\Theta_{j}=H$ if $i\neq j$. If $m>2^{|H|}$, then
$rc(CG(\Gamma))=3$.

###### Proof.

Let $|Z(\Gamma)|\geq 2$, $m>2^{|H|}$, and
$X=\bigcup\limits_{i=1}^{m}\Theta_{i}$. According to Theorem 3.1,
$rc(CG(\Gamma))\leq 3$. Since $|Z(\Gamma)|\geq 2$, we get $|H|\geq 2$.
According to Theorem 3.3, $rc(CG(\Gamma,X))=3$. It is obvious that
$CG(\Gamma,X)$ is a subgraph of $CG(\Gamma)$. The length of any path $P$ in
$CG(\Gamma)$, whose $E(P)$ is not the subset of $E(CG(\Gamma,X))$, that
connects any two nonadjacent vertices $a\in\Theta_{i}\setminus H$ and
$b\in\Theta_{j}\setminus H$ for $i\neq j$ is at least $3$. Therefore, we need
an edge coloring with at least 3 colors to make $CG(\Gamma)$ rainbow-
connected, and hence $rc(CG(\Gamma))\geq 3$. Since $rc(CG(\Gamma))\leq 3$, we
get $rc(CG(\Gamma))=3$.

Now let $|Z(\Gamma)|=1$, $m>2^{|H|}$, and $\Gamma$ has at most $3$ maximal
abelian subgroups of order $2$. According to Theorem 3.1, $rc(CG(\Gamma))\leq
3$. Let $X=\bigcup\limits_{i=1}^{m}\Theta_{i}$ and $|H|=1$. Since
$|Z(\Gamma)|=|H|=1$, we get $Z(\Gamma)=H$ and $m\geq 3$. Suppose that
$rc(CG(\Gamma,X))=2$. Choose three non-identity elements $c_{1}\in\Theta_{1}$,
$c_{2}\in\Theta_{2}$, and $c_{3}\in\Theta_{3}$. Clearly, every pair of the
three elements are not adjacent in $CG(\Gamma,X)$, and also in $CG(\Gamma,)$ .
Since $\Theta_{i}\cap\Theta_{j}=\\{e\\}$ for every $i,j\in\\{1,\dots,m\\}$,
where $i\neq j$, the only paths of length 2 in $CG(\Gamma,X)$, and also in
$CG(\Gamma)$, connecting every pair of the three elements are $c_{1}ec_{2}$,
$c_{1}ec_{3}$, and $c_{2}ec_{3}$. Without loss of generality, if we color the
edge $c_{1}e$ with color 1, the edge $c_{2}e$ with color 2, and the edge
$c_{3}e$ with color 2, then $c_{1}ec_{2}$ is the rainbow path connecting
$c_{1}$ and $c_{2}$, and $c_{1}ec_{3}$ is the rainbow path connecting $c_{1}$
and $c_{3}$. But there is no rainbow path connecting $c_{2}$ and $c_{3}$.
Hence, $rc(CG(\Gamma,X))$, and also $rc(CG(\Gamma))$, must be at least 3.
Since $rc(CG(\Gamma))\leq 3$, we get $rc(CG(\Gamma))=3$. If $|H|\geq 2$, using
a similar proof as in the case of $|Z(\Gamma)|\geq 2$, we get
$rc(CG(\Gamma))\geq 3$. Since $rc(CG(\Gamma))\leq 3$, we get
$rc(CG(\Gamma))=3$. ∎

For a finite nonabelian group $\Gamma$ with a nontrivial center which the
intersection of every pair of its maximal abelian subgroups equals its center,
Theorem 3.3 immediately gives us the following corollary.

######  Corollary 3.5.

Let $\Gamma$ be a finite nonabelian group with a nontrivial center
$Z(\Gamma)$, $\mathscr{C}$ be the collection of all maximal abelian subgroups
of $\Gamma$, and the intersection of every two members of $\mathscr{C}$ equals
$Z(\Gamma)$.

  1. (1)

$rc(CG(\Gamma))=2$ if and only if $|\mathscr{C}|\leq 2^{|H|}$,

  2. (2)

$rc(CG(\Gamma))=3$ if and only if $|\mathscr{C}|>2^{|H|}$.

The dihedral group $D_{6}$ and the alternating group $A_{4}$ are examples of
groups that meet the condition of Corollary 3.5. The presentation of $D_{6}$
is $D_{6}=\langle r,s:r^{3}=s^{2}=e,srs=r^{-1}\rangle$, where $e$ is the
identity element of the group. This group has four maximal abelian subgroups,
which are $\\{e,r,r^{2}\\}$, $\\{e,s\\}$, $\\{e,rs\\}$, and $\\{e,r^{2}s\\}$.
There are three maximal abelian subgroups of order 2 in this group. The center
of this group is $Z(D_{6})=\\{e\\}$ and the intersection of every two distinct
maximal abelian subgroups is $Z(D_{6})$. The center of group $A_{4}$ is
$Z(A_{4})=\\{(1)\\}$, which is the identity permutation. This group has five
maximal abelian subgroups. The maximal abelian subgroups of $A_{4}$ are
$\\{(1),(123),(132)\\}$, $\\{(1),(124),(142)\\}$, $\\{(1),(134),(143)\\}$,
$\\{(1),(234),(243)\\}$, and $\\{(1),(12)(34),(13)(24),(14)(23)\\}$. This
group has no maximal abelian subgroup of order 2. The intersection of every
two distinct maximal abelian subgroups of $A_{4}$ is $Z(A_{4})$. According to
Corollary 3.5, $rc(CGD_{6}))=rc(CG(A_{4}))=3$. Figure 3 shows the minimum
rainbow colorings of $CG(A_{4})$ and $CG(D_{6})$ with three colors.

Figure 3. (a) A minimum rainbow coloring of $CG(A_{4})$, (b) A minimum rainbow
coloring of $CG(D_{6})$.

An example of a finite nonabelian group that meets the condition of Theorem
3.4 is the generalized quaternion group $Q_{4n}$, where $n\geq 2$, with
presentation $Q_{4n}=\langle a,b:a^{n}=b^{2},a^{2n}=e,b^{-1}ab=a^{-1}\rangle$.
The center of the group is $Z(Q_{4n})=\\{e,a^{n}\\}$. Hence, $|Z(Q_{4n})|=2$.
The maximal abelian subgroups of the group are
$H_{i}=\\{e,a^{n},a^{i}b,a^{n+i}b\\}$ for $i\in\\{0,1,\dots,n-1\\}$ and
$H_{n}=\\{e,a,a^{2},\dots,a^{2n-1}\\}$. Therefore, the group has $n+1$ maximal
abelian subgroups and it is obvious that $Z(\Gamma)=H_{i}\cap H_{j}$ for
$i,j\in\\{0,2,\dots,n\\}$ where $i\neq j$. If $n\geq 4$, then $Q_{4n}$ has at
least 5 maximal abelian subgroups. Hence, according to Theorem 3.4,
$rc(CG(Q_{4n}))=3$ if $n\geq 4$. Figure 4 shows a minimum rainbow coloring of
the group $Q_{16}$.

Figure 4. A minimum rainbow coloring of the commuting graph of group $Q_{16}$
with three colors.

So far we have discussed the finite nonabelian groups whose rainbow connection
numbers of their commuting graphs are less than or equal to 3. In Theorem 3.6,
we characterize a finite nonabelian group whose commuting graph has rainbow
connection number at least 4.

######  Theorem 3.6.

For an integer $t\geq 4$, $rc(CG(\Gamma))=t$ if and only if $\Gamma$ is a
finite nonabelian group with a trivial center and has exactly $t$ maximal
abelian subgroups of order 2.

###### Proof.

Let $t\geq 4$ be an integer and $\Gamma$ be a finite nonabelian group with a
trivial center and has exactly $t$ maximal abelian subgroups of order 2. Let
$e$ be the identity element of $\Gamma$ and
$\mathscr{C}=\\{C_{1},\dots,C_{m}\\}$ be the collection of all maximal abelian
subgroups of $\Gamma$, where $m\geq 4$. Form the sets $\bar{\mathscr{C}}$ and
$\hat{C}$ as in the proof of Theorem 3.1. Recall that since
$|\bar{\mathscr{C}}|=t$, the commuting graph $CG(\Gamma)$ has exactly $t$
pendant edges. Therefore, $rc(CG(\Gamma))\geq t$. Next, we color the edges of
$CG(\Gamma)$ with $t$ colors as follows:

  1. (1)

the edge $e\bar{c}_{i}$ is colored with color $i$ for every
$i\in\\{1,2,\dots,t\\}$,

  2. (2)

the edge $e\hat{c}_{i}$ is colored with color 1 if $i$ is odd or color 2 if
$i$ is even for every $i\in\\{1,2,\dots,s\\}$,

  3. (3)

the other edges are colored with color 3.

The rainbow paths of $CG(\Gamma)$ under this edge coloring are as follows.

  1. (1)

For $i,j\in\\{1,2,\dots,t\\}$, where $i\neq j$, the rainbow path between
$\bar{c}_{i}$ and $\bar{c}_{j}$ is $\bar{c}_{i}e\bar{c}_{j}$.

  2. (2)

For every $j\in\\{1,2,\dots,s\\}$, the rainbow paths between $\bar{c}_{1}$ and
$\hat{c}_{j}$, and between $\bar{c}_{2}$ and $\hat{c}_{j}$, are the same as
the paths in the case of $t=2$ in Theorem 3.1.

  3. (3)

For every $i\in\\{3,\dots,t\\}$ and every $j\in\\{1,2,\dots,s\\}$, the rainbow
path between $\bar{c}_{i}$ and $\hat{c}_{j}$ is $\bar{c}_{i}e\hat{c}_{j}$.

  4. (4)

The rainbow paths between $\hat{c}_{i}$ and $\hat{c}_{j}$, where
$i,j\in\\{1,2,\dots,s\\}$, are the same as the paths between $\hat{c}_{i}$ and
$\hat{c}_{j}$ in the case of $t=0$ in Theorem 3.1.

Since every two distinct vertices of $CG(\Gamma)$ are connected by a rainbow
path under this edge coloring, we get $rc(CG(\Gamma))\leq t$. Since
$rc(CG(\Gamma))\geq t$, we get $rc(CG(\Gamma))=t$, where $t\geq 4$.

Now let $rc(CG(\Gamma))=t$, where $t\geq 4$. According to Theorem 3.1,
$\Gamma$ is a finite nonabelian group with a trivial center and has exactly
$s$ maximal abelian subgroups of order 2, where $s\geq 4$. Hence, $CG(\Gamma)$
has exactly $s$ pendant edges and $s\leq t$. According the previous result, we
can color the edges of $CG(\Gamma)$ by $s$ colors such that every two distinct
vertices of $CG(\Gamma)$ are connected by a rainbow path. Therefore,
$rc(CG(\Gamma))\leq s$. Since $rc(CG(\Gamma))=t$ and $s\leq t$, we get $s=t$.
∎

All results above show that the rainbow connection number of the commuting
graph of a finite nonabelian group with nontrivial center is related to the
number of maximal abelian subgroups of the group. Now recall that a maximal
abelian subgroup of order 2 of a finite nonabelian group $\Gamma$ consists of
the identity element of $\Gamma$ and an involution that do not commute with
any other nonidentity element of $\Gamma$. Hence, for a natural number $t$,
$\Gamma$ has exactly $t$ maximal abelian subgroups of order 2 if and only if
$\Gamma$ has exactly $t$ involutions that do not commute with any other
nonidentity element of the group. Thus, Theorem 3.6 gives us the following
corollary.

######  Corollary 3.7.

For a natural number $t\geq 4$, $rc(CG(\Gamma))=t$ if and only if $\Gamma$ is
a finite nonabelian group with a trivial center and has exactly $t$
involutions that do not commute with any other nonidentity element of
$\Gamma$.

According to Corollary 2, if $rc(CG(\Gamma))\geq 4$ for a finite group
$\Gamma$, then $\Gamma$ must be a group with a trivial center and has
$rc(CG(\Gamma))$ involutions that do not commute with any other nonidentity
element of $\Gamma$. If $\Gamma$ is a finite group with a trivial center and
$rc(CG(\Gamma))<4$, then we can be sure that $\Gamma$ has less than four
involutions that do not commute with any other nonidentity element of
$\Gamma$.

## References

  * [1] G. Aalipour, S. Akbari, P.J. Cameron, R. Nikandish, and F. Shaveisi, On the structure of the power graph and the enhanced power graph of a group, The Electronic J. Combin. 24 (2017), no. 3, P3.16.
  * [2] A. Abdollahi, S. Akbari, and H.R. Maimani, Non-commuting graph of a group, J. Algebra 298 (2006), no. 2, 468–492.
  * [3] M.R. Alfuraidan and Y.F. Zakariya, Inverse graphs associated with finite groups, Electron. J. Graph Theory Appl. 5 (2017), no. 1, 142–154.
  * [4] F.Ali and Y. Li, The connectivity and the spectral radius of commuting graphs on certain finite groups, Linear and Multilinear Algebra 69 (2021), no. 16, 2945-2958.
  * [5] S. Bau, P. Johnson, E. Jones, K. Kumwenda, and R. Matzke, Rainbow connectivity in some Cayley graphs, Australasian. J. Combin. 71 (2018), no. 3, 381–393.
  * [6] P. Cayley, Desiderata and suggestions: No. 2. The Theory of groups: graphical representation, American. J. Math. 1 (1878), no. 2, 174–176.
  * [7] I. Chakrabarty, S. Ghosh, and M.K. Sen, Undirected power graphs of semigroups, Semigroup Forum 78 (2009), 410–426.
  * [8] G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Mathematica Bohemica 133 (2008), no. 1, 85-98.
  * [9] R. Diestel, Graph theory, Springer-Verlag, New York, 2005.
  * [10] D.S. Dummit and R.M. Foote, Abstract algebra (3rd Edition), John Wiley & Sons, Inc., New Jersey, 2004.
  * [11] L.A. Dupont, D.G. Mendoza, and M. Rodríguez, The rainbow connection number of enhanced power graph, arXiv preprint (2017), https://doi.org/10.48550/arXiv.1708.07598.
  * [12] D. Fitriani and A.N.M. Salman, Rainbow connection number of amalgamation of some graphs, AKCE Int. J. Graphs Comb. 13 (2016), no. 1, 90-99.
  * [13] D. Fitriani, A.N.M. Salman, and Z.Y. Awanis, Rainbow connection number of comb product of graphs, Electron. J. Graph Theory Appl. 10 (2022), no. 2, 461-473.
  * [14] H. Li, X. Li, and S. Liu, The (strong) rainbow connection numbers of Cayley graphs on abelian groups, Computers and Math. with Appl. 62 (2011), no. 11, 4082-4088.
  * [15] Z. Lu and Y. Ma, Rainbow 2-connection numbers of Cayley graphs, Information Processing Letters 115 (2015), no. 4, 486-491.
  * [16] X. Ma, M. Feng, and K. Wang, The rainbow connection number of the power graph of a finite group, Graphs and Combinatorics 32 (2016), 1495-1504.
  * [17] Y. Ma and Z. Lu, Rainbow connection numbers of Cayley graphs, J. Combin. Optimization 34 (2017), no. 1, 182-193.
  * [18] R.F. Umbara, A.N.M. Salman, and P.E. Putri, On the inverse graph of a finite group and its rainbow connection number, Electron. J. Graph Theory Appl. 11 (2023), no. 1, 135–147.
  * [19] R.F. Umbara, A.N.M. Salman, and P.E. Putri, Rainbow connection numbers of the inverse graphs of some finite abelian groups, AIP Conference Proceedings, 2480 (2023), 030003.
  * [20] Y. Wei, X. Ma, and K. Wang, Rainbow connectivity of the non-commuting graph of a finite group, J. Algebra and Its Appl. 15 (2016), no. 7, 1650127.