(1, 2)-rainbow connection number at most 3 in connected dense graphs

Trung Duy Doan, Le Thi Duyen

Abstract


Let G be an edge-coloured connected graph G. A path P in the graph G is called l-rainbow path if each subpath of length at most l + 1 is rainbow. The graph G is called (k, l)-rainbow connected if any two vertices in G are connected by at least k pairwise internally vertex-disjoint l-rainbow paths. The smallest number of colours needed in order to make G (k, l)-rainbow connected is called the (k, l)-rainbow connection number of G and denoted by rck, l(G). In this paper, we consider the (1, 2)-rainbow connection number at most 3 in some connected dense graphs. Our main results are as follows: (1) Let n ≥ 7 be an integer and G be a connected graph of order n. If ω(G)≥n − 3, then rc1, 2(G)≤3. Moreover, the bound of the clique number is sharpness. (2) Let n ≥ 7 be an integer and G be a connected graph of order n. If |E(G)| ≥ C(n − 3, 2)+7, then rc1, 2(G)≤3.

Keywords


edge-colouring, rainbow connection, (1, 2)-rainbow connection.

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2023.11.2.6

References

E. Andrews, E. Laforge, C. Lumduanhom, and P. Zhang, On proper-path colorings in graphs, J. Combin. Math. Combin. Comput. 97 (2016) 189–207.

V. Borozan, S. Fujita, A. Gerek, C. Magnant, Y. Manoussakis, L. Montero, and Zs. Tuza, Proper connection of graphs, Discrete Math. 312 (2012) 2550–2560.

C. Brause, T.D. Doan, and I. Schiermeyer, On the minimum degree and the proper connection number of graphs, Electron. Notes Discrete Math. 55 (2016) 109–112.

C. Brause, T.D. Doan, and I. Schiermeyer, Proper connection number 2, connectivity, and forbidden subgraphs, Electron. Notes Discrete Math. 55 (2016) 105–108.

G. Chartrand, G.L. Johns, K.A. McKeon, and P. Zhang, Rainbow connection in graphs, Math. Bohemica 133 (1) (2008) 85–98.

G. Chartrand, S. Devereaux, and P. Zhang, Color-connected graphs and information transfer paths, Ars Combin. to appear

S. Chakraborty, E. Fischer, A. Matsliah, and R. Yuster, Hardness and algorithms for rainbow connection, J. Comb. Optim. 21 (2011)330-347

S. Devereaux, G.L. Johns, and P. Zhang, Color connection in graphs intermediate to proper and rainbow connection, J. Combin. Math. Combin. Comput. to appear

S. Devereaux and P. Zhang, k-rainbow colorings in graphs, manuscript

D. Fitriani, A.N.M. Salman, and Z.Y. Awanis, Rainbow connection number of comb product of graphs, Electron. J. Graph Theory Appl. 10 (2) (2022) 461–473.

F. Huang and X. Li, Hardness results for three kinds of colored connections of graphs, Theoretical Computer Science, https://doi.org/10.1016/j.tcs.2020.06.030

X. Li and C. Magnant, Properly colored notions of connectivity–a dynamic survey, Theory & Appl. Graphs 0(1) (2015), Art. 2.

X. Li, C. Magnant, M. Wei, and X. Zhu, Generalized rainbow connection of graphs and their complements, Discuss. Math. Graph Theory 38 (2018) 371–384.

X. Li, Y. Shi, and Y. Sun, Rainbow connections of graphs: A survey, Graphs & Combin. 29 (2013) 1–38.

X. Li and Y. Sun, Rainbow Connections of Graphs, Springer Briefs in Math., Springer, New York (2012).

F. Septyanto and K. A. Sugeng, Color code techniques in rainbow connection, Electron. J. Graph Theory Appl. 6 (2) (2018) 347–361

B.H. Susanti, A.N.M. Salman, and R. Simanjuntak, The rainbow 2-connectivity of Cartesian products of 2-connected graphs and paths, Electron. J. Graph Theory Appl. 8 (1) (2020), 145–-156.

D.B. West, Introduction to Graph Theory, Prentice Hall, 2001.

D.R. Woodall, Maximal circuits of graphs I, Acta Math. Acad. Sci. Hungar. 28 (1976) 77–80.

X. Zhu, M. Wei, and C. Magnant, Generalized Rainbow Connection of Graphs, Bull. Malays. Math. Sci. Soc. 44 (2021) 3991–-4002. https://doi.org/10.1007/s40840-021-01119-6.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats