On the General Position Number of Complementary Prisms

• Autorzy: Neethu P. K. , Chandran S. V. Ullas , Changat Manoj , Klavžar Sandi

Identyfikatory

DOI

10.3233/FI-2021-2006

• Języki publikacji: EN

Abstrakty

EN

The general position number gp(G ) of a graph G is the cardinality of a largest set of vertices S such that no element of S lies on a geodesic between two other elements of S. The complementary prism G G ¯ of G is the graph formed from the disjoint union of G and its complement G ¯ by adding the edges of a perfect matching between them. It is proved that gp(G G ¯ ) ≤ n (G ) + 1 if G is connected and gp(G G ¯ ) ≤ n (G ) if G is disconnected. Graphs G for which gp(G G ¯ ) = n (G ) + 1 holds, provided that both G and G ¯ are connected, are characterized. A sharp lower bound on gp(G G ¯ ) is proved. If G is a connected bipartite graph or a split graph then gp(G G ¯ ) ∈ {n (G ), n (G )+1}. Connected bipartite graphs and block graphs for which gp(G G ¯ ) = n (G ) + 1 holds are characterized. A family of block graphs is constructed in which the gp-number of their complementary prisms is arbitrary smaller than their order.

Słowa kluczowe

EN

general position set; complementary prism; bipartite graph; split graph; block graph

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 178, nr 3
• Strony: 267--281
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Neethu P. K.

• Department of Mathematics, Mahatma Gandhi College, University of Kerala, Thiruvananthapuram-695004, Kerala, India

autor

Chandran S. V. Ullas

• Department of Mathematics, Mahatma Gandhi College, University of Kerala, Thiruvananthapuram-695004, Kerala, India

autor

Changat Manoj

• Department of Futures Studies, University of Kerala, Thiruvananthapuram-695581, Kerala, India

autor

Klavžar Sandi

• Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

Bibliografia

• [1] Manuel P, Klavžar S. A general position problem in graph theory. Bull. Aust. Math. Soc., 2018. 98(2):177-187. doi:10.1017/S0004972718000473. URL https://doi.org/10.1017/S0004972718000473.
• [2] Dudeney HE. Amusements in Mathematics. Dover Publications, Inc., New York, 1959.
• [3] Froese V, Kanj I, Nichterlein A, Niedermeier R. Finding points in general position. Internat. J. Comput. Geom. Appl., 2017. 27(4):277-296. doi:10.1142/S021819591750008X. URL https://doi.org/10.1142/S021819591750008X.
• [4] Ku CY, Wong KB. On no-three-in-line problem on m-dimensional torus. Graphs Combin., 2018. 34(2):355-364. doi:10.1007/s00373-018-1878-8. URL https://doi.org/10.1007/s00373-018-1878-8.
• [5] Misiak A, Stępień Z, Szymaszkiewicz A, Szymaszkiewicz L, Zwierzchowski M. A note on the no-three-in-line problem on a torus. Discrete Math., 2016. 339(1):217-221. doi:10.1016/j.disc.2015.08.006. URL https://doi.org/10.1016/j.disc.2015.08.006.
• [6] Payne MS, Wood DR. On the general position subset selection problem. SIAM J. Discrete Math., 2013. 27(4):1727-1733. doi:10.1137/120897493. URL https://doi.org/10.1137/120897493.
• [7] Skotnica M. No-three-in-line problem on a torus: periodicity. Discrete Math., 2019. 342(12):111611, 13. doi:10.1016/j.disc.2019.111611. URL https://doi.org/10.1016/j.disc.2019.111611.
• [8] Chandran S V U, Jaya Parthasarathy G. The geodesic irredundant sets in graphs. Int. J. Math. Combin., 2016. 4:135-143.
• [9] Manuel P, Klavžar S. The graph theory general position problem on some interconnection networks. Fund. Inform., 2018. 163(4):339-350. doi:10.3233/fi-2018-1748. URL https://doi.org/10.3233/fi-2018-1748.
• [10] Anand BS, Chandran S V U, Changat M, Klavžar S, Thomas EJ. Characterization of general position sets and its applications to cographs and bipartite graphs. Appl. Math. Comput., 2019. 359:84-89. doi:10.1016/j.amc.2019.04.064. URL https://doi.org/10.1016/j.amc.2019.04.064.
• [11] Ghorbani M, Klavžar S, Maimani HR, Momeni M, Rahimi-Mahid F, Rus G. The general position problem on Kneser graphs and on some graph operations. Discuss. Math. Graph Theory, 2019. doi:10.7151/dmgt.2269.
• [12] Klavžar S, Rus G. The general position number of integer lattices. Appl. Math. Comput., 2021. 390:125664. doi:10.1016/j.amc.2020.125664. URL https://doi.org/10.1016/j.amc.2020.125664.
• [13] Klavžar S, Patkós B, Rus G, Yero IG. On general position sets in Cartesian products. arXiv [math.CO], 2019. URL arXiv:1907.04535v3.
• [14] Klavžar S, Yero IG. The general position problem and strong resolving graphs. Open Math., 2019. 17(1):1126-1135. doi:10.1515/math-2019-0088. URL https://doi.org/10.1515/math-2019-0088.
• [15] Patkós B. On the general position problem on Kneser graphs. Ars Math. Contemp., 2020. 18(2):273-280. doi:10.26493/1855-3974.1957.a0f. URL https://doi.org/10.26493/1855-3974.1957.a0f.
• [16] Haynes TW, Henning MA, Slater PJ, van der Merwe LC. The complementary product of two graphs. Bull. Inst. Combin. Appl., 2007. 51:21-30.
• [17] Zatesko LM, Carmo R, Guedes ALP, Zorzi A, Machado RCS, Figueiredo CMH. On the chromatic index of complementary prisms. Acta Math. Univ. Comenian. (N.S.), 2019. 88(3):1071-1077.
• [18] Haynes TW, Henning MA, van der Merwe LC. Domination and total domination in complementary prisms. J. Comb. Optim., 2009. 18(1):23-37. doi:10.1007/s10878-007-9135-8. URL https://doi.org/10.1007/s10878-007-9135-8.
• [19] Meierling D, Protti F, Rautenbach D, de Almeida AR. Cycles in complementary prisms. Discrete Appl. Math., 2015. 193:180-186. doi:10.1016/j.dam.2015.04.016. URL https://doi.org/10.1016/j.dam.2015.04.016.
• [20] Duarte MA, Penso L, Rautenbach D, Souza UdS. Complexity properties of complementary prisms. J. Comb. Optim., 2017. 33(2):365-372. doi:10.1007/s10878-015-9968-5. URL https://doi.org/10.1007/s10878-015-9968-5.
• [21] Cardoso DM, Carvalho P, de Freitas MAA, Vinagre CTM. Spectra, signless Laplacian and Laplacian spectra of complementary prisms of graphs. Linear Algebra Appl., 2018. 544:325-338. doi:10.1016/j.laa.2018.01.020. URL https://doi.org/10.1016/j.laa.2018.01.020.
• [22] Castonguay D, Coelho EMM, Coelho H, Nascimento JR. A note on the convexity number of complementary prisms. Discrete Math. Theor. Comput. Sci., 2019. 21(4):Paper No. 4, 10.
• [23] Bendali-Braham A, Ikhlef-Eschouf N, Blidia M. Some results on the b-chromatic number in complementary prism graphs. RAIRO Oper. Res., 2019. 53(4):1187-1195. doi:10.1051/ro/2018054. URL https://doi.org/10.1051/ro/2018054.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).