Monochromatic k-connection of graphs

Abstract

An edge-coloured path is monochromatic if all of its edges have the same colour. For a k-connected graph G, the monochromatic k-connection number of G, denoted by mck(G), is the maximum number of colours in an edge-colouring of G such that, any two vertices are connected by k internally vertex-disjoint monochromatic paths. In this paper, we shall study the parameter mck(G). We obtain bounds for mck(G), for general graphs G. We also compute mck(G) exactly when k is small, and G is a graph on n vertices, with a spanning k-connected subgraph having the minimum possible number of edges, namely [Formula presented]. We prove a similar result when G is a bipartite graph.