UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Maximum packings in tripartite graphs Rao, You 2020

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2020_february_rao_you.pdf [ 488.27kB ]
JSON: 24-1.0388489.json
JSON-LD: 24-1.0388489-ld.json
RDF/XML (Pretty): 24-1.0388489-rdf.xml
RDF/JSON: 24-1.0388489-rdf.json
Turtle: 24-1.0388489-turtle.txt
N-Triples: 24-1.0388489-rdf-ntriples.txt
Original Record: 24-1.0388489-source.json
Full Text

Full Text

Maximum Packings in TripartiteGraphsbyYou RaoB.Sc. Hons, The University of British Columbia, 2017A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe College of Graduate Studies(Mathematics)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)January 2020c© You Rao, 2020The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Maximum Packings in Tripartite Graphssubmitted by You Rao in partial fulfilment of the requirements of the de-gree of Master of ScienceDr. Wayne Broughton, Irving K. Barber School of Arts and SciencesSupervisorDr. Donovan Hare, Irving K. Barber School of Arts and SciencesSupervisory Committee MemberDr. Javad Tavakoli, Irving K. Barber School of Arts and SciencesSupervisory Committee MemberDr. Holger Andreas, Irving K. Barber School of Arts and SciencesUniversity ExamineriiAbstractThis thesis is motivated by an attempt to prove a conjecture in designtheory due to Hiralal Agrawal, by interpreting it in graph theory as a con-sequence of a possible extension of Hall’s Marriage Theorem to tripartitegraphs. Previous work on Agrawal’s conjecture has been done from designtheory perspective. We define edge M-r-regular tripartite graphs, inspiredby Agrawal’s design theory construction, and consider the conjecture that ifone side of a tripartite graph is a minimum transversal of the triangles in thegraph, then there exists a packing of triangles in the graph that saturatesthat side. Although there are counterexamples to this general statement, ithas been shown to hold for certain special kinds of tripartite graphs, and weconjecture that it holds for edge M-r-regular tripartite graphs when r ≥ 3.We use techniques in an array representation of the graph to find a maxi-mum packing in this type of graph, but cannot find an effective method toprove that a complete packing exists in general.We also study edge M-2-regular tripartite graphs and show that sucha graph satisfies the statement of the conjecture if and only if its trianglegraph is bipartite, and that this is also equivalent to the orientability of thetriangulated surface defined by the triangles of the graph.iiiLay SummaryThis thesis is motivated by a construction in the statistical design ofexperiments which was suggested by Hiralal Agrawal in 1966. He couldnot prove that his method would work in general, and this is still an openquestion. We interpret his question in terms of certain kinds of graphs, asfinding the largest possible number of triangles in each of these graphs thatdo not share any edge. We prove some related results and study techniquesfor constructing the largest possible set of triangles for some of these graphs.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgement . . . . . . . . . . . . . . . . . . . . . . . . . . xDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Basic Concepts of General Graphs . . . . . . . . . . . . . . . 11.2 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3 Triangles in Graphs . . . . . . . . . . . . . . . . . . . . . . . 91.4 Hypergraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12Chapter 2: Hall’s Marriage Theorem and Extensions in Tri-partite Graphs . . . . . . . . . . . . . . . . . . . . . 132.1 Bipartite Graphs and Matchings . . . . . . . . . . . . . . . . 132.2 Tripartite Case Extension . . . . . . . . . . . . . . . . . . . . 152.3 Tuza’s Conjecture and Related Studies . . . . . . . . . . . . . 182.3.1 Proof of Theorem 2.3.2 . . . . . . . . . . . . . . . . . 20Chapter 3: Agrawal’s Conjecture and Edge M-r-Regular Tri-partite Graph . . . . . . . . . . . . . . . . . . . . . . 223.1 Symmetric Design and Agrawal’s Conjecture . . . . . . . . . 223.2 Agrawal’s Construction and Tripartite Graph . . . . . . . . . 26vTABLE OF CONTENTSChapter 4: Triangle Presentation of Tripartite Graphs . . . . 284.1 Method of Listing Triangles . . . . . . . . . . . . . . . . . . . 284.2 Minimum T -Transversal in Triangle Array Representation . . 314.3 Induced Odd Cycles in Triangle Array Representation . . . . 35Chapter 5: Maximum Packing of Edge M-2-Regular Tripar-tite Graphs . . . . . . . . . . . . . . . . . . . . . . . 395.1 Properties of Edge M-2-Regular Tripartite Graphs . . . . . . 395.1.1 Proof of Theorem 5.1.1 . . . . . . . . . . . . . . . . . 405.2 Orientability of the Surface Formed by an Edge M-2-RegularTripartite Graph . . . . . . . . . . . . . . . . . . . . . . . . . 41Chapter 6: Pseudo-Packing Technique in Edge M-r-RegularTripartite Graph . . . . . . . . . . . . . . . . . . . . 44Chapter 7: Conclusion and Future Work . . . . . . . . . . . . . 487.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 49Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Appendix A: Tables . . . . . . . . . . . . . . . . . . . . . . . . . . 54A.1 Detailed Switch Steps of Edge M-3-regular graph from (11,5,2)-design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54A.2 Triangle Array Representation of graph from (19,9,4)-design . 55viList of TablesTable 3.1 Example of Agrawal’s structure from (7,3,1)-design . . 24Table 3.2 Sample partial satisfied triple array of Table 3.1 . . . . 24Table 3.3 Example of Agrawal’s structure from (11,5,2)-design . 25Table 3.4 Example triple array (10,5,3,2,3: 5×6) from (11,5,2)-design . . . . . . . . . . . . . . . . . . . . . . . . . . . 25Table 4.1 Array of triangles of G . . . . . . . . . . . . . . . . . . 29Table 4.2 Triangle array representation of G . . . . . . . . . . . 30Table 4.3 Example of A(1)S1 . . . . . . . . . . . . . . . . . . . . 33Table 4.4 Example of A(3)S1 . . . . . . . . . . . . . . . . . . . . 33Table 4.5 Example of an induced odd cycle in M . . . . . . . . . 37Table 4.6 Example triangle array representation of graph from(11,5,2)-design and with an example induced C9 . . . . 37Table 4.7 Example of a maximum packing of Table 4.6 . . . . . 37Table 6.1 Example pseudo-packing of Table 4.6 . . . . . . . . . . 44Table 6.2 Example after a switch of Table 6.1 . . . . . . . . . . . 45Table 6.3 Example after six switches of Table 6.1 . . . . . . . . . 45Table 6.4 Example of the seventh switch of Table 6.1 . . . . . . 46Table 6.5 Example after eight switch of Table 6.1 . . . . . . . . . 46Table A.1 First switch of Table 6.1 . . . . . . . . . . . . . . . . . 54Table A.2 Second switch of Table 6.1 . . . . . . . . . . . . . . . . 54Table A.3 Third switch of Table 6.1 . . . . . . . . . . . . . . . . 54Table A.4 Fourth switch of Table 6.1 . . . . . . . . . . . . . . . . 55Table A.5 Fifth switch of Table 6.1 . . . . . . . . . . . . . . . . . 55Table A.6 Sixth switch of Table 6.1 . . . . . . . . . . . . . . . . . 55Table A.7 Triangle Array Representation of graph from (19,9,4)-design . . . . . . . . . . . . . . . . . . . . . . . . . . . 56Table A.8 Example maximum packing of Table A.7 . . . . . . . . 56viiList of FiguresFigure 1.1 Example of simple and non-simple graph . . . . . . . 2Figure 1.2 Example graph and its adjacency matrix . . . . . . . 2Figure 1.3 Example of induced subgraph and non-induced sub-graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 3Figure 1.4 K3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Figure 1.5 K4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Figure 1.6 K3,3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Figure 1.7 K2,2,2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Figure 1.8 Example of complement graph . . . . . . . . . . . . . 5Figure 1.9 Example of a vertex cover and a minimum vertex cover 6Figure 1.10 Example of an edge cover (blue) and a minimum edgecover (red) . . . . . . . . . . . . . . . . . . . . . . . . 6Figure 1.11 Example for θ, ω, χ . . . . . . . . . . . . . . . . . . . 7Figure 1.12 C5, C5 . . . . . . . . . . . . . . . . . . . . . . . . . . 8Figure 1.13 Example of maximal and maximum matching . . . . 9Figure 1.14 Example of a T -transversal . . . . . . . . . . . . . . . 10Figure 1.15 Example of triangle graph for K2,2,2 . . . . . . . . . . 11Figure 1.16 Example original graphs of triangle graph K4 . . . . . 12Figure 1.17 Example of Hypergraph . . . . . . . . . . . . . . . . . 12Figure 2.1 Example of a matching of a bipartite graph saturatingX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14Figure 2.2 Counterexample of statement 1 . . . . . . . . . . . . . 15Figure 2.3 Example of a tripartite graph G and the correspond-ing hypergraph H . . . . . . . . . . . . . . . . . . . . 16Figure 2.4 Counterexample G . . . . . . . . . . . . . . . . . . . . 17Figure 2.5 Hypergraph H corresponding to G . . . . . . . . . . . 17Figure 2.6 Triangle graph T (G) . . . . . . . . . . . . . . . . . . . 17Figure 2.7 Example of Fact 2.3.5 in C7 . . . . . . . . . . . . . . 20Figure 3.1 Fano plane . . . . . . . . . . . . . . . . . . . . . . . . 23viiiLIST OF FIGURESFigure 3.2 Agrawal’s construction from (7,3,1)-design in tripar-tite graph . . . . . . . . . . . . . . . . . . . . . . . . . 26Figure 4.1 Example graph G . . . . . . . . . . . . . . . . . . . . 29Figure 4.2 Example subset S1 of MAB . . . . . . . . . . . . . . . 32Figure 4.3 Agrawal’s construction from (7,3,1)-design in tripar-tite graph and its array representation . . . . . . . . . 36Figure 5.1 Example of triangle orientation . . . . . . . . . . . . . 42Figure 5.2 Example of a sphere and a mobius strip . . . . . . . . 42Figure 5.3 Example of two edge-joint triangle with one orienta-tion agrees RGB and the other orientation disagreeswith RGB . . . . . . . . . . . . . . . . . . . . . . . . 42Figure 5.4 Surface formed by triangles in K2,2,2 . . . . . . . . . . 43ixAcknowledgementFirst and foremost, I really appreciate all the help from my supervisorDr. Wayne Broughton throughout my undergrad and graduate student life.Without his precious advice in both math and life, I would not have thecourage to accomplish my Master’s degree.I would like to thank Dr. Donovan Hare and Dr. Javad Tavakoli forbeing on my committee, Dr. Holger Andreas to be my University Exam-iner. I would also like to thank Dr. Rebecca Tyson for her great help andencouragement to me to choose to be a math major student. I really appre-ciate Dr. Qiduan Yang, Dr. Shawn Wang and Dr. Heinz Bauschke for theirgenerous kindness of sharing knowledge with me.Thanks to UBC Okanagan campus for financial support throughout mygraduate studies.I would also wish to thank Dr. Blair Spearman, who initially acceptedme as his student, although this was tragically cut very short. I wish Icould have met him earlier. Through him, I got to know his great students:Dr. Paul Lee, Dr. Chad Davis, Dr. Lindsey Reinholz, Stephen Brown andJeewon Yoo. Thank you all for the help and advice.I thank all my friends for any kind of help in my life when I am a studentand teaching assistant in UBCO, and especially for all the support from myfriend Jingshi Guan. I could not get through my hard times without yourcompany.Last but not the least, I really appreciate all the support from my belovedparents. I am blessed to be your child and your unconditional love is thestrongest shelter in my life.xDedicationTo my parents, my aunt and uncle, my friends.To Dr. Blair Spearman.xiChapter 1IntroductionIn this chapter, we will introduce some basic definitions in graphtheory that will be used later in this thesis. The materials in thischapter are mainly from [Wes] and [BM+76]. We will provide someexamples of some definitions.1.1 Basic Concepts of General GraphsDefinition 1.1.1. A graph is a mathematical structure consisting ofa collection of points called vertices (singular: vertex ) and a collectionof unordered pairs of points called edges. The points in a pair arecalled the endpoints of the edge and they are joined by the edge. Theedge is incident with its endpoints. In this thesis, we will only considerundirected graphs.For a graph G with n vertices and m edges we denote its ver-tex set by V (G) := {v1, v2, · · · , vn} and its edge set by E(G) :={e1, e2, · · · , em}.Definition 1.1.2. Two vertices are adjacent if they are connected byan edge. Two adjacent vertices can be connected by more than oneedge, which is called multiple edges. If u and v are adjacent, then u isa neighbour of v and vice versa. The neighbourhood of a vertex is theset of its neighboursDefinition 1.1.3. A loop is an edge whose endpoints are the samevertex (considered to be adjacent to itself).Definition 1.1.4. A graph G is simple if it does not contain anymultiple edges and loops.Example 1.1.5. The two graphs drawn below are examples of a simpleand a non-simple graph.11.1. Basic Concepts of General Graphsv2v1 v3v4Simple Graphe 2 e4e1e3v2v1v3v4Non-simple Graphe 2e 3e4e1Figure 1.1: Example of simple and non-simple graphDefinition 1.1.6. A graph is connected if for any two disjoint non-empty subsets X, Y of the vertex set such that V = X⋃Y , thereexists at least one edge with one endpoint in X and the other endpointin Y .Definition 1.1.7. The adjacency matrix of a finite graph G = (V,E)(where |V | = n and |E| = m) is a square n × n matrix with each rowand column labeled by a vertex. The entry in row u and column vis the number of edges having u and v as endpoints. Note that theadjacency matrix of an undirected graph is symmetric.Example 1.1.8. Shown below is a finite undirected graph G and itsadjacency matrix.e2e 3e1e4e5e6uv wxGu v w xu 0 1 2 0v 1 2 1 1w 2 1 0 0x 0 1 0 0Adjacency matrix of GFigure 1.2: Example graph and its adjacency matrixDefinition 1.1.9. Let G be a simple graph. A subgraph H of G is agraph such that all of the vertices and edges in H are in G; that is,V (H) ⊆ V (G) and E(H) ⊆ E(G). A subgraph H is induced if everyedge in E(G) whose endpoints are in V (H) is also in E(H).Example 1.1.10. H1 and H2 below are two subgraphs of G.21.1. Basic Concepts of General Graphsv1v2v3v4v5v6v7v8Gv1v4v5v6v7H1v1v4v5v6v7H2Figure 1.3: Example of induced subgraph and non-induced subgraphWe can see that: V (G) = {v1, v2, v3, v4, v5, v6, v7, v8} and V (H1) =V (H2) = {v1, v4, v5, v6, v7} ⊂ V (G). However, H2 does not contain allthe edges of G whose endpoints are in V (H2), such as the v4v6 andv6v7, while H1 includes all edges of G joining vertices in V (H1). So H1is an induced subgraph of G and H2 is not.Definition 1.1.11. Let G be a simple graph. G is complete if everypair of distinct vertices in G is adjacent to each other.Definition 1.1.12. Let G be a simple graph and let S ⊂ V (G). Ifevery vertex in S is not adjacent to any other vertex in S, we say Sis an independent set. If V (G) can be partitioned into two disjointindependent sets X, Y (called parts), (so V (G) = X ∪Y and X ∩Y =∅), then G is a bipartite graph denoted by G[X, Y ]. If V (G) can bepartitioned into three disjoint independent sets, then G is a tripartitegraph. In general, for any simple graph G, if V (G) can be partitionedinto k disjoint independent sets, then G is k-partite.Definition 1.1.13. Let G[X, Y, Z] be a tripartite graph with vertexparts X, Y , Z. From the definition of tripartite graph, the edge setcan be partitioned into three sets: EXY := {xy ∈ E(G)|x ∈ X, y ∈ Y },EXZ := {xz ∈ E(G)|x ∈ X, z ∈ Z}, EY Z := {yz ∈ E(G)|y ∈ Y, z ∈Z}. Each edge set is a side of the tripartite graph.31.1. Basic Concepts of General GraphsDefinition 1.1.14. A graph is a complete k-partite graph if it is a k-partite graph and each vertex is adjacent to every other vertex in theother part.Example 1.1.15. The usual way to denote a complete graph with nvertices is Kn, and for a complete bipartite graph with parts of sizem and l we write Km,l. The notation of complete k-partite graph isK with subscripts indicating the sizes of the disjoint parts. Below areexamples of complete graphs.Figure 1.4: K3 Figure 1.5: K4Figure 1.6: K3,3 Figure 1.7: K2,2,2Definition 1.1.16. The degree of a vertex v is the number of edgeswhich include it as an endpoint, denoted d(v). Every loop is countedtwice. For example, every vertex in K4 has degree 3. If a vertex hasdegree 0, then it is an isolated vertex.Fact 1.1.17. For any graph G = (V,E),∑v∈Vd(v) = 2|E|.Proof. Every edge has two endpoints (possibly same vertex), so everyedge is counted twice in the summation of the degrees of all vertices.Definition 1.1.18. A graph is regular if every vertex has the samedegree. A regular graph in which every vertex has degree k is called ak-regular graph. For example, K4 is a 3-regular graph.41.1. Basic Concepts of General GraphsDefinition 1.1.19. A graph is edge regular if it is a regular graphwith every adjacent pair of vertices having exactly the same number ofcommon neighbours. For example, K2,2,2 is edge regular.Definition 1.1.20. Let G be a simple graph. The complement graphof G, denoted as G, is a graph which has the same vertex set V (G),but any two adjacent vertices in G are not adjacent in G, and thosenonadjacent vertices in G are adjacent in G.Example 1.1.21. The two graphs below are an example of a graphand its complement.G GFigure 1.8: Example of complement graphNote that for any complete graph G, the graph G contains no edge.Definition 1.1.22. Let G = (V,E). A vertex cover is a subset of Vsuch that every element in E has at least one endpoint in this subset.If a vertex cover contains the least number of vertices compared to allother vertex covers in G, then it is a minimum vertex cover.Example 1.1.23. On the left below is an example of a vertex cover (inblue) of a graph and on the right is an example of a minimum vertexcover (in red).51.1. Basic Concepts of General GraphsFigure 1.9: Example of a vertex cover and a minimum vertex coverDefinition 1.1.24. Let G = (V,E). An edge cover is a subset of Esuch that every element in V is an endpoint of an edge in the subset.Note that if G contains at least one isolated vertex, then G does nothave an edge cover. A minimum edge cover of G is an edge cover whichhas the smallest possible number of elements among all edge covers.Example 1.1.25. The two diagrams below are examples of an edgecover (in blue) and a minimum edge cover (in red) in a graph.Figure 1.10: Example of an edge cover (blue) and a minimum edge cover(red)Note that minimum vertex covers and minimum edge covers are notunique in general.Definition 1.1.26. Let G be a simple graph. A clique of G is a subsetof vertices in which every vertex in the set is adjacent to every othervertex. In other words, a clique is the vertex set of a complete subgraphand a complement of a clique is an independent set.Definition 1.1.27. The clique number of a simple graph G, denotedby ω(G), is the maximum number of vertices in a clique in G.Definition 1.1.28. The clique covering number of a simple graph G,denoted by θ(G), is the minimum cardinality of a set of cliques whoseunion includes all vertices of G.61.1. Basic Concepts of General GraphsDefinition 1.1.29. The chromatic number of a simple graph G, de-noted by χ(G), is the minimum number of colours required to colour thevertices of G so that no two adjacent vertices receive the same colour.Note that χ(G) is the smallest number k such that G is k-partite.Fact 1.1.30. For any simple graph G, χ(G) ≥ ω(G).Proof. The maximum clique has to be assigned different colours so bydefinition χ(G) ≥ ω(G).Example 1.1.31. A simple graph G and its complement G are givenbelow.bdGeacdcGbaeFigure 1.11: Example for θ, ω, χWe can see that for G, the clique with the maximum number ofvertices is {a, b, e}, so ω(G) = 3. Since ω(G) = 3, we need at leastthree different colors to cover all the vertices in G and as we can seefrom the graph, in fact χ(G) = 3. If we take the maximum clique andanother clique {c, d}, then we have included all vertices in G. Thusθ(G) = 2. Looking at G, we can see ω(G) = 2, χ(G) = 2, θ(G) = 3.Fact 1.1.32. For any simple graph G, χ(G) = θ(G).Proof. It follows from the definitions. All vertices in a clique of G arenon-adjacent in G, therefore, a clique in G can be assigned same colourin G. Hence the minimum number of cliques that include all verticesin G is equal to the minimum number of colours required to colour allvertices of G.71.1. Basic Concepts of General GraphsDefinition 1.1.33. A graph G is perfect if the chromatic number ofevery induced subgraph equals the clique number of this subgraph.Equivalently, G is perfect if and only if for all induced subgraphs H ⊆G:χ(H) = ω(H)Definition 1.1.34. A walk W is a sequence of vertices and edges“v0, e1, v1, e2, v2, · · · , vn−1, en, vn”, where vi−1vi = ei for all 1 ≤ i ≤ n.The length of a walk is the number of the edges contained in the walk.A path is a walk in which every vertex appears no more than once.Definition 1.1.35. A cycle is a path but with the exception that thestarting and ending point are the same vertex. Note that a loop is acycle of length 1, and a cycle of length 3 is a triangle. Briefly, we useeven cycle for a cycle with even length; and odd cycle for a cycle withodd length.Example 1.1.36. A common notation for a cycle of length n is Cn.Below is a cycle of length 5 (C5) and its complement.b cdaeC5b cdaeC5Figure 1.12: C5, C5Definition 1.1.37. Let G and H be simple graphs. We say G isisomorphic to H if there exists a bijection f : V (G) → V (H) suchthat for any pair of vertices u and v in V (G), uv ∈ E(G) if and only iff(u)f(v) ∈ E(H). For example, C5 is isomorphic to C5.Definition 1.1.38. Given a fixed graph H, an H-free graph is a graphsuch that it does not contain any induced subgraph which is isomor-phic to H. For instance, a triangle-free graph is a graph without anytriangles. Note that any tripartite graph is K4-free.81.2. Matching1.2 MatchingDefinition 1.2.1. A matching in an undirected simple graph is a set ofedges which do not have any common endpoint. The vertices incidentwith the edges in a matching are saturated by the matching and thosevertices not incident by the edges in the matching are unsaturated. Ifevery vertex of a graph is saturated by a matching, then we say thismatching is a complete matching. A maximal matching is a matchingsuch that adding any edge not in the matching will make the new setof edges no longer a matching. A maximum matching of a graph thathas the largest possible size of a matching in this graph.Example 1.2.2. The graphs below are examples of a maximal match-ing (blue) and a maximum matching (red) in the same graph.maximal matching maximum matchingFigure 1.13: Example of maximal and maximum matchingNote that a maximum matching is a maximal matching but a max-imal matching does not always have maximum size. We can see fromthe example above that the maximal matching has size 5 while themaximum matching has size 6.1.3 Triangles in GraphsStarting from this section, we will define some terms and notationwe will use in this thesis, but these are not used consistently by otherauthors. In [HK98] pairwise edge-disjoint triangles are described as“independent”, but in [HKT12] these are called a “triangle packing”.The term “packing” is also used for more general vertex sets, but sincewe will only focus on triangles in graphs, we abbreviate the term as“packing” to indicate a “triangle packing” in this thesis. Similarly,91.3. Triangles in Graphs“triangle edge cover” was used in [HKT12], but to avoid confusion withthe more common definition of edge cover given in Definition 1.1.24, wewill follow the terminology in [LBT12] and call this a “T -transversal”.The term “transversal” is more frequently used in hypergraphs.Definition 1.3.1. Let T be the set of all triangles in a simple graph G.A subset T ′ ⊆ T is independent if any two triangles in T ′ do not shareany common vertex. We say T ′ is a packing if any two triangles in T ′do not share any edge, or equivalently all triangles in T ′ are pairwiseedge-disjoint.Definition 1.3.2. If Tm ⊆ T is a packing such that |Tm| ≥ |T ′| forall the packings T ′ ⊆ T , then we say Tm is a maximum packing anddenote |Tm| = νM(G).Definition 1.3.3. A T-transversal is a subset E ′ ⊆ E such that everyelement in T contains at least one edge from E ′.Definition 1.3.4. If Em ⊆ E is a T -transversal in a simple graphG with |Em| ≤ |E ′| for all T -transversals E ′, then we say Em is aminimum T -transversal and denote |Em| = τM(G).Example 1.3.5.a b cd efFigure 1.14: Example of a T -transversalFrom the graph above we can see there are four triangles in to-tal. The maximum packing is: {abd, bce, def}, so νM(G) = 3, andwe can cover the four triangles by taking a minimum T -transversal:{bd, be, de}, so τM(G) = 3.101.3. Triangles in GraphsFact 1.3.6. For any simple graph G:νM(G) ≤ τM(G) ≤ 3νM(G).Proof. Assume there exists a maximum packing whose size is greaterthan τM, then there will be at least two triangles in this maximumpacking will share an edge in a minimum T -transversal and this con-tradicts the definition of the maximum packing. Thus, νM(G) ≤ τM(G)is always true. The set of all the edges of the triangles in a maximumpacking must contain at least one edge of all triangles in G, or elsethere must exist a bigger packing, which contradicts the definition. Sothere exists an upper bound τM(G) ≤ 3νM(G). Overall, these give thefact above.Definition 1.3.7. Let G be a simple graph, the triangle graph of G,denoted as T (G), is the graph with vertices representing the trianglesof G, and two vertices of T (G) are adjacent if and only if the corre-sponding triangles of G share an edge.B CDF EAK2,2,2CDEABC BCDACEABF BDFDEFAEFT (K2,2,2)Figure 1.15: Example of triangle graph for K2,2,2Remark 1.3.8. Any graph has a unique triangle graph, but for anygiven triangle graph it may not always correspond to a unique originalgraph.Example 1.3.9. If we are given K4 as a triangle graph, it has thefollowing two possible original graphs:111.4. HypergraphFigure 1.16: Example original graphs of triangle graph K41.4 HypergraphDefinition 1.4.1. A hypergraph H is a generalization of a graph inwhich the edge set is a subset of the power set of vertices. These edgesare called hyperedges.Example 1.4.2. The graph below is an example of a hypergraph withvertex set V := {v1, v2, v3, v4, v5, v6, v7, v8, v9}, and edge set E:={e1, e2, e3, e4, e5} ={{v2, v4, v5, v8}, {v8}, {v6, v7}, {v1, v8, v9}, {v7, v9}}v1v2v3v4v5v6v7v8v9He3e1e2e4e5Figure 1.17: Example of HypergraphDefinition 1.4.3. Let H = (V,E) be a hypergraph, if every elementin E(H) has exactly the same size k, then we say H is a k-uniformhypergraph.Definition 1.4.4. Let H be a hypergraph. The maximum number ofdisjoint hyperedges is denoted by ν(H). A transversal in a hypergraphis a vertex set which contains at least one vertex from each hyperedge.The minimum size of all transversals is denoted by τ(H).12Chapter 2Hall’s Marriage Theoremand Extensions in TripartiteGraphsIn this chapter, we will introduce some classical results in concern-ing bipartite graph: the Ko¨nig-Egerva´ry Theorem, and its relation toHall’s Marriage Theorem. Then we will mention some generalizationsof Hall’s Theorem in hypergraphs, and then move on to our work intripartite graphs.2.1 Bipartite Graphs and MatchingsIn 1931, De´nes Ko¨nig proved that in any bipartite graph, the sizeof a minimum vertex cover and the maximum matching size are equal.In the same year, coincidentally, Jeno¨ Egerva´ry proved a more generalresult independently in weighted graphs [BLW86]. This theorem is nowoften known as the Ko¨nig and Egerva´ry Theorem.Theorem 2.1.1. Ko¨nig-Egerva´ry Theorem (K-E Theorem)In any bipartite graph, the number of edges in a maximum matchingequals the number of vertices of a minimum vertex cover.In 1935, Philip Hall proved his theorem (known as Hall’s MarriageTheorem), which states a necessary and sufficient condition for theexistence of a maximum matching that saturates one side of a bipartitegraph.Theorem 2.1.2. Hall’s Matching TheoremLet G be a finite bipartite graph with parts X and Y . Let S be asubset of X and N(S) be the set of all the neighbours of vertices in aset S. There exists a matching in G that saturates every vertex in X132.1. Bipartite Graphs and Matchingsif and only if every subset S of X satisfies the following condition:|N(S)| ≥ |S|.Example 2.1.3. The graph below is a bipartite graph whose two partsare X, Y .a5a4a3a2a1b6b5b4b3b2b1X YFigure 2.1: Example of a matching of a bipartite graph saturating XWe can use the K-E Theorem to provide a quick proof of Hall’sMarriage Theorem as follows:Proof. Assume G[X, Y ] is a bipartite graph, |S| ≤ |N(S)| for all subsetS in X.Suppose there exists a vertex cover W = A ∪ B where A ⊂ Y andB ⊂ X such that |W | < |X|. It then follows that |X\B| > |A|. Butsince W is a vertex cover, we have:N(X\B) ⊆ A =⇒ |N(X\B)| ≤ |A|.Therefore |X\B| > |N(X\B)|, which contradicts our assumption that|S| ≤ |N(S)| for all subsets of X. So we obtain that X is a minimumvertex cover. By the K-E Theorem, G has a maximum matching whosesize is |X|, and by definition of matching, this maximum matching mustsaturate every vertex in X.Now suppose there exists a matching M that saturates every ver-tex in X. Since G is bipartite, X must cover all edges in G. Fromthe assumption that M saturates X, it follows that M is a maximummatching in G, and we also have |M | = |X|. Therefore, X is a mini-mum vertex cover, which is equivalent to |N(S)| ≥ |S| ∀S ⊆ X.142.2. Tripartite Case ExtensionHall’s theorem has been used for many real-life matching problems,and applied in combinatorial problems such as creating Latin squares[Bri], and also in group theory [BW09]. We can see that Hall’s theoremis a special case of the K-E Theorem, and it determines an importantbijection condition for min-max equality in bipartite graphs: there ex-ists an X-saturated matching if and only if X is a minimum vertexcover. So we were wondering if a similar property will still hold intripartite graphs, which will be introduced in the next section.2.2 Tripartite Case ExtensionIn bipartite graphs, an edge can be considered as a pair of mutuallyadjacent vertices from both parts. Now we are considering tripartitegraphs, a similar idea in tripartite graph leads to a set of mutuallyadjacent vertices from all three parts, which is a triangle.When trying to extend Hall’s theorem to tripartite graphs, we firstconsider the following idea:Statement 1: For any tripartite graph, if one of the vertex partshas the minimum number of vertices required to cover all the trianglesin this graph, then the size of this part is equal to the maximum size ofa set of independent triangles in this graph.But it is very easy to find a counterexample for this statement:Figure 2.2: Counterexample of statement 1Vertex colours indicate the vertex partition. If we take any twovertices of the same colour, we can cover all four triangles in the graph.However, we can find only one independent triangle in the graph above.152.2. Tripartite Case ExtensionSo it does not look like a promising approach to consider the equalitybetween the size of minimum vertex cover of triangles and maximumindependent triangle set for general tripartite graphs.Since a triangle has three edges, if we have a tripartite graph G thenwe can define a 3-uniform hypergraph H whose vertices correspond toedges in G, and whose hyperedges correspond to the three edges in atriangle in G.G HFigure 2.3: Example of a tripartite graph G and the corresponding hyper-graph HWe can see there is a “matching” of three disjoint hyperedges inH, and three vertices that cover all the hyperedges in H, so the sizeof a minimum vertex cover is equal to the maximum size of a match-ing of disjoint hyperedges in H. These correspond to a minimum T -transversal and a maximum packing in G. Instead, we can consider thesize of a minimum number of edges covering all the triangles and thesize of a maximum packing, and we will get the following statement:Statement 2: For any tripartite graph G, if one side is a minimumT -transversal then τM(G) = νM(G).However, this statement is still false in general. Below is the smallestcounterexample, which is found in [HK98]:162.2. Tripartite Case ExtensionGa1a2b1b2b3c1c2c3 c4Figure 2.4: Counterexample Ga1c1a1c2a2c4a1c3a2c2a2c3b3c2b2c3b1c1b2c1b2c4 b3c4b1c2a1b1a2b3a2b2a1b2 a1b3Figure 2.5: Hypergraph H corresponding to GT (G) : C9Figure 2.6: Triangle graph T (G)The graph G above has nine triangles in total, and we can see172.3. Tuza’s Conjecture and Related Studiesthat every edge is contained by at most two triangles, so we willneed at least five edges to cover all the triangles in G. The edge set{a1b1, a1b2, a1b3, a2b1, a2b2} has size 5 which is one side of G and henceit is a minimum T -transversal. So G clearly satisfies the condition, butthe maximum packing size is 4. To see this, note that finding the max-imum packing in G and finding the maximum size of an independentvertex set in T (G) are equivalent. Since T (G) is C9, a maximum set ofindependent vertex set cannot consist with two consecutive vertices inthis cycle, so the maximum size of an independent set is 4. Therefore,the maximum packing size of G is 4.The smallest size of counterexample is significantly larger than thesmallest counterexample of statement 1, which suggests that the hy-pergraph point of view might be more promising.If we consider a bipartite graph as a special kind of hypergraph,then the K-E Theorem is equivalent to the following statement:For any 2-uniform 2-partite hypergraph H, τ(H) = ν(H).This is just the case r = 2 of a conjecture called “Ryser’s Conjec-ture” [Tuz83]:Conjecture 2.2.1. Ryser’s Conjecture (1971): If H is a r-uniformr-partite hypergraph, then τ(H) ≤ (r − 1)ν(H).This conjecture is still open for r ≥ 4, but the r = 3 case was provedby Ron Aharoni in [Aha01] in 2001, by using a generalized hypergraphversion of Hall’s Theorem, which was proved in 2000 and publishedin [AH00]. However, the hypothesis of their theorem is very strongand the kinds of tripartite graphs we will consider in Chapter 3 do notsatisfy this condition. Therefore, we turn to look at a similar conjecturein the next section.2.3 Tuza’s Conjecture and Related StudiesIn 1981, Tuza conjectured the following:Conjecture 2.3.1. Tuza’s Conjecture: If G is a graph and H is the3-uniform hypergraph whose vertices are the edges of triangles in G,then τ(H) ≤ 2ν(H). [Tuz90]182.3. Tuza’s Conjecture and Related StudiesThis hypergraph version description looks very similar to Ryser’sconjecture, and it is equivalent to the statement τM(G) ≤ 2νM(G) inthe graph G. Note that from Fact 1.3.6 that τM(G) ≤ 3νM(G), so Tuzaconjectured a smaller upper bound of τM(G) for general graphs. It isa weaker relation compared to τM(G) = νM(G) in Statement 2 in theprevious section, but it is not limited to a particular graph class.From the counterexample Figure 2.4 in Section 2.2, it might seemthat for any tripartite graph G, if T (G) is odd-cycle-free, then νM(G) =τM(G). In fact, this is proved in [LBT12] as the following theorem:Theorem 2.3.2. If G is a K4-free graph whose triangle graph T (G) isC2k+1-free for all k ≥ 2, then τM(G) = νM(G).Note that all tripartite graphs are K4-free, but only some of themare applicable to this theorem. For completeness, we will provide aproof with more detail than [LBT12]. Before proving this theorem,we will introduce the Strong Perfect Graph Theorem which was con-jectured by Berge Claude in 1961 [Ber61], and was proved in 2006 byMaria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas.The proof can be found in [CRST06].Theorem 2.3.3. (Strong Perfect Graph Theorem) A graph is perfectif and only if it is C2k+1-free and C2k+1-free.We will also need the following facts:Lemma 2.3.4. For any K4-free graph G, a clique of size n in T (G)corresponds to an edge in G that is shared by n triangles.Proof. Consider three triangles 41, 42, 43 in the graph G with thecorresponding vertices t1, t2, t3 in the triangle graph T (G). Supposet1, t2, t3 are in a clique, so they form a triangle in T (G). Let u1, u2, u3be the three vertices of 41 and u1, u2, u′3 be the three vertices of 42with shared common edge u1u2. Now assume 43 does not contain theedge u1u2. Since t1, t3 and t2, t3 are adjacent, we have the vertices of43 are either (u1, u3, u′3) or (u2, u3, u′3). Then u1, u2, u3, u′3 will form aK4 in G, which contradicts that G was assumed to be K4-free.Fact 2.3.5. For any integer k > 2, C2k+1 contains two cliques sharingan edge.Example Tuza’s Conjecture and Related StudiesFigure 2.7: Example of Fact 2.3.5 in C7The graph above has two cliques coloured by red and blue, and theshared edge of the two cliques is coloured in purple. For any largerk, C2k+1 contains C7 as an induced subgraph, so Fact 2.3.5 followsimmediately from this example.2.3.1 Proof of Theorem 2.3.2Proof. Assume G is K4-free and T (G) is odd cycle-free. By definition,the vertices in T (G) corresponding to a maximum packing of G areindependent, so in T (G) they are all adjacent to each other, whichforms a clique in T (G). So νM(G) is equal to the maximum cliquenumber of T (G), which is:νM(G) = ω(T (G)).By Lemma 2.3.4, a clique in T (G) corresponds to triangles sharingone edge in G. Thus, the minimum number of cliques to cover allvertices in T (G) equals the minimum number of edges covering all thetriangles in G. By definition, τM(G) is equal to the size of minimumT -transversal in G. This gives:θ(T (G)) = τM(G).By Fact 1.1.32, we have χ(T (G)) = θ(T (G)) = τM(G).From above, since νM(G) = ω(T (G)) and τM(G) = χ(T (G)), thismeans that νM(G) = τM(G) if and only if ω(T (G)) = χ(T (G)) for thegraph G.Since we assume T (G) is odd cycle-free and C5 is isomorphic toC5, so T (G) is C5-free. From Lemma 2.3.4 and Fact 2.3.5, we can202.3. Tuza’s Conjecture and Related Studiesshow that T (G) is C2k+1-free for all k ≥ 2. If not, then there are twocliques in T (G) sharing more than one vertex, corresponding to twoedges in G that are common to more than one triangle in G. This is acontradiction since two triangles cannot share more than one commonedge for any simple graph.So T (G) is C2k+1-free, and by assumption, T (G) is C2k+1-free. There-fore T (G) is also C2k+1-free and C2k+1-free. Applying Theorem 2.3.3,we obtain that T (G) is perfect, which implies:χ(T (G)) = ω(T (G)).Therefore, we obtain:τM(G) = νM(G).Therefore, if G is K4-free and T (G) is C2k+1-free, then τM(G) = νM(G).Note that this theorem only defines a sufficient condition for a tri-partite graph to have equality between τM and νM (its triangle graph isC2k+1-free). We have found some tripartite graphs (shown in Chapter3 and 4) whose triangle graph contains many induced odd cycles andthey still satisfy the above equality. However, these graphs are largeand it is also very hard to find a maximum packing in a big graph. Sowe would like to introduce a method in Chapter 4 for presenting alltriangles in any tripartite graph in an easier way.21Chapter 3Agrawal’s Conjecture andEdge M-r-Regular TripartiteGraphIn this chapter, we will explain Hiralal Agrawal’s conjecture andthe relationship between his design structure and edge M-r-regular tri-partite graphs.3.1 Symmetric Design and Agrawal’s ConjectureDefinition 3.1.1. A block design (v, b, r, k, λ) is a family of b subsets(called “blocks”) of a set of v points, such that each block contains kpoints, and each point occurs in r blocks, and any two different pointsare in precisely λ common blocks.Definition 3.1.2. A symmetric (v, k, λ)-design is a block design con-taining v points and v blocks, where each block has size k and any twodifferent points are on precisely λ common blocks. [BJL99]A typical example of symmetric design is (7,3,1)-design. Let the setof 7 points be {0, 1, 2, 3, 4, 5, 6} and let the 7 blocks be given by:{1, 2, 4}, {2, 3, 5}, {3, 4, 6}, {4, 5, 0}, {5, 6, 1}, {6, 0, 2}, {0, 1, 3}.Note that out of the 7 blocks formed by these points, each point occurs3 times and each block contains 3 points, and any two different pointsare in 1 block.The figure below is a typical way of presenting the (7,3,1)-design,which is also known as the Fano plane. In the Fano plane, a block isrepresented as a line or a circle containing three points:223.1. Symmetric Design and Agrawal’s Conjecture0 4163 25Figure 3.1: Fano planeHiralal Agrawal in [Agr66] suggested using symmetric designs in amethod for constructing a new structure in statistical design theory.This structure is defined in [McS05] as the following:Definition 3.1.3. A triple array is an r × c array on v symbolssuch that no two in one row or in one column and having parame-ters (v, k, λrr, λcc, λrc : r × c) such that:1) Each symbol occurs k times2) Any two rows having λrr common symbols.3) Any two columns share λcc common symbols4) Any row and column share λrc common symbols.This construction first needs to pick a block B1 from the symmetricdesign and use its points to labels the rows of the triple array. Useall the other v − k points which are not in B1 (equivalently in B1) tolabel the columns. These form a k× (v−k) array of empty cells whereeach cell has position (i, j), for some i ∈ B1, j ∈ B1. If we considerall the other blocks as the set of symbols, then each cell (i, j) is firstfilled with those symbols representing blocks that do not contain i butdo contain j. We then choose exactly one symbol from each cell suchthat none of these chosen symbols will occur more than once in a rowor in a column. Since we start from a symmetric design, this structureturns out to satisfy all the conditions of a triple array.The structure below is an example formed by the (7,3,1)-design. Ifwe choose to fix the block having points 1, 2, 4 so that these pointslabel the rows, then 0, 3, 5, 6 label the columns. The rest of the blocksare the symbols that are allowed to be filled in the labelled cells. We233.1. Symmetric Design and Agrawal’s Conjecturesimplify these symbols by giving them a name:B = {0, 1, 3} C = {2, 3, 5} D = {3, 4, 6}E = {4, 5, 0} F = {5, 6, 1} G = {6, 0, 2}0 3 5 61 EG CD CE DG2 BE BD EF DF4 BG BC CF FGTable 3.1: Example of Agrawal’s structure from (7,3,1)-designNow we try to choose only one symbol from each cell in Table 3.1such that no symbol occurs more than once in the same row or column,in order to find a triple array from it. However, the best set of symbolsthat we pick cannot satisfy all the conditions of a triple array. Belowis an example of the partially satisfied triple array from (7,3,1)-design:0 3 5 61 E D C2 B E DF4 G BC F GTable 3.2: Sample partial satisfied triple array of Table 3.1In other words, Agrawal’s construction does not apply in every case.However, this is the only known counterexample from his constructionand starting from the next smallest symmetric (11,5,2)-design, we couldobtain the following construction:If we use Z11, take the quadratic residues as the points in the firstblock, B1 = {1, 3, 4, 5, 9}, then non-quadratic residues will be the pointslabeling the columns: B1 = {0, 2, 6, 7, 8, 10}. Assign the remainingblocks as the following symbols:B = {2, 4, 5, 6, 10} C = {3, 5, 6, 7, 0}D = {4, 6, 7, 8, 1} E = {5, 7, 8, 9, 2}F = {6, 8, 9, 10, 3} G = {7, 9, 10, 0, 4}H = {8, 10, 0, 1, 5} I = {9, 0, 1, 2, 6}J = {10, 1, 2, 3, 7} K = {0, 2, 3, 4, 8}243.1. Symmetric Design and Agrawal’s ConjectureThe table below shows all the possible symbols that are allowed tobe in each position:0 2 6 7 8 101 CGK BEK BCF CEG EFK BFG3 GHI BEI BDI DEG DEH BGH4 CHI EIJ CFI CEJ EFH FHJ5 GIK IJK DFI DGJ DFK FGJ9 CHK BJK BCD CDJ DHK BHJTable 3.3: Example of Agrawal’s structure from (11,5,2)-designNow if we pick one symbol from each cell such that all picked sym-bols occur only once in a row and column, then we can obtain a triplearray from this structure. Below is an example triple array obtainedfrom above:0 2 6 7 8 101 C B F E K G3 I E D G H B4 H I C J E F5 G K I D F J9 K J B C D HTable 3.4: Example triple array (10,5,3,2,3: 5×6) from (11,5,2)-designThese leads to Agrawal’s conjecture:Conjecture 3.1.4. If there is a symmetric (v + 1, r, λcc)-design withr − λcc >2, then there is a triple array (v, k, λrr, λcc, λrc : r × c) withv = r + c− 1 [NO¨15]We can see that the (7, 3, 1)-design where 3 − 1 = 2 ≯ 2 is notincluded in this conjecture. The converse of this conjecture was provedin [PWY05]. One of the infinite families of triple arrays that has beenfound is named “Paley Triple Arrays”. While all the previous workabout this conjecture is in design theory [Wal14], we found a graphicalmethod to approach this conjecture, which will be introduced in thenext section.253.2. Agrawal’s Construction and Tripartite Graph3.2 Agrawal’s Construction and Tripartite GraphConsider Agrawal’s construction from any symmetric (v+ 1, r, λcc)-design where we pick a block B1 and let W be the remaining v blocks.We can make a tripartite graph whose vertex parts are: B1 (r vertices),B1 (v+1−r vertices) and W (v vertices). We make a complete bipartitegraph on B1 and B1, so that these edges represent the cells in the arrayin Agrawal’s construction. Any vertex i ∈ B1 and a block A ∈ Ware adjacent if i /∈ A, and any vertex j ∈ B1 is adjacent to a blockA ∈ W if j ∈ A, so that these represent the cells in which the symbolcorresponding to A appears in Agrawal’s array. Each vertex in W isadjacent to r − λcc vertices in each of the two other vertex sets.•B(0, 1, 3)•C(2, 3, 5)•D(3, 4, 6)•E(4, 5, 0)•F (5, 6, 1)•G(6, 0, 2)1240356Figure 3.2: Agrawal’s construction from (7,3,1)-design in tripartite graphFrom Agrawal’s construction, we have obtained a special kind oftripartite graph that has the exact same number of edges in each sideand such that every edge is shared by the same number of triangles.We define this kind of tripartite graph as the following:Definition 3.2.1. A tripartite graph G is edge M-r-regular if everyedge in G is shared by exactly r triangles.263.2. Agrawal’s Construction and Tripartite GraphNote that a tripartite graph G being edge M-r-regular is not equiv-alent to it being edge regular, since an edge M-r-regular graph doesnot need to be a regular graph. Like the example from above, thevertices from different vertex sets have different degrees, where edgeregular graphs are required to be regular graphs. If G[A,B,C] is edgeM-r-regular, then every edge in G is shared by the same number oftriangles, so we obtain that every side has the same number of edges,that is:|EAB| = |EAC | = |EBC |.Let ET be a T -transversal of an edge M-r-regular tripartite graphG[A,B,C]. Since every edge is shared by r triangles, so ET covers atmost |ET | · r triangles. But we know that the total number of trianglesin G is |EAB| · r. So for any T -transversal, we have:|ET | · r ≥ |EAB| · r =⇒ |ET | ≥ |EAB|This gives every edge side of G is a minimum T -transversal.It is interesting that any regular bipartite graph satisfies the Hall’smatching condition, which is: one part of regular bipartite graph is aminimum vertex cover. And now we found a similar result in tripartitegraph as any edge M-r-regular tripartite graph always satisfies that oneside is a minimum T -transversal.To make a triple array, we need to pick one symbol from each cellsuch that every picked symbol only appears once in a row and columnof all positions. From the perspective of the graph that we constructedfrom Agrawal’s method, a triple array is equivalent to picking one tri-angle from each edge of the complete bipartite side such that all thesepicked triangles are pairwise edge-disjoint. If any two of these trianglesare not edge-disjoint, then the corresponding symbols will appear morethan once in a column or in a row. This is exactly the same as findinga (maximum) packing that saturates a side of the tripartite graph, sothat we can have a maximum packing whose size is equal to the size of aminimum T -transversal. So we can generalize the Agrawal’s conjecturein graph perspective as the following:Conjecture 3.2.2. For any edge M-r-regular tripartite graph G (r ≥3), τM(G) = νM(G).Our approach to this conjecture will be introduced in the next chap-ter.27Chapter 4Triangle Presentation ofTripartite GraphsIn this chapter, we will introduce a method for listing all trianglesfor any tripartite graph.4.1 Method of Listing TrianglesA common method of studying triangles of a given graph is bystudying its triangle graph. However, the triangle graph does not nec-essarily contain the information that it came from a tripartite graph.Likewise, it is also hard to determine whether or not a given graph isthe triangle graph of a tripartite graph. So we need an easier way topresent all of the triangles in any tripartite graph in order to studythem.Let G[A,B,C] be any undirected finite tripartite graph with vertexpartition sets: A := {ai}, B := {bj} and C := {ck} and the edgesubsets: EAB, EAC and EBC . We assumed EAB has the fewest numberof edges. Without loss of generality, we assume every vertex and edge inG is contained in at least one triangle. Since a triangle inG contains onevertex from each part, we can name any triangle in G unambiguouslyas: aibjck and clearly it contains three edges from different edge sets:aibj, aick and bjck. If we make an array, then we can use all the verticesof A to label the columns and all the vertices of B to label the rowsaccording to the numerical order of their subscripts in the set. If thereis a triangle aibjck in G, then we can put ck in this cell.284.1. Method of Listing Trianglesa1a2a3b1b2b3b4c1 c2 c3 c4 c5Figure 4.1: Example graph GFor example, the graph G above is a tripartite graph whose alledges and vertices are contained by at least one triangle. The array ofG below shows all the triangles in G.a1 a2 a3b1 ∅ c1c2c5 c2c5b2 c1c3 c1 ∅b3 c3 ∅ c2c4c5b4 ∅ c5 ∅Table 4.1: Array of triangles of GFor the non-adjacent pairs of vertices between A and B, we put“∅” in those cells. Both c1 and c3 appear in the a1 column and b2 row.It shows the existence of the two triangles: a1b2c1 and a1b2c3, whichclearly presents the two triangles are sharing the edge a1b2. So if a cellof ai and bj contains n vertices from C, then it is indicating there aren triangles sharing the edge aibj. If there are some triangles sharing294.1. Method of Listing Trianglesan edge from EAC or EBC , then we can see this from repeated valuesof subscripts in a column or in a row. For example, c3 appears in twocells of the a1 column. It shows that there are two adjacent trianglesa1b2c3 and a1b3c3 sharing the edge a1c3. So we can conclude that if anyck appears λ times in the ai column, then there are λ triangles sharingthe edge aick. Similarly, if ck appears δ times in the same bj row, thenthis indicates δ triangles sharing the edge bjck.To simplify the presentation of the array of triangles, we can presentall the triangles ofG by just listing the value of the subscripts of verticesin C in the cells of the array, and call the result the “Triangle ArrayRepresentation” of G, denoted by M . We denote the cell in the aicolumn and bj row position by Mi,j.∅ 125 2513 1 ∅3 ∅ 245∅ 5 ∅Table 4.2: Triangle array representation of GFrom M , we can see that “1” appears in M1,2 and M2,1 indicatingthe existence of the four edges: a1c1, b2c1 and a2c1, b1c1. Since inthe example of Table 4.2, a2 and b2 are adjacent, a2b2c1 is a triangle.Hence, “1” appears in M2,2. And a1, b1 are not adjacent, so “1” cannotoccur in M1,1. We name those cells having “∅” as non-existing cellsand these cells having entries as existing cells. Then we can obtain thefollowing fact in general:Fact 4.1.1. If value “k” appears in both Mi1,j1 and Mi2,j2 then “k”must also appear in Mi2,j1 and Mi1,j2 as long as they are existing cellsof M .If an M does not conflict with Fact 4.1.1 for all k, then we canalways find an undirected tripartite graph G such that every edge inG is contained in at least one triangle. Essentially, M contains allof the information in T (G) of any undirected tripartite graph G, butcompared to T (G), M is easier to visualize for any G which has largesize, and preserves the tripartite structure of G.304.2. Minimum T -Transversal in Triangle Array Representation4.2 Minimum T -Transversal in Triangle ArrayRepresentationIn the construction of the triangle array representation of G, theexisting cells of M represent the edges of the smallest side of G. InSection 2.2 statement 2, we considered the condition that the small-est side of a tripartite graph is a minimum T -transversal. So in thissection, we find an equivalent condition for the smallest side EAB tobe a minimum T -transversal, and how it appears in the triangle arrayrepresentation.It follows from the proof of Hall’s Theorem in Chapter 2 that forany bipartite graph G[X, Y ]:X is a minimum vertex cover ⇐⇒ ∀S ⊆ X, |N(S)| ≥ |S|.Similarly, in a tripartite graph G[A,B,C], if EAB is a minimum T -transversal, then for any subset S of EAB, the set of triangles coveredby S cannot be covered by a set of edges from the other two sides whosesize is less than |S|. Denote YS ⊆ (EAC ∪ EBC) to be a minimum setof edges that covers all the triangles which are covered by S ⊆ EAB,and then we can obtain the following theorem:Theorem 4.2.1. For any tripartite graph G[A,B,C]:EAB is a minimum T-transversal ⇐⇒ ∀S ⊆ EAB, |YS| ≥ |S|.Proof. Assume every S ⊆MAB satisfies the condition: |YS| ≥ |S|.Let W = S1 ∪ WAB be a T -transversal, where WAB ⊂ EAB andS1 ⊂ (EAC ∪EBC). Suppose |W | < |EAB|, then |W | − |WAB| = |S1| <|EAB|−|WAB|. Let S be the set EAB \WAB. Necessarily, S1 must coverall the triangles that covered by S. Since YS is a minimum set of edgesthat covers all the triangles which are covered by S, by definition,|YS| ≤ |S1| < |S| and this contradicts the assumption. Therefore|W | ≥ |EAB|, which implies EAB is a minimum T -transversal.Now assume |EAB| = τM. Suppose there exists a set S ⊆ EAB suchthat |YS| < |S|. Then there exists a smaller sized set of edges thatcovers the set of triangles covered by S, and (EAB \ S) ∪ YS is a T -transversal which is smaller than EAB, contradicting the minimality ofEAB. Hence, for every S ⊆ EAB, |YS| ≥ |S|.314.2. Minimum T -Transversal in Triangle Array RepresentationSince the triangle array representation M is a way of listing all thetriangles in a tripartite graph G[A,B,C] where EAB is the smallestside, if G satisfies the condition in Theorem 4.2.1, then we say all theexisting cells of M represent a minimum T -transversal. Before movingon to the array version of the theorem above, we need to know whatthe edges and a T -transversal look like in M .We say that each existing cell covers its entries and these cellsrepresent the edges in EAB. Let MAB = {Mij∣∣∀aibj ∈ EAB} be the setof all existing cells of M . If a value k appears in one column ai of M ,this represents the edge aick in G, which we can imagine as a straightline in the column ai covering all the entries in that column with valuek, which we denote by Ci(k). Similarly for the rows, we can picturethe bjck edge as a straight line in the row bj covering entries with valuek and denote it as Rj(k). By definition, a T -transversal covers allthe triangles of a graph, so a collection of existing cells and straightlines that covers all the entries in M is equivalent to a T -transversalof the original graph G. Clearly, all the existing cells in M cover allthe entries in M , so MAB represents a T -transversal. Now we needto find how does the condition in Theorem 4.2.1 act in triangle arrayrepresentation.Example 113 ∅S1∅ 125 2513 1 ∅13 ∅ 245∅ 5 ∅MABC1(3)R2(1)Figure 4.2: Example subset S1 of MABConsider the example triangle arrary representation from Section4.1. Take a subset S1:= {M1,2,M1,3,M2,2}, which represents three edgesS1E := {a1b2, a1b3, a2b2} ⊂ EAB that covers four triangles: a1b2c1,a1b2c3, a1b3c3, a2b2c1. We can see these triangles can be covered by thetwo edges: a1c3 and b2c1. So if we let YS1E = {a1c3, b2c1}, then (EAB \S1E) ∪ YS1E is a smaller T -transversal compared to EAB. In terms of324.2. Minimum T -Transversal in Triangle Array Representationtriangle array representation, if we take (MAB\S1)∪{C1(3)}∪{R2(1)},then we can still cover all the entries in M and it has smaller size thanMAB.So from Theorem 4.2.1 and the correspondence between a graphand its triangle array representation, if MAB represents a minimumT -transversal of G, then the following statement must hold:Proposition 4.2.3. Let G[A,B,C] be an undirected simple tripartitegraph, M be the corresponding triangle array representation and US bea minimum set of straight lines that covers all the entries which arecovered by a subset S of MAB, then |MAB| = τM(G) if and only if everyS ⊆MAB satisfies the following condition:|US| ≥ |S|.If MAB of a given M satisfies Proposition 4.2.3, then we can sayMAB represents a minimum T -transversal of its original graph.Now we define the “appearance matrix” A(k)S for each value “k”occurring in a cell of a subset S of MAB, where A(k)S has the same rowand column labeling as M . Each position in A(k)S has “1” where “k”appears in S of the corresponding position in M , and “0” everywhereelse. For instance, the appearance matrices of S1 in Example 4.2.2 arethe following: 0 0 01 1 00 0 00 0 0Table 4.3: Example of A(1)S10 0 01 0 01 0 00 0 0Table 4.4: Example of A(3)S1where A(2)S1 , A(4)S1 and A(5)S1 are all zero matrices.Essentially, a line covering all the “1” in a column or in a row inA(k)S is equivalent to a straight line that covers all the entries having334.2. Minimum T -Transversal in Triangle Array Representationvalue “k” in S, which corresponds to an edge from EAC or EBC , re-spectively. Now we apply a (0,1)-matrix version of Ko¨nig’s Theorem[VLWW01]:Theorem 4.2.4. The minimum number of lines of (0,1)-matrix thatcontains all the 1’s of the (0,1)-matrix is equal to the maximum numberof 1’s in the (0,1)-matrix, no two on a line.This tells us the smallest number of straight lines to cover all theentries having value “k” in S is equal to the maximum number ofentries having value “k” where no two are in the same row or in thesame column, and these lines correspond to a minimum set of edgesfrom EAC ∪ EBC that covers all the triangles containing ck in S. Foreach value k, we define S(k) to be the smallest number of straight linescovering all the entries in S with value “k”. Combining Proposition4.2.3 and Theorem 4.2.4, we can obtain the following:Corollary 4.2.5. For a given M of a tripartite graph G[A,B,C],|MAB| = τM if and only if every S ⊆ MAB satisfies the following con-dition:|C|−1∑k=0S(k) ≥ |S|.Notice that the minimum set of lines covering all the entries in Swith value k is independent for each k. So we can minimize |US| bychoosing a minimum set of lines covering the entries of each value k inS, and so |US| =|C|−1∑k=0S(k).Now we want to find a maximum packing of the tripartite graphwhich size is equal to τM(G). Notice that a packing can be presented intriangle array representation as a selection of entries from MAB whereat most one entry has been picked from every cell, and these entries donot appear more than once in a row or a column. If we select the entrieswith value k separately for each k, then Theorem 4.2.4 guaranteessuch a selection of maximum size S(k). However, the union of theseselections will most likely result in a set of entries with more than onein the same cell. Allowing for this circumstance, we define the term“pseudo-packing” in triangle array representation as the following:344.3. Induced Odd Cycles in Triangle Array RepresentationDefinition 4.2.6. A pseudo-packing PS of an S ⊆MAB is a choice ofentries from the cells in S such any value “k” appears no more thanonce in one row or in one column, where each cell can have more thanone entry being picked.Then by Theorem 4.2.4, the maximum number of entries with valuek that we can pick in a pseudo-packing is equal to S(k). Combiningthis result with Corollary 4.2.5 we can also obtain that:Theorem 4.2.7. .MAB represents a minimum T-transversal⇐⇒∀S ⊆MAB, ∃ PS, |PS| =|C|−1∑k=0S(k) ≥ |S|.If an MAB satisfies Proposition 4.2.3, then in particular this theo-rem guarantees that there exists a pseudo-packing of MAB such that|PMAB | ≥ |MAB|. Our next step is to make this PMAB less “pseudo”until there is no cell that contains more than one entry of PMAB ; thenwe have found a real packing. Our goal is to find an efficient proceduresuch that we can obtain a maximum packing from this pseudo-packing.If every cell in MAB has exactly one entry in this packing, then equiv-alently, we obtain a packing of triangles whose size is equal to theminimum T -transversal, which means τM(G) = νM(G). If this can bedone whenever G is any edge M-r-regular tripartite graph where r ≥ 3,then we would have proven the Conjecture 3.2.2. We will introduce atechnique to help find a maximum packing from a “pseudo-packing”in Chapter 6. For now, we know the statement 2 in Section 2.2 hascounterexamples, but Agrawal’s conjecture does not have any knowncounterexample. So we focus on those tripartite graphs constructedfrom Agrawal’s method, which will always give edge M-r-regular tri-partite graphs.4.3 Induced Odd Cycles in Triangle ArrayRepresentationFrom Chapter 3, it is clear that every side of M-r-regular tripar-tite graph from Agrawal’s construction has the same number of edges,354.3. Induced Odd Cycles in Triangle Array Representationwhere one of the sides can be seen as a complete bipartite subgraph.Here we could take the complete bipartite side as the row and the col-umn of the triangle array representation so all the cells are existingcells.b1b2b3a1a2a3a4c1c2c3c4c5c646 23 24 3614 13 45 3516 12 25 56MFigure 4.3: Agrawal’s construction from (7,3,1)-design in tripartite graphand its array representationFrom Chapter 3, we know that every side of an edge M-r-regulartripartite graph is a minimum T -transversal. So clearly, for edge M-r-regular tripartite graphs, MAB will satisfy the Proposition 4.2.3.From Theorem 2.3.2, we know that if a triangle graph of a tripartitegraph does not contain any induced odd cycle, then it has νM = τM.We found the converse of this theorem does not always hold, and wewill show some examples of induced odd cycles in the triangle arrayrepresentation.An induced odd cycle in a triangle graph is a sequence of an oddnumber of vertices where any vertex is only adjacent to the consecu-tive vertices in this sequence. So in triangle array representation, aninduced odd cycle will be presented as a cyclic sequence of an oddnumber of entries which satisfies the following conditions:1. Any two consecutive entries in the sequence are either in the samecell or have the same value in a common row or in a commoncolumn;364.3. Induced Odd Cycles in Triangle Array Representation2. Any two non-consecutive entries with the same value in the se-quence must be in different rows and columns.3. Any two non-consecutive entries with different value cannot be inthe same cell.We can see from Figure 4.3, there are many induced odd cycles inits triangle graph, the entries highlighted in red below is an inducedC9 in M .46 23 24 3614 13 45 3516 12 25 56Table 4.5: Example of an induced odd cycle in MHowever, for each edge M-r-regular tripartite graph from Agrawal’sconstruction where r ≥ 3, even though we can find many inducedodd cycles in its triangle graph, we might still find that the maximumpacking has size equal to τM. Below is a triangle array representationof graph from (11,5,2)-design.260 140 125 246 450 156678 148 138 346 347 167278 489 258 249 457 579680 890 358 369 350 569270 190 123 239 370 179Table 4.6: Example triangle array representation of graph from (11,5,2)-design and with an example induced C92 1 5 4 0 68 4 3 6 7 17 8 2 9 4 56 0 8 3 5 90 9 1 2 3 7Table 4.7: Example of a maximum packing of Table 4.6Consider the cases above and Theorem 2.3.2, it gives us a sensethat the existence of induced odd cycles in triangle graphs will not374.3. Induced Odd Cycles in Triangle Array Representationbe a reason causing the inequality between the τM and νM. Since thesmallest counterexample from (7, 3, 1)-design is an edge M-2-regulartripartite graph, we first focus on this smallest counterexample graphclass and try to find some properties which it has and may result inthe inequality between τM(G) and νM(G). The result will be presentedin the next chapter.38Chapter 5Maximum Packing of EdgeM-2-Regular TripartiteGraphsThis chapter presents our main results on edge M-2-regular tripartitegraphs.5.1 Properties of Edge M-2-Regular TripartiteGraphsWe provide a result that comes from the smallest counterexampleof Agrawal’s construction and provide a proof of this result.Theorem 5.1.1. If G is edge M-2-regular tripartite graph, then τM(G) =νM(G) if and only if T (G) is bipartite.Before proving this theorem, we will provide some facts for laterproof in Section 5.2.Lemma 5.1.2. Let G be any edge M-r-regular tripartite graph, thenT (G) is k-regular graph where k = 3 · (r − 1).Proof. By definition, every edge in G is contained in r triangles soevery edge of every triangle is also shared by (r − 1) other triangles,and hence every triangle in G is adjacent to 3 · (r − 1) triangles. Thismeans every vertex in T (G) is adjacent to exactly 3 ·(r−1) neighbours,and therefore T (G) is 3 · (r − 1)-regular.Fact 5.1.3. For any bipartite graph G[X, Y ]:∑v∈Xd(v) =∑v∈Yd(v).395.1. Properties of Edge M-2-Regular Tripartite GraphsProof. It follows directly from the definition that each edge has oneendpoint in X and the other endpoint in Y so the sum of the degreesof all vertices in X is the number of edges in G[X, Y ], which is samefor the sum of the degrees of all vertices in Y .Fact 5.1.4. For any k-regular bipartite graph G[X, Y ] where k ≥ 1,|X| = |Y |.Proof. By Fact 5.1.3, we have:|X| · k =∑v∈Xd(v) =∑v∈Yd(v) = |Y | · k =⇒ |X| = |Y |.5.1.1 Proof of Theorem 5.1.1Proof. Let G be any edge M-2-regular tripartite graph so that everyedge in a minimum T -transversal of G is shared by at most two tri-angles. If there are n triangles in G, then the minimum T -transversalsize is greater than or equal ton2.τM(G) ≥ n2. (5.1)Since there are n triangles in G, every triangle has three edges, andevery edge is shared by exactly two triangles, so |E(G)| = 3n2andeach side has the same number of edges, which is|E(G)|3=n2. So theminimum T -transversal size has to be less or equal to the size of anyedge side.τM(G) ≤ n2. (5.2)From (5.1) and (5.2), we see τM =n2.“=⇒” Assume T (G) is bipartite. Then by Lemma 5.1.2, d(v) = 3for all vertices in T (G). By Fact 5.1.4 we have:|X| = |Y | = n2.405.2. Orientability of the Surface Formed by an Edge M-2-Regular Tripartite GraphSince the maximum independent vertex set of T (G) is equivalent tothe maximum packing size of G, so we obtain:|X| = n2= νM(G) =⇒ νM(G) = τM(G).“⇐=” Assume τM(G) = νM(G). From above, we obtain τM(G) =νM(G) =n2which is equivalent to the size of a maximum independentvertex set in T (G), denoted |X|. Since T (G) is 3-regular, we have:∑v∈Xd(v) = 3|X| = 3n2.So X indicates that T (G) has at least3n2edges. Since |V (T (G))| = n,by Fact 1.1.17,|E(T (G))| = 3n2.This means T (G) has exactly3n2edges. Now suppose T (G) is notbipartite, so by definition, there exists a vertex set which containssome edges both of whose endpoints are not in X. This contradict theabove as X contains one endpoint of all edges in T (G). Hence T (G) isbipartite.5.2 Orientability of the Surface Formed by anEdge M-2-Regular Tripartite GraphWe will provide some background before moving on to our result.In graphs, if two triangles are not independent, they are eitherjoined by a vertex or by an edge. Let G be an edge M-2-regular tri-partite graph, then the simplicial 2-complex [Mun18] X(G) formed bythe union of triangles of G is naturally viewed as a triangulated surfacewithout boundary.Every triangle has two orientations by cyclically ordering its ver-tices. For example if we let triangle vertices be “1”, “2” and “3”, theycan be ordered either 123 or 132.415.2. Orientability of the Surface Formed by an Edge M-2-Regular Tripartite Graph1 32312Figure 5.1: Example of triangle orientationWe define the orientability of a surface as the following:Definition 5.2.1. If every triangle in a triangulated surface can beoriented such that any two triangles sharing an edge have oppositeorientation on common edge, then the surface is orientable.A typical example of an orientable surface is “sphere” and a well-known non-orientable surface is “Mobius Strip”.Sphere Mobius StripFigure 5.2: Example of a sphere and a mobius stripIf we assign the three colours: red, green and blue to three parti-tioned vertex sets of a tripartite graph, then we can distinguish trianglesin this graph by fix a triangle orientation with vertex colour sequence:red→green→blue (“RGB”) so that any orientation of a triangle in thistripartite graph either agrees with “RGB” or disagrees with “RGB”.Then for any two edge-joint triangles, one must agree with RGB andthe other must disagree with RGB.Figure 5.3: Example of two edge-joint triangle with one orientation agreesRGB and the other orientation disagrees with RGB425.2. Orientability of the Surface Formed by an Edge M-2-Regular Tripartite GraphIn any orientation of an orientable surface, we can distinguish thetriangles whose orientation agrees or disagrees with RGB. Any twotriangles that agree with RGB must be edge-disjoint, so this can be usedto partition all the triangles of G into two sets of edge-disjoint triangles.And this is equivalent to all vertices of T (G) can be partitioned intotwo independent sets =⇒ T (G) is bipartite.Conversely, suppose T (G) is bipartite, then all adjacent pair of ver-tices must be in different vertex partition sets. For these correspondingtwo sets of triangles in G, we can orient the triangles in one set to agreewith RGB, and the triangles in the other set to disagree with RGB.So for any two adjacent triangles of G, they must have different orien-tations. Therefore, X(G) is orientable and we obtain the theorem asbelow:Theorem 5.2.2. The surface X(G) is orientable if and only if T (G)is bipartite.Combine the Theorem 5.1.1 and Theorem 5.2.2, we could obtain:Corollary 5.2.3. If G is edge M-2-regular tripartite graph, then τM(G) =νM(G) if and only if X(G) is orientable.For example, K2,2,2 is an edge M-2-regular tripartite graph. It iseasy to see from below that it forms a closed orientable surface (whichcalled “octahedron”).Figure 5.4: Surface formed by triangles in K2,2,2As another example, the graph from Agrawal’s construction using(7,3,1)-design turns out to be homeomorphic to a real projective plane,which is a non-orientable surface.43Chapter 6Pseudo-Packing Technique inEdge M-r-Regular TripartiteGraphIn Chapter 3 and 4, we showed that if the size of a maximum packingin a triangle array representation of an edge M-r-regular graph is equalto the size of a minimum T -transversal, then we can select exactlyone entry from every existing cell such that no two of these entriesare having same value in one row and column. We constructed andwill show the method for finding a maximum packing from pseudo-packing in the form of triangle array representation that works forgeneral tripartite graph which one side is a minimum T -transversal.By Theorem 4.2.7, if MAB represents a minimum T -transversal,then we must have a pseudo-packing which size has at least τM. Weknow that for any edge M-r-regular tripartite graph G[A,B,C], EAB isa minimum T -transversal, thus MAB satisfies the condition of Theorem4.2.7, hence we can find a pseudo-packing of size τM from MAB. Wewill find a maximum packing from a pseudo-packing and we name thismethod as: “pseudo-packing technique”. We will show this methodby showing the procedures on the edge M-3-regular tripartite graphobtained from (11,5,2)-design.For the triangle array representation of a certain graph G, we willfind a maximum sized “pseudo-packing” first.260 14 578 13 4689 2 4570 8 39 562 30 179Table 6.1: Example pseudo-packing of Table 4.644Chapter 6. Pseudo-Packing Technique in Edge M-r-Regular Tripartite GraphBy Fact 4.1.1, we know that if entries with value “k” appear inboth Mi1,j1 and Mi2,j2 , then the entries with “k” should also appearin Mi2,j1 ,Mi1,j2 if they belong to MAB. So we can “switch” these twopicked entries from Mi1,j1 and Mi2,j2 to Mi2,j1 and Mi1,j2 in this pseudo-packing.For example, since both M1,1 and M5,5 of the pseudo-packing inTable 6.1 have the entry “0”, where M1,5 and M5,1 are empty, we canmake a “switch” and reduce the number of empty cells by two for thispseudo-packing.26 14 5 078 13 4689 2 4570 8 39 560 2 3 179Table 6.2: Example after a switch of Table 6.1Follow this “switch” process to reduce the number of empty cellsuntil we cannot find any switch to reduce the number of empty cells ofthis pseudo-packing.2 1 5 4 0 68 4 3 6 7 17 8 2 45 96 0 8 39 50 9 1 2 3 7Table 6.3: Example after six switches of Table 6.1Detailed switch steps are shown in Appendix A.1. We can see fromabove that after the sixth switch, if we do not want to increase thenumber of empty cells in this pseudo-packing, then we have to look forwhere after the switch has been made, the number of empty cells doesnot change.45Chapter 6. Pseudo-Packing Technique in Edge M-r-Regular Tripartite Graph2 1 5 4 0 68 4 3 6 7 17 8 2 4 596 0 8 39 50 9 1 2 3 7Table 6.4: Example of the seventh switch of Table 6.1After this switch, M6,3 and M4,4 are having the same value entries“9”, where M4,3 and M6,4 are the currently empty cells. So we canmake a switch to reduce the number of empty cells by two and hencewe obtain a maximum packing.2 1 5 4 0 68 4 3 6 7 17 8 2 9 4 56 0 8 3 5 90 9 1 2 3 7Table 6.5: Example after eight switch of Table 6.1In summary, when determining the next action, a switch reducingthe number of empty cells by 2 is chosen before one that reduce thenumber of empty cells by 1, which is chosen before a switch that doesnot reduce the number of empty cells. However, for those switches re-ducing the same number of empty cells, we do not have certain criteriato determine which one is better.We have tested this method in other edge M-r-regular tripartitegraphs (For example, see Appendix A.2) and other general tripartitegraphs that satisfy one side being a minimum T -transversal. We havefound that if a graph does not have the equality τM = νM, then there willalways be at least one empty cell and some other cells with more thanone entries in the pseudo-packing. As we assume every edge in graph isshared by more than one triangle, every value must occur at least twicein a row or column in the graph’s triangle array representation. So if atripartite graph G satisfies 4.2.7 and has τM(G) > νM(G), then we willget into endless switches and cannot reduce the number of empty cellby using this method. For example, if we use the same process in thetriangle array representation of the graph from Agrawal’s construction46Chapter 6. Pseudo-Packing Technique in Edge M-r-Regular Tripartite Graphusing (7,3,1)-design, we will perform endless switches not knowing whento stop. For small graphs, we can find the pattern of repetitive switcheseasily so that we can stop after the repetitive steps occur. However,even though we apply this method only to finite graphs, find repetitivepattern can be extremely hard for large graphs.If we measure the progress by the number of empty cells in thepseudo-packing, then this technique can be stopped when there is nolonger possible to reduce the number of empty cells. This leads us toeither of the two cases below without reducing the progress:(1) Perform endless switches or(2) Stop as every existing cell is filledSo the result from technique guarantees a maximal packing if wekeep one entry only in every non-empty cell from the result. And as faras we have tested, this technique always reaches a maximum packingof G even if τM(G) > νM(G). Based on our experiment, we conjecturedthe following statement without a proof:Conjecture 6.0.1. If we define the “pseudo-packing technique” as thefollowing:First find a maximum sized pseudo-packing. Then make switcheswith respect to the Fact 4.1.1 with progress measured by reducing num-ber of empty cells and stop this technique when either the following twocases happening:(1) Perform endless switches or(2) Stop as every existing cell is filledThen it is always possible to reach a maximum packing with thismethod.Our potential future research for this “pseudo-packing technique”will find efficiency criteria of those switches making the same progress.From the previous example, suppose we choose a different entry toswitch from the first step, then our experiment shows that it can takelonger process to find a maximum packing through this technique.Therefore, finding the criteria of the efficiency is helpful for prove thisconjecture theoretically.47Chapter 7Conclusion and Future Work7.1 ConclusionIn this thesis, we looked couple results in order to help us to proveHiralal Agrawal’s conjecture.In Chapter 2, we first focused on generalizing Hall’s Theorem intripartite graph as the graphs obtained from Agrawal’s method auto-matically satisfy Hall’s condition in tripartite graph:If one side of a tripartite graph G is a minimum T -transversal, thenτM(G) = νM(G).However, we have found counterexample to the above statement.Later, we focused on finding a stronger condition for obtaining anequivalent relation between τM(G) and νM(G) by looking at a resultfrom Tuza’s conjecture related research:If G is tripartite graph and T (G) is induced odd cycle-free, thenτM(G) = νM(G).However, the converse of the theorem above does not hold and wehave found counterexamples from graphs obtained through construc-tions from Agrawal’s method.In Chapter 3, we have defined a type of graph as “edge M-r-regulartripartite graph” and generalized the Agrawal’s conjecture as the fol-lowing:For any edge M-r-regular tripartite graph G (r ≥ 3), τM(G) = νM(G).In Chapter 4, we introduced “triangle array representation” forstudying edge M-r-regular tripartite graph efficiently and we used itto show a counterexample of the converse of the Theorem 2.3.2.We have proved for any edge M-2-regular tripartite graphG, τM(G) =νM(G) if and only if T (G) is bipartite in Chapter 5 and we use this re-sult to obtain another result: G forms an orientable surface if and only487.2. Future Workif T (G) is bipartite, which is equivalent to τM(G) = νM(G). It is aninteresting direction to look at this question in a topological way.In Chapter 6, we came up with a “pseudo-packing technique” forfinding maximum packing in triangle array representation but we havenot found any efficiency criteria for each switch.7.2 Future WorkFrom our random general tripartite graph case for finding stoppingcriteria of the “pseudo-packing procedure”, we observed that:Statement: For tripartite graph G whose any of its edge is sharedby at least three triangles, then τM(G) = νM(G).Note that the statement above does not require any side of G to bea minimum T -transversal and we have not found any counterexamplefor the statement above. This is more like a tripartite graph version ofKo¨nig-Egerva´ry Theorem. If we can prove this statement, or prove itwith a stronger condition: if one side of G is a minimum T -transversal,then we can prove the Conjecture 3.2.2 and hence prove the HiralalAgrawal’s conjecture. But we do not have enough evidence to call itas a conjecture or any appropriate approach for proving it yet.Below are interesting open questions left from this thesis research:1. Will the orientability of a triangulated surface be helpful for de-termining whether or not there exists a maximum packing of sizeis equal to the minimum edge cover of all triangles in edge M-r-regular tripartite graph?2. Will the “pseudo-packing technique” always produce a maximumpacking of a tripartite graph?3. What are the selection criteria among the switches making thesame progress in the “pseudo-packing technique”?4. Will the following generalized Ko¨nig-Egerva´ry Theorem be true?That is: For every tripartite graph G whose edges are each in atleast three triangles, the size of minimum edge cover of trianglesand the size of maximum packing are equal.49Bibliography[Agr66] Hiralal Agrawal. Some methods of construction of de-signs for two-way elimination of heterogeneity1. Journal ofthe American Statistical Association, 61(316):1153–1171,1966. → pages 23[AH00] Ron Aharoni and Penny Haxell. Hall’s theorem for hyper-graphs. Journal of Graph Theory, 35(2):83–88, 2000. →pages 18[Aha01] Ron Aharoni. Ryser’s conjecture for tripartite 3-graphs.Combinatorica, 21(1):1–4, 2001. → pages 18[Ber61] Claude Berge. Farbung von graphen, deren samtlichebzw. deren ungerade kreise starr sind. WissenschaftlicheZeitschrift, 1961. → pages 19[BJL99] Thomas Beth, Dieter Jungnickel, and Hanfried Lenz. De-sign theory. Cambridge University Press, 1999. → pages22[BLW86] Norman Biggs, E Keith Lloyd, and Robin J Wilson. GraphTheory, 1736-1936. Oxford University Press, 1986. →pages 13[BM+76] John Adrian Bondy, Uppaluri Siva Ramachandra Murty,et al. Graph theory with applications, volume 290. Macmil-lan London, 1976. → pages 1[Bri] Brilliant.org. Applications of hall’s mar-riage theorem. https://brilliant.org/wiki/applications-of-hall-marriage-theorem/. → pages15[BW09] John R Britnell and Mark Wildon. Commuting conjugacyclasses: an application of hall’s marriage theorem to group50Bibliographytheory. Journal of Group Theory, 12(6):795–802, 2009. →pages 15[CRST06] Maria Chudnovsky, Neil Robertson, Paul Seymour, andRobin Thomas. The strong perfect graph theorem. Annalsof mathematics, pages 51–229, 2006. → pages 19[HK98] Penny E Haxell and Yoshiharu Kohayakawa. Packing andcovering triangles in tripartite graphs. Graphs and Com-binatorics, 14(1):1–10, 1998. → pages 9, 16[HKT12] Penny Haxell, Alexandr Kostochka, and Ste´phanThomasse´. Packing and covering triangles in k 4-free pla-nar graphs. Graphs and Combinatorics, 28(5):653–662,2012. → pages 9, 10[LBT12] S Aparna Lakshmanan, Cs Bujta´s, and Zs Tuza. Smalledge sets meeting all triangles of a graph. Graphs andCombinatorics, 28(3):381–392, 2012. → pages 10, 19[McS05] John P McSorley. Double arrays, triple arrays and bal-anced grids with v= r+c- 1. Designs, Codes and Cryptog-raphy, 37(2):313–318, 2005. → pages 23[Mun18] James R Munkres. Elements of algebraic topology. CRCPress, 2018. → pages 41[NO¨15] Tomas Nilson and Lars-Daniel O¨hman. Triple arraysand youden squares. Designs, Codes and Cryptography,75(3):429–451, 2015. → pages 25[PWY05] Donald A Preece, Walter D Wallis, and Joseph L Yu-cas. Paley triple arrays. Australasian Journal of Com-binatorics, 33:237, 2005. → pages 25[Tuz83] Zsolt Tuza. Rysers conjecture on transversals of r-partitehypergraphs. Ars Combinatoria, 16:201–209, 1983. →pages 18[Tuz90] Zsolt Tuza. A conjecture on triangles of graphs. Graphsand Combinatorics, 6(4):373–380, 1990. → pages 1851Bibliography[VLWW01] Jacobus Hendricus Van Lint, Richard Michael Wilson, andRichard Michael Wilson. A course in combinatorics. Cam-bridge university press, 2001. → pages 34[Wal14] WD Wallis. Triple arrays and related designs. DiscreteApplied Mathematics, 163:220–236, 2014. → pages 25[Wes] Douglas B West. Introduction to graph theory. 1996. Pren-tiss Hall, Upper Saddle River, NJ. → pages 152Appendix53Appendix ATablesA.1 Detailed Switch Steps of Edge M-3-regulargraph from (11,5,2)-design26 14 5 078 13 4689 2 4570 8 39 560 2 3 179Table A.1: First switch of Table 6.12 14 5 0 678 13 4689 2 4576 0 8 39 50 2 3 179Table A.2: Second switch of Table 6.12 14 5 0 678 13 468 2 457 96 0 8 39 50 9 2 3 17Table A.3: Third switch of Table 6.154A.2. Triangle Array Representation of graph from (19,9,4)-design2 14 5 0 68 13 46 77 8 2 45 96 0 8 39 50 9 2 3 17Table A.4: Fourth switch of Table 6.12 14 5 0 68 3 46 7 17 8 2 45 96 0 8 39 50 9 1 2 3 7Table A.5: Fifth switch of Table 6.12 1 5 4 0 68 4 3 6 7 17 8 2 45 96 0 8 39 50 9 1 2 3 7Table A.6: Sixth switch of Table 6.1A.2 Triangle Array Representation of graph from(19,9,4)-designQR of Z19 = {1, 4, 9, 16, 6, 17, 11, 7, 5} NQR of Z19 = {0, 2, 3, 8, 10, 12, 13, 14, 15, 18}If we take QR of Z19 as the vertex set A and NQR of Z19 as thevertex set B and assign the following subscripts to the vertices of vertexset C:55A.2. Triangle Array Representation of graph from (19,9,4)-designa = {2, 5, 10, 17, 7, 18, 12, 8, 6} b = {3, 6, 11, 18, 8, 0, 13, 9, 7}c = {4, 7, 12, 0, 9, 1, 14, 10, 8} d = {5, 8, 13, 1, 10, 2, 15, 11, 9}e = {6, 9, 14, 2, 11, 3, 16, 12, 10} f = {7, 10, 15, 3, 12, 4, 17, 13, 11}g = {8, 11, 16, 4, 13, 5, 18, 14, 12} h = {9, 12, 17, 5, 14, 6, 0, 15, 13}i = {10, 13, 18, 6, 15, 7, 1, 16, 14} j = {11, 14, 0, 7, 16, 8, 2, 17, 15}l = {12, 15, 1, 8, 17, 9, 3, 18, 16} l = {13, 16, 2, 9, 18, 10, 4, 0, 17}m = {14, 17, 3, 10, 0, 11, 5, 1, 18} n = {15, 18, 4, 11, 1, 12, 6, 2, 0}o = {16, 0, 5, 12, 2, 13, 7, 3, 1} p = {17, 1, 6, 13, 3, 14, 8, 4, 2}q = {18, 2, 7, 14, 4, 15, 9, 5, 3} r = {0, 3, 8, 15, 5, 17, 10, 6, 4}Then we could obtain the following triangle array representation ofan edge M-5-regular graph:bhjlr bhjmo jmnor bchmn cjlmo bcnor chlor hlmnr bcjlnaejlq adejo ajonp adnpq djloq denoq alopq delnp ejlnpbefqr bekmo fmopr bfmpq fkmoq beoqr kopqr ekmpr befkpabgjr abdjk agjpr abcdp cdgjk bcdgr ackpr dgkpr bcjkpaeflr adeim afimr acdfm cdflm cdeir acilr delmr cefilaefgh aehko afgno acfhn cfgko cegno achko eghkn cefknbfghl bdhio fgiop bdfhp dfglo bdgio hilop adhlp bfilpeghjq ehijm gijmp chmpq cgjmq cegiq chipq eghmp ceijpfhjqr dhijk fijnr dfhnq dfjkq dinqr hikqr dhknr fijknabglq abikm agimn abmnq gklmq bginq aiklq gklmn biklnTable A.7: Triangle Array Representation of graph from (19,9,4)-designj h n c m o r l bl j o d q e a n pq b m p f r o k er a j b c g p d ke m f a l d c r ia o g f k c h e ng d i h o b l p fh e p m j i q g cf k r n d q i h jb i a q g n k m lTable A.8: Example maximum packing of Table A.756


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items