Monochromatic k-connection of graphs - Cai, Qingqiong; Fujita, Shinya; Liu, Henry; Park, Boram (Discrete Applied Mathematics, 2025)
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.
Keywords: Connection number; Edge-colouring; General graph; Graph G; K-connected; K-connected graphs; Monochromatic (k-)connection number; Monochromatic path; Monochromatics; Vertex disjoint; Edge-colouring; k-connected graph; Monochromatic (k-)connection number