The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths

被引：3

作者：

Susanti, Bety Hayat ^{[1
,2
]}

Salman, A. N. M. ^{[1
]}

Simanjuntak, Rinovia ^{[1
]}

机构：

[1] Inst Teknol Bandung, Fac Math & Nat Sci, Combinatorial Math Res Grp, Jalan Ganesa 10, Bandung, Indonesia

[2] Sekolah Tinggi Sandi Negara, Bogor, Indonesia

来源：

ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS | 2020年 / 8卷 / 01期

关键词：

Cartesian product; 2-connected graph; rainbow; 2-connectivity; rainbow path; CONNECTION NUMBER; POWER;

D O I：

10.5614/ejgta.2020.8.1.11

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An edge-colored graph G is rainbow k-connected, if there are k-internally disjoint rainbow paths connecting every pair of vertices of G. The rainbow k-connection number of G, denoted by rc(k)(G), is the minimum number of colors needed for which there exists a rainbow k-connected coloring for G. In this paper, we are able to find sharp lower and upper bounds for the rainbow 2-connection number of Cartesian products of arbitrary 2-connected graphs and paths. We also determine the rainbow 2-connection number of the Cartesian products of some graphs, i.e. complete graphs, fans, wheels, and cycles, with paths.

引用

页码：145 / 156

页数：12

共 27 条

[1] Rainbow Connection Number of Graph Power and Graph Products [J].

Basavaraju, Manu ;

Chandran, L. Sunil ;

Rajendraprasad, Deepak ;

Ramaswamy, Arunselvan .

GRAPHS AND COMBINATORICS, 2014, 30 (06) :1363-1382

[2] Hardness and algorithms for rainbow connection [J].

Chakraborty, Sourav ;

Fischer, Eldar ;

Matsliah, Arie ;

Yuster, Raphael .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2011, 21 (03) :330-347

[3]

Chartrand G., 2012, A First Course in Graph Theory

[4]

Chartrand G, 2008, MATH BOHEM, V133, P85

[5] The Rainbow Connectivity of a Graph [J].

Chartrand, Gary ;

Johns, Garry L. ;

McKeon, Kathleen A. ;

Zhang, Ping .

NETWORKS, 2009, 54 (02) :75-81

[6]

Deniawanty R, 2015, PROCEDIA COMPUTER SC, V74, P143, DOI [10.1016/j.procs.2015.12.090, DOI 10.1016/J.PROCS.2015.12.090]

[7]

Diestel R., 2017, Graph Theory, DOI [DOI 10.1007/978-3-662-53622-3, DOI 10.1007/978-3-662-70107-2]

[8] Rainbow connection number of amalgamation of some graphs [J].

Fitriani, D. ;

Salman, A. N. M. .

AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2016, 13 (01) :90-99

[9]

Fujita S., 2011, ELECT NOTES DISCRETE, V38, P361, DOI DOI 10.1016/j.endm.2011.09.059

[10] Rainbow Connection and Graph Products [J].

Gologranc, Tanja ;

Mekis, Gasper ;

Peterin, Iztok .

GRAPHS AND COMBINATORICS, 2014, 30 (03) :591-607

← 1 2 3 →