On very strongly perfect Cartesian product graphs

Ganesh Gandal; R Mary Jeya Jothi; Narayan Phadatare; Ganesh Gandal; R Mary Jeya Jothi; Narayan Phadatare

doi:10.3934/math.2022148

AIMS Mathematics

2022, Volume 7, Issue 2: 2634-2645. doi: 10.3934/math.2022148

Previous Article Next Article

Research article

On very strongly perfect Cartesian product graphs

1.
Department of Mathematics, Sathyabama Institute of Science and Technology, Chennai-600119, India
2.
Department of Mathematics, Savitribai Phule Pune University, Pune-411007, India

Received: 29 April 2021 Accepted: 05 November 2021 Published: 18 November 2021
MSC : 05C69, 05C38, 05C40

Let $ G_1 \square G_2 $ be the Cartesian product of simple, connected and finite graphs $ G_1 $ and $ G_2 $. We give necessary and sufficient conditions for the Cartesian product of graphs to be very strongly perfect. Further, we introduce and characterize the co-strongly perfect graph. The very strongly perfect graph is implemented in the real-time application of a wireless sensor network to optimize the set of master nodes to communicate and control nodes placed in the field.
- odd cycle,
- bipartite graph,
- strong independent set,
- very strongly perfect graph
Citation: Ganesh Gandal, R Mary Jeya Jothi, Narayan Phadatare. On very strongly perfect Cartesian product graphs[J]. AIMS Mathematics, 2022, 7(2): 2634-2645. doi: 10.3934/math.2022148

Related Papers:

Abstract

Let $ G_1 \square G_2 $ be the Cartesian product of simple, connected and finite graphs $ G_1 $ and $ G_2 $. We give necessary and sufficient conditions for the Cartesian product of graphs to be very strongly perfect. Further, we introduce and characterize the co-strongly perfect graph. The very strongly perfect graph is implemented in the real-time application of a wireless sensor network to optimize the set of master nodes to communicate and control nodes placed in the field.

References

[1]	A. Tucker, Coloring perfect $(K_{4}-e)$-free graphs, J. Combin. Theory, Ser. B, 42 (1987), 313–318. doi: 10.1016/0095-8956(87)90048-7. doi: 10.1016/0095-8956(87)90048-7
[2]	C. T. Hoàng, On a conjecture of Meyniel, J. Combin. Theory, Ser. B, 42 (1987), 302–312. doi: 10.1016/0095-8956(87)90047-5. doi: 10.1016/0095-8956(87)90047-5
[3]	C. Berge, P. Duchet, In: Strongly perfect graphs, North-Holland mathematics studies, North-Holland, 21 (1984), 57–61.
[4]	C. Berge, Farbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin Luther Univ., Halle-Wittenberg Math.-Natur. Rethe, 1961,114–115.
[5]	D. B. West, Introduction to graph theory, 2 Eds., Prentice-Hall of India, New Delhi, 2002.
[6]	E. Mandrescu, Strongly perfect product of graphs, Czechoslovak Math. J., 41 (1991), 368–372.
[7]	F. Harary, Graph theory, 3 Eds., Narosa, New Delhi, 1988.
[8]	G. Ravindra, K. R. Parthasarathy, Perfect product graphs, Discrete Math., 20 (1977), 177–186. doi: 10.1016/0012-365X(77)90056-5. doi: 10.1016/0012-365X(77)90056-5
[9]	G. Ravindra, Meyniel graphs are strongly perfect, J. Combin. Theory, Ser. B, 33 (1982), 187–190. doi: 10.1016/0095-8956(82)90068-5. doi: 10.1016/0095-8956(82)90068-5
[10]	G. R. Gandal, R. M. Jothi, The products of very strongly perfect graphs and its applications in machine learning, In: V. H. Patil, N. Dey, P. N. Mahalle, M. Shafi Pathan, V. V. Kimbahune, Proceeding of first doctoral symposium on natural computing research, Lecture Notes in Networks and Systems, 169 (2021), 133–144. doi: 10.1007/978-981-33-4073-2_14.
[11]	H. Meyniel, The graphs whose odd cycles have at least two chords, Ann. Discrete Math., 21 (1984), 115–119.
[12]	K. R. Parthasarathy, G. Ravindra, The validity of the strong – perfect graph conjecture for $(K_{4} - e)$-free graphs, J. Combin. Theory, Ser. B, 26 (1979), 98–100. doi: 10.1016/0095-8956(79)90047-9. doi: 10.1016/0095-8956(79)90047-9
[13]	M. Kwa÷nik, A. Szelecka, Strong perfectness of the generalized Cartesian product of graphs, Discrete Math., 164 (1997), 213–220. doi: 10.1016/S0012-365X(96)00053-2. doi: 10.1016/S0012-365X(96)00053-2
[14]	M. Chudnovsky, M. Pilipczuk, M. Pilipczuk, S. Thomasse, On the maximum weight independent set problem in graphs without induced cycles of length at least five, SIAM J. Discrete Math., 34 (2020), 1472–1483. doi: 10.1137/19M1249473. doi: 10.1137/19M1249473
[15]	M. Carlos-Mancilla, E. López-Mellado, M. Siller, Wireless sensor networks formation: Approaches and techniques, J. Sensors, 2016 (2016), 2081902. doi: 10.1155/2016/2081902. doi: 10.1155/2016/2081902
[16]	S. Hougardy, Classes of perfect graphs, Discrete Math., 306 (2006), 2529–2571. doi: 10.1016/j.disc.2006.05.021. doi: 10.1016/j.disc.2006.05.021
[17]	S. M. Ayat, S. M. Ayat, M. Ghahramani, The independence number of circulant triangle-free graphs, AIMS Math., 5 (2020), 3741–3750. doi: 10.3934/math.2020242. doi: 10.3934/math.2020242
[18]	V. Chvátal, Perfectly ordered graphs, North-Holland Math. Stud., 88 (1984), 63–65. doi: 10.1016/S0304-0208(08)72923-2. doi: 10.1016/S0304-0208(08)72923-2

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)