Article ID Journal Published Year Pages File Type
5776936 Discrete Mathematics 2017 7 Pages PDF
Abstract
An arc-coloring of a strongly connected digraph D is a strongly monochromatic-connecting coloring if for every pair u,v of vertices in D there exist an (u,v)-monochromatic path and a (v,u)-monochromatic path. Let smc(D) denote the maximum number of colors that can be used in a strongly monochromatic-connecting coloring of D. In this paper we prove that if D is a strongly connected oriented graph of size m, then smc(D)=m−Ω(D)+1, where Ω(D) is the minimum size of a spanning strongly connected subdigraph of D. As a corollary of this result, we see that a strongly connected oriented graph D of order n is hamiltonian if and only if smc(D)=m−n+1.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,