In this paper, we determine the cardinality of an optimal independent set in the neighborhood system of a balanced biclique in a graph. We introduce a bivariate polynomial which represents the number of balanced bicliques corresponding to the cardinalities of maximum independent sets. Finally, we establish the explicit forms of the balanced biclique independent neighborhood polynomials of some special graphs.

independent set, independent neighborhood system, graph polynomial.

Received: November 12, 2023; Revised: November 29, 2023; Accepted: December 20, 2023; Published: January 12, 2024

How to cite this article: Rosalio G. Artes Jr., Regimar A. Rasid, Sherna A. Rasid, Bayah J. Amiruddin-Rajik and Al-Jayson U. Abubakar, Independent sets in the neighborhood systems of balanced bicliques: optimization and polynomial representations, Advances and Applications in Discrete Mathematics 41(1) (2024), 97-104. http://dx.doi.org/10.17654/0974165824006

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] R. A. Anunciado and R. G. Artes Jr., Connected dominating independent neighborhood polynomial of graphs, Advances and Applications in Discrete Mathematics 39(1) (2023), 73-80. https://doi.org/10.17654/0974165823036.
[2] A. L. Arriesgado and R. G. Artes Jr., Convex independent common neighborhood polynomial of a graph, Advances and Applications in Discrete Mathematics 38(2) (2023), 145-158. https://doi.org/10.17654/0974165823025.
[3] A. L. Arriesgado, S. C. Abdurasid and R. G. Artes Jr., Connected common neighborhood systems of cliques in a graph: a polynomial representation, Advances and Applications in Discrete Mathematics 38(1) (2023), 69-81.
https://doi.org/10.17654/0974165823019.
[4] A. L. Arriesgado, J. I. C. Salim and R. G. Artes Jr., Clique connected common neighborhood polynomial of the join of graphs, Int. J. Math. Comput. Sci. 18(4) (2023), 655-659.
[5] A. L. Arriesgado, J. I. C. Salim and R. G. Artes Jr., Polynomial representation of the neighborhood systems of cliques in the corona of graphs, Advances and Applications in Discrete Mathematics 40(1) (2023), 11-18.
https://doi.org/10.17654/0974165823054.
[6] R. G. Artes Jr., A. J. U. Abubakar and S. U. Kamdon, Polynomial representations of the biclique neighborhood of graphs, Advances and Applications in Discrete Mathematics 37 (2023), 37-45. http://dx.doi.org/10.17654/0974165823010.
[7] R. G. Artes Jr., R. H. Moh. Jiripa and J. I. C. Salim, Connected total dominating neighborhood polynomial of graphs, Advances and Applications in Discrete Mathematics 39(2) (2023), 145-154. http://dx.doi.org/10.17654/0974165823042.
[8] R. G. Artes Jr. and J. B. Nalzaro, Combinatorial approach for counting geodetic sets with subdominating neighborhood systems, Advances and Applications in Discrete Mathematics 38(2) (2023), 179-189.
https://doi.org/10.17654/0974165823027.
[9] R. G. Artes Jr. and R. A. Rasid, Balanced biclique polynomial of graphs, Glob. J. Pure Appl. Math. 12(5) (2016), 4427-4433.
[10] R. G. Artes Jr. and R. A. Rasid, Combinatorial approach in counting the balanced bicliques in the join and corona of graphs, Journal of Ultra Scientist of Physical Sciences 29(5) (2017), 192-195.
[11] A. M. Asdain, B. J. Amiruddin, R. A. Rasid, J. I. C. Salim and R. G. Artes Jr., Polynomial representations of a balanced biclique common neighborhood system of graphs, Advances and Applications in Discrete Mathematics 40(2) (2023), 187-194. https://doi.org/10.17654/0974165823065.
[12] A. R. Bakkang, R. A. Rasid and R. G. Artes Jr., Combinatorial approach in counting the neighbors of cliques in a graph, Advances and Applications in Discrete Mathematics 40(2) (2023), 167-175.
https://doi.org/10.17654/0974165823063.
[13] J. Ellis-Monaghan and J. Merino, Graph Polynomials and Their Applications II: Interrelations and Interpretations, Birkhauser, Boston, 2011.
[14] F. Harary, Graph Theory, CRC Press, Boca Raton, 2018.
[15] R. G. Artes Jr., M. A. Langamin and A. B. Calib-og, Clique common neighborhood polynomial of graphs, Advances and Applications in Discrete Mathematics 35 (2022), 77-85. https://doi.org/10.17654/0974165822053.