On complete 4-partite graphs with spanning maximal planar subgraphs

Date of Publication

2018

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Mathematics

Subject Categories

Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Thesis Adviser

Isagani B. Jos

Defense Panel Chair

Severino B. Gervacio

Defense Panel Member

Francis Joseph H. Campena
Leonor A. Ruivivar
Yvette F. Lim
Neil M. Mame

Abstract/Summary

A spanning maximal planar subgraph T = (V E0) is a spanning planar subgraph of a simple, finite, undirected graph G = (V E), with the property of being a maximal planar graph. That is, there exists a drawing of T on the plane, such that there are no edge-crossings and all the regions of T are bounded by exactly three edges. We refer to finding a spanning maximal planar subgraph of G, as the SMPS problem. This problem belongs to the problem of graph planarization, and we discuss how the SMPS is related to the concepts of graph planarization. In this study, we tackle the SMPS problem for complete 4-partite graphs. It is shown that for the class of graphs K1 1 1 z and K1 1 y z , a SMPS will exist if and only if z 2 f1 2g and jy {u100000} zj 1, respectively. The SMPS of these graphs were utilized to construct SMPS for more general complete 4-partite graphs K1 x y z and Kw x y z with larger order, leading to relationships between the cardinalities w x y and z. Such construction of larger SMPS requires various methods of adding vertices, and consequently edges, to a maximal planar graph. These methods are elaborated in detail, and the conditions when they can be carried out are discussed. Algorithms were developed with the aid of these methods in generating larger SMPS. It is also presented here how the SMPS problem for complete tripartite graphs could be used to solve some problems in the complete 4-partite case. The results produced in the study were applied to complete 4-partite graphs with order at most 15, to classify which among the configurations of cardinalities of the four partite sets induce a complete 4-partite graph with a SMPS. A necessary and sufficient condition in order for a SMPS to exist in any complete 4-partite graph was also found in this research.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

CDTG007628

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

1 computer disc; 4 3/4 in.

Keywords

Graph theory

This document is currently not available here.

Share

COinS