Total rainbow k-connection in graphs

Research output: Contribution to journalArticle

23 Citations (Scopus)

Abstract

Let k be a positive integer and G be a k-connected graph. In 2009, Chartrand, Johns, McKeon, and Zhang introduced the rainbow k-connection number rck(G) of G. An edge-coloured path is rainbow if its edges have distinct colours. Then, rck(G) is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by k internally vertex-disjoint rainbow paths. The function rck(G) has since been studied by numerous researchers. An analogue of the function rck(G) involving vertex colourings, the rainbow vertex k-connection number rvck(G), was subsequently introduced. In this paper, we introduce a version which involves total colourings. A total-coloured path is total-rainbow if its edges and internal vertices have distinct colours. The total rainbow k-connection number of G, denoted by trck(G), is the minimum number of colours required to colour the edges and vertices of G, so that any two vertices of G are connected by k internally vertex-disjoint total-rainbow paths. We study the function trck(G) when G is a cycle, a wheel, and a complete multipartite graph. We also compare the functions rck(G), rvck(G), and trck(G), by considering how close and how far apart trck(G) can be from rck(G) and rvck(G).
Original languageUnknown
Pages (from-to)92-101
JournalDiscrete Applied Mathematics
Volume174
Issue numberNA
DOIs
Publication statusPublished - 1 Jan 2014

Cite this