Date of Publication

7-5-2025

Document Type

Master's Thesis

Degree Name

Master of Science in Mathematics

Subject Categories

Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics Department

Thesis Advisor

Francis Joseph H. Campeña

Defense Panel Chair

Severino V. Gervacio

Defense Panel Member

Isagani B. Jos
John Rafael M. Antalan

Abstract/Summary

Let G be a triangle-free graph with chromatic number k. In 1955, J. Mycielski introduced a graph operation called the Mycielskian of G (also called the star shadow graph of G), denoted by μ(G), and proved that it is also a triangle-free graph with a chromatic number k+1. Inspired by this, we propose two new variations: the star double graph of G, denoted by D*(G), and the Mycielskian of G with index t, denoted by μᵗ(G), for a nonegative integer t. This study explores the structural properties of these newly introduced graph operations and examines their similarities to the classical Mycielskian construction.

Furthermore, we compute key topological indices for star shadow graphs and star double graphs, including the Harary index, Wiener index, and the Zagreb coindices. Additionally, we investigate the existence of independent [1,2]-sets in the Mycielskian of common graph families.

Abstract Format

html

Language

English

Format

Electronic

Keywords

Graph theory

Upload Full Text

wf_yes

Embargo Period

8-6-2025

Download

Share

COinS