Open Collections

Maximum packings in tripartite graphs

University of British Columbia

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.

Text

2020-01-29

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73428

Mathematics

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/