An induced subgraph H of a graph G is a balanced biclique of G if  for some . The balanced biclique polynomial of G is given  by  where   is the number of balanced bicliques of G of order 2i and is the cardinality of a maximum balanced biclique of G. The balanced biclique neighborhood polynomial of G which counts the balanced bicliques of G with corresponding neighborhood system cardinality is given by  where  is the number of balanced bicliques of G of order 2i with neighborhood cardinality equal to j and  is the cardinality of a maximum balanced biclique of G. In this paper, we establish the balanced biclique neighborhood polynomial of some special graphs such as cycle, complete graph, complete bipartite graph, and complete q‑partite graph.

balanced biclique, balanced biclique polynomial, balanced biclique neighborhood polynomial.

Received: November 2, 2022;  Accepted: January 2, 2023; Published: January 25, 2023

How to cite this article: Rosalio G. Artes, Jr., Al-Jayson U. Abubakar and Sisteta 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

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

References:

[1] S. Akbari and M. R. Oboudi, On the Edge Cover Polynomial of Graphs, European J. Combin. 34(2) (2013), 297-321.
[2] A. Ali and W. A. M. Said, Wiener polynomials for Steiner distance of graphs, Jordan Journal of Applied Sciences 8(2) (2006), 64-71.
[3] S. Alikhani and T. Hamzeh, On the domination polynomials of complete partite graphs, World Applied Sciences Journal 9(1) (2010), 23-24.
[4] 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.
[5] R. G. Artes, Jr. and R. A. Rasid, Balanced biclique polynomial of graphs, Glob. J. Pure Appl. Math. 12(5) (2016), 4427-4433.
[6] 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.
[7] Klaus Dohmen, Andre Ponitz and Peter Tittmann, A new two-variable generalization of the chromatic polynomial, Discrete Mathematics and Theoretical Computer Science 6 (2003), 69-90.
[8] J. A. Ellis-Monaghan and C. Merino, Graph polynomials and their applications II: interrelations and interpretations, M. Dehmer, ed., Structural Analysis of Complex Networks, Birkhauser Boston, 2011.
[9] E. J. Farell, A note on the clique polynomial and its relation to other graph polynomials, J. Math. Sci. Calcutta 8 (1997), 97-102.
[10] I. Gutman, Graphs and graph polynomials of interest in chemistry, applications in chemistry, Lecture Notes in Computer Science Series (LNCS), Volume 246, 2005.
[11] C. Hoede and X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994), 219-228.
[12] B. Lass, Matching polynomials and duality, Combinatorica 24(3) (2004), 427 440.
[13] L. S. Laja and R. G. Artes, Jr., Zeros of convex subgraph polynomials, Appl. Math. Sci. 8(59) (2014), 2917-2923.