pp 56-63 (Vol 12 2019)

T.J.B. Estrada1,* and
I.B. Jos

1 Don Mariano Marcos Memorial State University–SLUC, Agoo, La Union, Philippines
2 Mathematics and Statistics Department, De La Salle University, Manila, Philippines

Corresponding Author: tjart_estrada@dlsu.edu.ph


A spanning maximal planar subgraph (SMPS) T of a simple, finite, undirected graph G is a spanning subgraph of G that is also a maximal planar graph. In this paper, we introduce some methods of constructing complete 4-partite graphs Kw,x,y,z with SMPS. We utilize these methods to the SMPS problem for complete tripartite graphs to generate complete 4-partite graphs with SMPS and provide some relationships between the cardinalities of the two graphs.