The size of graphs with restricted rainbow $2$-connection number

Author name not available (Why is that?)

Publication date: 23 June 2021

Abstract: Let

k

be a positive integer, and

G

be a

k

-connected graph. An edge-coloured path is emph{rainbow} if all of its edges have distinct colours. The emph{rainbow

k

-connection number} of

G

, denoted by

r c_{k} (G)

, is the minimum number of colours in an edge-colouring of

G

such that, any two vertices are connected by

k

internally vertex-disjoint rainbow paths. The function

r c_{k} (G)

was introduced by Chartrand, Johns, McKeon and Zhang in 2009, and has since attracted significant interest. Let

t_{k} (n, r)

denote the minimum number of edges in a

k

-connected graph

G

on

n

vertices with

r c_{k} (G) l e r

. Let

s_{k} (n, r)

denote the maximum number of edges in a

k

-connected graph

G

on

n

vertices with

r c_{k} (G) g e r

. The functions

t_{1} (n, r)

and

s_{1} (n, r)

have previously been studied by various authors. In this paper, we study the functions

t_{2} (n, r)

and

s_{2} (n, r)

. We determine bounds for

t_{2} (n, r)

which imply that

t_{2} (n, 2) = (1 + o (1)) n l o g_{2} n

, and

t_{2} (n, r)

is linear in

n

for

r g e 3

. We also provide some remarks about the function

s_{2} (n, r)

.