Rainbow Connection Number of Graphs with Diameter 3

• Autorzy: Hengzhe Li , Xueliang Li , Yuefang Sun
• Języki publikacji: EN

Abstrakty

EN

A path in an edge-colored graph G is rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer k for which there exists a k-edge-coloring of G such that every pair of distinct vertices of G is connected by a rainbow path. Let f(d) denote the minimum number such that rc(G) ≤ f(d) for each bridgeless graph G with diameter d. In this paper, we shall show that 7 ≤ f(3) ≤ 9.

Słowa kluczowe

EN

edge-coloring; rainbow path; rainbow connection number; diameter

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C40: Connectivity

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 1
• Strony: 141-154

Daty

wydano

2017-02-01

otrzymano

2015-10-22

poprawiono

2016-03-04

zaakceptowano

2016-03-04

online

2017-01-13

Twórcy

autor

Hengzhe Li

• Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071,

autor

Xueliang Li

• Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071,

autor

Yuefang Sun

• Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071,

Identyfikatory

DOI

10.7151/dmgt.1920