The Complexity of Pencil Graph and Line Pencil Graph

Hanssen, Calvin
Fran, Fransiskus
Yundari, Yundari

Pythagoras: Jurnal Matematika dan Pendidikan Matematika
Vol. 19 No. 2: December 2024

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.