Abstract: Let G be a graph. For i = g(G), g(G)+1, …, c(G), where g(G) is the length of shortest cycle in G and c(G) is the length of longest cycle in G, we say that G is a weakly pancyclic graph if it contains cycles of every length from g(G) to c(G). The weakly pancyclic polynomial of G is defined by
where yi(G) is the number of weakly pancyclic subgraphs of G with order i. This study presents explicit formulations for the weakly pancyclic polynomial of specific graphs including complete graph Kn, complete bipartite graph Km,n and graphs of the form G + K1 Specifically, it explores the fan Fn, and wheel Wn. Additionally, the study furnishes a characterization of weakly pancyclic graphs and establishes a lower bound on the coefficients of the polynomial for
|
Keywords and phrases: pancyclic, weakly pancyclic, weakly pancyclic polynomial.
Received: January 16, 2024; Revised: February 12, 2024; Accepted: February 21, 2024; Published: February 24, 2024
How to cite this article: Sharifa Dianne A. Aming, Ladznar S. Laja, Javier A. Hassan and Amy A. Laja, Weakly pancyclic polynomial of a graph, Advances and Applications in Discrete Mathematics 41(2) (2024), 167-178. http://dx.doi.org/10.17654/0974165824012
This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License
References: [1] B. Bollobas and A. Thomason, Weakly pancyclic graphs, J. Combin. Theory Ser. B 77 (1999), 121-137. [2] S. Brandt, A sufficient condition for all short cycles, Discrete Appl. Math. 79(1-3) (1997), 63-66. [3] J. Brown and R. Hoshino, Independence Polynomials of circulants with an application to music, Discrete Math. 309 (2009), 2292-2304. [4] L. S. Laja, Convex subgraph polynomials of degree 3 or 4, rooted and co-normal of graphs, Advances and Applications in Discrete Mathematics 41(1) (2024), 27-40. [5] L. S. Laja, On convex subgraph polynomials and some of its important values, Advances and Applications in Discrete Mathematics 41(1) (2024), 57-76. [6] L. S. Laja and R. G. Artes, Jr, Zeros of convex subgraph polynomials, Appl. Math. Sci. 8(59) (2014), 2917-2923. [7] L. S. Laja and R. G. Artes, Jr, Convex subgraph polynomials of the join and the composition of graphs, International Journal of Mathematical Analysis 10(11) (2016), 515-529. [8] V. E. Levit and E. Mandrescu, Independence polynomials of a graph-a survey, Proceedings of the 1st International Conference on Algebraic Informatics, Greece, 2005, pp. 233-254. [9] A. B. Tapeing and L. S. Laja, Co-segregated polynomial of graphs, Advances and Applications in Discrete Mathematics 40(1) (2023), 101-112. [10] A. B. Tapeing, L. S. Laja, J. Hassan and H. B. Copel, Totally segregated polynomial of graphs, Advances and Applications in Discrete Mathematics 40(2) (2023), 213-223.
|