An exposition on singular graphs: The cartesian product of two graphs

Date of Publication

2006

Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Thesis Adviser

Severino V. Gervacio

Defense Panel Member

Yvette F. Lim
Isagani B. Jos
Alana Margarita R. Hernandez

Abstract/Summary

This paper is an exposition of the Singular graphs: The Cartesian Product of Two Graphs, from the study of Severino V. Gervacio.

The adjacency matrix of agraph G with vertices V1, V2,...,Vn is the n x n matrix A(G) = [aij], where aij = 1 if Vi and Vj are adjacent, and aij = 0 otherwise. The graph G is said to be singular if A(G) i singular,i.e., det A(G) = 0 otherwise, G is said to be non-singular.

The cartesian product of two graphs G and H, denoted by G x H, may be singular or non-singular, independently of the singularity or non-singularity of G and H.

We show that det A(Kn0 = (-1) n-1 (n-1) and hence Kn is non-singular only when n-2. If G is any graph, we prove that G x Kn is singular if and only if 1 or (1-n) is an eigenvalue of A(G). In particular, we show that the cartesian product of Cm and Kn, n-4, is singular if and only if m=0 (mod 6). Also, for 1- n-3, we show that Cm x K1 is singular if and only if m = 0 (mod 4) or m = 0 (mod 6), Cm x K2 is singular if and only if m = 0 (mod 30 and Cm x K3 is singular if and only if m = 0 (mod 2). We also prove that det (A(Km x Kn)) = (-2) (m-1)(n-1)(m-2)n-1(n-2)m-1(m+n-2). As a corollary, Km x Kn is singular if and only m = 2 or n = 2.

Abstract Format

html

Language

English

Format

Print

Accession Number

TU13536

Shelf Location

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

Physical Description

v, 52, 6 leaves : ill.

Keywords

Matrices; Matrix inversion; Algebras, Linear; Algebra--Graphic methods; Graph theory

This document is currently not available here.

Share

COinS