Graphs with (strong) proper connection numbers \(m - 3\) and \(m - 4\). (English) Zbl 1511.05118
Summary: In 2016, C. Lumduanhom et al. [Discuss. Math., Graph Theory 36, No. 2, 439–453 (2016; Zbl 1338.05088)] determined all graphs of size \(m\) with PC-number or SPC-number \(m - 1\), \(m - 2\), \(m - 3\). But we find that the graphs with SPC-number \(m - 3\) are not completely characterized. In this article, we characterize all graphs with SPC-number \(m - 3\). Moreover, we present all graphs satisfying PC-number or SPC-number \(m - 4\).
Citations:
Zbl 1338.05088References:
| [1] | Andrews, E.; Lumduanhom, C.; Laforge, E.; Zhang, P., On proper-path colorings in graphs, J. Combin. Math. Combin. Comput., 97, 189-207 (2016) · Zbl 1347.05055 |
| [2] | Basavaraju, M.; Chandran, L. S.; Rajendraprasad, D.; Ramaswamy, A., Rainbow connection number and radius, Graphs Combin., 30, 2, 275-285 (2014) · Zbl 1298.05103 |
| [3] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer Berlin · Zbl 1134.05001 |
| [4] | Borozan, V.; Fujita, S.; Gerek, A.; Magnant, C.; Manoussakis, Y.; Montero, L.; Tuza, Z., Proper connection of graphs, Discrete Math., 312, 17, 2550-2560 (2012) · Zbl 1246.05090 |
| [5] | Chartrand, G.; Johns, G. L.; McKeon, K. A.; Zhang, P., Rainbow connection in graphs, Math. Bohem., 133, 1, 85-98 (2008) · Zbl 1199.05106 |
| [6] | Fujita, S.; Magnant, C., Properly colored paths and cycles, Discrete Appl. Math., 159, 14, 1391-1397 (2011) · Zbl 1228.05150 |
| [7] | Guan, X.; Xue, L.; Cheng, E.; Yang, W., Minimum degree and size conditions for the proper connection number of graphs, Appl. Math. Comput., 352, 205-210 (2019) · Zbl 1428.05166 |
| [8] | Huang, F.; Li, X.; Wang, S., Proper connection numbers of complementary graphs, Bull. Malays. Math. Sci. Soc., 41, 3, 1199-1209 (2018) · Zbl 1393.05179 |
| [9] | Huang, X.; Li, X.; Shi, Y.; Yue, J.; Zhao, Y., Rainbow connections for outerplanar graphs with diameter 2 and 3, Appl. Math. Comput., 242, 277-280 (2014) · Zbl 1334.05038 |
| [10] | Krivelevich, M.; Yuster, R., The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory, 63, 3, 185-191 (2010) · Zbl 1193.05079 |
| [11] | Lei, H.; Li, S.; Liu, H.; Shi, Y., Rainbow vertex connection of digraphs, J. Comb. Optim., 35, 1, 86-107 (2018) · Zbl 1386.05077 |
| [12] | X. Li, C. Magnant, Properly colored notions of connectivity—A dynamic survey, Theory Appl. Graphs 0 (1) (2015), Article 2. |
| [13] | Li, X.; Shi, Y., Rainbow connection in 3-connected graphs, Graphs Combin., 29, 5, 1471-1475 (2013) · Zbl 1272.05053 |
| [14] | Li, X.; Shi, Y., On the rainbow vertex-connection, Discuss. Math. Graph Theory, 33, 2, 307-313 (2013) · Zbl 1293.05116 |
| [15] | Li, X.; Shi, Y.; Sun, Y., Rainbow connections of graphs: a survey, Graphs Combin., 29, 1, 1-38 (2013) · Zbl 1258.05058 |
| [16] | Li, X.; Sun, Y., Rainbow Connections of Graphs, SpringerBriefs in Math. (2012), Springer: Springer New York · Zbl 1250.05066 |
| [17] | Li, X.; Wei, M.; Yue, J., Proper connection number and connected dominating sets, Theor. Comput. Sci., 607, 3, 480-487 (2015) · Zbl 1333.05227 |
| [18] | Liu, H.; Mestre, A.; Sousa, T., Total rainbow \(k\)-connection in graphs, Discrete Appl. Math., 174, 92-101 (2014) · Zbl 1298.05127 |
| [19] | Lumduanhom, C.; Laforge, E.; Zhang, P., Characterization of graphs having large proper connection number, Discuss. Math. Graph Theory, 36, 2, 439-453 (2016) · Zbl 1338.05088 |
| [20] | Ma, Y.; Lu, Z., Rainbow connection numbers of Cayley graphs, J. Combin. Optim., 34, 1, 182-193 (2017) · Zbl 1378.05068 |
| [21] | Ma, Y.; Nie, K.; Jin, F.; Wang, C., Total rainbow connection numbers of some special graphs, Appl. Math. Comput., 360, 213-220 (2019) · Zbl 1428.05113 |
| [22] | Magnant, C.; Morley, P. R.; Porter, S.; Nowbandegani, P. S.; Wang, H., Directed proper connection of graphs, Mat. Vesnik, 68, 1, 58-65 (2016) · Zbl 1462.05159 |
| [23] | Schiermeyer, I., Rainbow connection and minimum degree, Discrete Appl. Math., 161, 12, 1784-1787 (2013) · Zbl 1287.05047 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
