Back to search

University of British Columbia

Maximum packings in tripartite graphs

Abstract

dc:description

This thesis is motivated by an attempt to prove a conjecture in design theory due to Hiralal Agrawal, by interpreting it in graph theory as a consequence of a possible extension of Hall's Marriage Theorem to tripartite graphs. Previous work on Agrawal's conjecture has been done from design theory perspective. We define edge △-r-regular tripartite graphs, inspired by Agrawal's design theory construction, and consider the conjecture that if one side of a tripartite graph is a minimum transversal of the triangles in the graph, then there exists a packing of triangles in the graph that saturates that side. Although there are counterexamples to this general statement, it has been shown to hold for certain special kinds of tripartite graphs, and we conjecture that it holds for edge △-r-regular tripartite graphs when r≥3. We use techniques in an array representation of the graph to find a maximum packing in this type of graph, but cannot find an effective method to prove that a complete packing exists in general. We also study edge △-2-regular tripartite graphs and show that such a graph satisfies the statement of the conjecture if and only if its triangle graph is bipartite, and that this is also equivalent to the orientability of the triangulated surface defined by the triangles of the graph.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Rao, You

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/73428

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Rao, You. Maximum packings in tripartite graphs. master's thesis, University of British Columbia, 2020. http://hdl.handle.net/2429/73428