The Complexity of Pencil Graph and Line Pencil Graph

Calvin Hanssen; Fransiskus Fran; Yundari Yundari

doi:10.21831/pythagoras.v19i2.77747

The Complexity of Pencil Graph and Line Pencil Graph

Calvin Hanssen, Department of Mathematics, Universitas Tanjungpura, Indonesia
Fransiskus Fran, Department of Mathematics, Universitas Tanjungpura
Yundari Yundari, Department of Mathematics, Universitas Tanjungpura, Indonesia

10.21831/pythagoras.v19i2.77747

Abstract

Let 𝒢 be a linked and undirected graph. Every linked graph 𝒢 must contain a spanning tree 𝒯, which is a subgraph of 𝒢that is a tree and contain all the nodes of 𝒢. The number of spanning trees in graph 𝒢, also called the complexity of the graph 𝒢, represented by τ(𝒢), is the total number of distinct spanning trees of graph 𝒢. This research aims to formulate the complexity of pencil graph and line pencil graph. In this research, the complexity of pencil graph and line pencil graph are determined using graph complement approach. The result of the research are the complexity of pencil graph and line pencil graph.

Keywords

complexity; block matrix; pencil graph

References

Afzal, H. U., Javaid, M., Ovais, A., & Nur Alam, M. (2022). Computation of the complexity of networks under generalized operations. Complexity, 2022(1), 6288054.

Ali, A., Furtula, B., Redžepović, I., & Gutman, I. (2022). Atom-bond sum-connectivity index. Journal of Mathematical Chemistry, 60(10), 2081-2093.

Chartrand, G., Lesniak, L, & Zhang, P. (2016). Graphs & Digraphs, 6th ed. Boca Raton London New York: CRC Press Taylor & Francis Group.

Daoud, S. N. (2019). Number of Spanning trees of cartesian and composition products of graphs and Chebyshev polynomials. IEEE Access, 7, 71142-71157.

Daoud, S. N. (2017). Complexity of graphs generated by wheel graph and their asymptotic limits. Journal of the Egyptian Mathematical Society, 25(4), 424-433.

Daoud, S. N., & Mohamed, K. (2017). The complexity of some families of cycle-related graphs. Journal of Taibah University for science, 11(2), 205-228.

Daoud, S. N. (2019). Number of spanning trees of some families of graphs generated by a triangle. Journal of Taibah University for Science, 13(1), 731-739.

Daoud, S. N. (2014). Number of spanning trees of different products of complete and complete bipartite graphs. Mathematical Problems in Engineering, 2014(1), 965105.

Daoud, S. N., & Mohamed, K. A. (2014). Complexity of some special named graphs with double edges. Journal of Taibah University for Science, 8(2), 162-174.

Daoud, S. N., & Saleh, W. (2020). Number of Spanning Trees of Some of the Families of Sequence Graphs Generated by Triangle Graph. International Journal of Mathematical Combinatorics, 3, 26-55.

Daoud, S. N., & Aljohani, M. (2023). Number of Spanning Trees of Sequence of Some Families of Graphs That Have the Same Average Degree and Their Entropies. International J. Math. Combin. Vol, 4, 14-32.

Daoud, S. N., & Saleh, W. (2020). Number of Spanning Trees of Some of Pyramid Graphs Generated by a Wheel Graph. Mathematical Combinatorics, 43.

Daoud, S. N., & Siddiqui, M. K. (2019). On the Complexity of Some Classes of Circulant Graphs and Chebyshev Polynomials. International J. Math. Combin. Vol, 4, 29-47.

Deen, M. R. (2023). Enumeration of spanning trees in prisms of some graphs. Proyecciones (Antofagasta), 42(2), 339-391.

El Deen, M. R. Z., & Aboamer, W. A. (2021). Complexity of some duplicating networks. IEEE Access, 9, 56736-56756.

Fran, F., Alexander, Yundari, Romanda, P., & Febyolga, E. (2024). The Complexity of Octopus Graph, Friendship Graph, and Snail Graph. EduMatSains : Jurnal Pendidikan, Matematika Dan Sains, 9(1), 84-101.

Harris, J. M. (2008). Combinatorics and graph theory.

Javaid, M., Afzal, H. U., & Wang, S. (2021). Complexity of Some Generalized Operations on Networks. Complexity, 2021(1), 9999157.

Jia-Bao, L., & Daoud, S. N. (2019). Number of Spanning Trees in the Sequence of Some Graphs. Complexity, 2019.

Joedo, J. C., Kristiana, A. I., Agustin, I. H., & Nisviasari, R. (2022). On the rainbow antimagic coloring of vertex amalgamation of graphs. In Journal of Physics: Conference Series (Vol. 2157, No. 1, p. 012014). IOP Publishing.

Lipschutz, S., dan Lipson,M. L. (2017) Discrete Mathematics (Schaum’s Outlines), 3rd ed. McGraw Hill Education.

Liu, J. B., & Daoud, S. N. (2018). The complexity of some classes of pyramid graphs created from a gear graph. Symmetry, 10(12), 689.

Roza, I. (2016). Graf garis (line graph) dari graf siklus, graf lengkap dan graf bintang. Jurnal Matematika UNAND, 3(2), 1-4.

Simamora, D. N., & Salman, A. N. M. (2015). The rainbow (vertex) connection number of pencil graphs. Procedia Computer Science, 74, 138-142.

Verma, P., Nagarajan, S., & Raj, A. (2022). Teori grafik spektral osilasi otak—ditinjau kembali dan disempurnakan. NeuroImage , 249 , 118919.

Zhang, J., & Yan, W. (2020). Counting spanning trees of a type of generalized Farey graphs. Physica A: Statistical Mechanics and its Applications, 555, 124749.

Zeen El Deen, M. R., & El-Sherbiny, H. (2022). Enumerating Spanning Trees of Some Advanced Families of Graphs. Frontiers in Scientific Research and Technology, 3(1), 20-35.

Zeen El Deen, M. R., Aboamer, W. A., & El-Sherbiny, H. M. (2023). The Complexity of the Super Subdivision of Cycle-Related Graphs Using Block Matrices. Computation, 11(8), 162.

Zeen El Deen, M. R., & Aboamer, W. A. (2021). Complexity of some graphs generated by square. J. Math. Comput. Sci., 11(4), 4248-4283.

Zeen El Deen, M. R., Aboamer, W. A., & El-Sherbiny, H. M. (2024). Explicit Formulas for the Complexity of Networks Produced by New Duplicating Corona and Cartesian Product. Journal of Mathematics, 2024(1), 9131329.

DOI: https://doi.org/10.21831/pythagoras.v19i2.77747