Monochromatic connecting colorings in strongly connected oriented graphs

被引：8

作者：

Gonzalez-Moreno, Diego ^{[1
]}

Guevara, Mucuy-Kak ^{[2
]}

Jose Montellano-Ballesteros, Juan ^{[3
]}

机构：

[1] Univ Autonoma Metropolitana Cuajimalpa, Dept Matemat Aplicadas & Sistemas, Ciudad De Mexico, Cdmx, Mexico

[2] Univ Nacl Autonoma Mexico, Fac Ciencias, Mexico City 04510, DF, Mexico

[3] Univ Nacl Autonoma Mexico, Inst Matemat, Mexico City 04510, DF, Mexico

来源：

DISCRETE MATHEMATICS | 2017年 / 340卷 / 04期

关键词：

Monochromatic; Strong connectivity; Coloring; Oriented graph; RAINBOW CONNECTION;

D O I：

10.1016/j.disc.2016.11.016

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 Omega(D)+ 1, where Omega(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. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：578 / 584

页数：7

共 7 条

[1] Alva-Samos J., 2016, GRAPHS COMB IN PRESS, P1
[2] Bang-Jensen J, 2000, Digraphs: Theory, Algorithms and Applications
[3] Berge C., 1989, GRAPHS
[4] Colorful monochromatic connectivity
Caro, Yair
Yuster, Raphael
[J]. DISCRETE MATHEMATICS, 2011, 311 (16) : 1786 - 1792
[5] Chartrand G, 2008, MATH BOHEM, V133, P85
[6] Rainbow connection in oriented graphs
Dorbec, Paul
Schiermeyer, Ingo
Sidorowicz, Elzbieta
Sopena, Eric
[J]. DISCRETE APPLIED MATHEMATICS, 2014, 179 : 69 - 78
[7] Li X., 2013, RAINBOW CONNECTIONS

← 1 →