Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776936 | Discrete Mathematics | 2017 | 7 Pages |
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
Diego González-Moreno, Mucuy-kak Guevara, Juan José Montellano-Ballesteros,