Perfect Matchings After Vertex Deletions in n-dimensional Lattice Graphs by Hangjun Yang B . S c , Zhejiang University, China, 2003 A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F THE REQUIREMENTS FORT H E DEGREE OF M a s t e r of Science in T H E F A C U L T Y O F G R A D U A T E STUDIES Mathematics The University of British Columbia August 2005 © Hangjun Yang, 2005 Abstract This thesis studies lattice graphs which are readily seen to have many perfect matchings and considers whether if we delete vertices the resulting graphs continue to have perfect matchings. It is clear that one can destroy the property of having a perfect matching by deleting an odd number of vertices, by deleting all the neighbours of a given vertex, etc. Besides these trivial "destructions", in order to guarantee the resulting graph still have perfect matchings, we require the deleted vertices to be mutually far apart. In this thesis, we consider an n-dimensional lattice graph Q(m, n) with bipartition of black and white vertices, where m is even. If the distance of any two deleted black (or white) vertices is greater than 4n(n + l)y/m, then the resulting graph (after vertex deletions) continues to have a perfect matching. Contents Abstract ii Contents iii List of Tables v List of Figures vi Acknowledgements 1 2 vii Background 1 1.1 Basic Concepts 1 1.2 Matchings 3 1.2.1. Matchings in Bipartite Graphs 3 1.2.2 Matchings in General Graphs 5 1.3 Networks and Flows 6 1.4 Capacitated Perfect 6-matchings and Bidirected Flows 8 Applications of Matchings 2.1 12 Applications of Matchings in Bipartite Graphs 12 2.1.1 12 The Assignment Problem iii \ 2.1.2 2.2 The Dimer Problem 14 Applications of Matchings in General Graphs 16 2.2.1 The Chinese Postman Problem 16 2.2.2 Quadrilateral Mesh Generation in Computer-Aided Design 3 Introduction of the Problem 4 . 17 19 3.1 Robustness 19 3.2 Motivation 20 3.3 Definitions and Notations 21 3.4 A Result in the 2-D Case 23 Main Result for n-dimensional Lattice Graphs 25 4.1 Statement of Theorem 4.1 25 4.2 Proof of Theorem 4.1 29 Bibliography 36 iv List of Tables 2.1 T a b l e a u F o r m of the K a b u k i Electronics Assignment P r o b l e m . . . . 2.2 T h e O p t i m a l Assignment of the K a b u k i Electronics Assignment P r o b lem 13 14 v' List of Figures 1.1 A pictorial representation of a graph 2 1.2 A matching M i and a perfect matching M^. 3 3.1 Q(m,2) gives an m x m lattice graph, here m = 20 22 4.1 A 2-D diamond with d = 8 in the checkerboard with m — 20 27 4.2 A sketch of a 3-D diamond 28 vi > Acknowledgements This thesis was conducted under the supervision of Dr. Richard Anstee. I would like to thank him for his guidance, advice and encouragement. HANGJUN The University August of British Columbia 2005 vii YANG Chapter 1 Background This chapter mostly follows the terminology in the textbook Introduction to Graph Theory by West [31]. 1.1 Basic Concepts , When speaking of graphs we might think about pictures of some kind that are used to represent information such as bar graphs, flow charts and graphs of functions. But the graphs we shall discuss' are quite different. They correspond more closely with the objects which, in everyday language that we call "networks". A graph G with n vertices and m edges consists of a vertex set V(G) — {v\,... ,v } n and an edge set E(G) — { e i , . . . , e m }, where each edge consists of two (possibly equal) vertices i n V(G) called its endpoints. We usually write G = (V(G), E(G)), or simply G — (V, E). A directed graph or digraph G consists of a vertex set V(G) and an edge set E(G), where each edge is an ordered pair of vertices. A loop is an edge whose endpoints are equal. Parallel edges or multiple edges are edges that have the same pair of endpoints. A simple graph is a graph having 1 a d c Figure 1.1: A pictorial representation of a graph no loops or multiple edges. A complete graph is a simple graph in which every pair of vertices is an edge. Denote a complete graph with n vertices by K . n A graph is finite if its vertex set and edge set are finite. We emphasize here that every graph mentioned in this paper is finite. A typical example of a simple graph G = (V, E) is given by the sets V = {a, b, c, d, z}, E = {(a, b), (a, d), (b, z), (c, d), (d, z)}. We represent the vertices as points, and join two points by a line whenever the corresponding pair of vertices is an edge. Thus Figure 1.1 is a pictorial (or graphical) representation of the graph given in the example above. A walk of length k is a sequence VQ, e i , V\, e2,. • . , e^, of vertices and edges such that e{ — Vi-\Vi for all i. A path is a walk with no repeated vertex. A trail is a walk with no repeated edge. A walk (or trail) is closed if it has length at least one and its endpoints are equal. A walk vo, e\, v\, ei-, • • • > 6fc, vk whose vertices are all distinct except that VQ = is called a cycle. We call a cycle odd if it has an odd number of distinct vertices (and an odd number of edges). A walk specifies a route in G which proceeds through a sequence of vertices joined by edges. A walk may visit any vertex an arbitrary number of times. In a path, each vertex is visited at most once. A u,v-path is a path whose first vertex is 2 u and last vertex is v. A graph G is bipartite if V(G) is the union of two disjoint sets X and Y such that each edge consists of one vertex from X and one vertex from Y. We say G is a bipartite graph with bipartition X, Y. Here is an important fact about bipartite graphs. T h e o r e m 1.1 A graph G is bipartite if and only if it contains no odd cycles. Theorem 1.1 implies that whenever a graph G is not bipartite, we can prove this statement by presenting an odd cycle in G. 1.2 1.2.1 Matchings Matchings in Bipartite Graphs A matching of size A; in a graph G is a set of k pairwise disjoint edges. The vertices belonging to the edges of a matching are saturated by the matching; the others are unsaturated. If a matching saturates every vertex of G, then it is a perfect matching. A maximum matching is a matching of maximum size. Figure 1.2: A matching Mi and a perfect matching Mi. In Figure 1.2 two matchings M\ and Mi in the same bipartite graph are 3 illustrated; the edges which belong to the matchings are indicated by dashed lines. In particular, My is a perfect matching. Given a matching M , an M-alternating path is a path that alternates between edges in M and edges not in M. A n M-alternating path P that begins and ends at M-unsaturated vertices is an M-augmenting path; replacing MC\E(P) by E(P) — M produces a new matching M' with one more edge that M. Maximum matchings are characterized by the absence of augmenting path, which was proven by in 1957. Theorem 1.2 (Berge [5])A matching M in a graph (not necessarily bipartite) G is a maximum matching in G if and only if G has no M-augmenting path. A vertex cover of G is a set S of vertices such that S contains at least one endpoint of every edge of G. The vertices in S "cover" the edges of G. The Konig-Egervary Theorem states an equality relation between maximum matching and minimum vertex covering in bipartite graphs. Theorem 1.3 (Konig [20], Egervdry [10]) If G is a bipartite graph, then the max- imum size of a matching in G equals the minimum size of a vertex cover of G. For any S C I , let N(S) denote the set of vertices having a neighbor in 5. If a matching M saturates X, it must be true that |iV(S)| > \S\. This is known as Hall's condition. In 1935, the mathematician Philip Hall proved that this obvious necessary condition is also sufficient. Theorem 1.4 (Hall [16]) If G is a bipartite graph with bipartition X,Y, then G has a matching M that saturates X if and only if |iV(5)| > \S\ for all S C X. When the sets of the bipartition have the same size, i.e., \X\ — \Y\, then G has a perfect matching under Hall's condition. 4 C o r o l l a r y 1.5 If G is a bipartite graph with bipartition X,Y G has a perfect matching if and only if |iV(S)| > |5| for all and \X\ = \Y\, then S C I . The degree of a vertex v in a graph G, written da(v) or d(v), is the number of non-loop edges containing v plus twice the number of loops containing v. The maximum degree is A ( G ) ; the minimum degree is 6(G). A graph G is regular if A(G) = 6(G); k-regular if A(G) = 6(G) = k. The "first" Theorem of graph theory tells us the sum of vertex degrees is twice the number of edges. Thus every graph has an even number of vertices of odd degree. If G is a A;-regular bipartite graph, then it is easy to show that G satisfies Hall's condition, i.e. \N(S)\ > \S\ for all 5 C X. C o r o l l a r y 1.6 1.2.2 For k > 0, every k-regular bipartite graph has a perfect matching. Matchings in General G r a p h s A graph G is connected if it has a path for each pair u, v € V(G); otherwise it is disconnected. A subgraph of a graph G is a graph H such that V(H) C V(G) and E(H) C E(G). A n induced subgraph of G is a subgraph H of G such that E(H) consists of all edges of G whose endpoints belong to V(H). For any subset S C V(G) , G — S denotes the induced subgraph on V(G) — S. The components of a graph G are its maximal connected subgraphs. A cut-edge or cut-vertex of a graph is an edge or vertex whose deletion increases the number of components. The order of a graph G, written n(G), is the number of vertices in G. A n odd component of a graph is a component of odd order; the number of odd components of H is o(H). Now we shall expand our discussion of matchings to general graphs. Tutte 5 found a necessary and sufficient condition for an arbitrary graph to have a perfect matching. T h e o r e m 1.7 (Tutte [SO]) A graph G has a perfect matching if and only if o(G — S) < \S\ for every S QY(G). Most applications of Tutte's Theorem involve showing that some other condition implies Tutte's condition, which then guarantees a perfect matching. Here is an example. C o r o l l a r y 1.8 (Petersen [27]) Every ^-regular graph with no cut-edge has a perfect matching. In this thesis, we will be examining bipartite graphs and will not be using Tutte's Theorem. 1.3 Networks and Flows A network is a digraph with a nonnegative capacity c(e) on each edge e and a distinguished source vertex s and sink vertex t. Vertices are also called nodes. A flow f assigning a value /(e) to each edge e. We write f (v) + or f (S) + for the total flow on edges exiting a node v or a set of nodes S; the total flow on entering edges i s / - ( t ; ) o r / - ( 5 ) . In terms o f / ( e ) , / > ) = £ /(e) a n d / " ( « ) = e=(v,u) f (S)= + £ /(e)and/-(5)= e=(v,u) £ £ /(e); e=(u,v) /(e). e=(u,v) A feasible flow satisfies the capacity constraints 0 < /(e) < c(e) for each edge and the conservation constraints f (v) + = f~{v) for each node v £ {s,t}. The value val(f) of a flow / is the net flow f~(t) — f {t) + 6 into the sink (or the net flow / (s) — + f~(s) out of the source). A maximumflowis a feasible flow of maximum value. A source/sink cut partitions the nodes of a network into a source set S containing s and a sink set T containing t. The elements of the cut [S,T] are the edges from S to T; every s,t-path uses at least one edge of [S,T]. The capacity of the cut [S, T], written cap(S,T), is the total of the capacities on the edges of [S,T]. The most important result in network flows is the Max-flow Min-cut Theo- rem, proved by Ford and Fulkerson [12]. This result can be viewed as a special case of the strong duality property in Linear Programming. T h e o r e m 1.9 (Max-flow Min-cut Theorem) In every network, the maximum value of a feasibleflowequals the minimum capacity of a source/sink cut. Let us now apply the Max-flow Min-cut Theorem to get a quick proof of the Konig-Egervary Theorem. Let G be a bipartite graph with bipartition X, Y. Build a network G' by directing all edges of G from X to Y, adding a new point s (the "source") joined to all points of X and a new point t (the "sink") to which all points of Y are joined. Assign capacity oo to all edges of G and capacity of 1 to all new edges of G'. It is easy to see that a maximum matching in G corresponds to a maximum flow in G', and so the maximum size of a matching equals the maximum value of a feasible flow. We need to show that the minimum size vertex cover in G equals the minimum capacity of a source/sink cut in G'. Assume I U J is a minimum vertex cover in G, where I C X and J C Y. Let S — {s} U (X — I) U J and T = {t} U I U (Y - J). Then cap{S,T) = \I U Jj = \I\ + | J | . We claim that [S,T] is a minimum source/sink cut in G'. Otherwise, there exists some cut [S',T'} such that cap(S',T') < cap{S,T). We may write S' = {s} U (X - V) U J' and 7 T = {t} Ul'u'Y- J') for some vertex cover V U J ' , where I' CX and J' C y . Then |7'| + \J'\ = cap(S',T') < cap(S,T) = \I\ + | J | . This leads to a contradiction. In combinatorial applications, we typically have integer capacities and want a solution in which the flow on each edge is an integer. C o r o l l a r y 1.10 (Integrality Theorem) If all capacities in a network are integers, then there is a maximum flow assigning integral flow to each edge. In Fulkerson, Hoffman and McAndrew [14], and Anstee.[3], there is an exploration of how network flow techniques can assist in finding general matchings. 1.4 Capacitated Perfect 6-matchings and Bidirected Flows Let G = (V, E) be a graph representing a communication network, i.e. the nodes v can be viewed as terminals and there is an edge {v, w} if two terminals can directly communicate. Every node v has capacity/demand b € N of possible v information exchange operations. Now the task is to find an intersection of the terminals such that the demand is fulfilled. We denote the number of uses of edge e by x and the set of edges having e a node v G V as one of their endnodes by 5(v). A mapping x : E H-> N is called a 6-matching if x{S(v)) := * ^ v eeS(v) b x V v€V. These conditions are called node constraints if x(5(v)) = b for all v and a mapping v fulfilling all these conditions is called a perfect b-matching on G: When b = 1 for v all vertices in G, then (perfect) 6-matchings are the usual (perfect) matchings. Now the problem is complicated by "capacity constraints" and "lower bounds" on the 8 edges, i.e. for every edge e G E there are two numbers l ,u e e with u > l > 0, which e e give the maximal necessary usage and minimal possible usage of a single edge in the graph. Then a mapping x is called a capacitated perfect b-matching if it is a perfect 6-matching on G and V e £ E. le < %e < Ue Now the optimization problem occurs when a cost function c : E — i > R is introduced giving for every edge e E E the cost for exchanging one unit from the tail node of e to the head node of e. Then we want to find a capacitated perfect 6-matching which minimizes total cost c(x) where eeE The above introduced capacitated perfect b-matching problem can be formu- lated as an integer linear programming problem. v min ^T^ c x e e eeE s.t. x(5{v)) = b V v e V v l < x < uy e e e e€E x e N. A bidirected graph G = (V, E) is a graph in which some edges (called loops) may have both ends incident with the same node, some edges (called lobes) may have only one end, and in which each edge has a direction associated with each node with which it is incident. Thus each edge has either one or two (not necessarily distinct) ends, and each of these ends is either a tail end or a head end. For any vertex v G V, we define for bidirected graphs 9 S(v) := the set of edges having exactly one end at v, j(v) := the set of edges having both ends at v, S (v) + := the set of edges in 5(v) whose single end at v is a head end, 6 (v) :— the set of edges in 6(v) whose single end at v is a tail end, 7 (v) := the set of loops having two head ends at v, 7~(i>) := the set of loops having two tail ends at v. Similarly, if we denote by x the number of units assigned to edge e, then we have e to find a mapping I : £ H N such that x(5 (v)) - x{S-(v)) + 2x('y (v)) - 2xia~(v)) = b V v € V. + + v These conditions are called flow conservation constraints and a mapping fulfilling all these conditions is called a bidirectedflowon G. Now the problem may again be complicated by "capacity constraint" and "lower bounds" on the edges, i.e. for every edge e € E there are two numbers l ,u e e with u > l > 0, which give the maximal e e necessary usage arid minimal possible usage of a single edge in the network. Then a mapping x is called a feasible bidirected flow if it is a bidirected flow on G and V e € E. As in the 6-matching problem we assume a cost function c : E i-> R giving for every edge e the cost for "transporting" one unit. Then the optimization problem is to find a feasible bidirected flow x which minimizes total cost c(x) where eeE The above introduced bidirected flow problem can also be formulated as an integer linear programming problem. 10 min c e x e eeE s.t. x(S (v)) - x(5~(v)) + 2x(>y (v)) - 2x(-y~ (v)) = b V v € V + + v l < e %e < uy e x e€E el. The bidirected flow problem looks quite similar to the capacitated b-matching problem. In fact a bidirected flow in a bidirected graph G = (V, E) can be reduced to a capacitated 6-matching in the undirected graph G' = (V U V, E) — with V = {i' : i e V} and E — {e : e € E}, where e are given below — by doing the following (Derigs [6] and Edmonds [8]). Let e = be an edge in E. • If e has 1 head for i and 1 head for j, then we construct one corresponding edge e = e= In particular, when i — j, i.e., e has 2 heads for i, then i.e., a loop at i'. • If e has 1 tail for i and 1 tail for j, then we construct e = (i, j). In particular, when i = j, i.e., e has 2 tails for i, then e — i.e., a loop at i. • If e has 1 head for i and 1 tail for j, then we construct e = (i', j ) . In particular, when i — j, i.e., e has 1 head and 1 tail for i, then e = (i', i). Thus a capacitated b-matching in a bidirected graph G = (V, E) is an assignment of nonnegative integers x to the edges e of G such that x fulfills the "lower bound" and e e "capacity" conditions and the capacity/demand b at each node v S V is fulfilled, in v the sense that edge e contributes — 2x , —x ,0, x , 2x units to the capacity/demand e e e e at v according to whether e has 2 tails, 1 tail, 0 ends, 1 head, 2 heads at v. 11 Chapter 2 Applications of Matchings There are many applications of matchings in both bipartite and non-bipartite graphs, such as the Assignment Problem, the Chinese Postman Problem, etc. 2.1 2.1.1 Applications of Matchings in Bipartite Graphs The Assignment Problem Assignment of people or other resources' to various workstations or certain equipment to accomplish certain tasks while minimizing the total cost is a frequent management decision problem. For example, assigning employees to various tasks, teachers to different classes, crews to projects, and ambulances to first-aid stations are good real-wold examples of assignment problems. The basic goal of the assignment problem is either to minimize the total cost of completing all the required tasks or to maximize the total payoff (or benefits) from the assignments. The following example is from Lee and Shim [22]. Example Kabuki Electronics specializes in producing electronic scanners. The com- 12 parry received a special order from a large cash-register company for optical scanners. To produce important components required for the scanner, the company has selected four employees for assignment to four different machines to complete the necessary tasks. Because of different individual training and experience, the cost of successful completion of the given task to each machine is different for the four employees. Only one employee can be assigned to each machine. Also, each task is completed independently by one employee on one machine. The assignment problem at Kabuki along with the cost involved for each employee to complete each task on each machine, is presented in Table 2.1. Notice that there are the same number of rows (employees) and columns (machines). Also, the amount of supply and demand for each row and each column is exactly one. Employee \ Machine 1 2 3 4 Demand A. 20 18 28 6 1 B 10 10 14 10 1 C 14 22 20 22 1 D 13 18 28 8 1 Supply 1 1 1 1 4 Table 2.1: Tableau Form of the Kabuki Electronics Assignment Problem In Table 2.1, we can easily see that it costs $20 for employee 1 to complete the task using machine A, $10 using machine B, and so on. The cost required for each employee to complete each task may be determined by the amount of time required and the amount of other resources (i.e., materials) used to complete the task. The objective of this assignment problem is to find the employee's optimum assignment schedule to each machine to minimize the total cost to complete the tasks. The assignment problem is a weighted bipartite matching problem, where 13 the costs are the weights. In particular, the sets of the bipartition have the same size, i.e., there are equal numbers of employees and machines. Our Goal is to find the perfect matching between employees and machines such that the total cost is minimized. The best known method to solve assignment problems is the Hungarian Method. For details, please refer to Kuhn [21] or Munkres [25]. The optimal assignment and total cost of the Kabuki Electronics Assignment Problem are as follows: Optimal Assignment Employee Machine Cost 1 D 13 2 B 10 3 C 20 4 A 6 T o t a l C o s t = $49 Table 2.2: The Optimal Assignment of the Kabuki Electronics Assignment Problem 2.1.2 The Dimer Problem The close-packed dimer model of statistical mechanics can be stated as fol- lows. One considers a set of sites and a set of bonds connecting certain pairs of' sites. Each bond b can absorb a "dimer" (which represents a diatomic molecule) with corresponding energy E^. It is required that each site is occupied exactly once by one the atoms of a dimer. A state s is an arrangement of dimers which meets this requirement, and its energy E(s) is E\> where the sum is taken over all bonds b which absorb a dimer. Then the partition function of the dimer model may be viewed as a density function of energy levels. The dimer model was first considered by Roberts [29] in 1935, and by Fowler and Rushbrook [13]. The dimer model for 2-dimensional lattice graphs appears in 14 calculations of the thermodynamic properties of a system of diatomic moleculesdimers arranged in a planar sheet. The partition function can be evaluated in polynomial time using Kasteleyn's method [18] for enumerating perfect matchings in planar graphs. One special type of graph for which enumeration of perfect matchings is of considerable "real-world" interest is the class of rectangular lattice graphs or chessboards (perhaps more accurately "go boards"). Consider an m x n chessboard with mn even. In how many ways can this board be covered by dominoes (dimers)? In graph theoretic terms, the dimer problem for 2-dimensional lattice graphs can be formulated as follows. Let L(m, n) denote the graph whose vertices are the squares (think of them as the centers of the squares) of an m x n chessboard with ran even, two being adjacent if and only if they have a boundary line in common. L(m,n) is a bipartite graph, which means that its vertices may be partitioned into two sets Zi,Z2 such that if e is an edge of L(m,n) then |e fl Z\\ — |e n Z2I = 1. Moreover, we have also that \Z\ \ = IZ2I = mn/2. Now, the problem is to determine the number $ ( L ( m , n)) of perfect matchings in L(m,n). Kasteleyn [18] gave the answer: m *(L m,»»=v* n ( n n / ( , r o s 2 , (^T» » + s 2 (^i») \ 1/4 • But the same problem for 3-dimensional lattices remains an important open problem of statistical physics (see Kasteleyn [19] for references). 15 2.2 2.2.1 Applications of Matchings in General Graphs The Chinese Postman Problem A postman has to leave a post office and traverse a number of streets at least once for delivering and picking up mails, then return to the post office to do his job. How should he plan his walk to minimize his walking distance or time? We can phrase it as a graph problem as follows: A postman traverses all edges in a road network, starting and ending at the same vertex. The edges have nonnegative weights representing distance or time. We seek a closed walk of minimum total length that covers each edge at least once. This is called the Chinese Postman Problem in honor of the Chinese mathematician Meigu Guan [15], who proposed it. Recall that a closed trail is a trail whose length is at least one and its endpoints are equal. We say that a graph whose edges comprise a single closed trail is Eulerian. We use the term circuit as another name for "closed trail"; a circuit containing every edge of G is an Eulerian circuit. We also use odd vertex or even vertex to indicate the parity of a vertex degree. If every vertex in the road network is even, then we can show that the graph G is Eulerian and so the minimum total length is the sum of the weights. Otherwise, we must repeat edges. If there are only two odd vertices, then we can use Dijkstra's Algorithm [7] to find the shortest path between them and solve the problem. If there are 2k (k > 2) odd vertices, then we can use the shortest path algorithm to find the shortest paths connecting each pair of odd vertices. We can use these lengths as weights on the edges of Kik, and then our problem is to find the minimum total weight of k edges that pair up these 2k vertices. This is a weighted version of the maximum matching problem. Edmonds and Johnson [9] described a way to solve 16 this Problem. A n interesting application of the Chinese Postman Problem is the Plotter Problem which was introduced by Asano, Edahiro, Imai, Iri and Murota [4]. The problem is the plotting of a large figure on a computer controlled plotter. They draw straight line segments between points to draw a piecewise linear curve then lift the pen up and travel to the next curve to be drawn. We may think of the plotter as a postman with a pen. In the Chinese Postman Problem we form an auxiliary complete graph defined on the vertices of odd degree. Each edge has a weight, namely the distance between the vertices in the original graph. In the Plotter Problem this weight is the distance, d((x\,yi), (22,2/2)) = max{|a:i — x%\ + \y\ — yiW- It is worth pointing out that the graph G in the Chinese Postman Problem must be connected (since the postman can only walk) while the graph G' in the Plotter Problem may be disconnected. If G' is connected, the solution is then the same as the that for the Chinese Postman Problem. Otherwise, we need first to add some extra edges carefully to make it connected. In fact, a minimal number of edges required to join components will correspond to the Travelling Salesman Problem (TSP). 2.2.2 Quadrilateral Mesh Generation in Computer-Aided Design Muller-Hannemann [26] considered the following definition of polygon for use in mesh generation. A polygon is a region in the plane or, more generally, of a smooth surface in the 3-dimensional space, bounded by a finite, closed sequence of straight line segments or curves (edges). A polygon is simple if its edges do not cross each other, and convex if the internal angle at each vertex is at most n. A mesh is a set of openly disjoint, convex and simple polygons. i 17 Miiller-Hannemann [26] has considered a mesh refinement problem arising in the computer-aided design ( C A D ) of motor vehicle parts, for example, bodyworks or chassis or their components: a coarse mesh of curved polygons, which approximates the surface of a workpiece, has to be refined into quadrilaterals such that the resulting mesh can be used for a numerical analysis. Originating from a concrete application, [26] has described the difficult modeling process, analyze the computational complexity of the mesh refinement problem in various forms, and develop a new algorithmic approach. In [26], we see an original application of network flow and matching techniques in a mesh refinement problem. The experiments in [26] showed that this approach usually leads to meshes with a very good quality. The mesh generation problem can be reduced to a bidirected flow problem on a bidirected graph G with capacity constraints and lower bounds on the edges and some additional node balance conditions (Muller-Hannemann [26]). We have shown in section 1.4 that the bidirected flow problem can be reduced to the capacitated perfect 6-matching problem. There are several polynomial algorithms for 6-matching problems (see Pulleyblank [28], Anstee [2], and Miller and Pekny [24]). 18 Chapter 3 Introduction of the Problem 3.1 Robustness Network robustness measures how well a network can continue to perform its function after node or arc failures. There are several different ways and methodologies to measure robustness of networks, e.g., resilience to random node failures (fragility), resilience to attacks (vulnerability), or number of alternative paths. The idea of "robustness" considered here is very different from network robustness. We study the robustness of a graph with respect to the property of having a perfect matching under the operations of vertex deletion. This thesis studies lattice graphs which are readily seen to have many perfect matchings and considers whether if we delete vertices the resulting graphs continue to have perfect matchings. In order to guarantee the resulting graphs still have perfect matchings, we require some constraints on the deleted vertices. We will impose the constraint that the deleted vertices are at a certain distance from each other. 19 3.2 Motivation T h i s thesis was motivated by a result of J a m i s o n a n d L o c h n e r [17]. studied a problem about tiling fringed chessboards with dominoes. They A fringe on a p x q chessboard is a set of additional nonadjacent squares added above the top row. T h e squares m a y be considered as colored black a n d white consistently w i t h the b o a r d . If the fringed b o a r d is to be tiled by dominoes, then the total number of black squares must equal the total number of white squares. In general, this parity condition is not sufficient. However, if the b o a r d is deep enough, i.e., p is big enough, then this parity condition does suffice to guarantee a tiling. A balanced fringe is a fringe that contains an equal number of black a n d white squares. T h e depth of a fringe X is defined as A(X) — m a x \Bi — Wj|, where l<i<q Bi is the number of black squares up to a n d including i a n d Wi is the number of white squares up to a n d including i. W e state the m a i n result of [17] without proof. Theorem 3.1 Let B be a fringed board with a balanced fringe X obtained from a p x q chessboard by adjoining X above the top row. If p = 2A(X), then B has a domino tiling. In order to tile a fringed b o a r d by dominoes, we first need to pair the squares in the fringe w i t h their adjacent squares i n the p x q chessboard. Now, we delete these pairs (i.e., the fringe a n d its adjacent squares) from the fringed b o a r d . Note that to cover a fringed b o a r d by dominoes is equivalent to cover the resulting b o a r d after deletion. F r o m the point of view of tiling w i t h dominoes, a d d i n g some nonadjacent squares (i.e., a fringe) above the top row to a p x q chessboard is equivalent to deleting their adjacent squares from the top row of the chessboard. In g r a p h theoretic terms, given a p x q (pq even) lattice graph, we delete 20 an equal number of black and white vertices from the top row. Theorem 3.1 says that if p is big enough then the resulting graph still has a perfect matching. In particular, q = p (p even) will work. Now, we consider a more general version of vertex deletion. A p x p lattice graph (p even) is easily seen to have many perfect matchings. Consider deleting an equal number of black and white vertices in this lattice graph (not restricted to the top row). We want the resulting graph continues \ to have a perfect matching. In order to avoid local problems (e.g. deleting all neighbors of a given vertex will result in a graph that has no perfect matching), we require that the deleted vertices to be mutually far apart. We will be more specific in Lemma 4.3. 3.3 Definitions and Notations The n-dimensional lattice graph Q(m,n) is the following graph: has vertices (x\, X 2 , . . . , x ) , where Xj G {1,2,... n edges ((xi,...,x;_i,Xj,x ,.. i+i .,x ), n Q(m,n) ,m} for i — 1,2, . . . , m , and (xi,...,Xj_i,Xj + 1,x ,.. . , x ) ) , where i+1 n Xj G { 1 , 2 , . . . , m} for j = 1,2,..., n and x, ^ m. For example, Q(m,n = 2) gives an m x m lattice graph divided into m 2 vertices of two alternating colors — black and white. Figure 3.1 illustrates a 2dimensional lattice graph with m = 20. To be precise, let's say the vertex (1,1,... ,1) is a white vertex. Then ( x i , X 2 , • • •, x ) is a white vertex if and only if n n x, = n (mod 2). i=l , Then Q(m,n) is a bipartite graph with bipartition W and B, where W is the set of all white vertices and B is the set of all black vertices. 21 16 11 6 1 1 6 11 16 F i g u r e 3.1: Q{m, 2) gives an m x m lattice graph, here m = 20. If m is o d d , then the total number of vertices in Q(m, n) is m , which is n also o d d a n d so there is no perfect m a t c h i n g for Q(m, n). In order to have a perfect \Q(m,n)\ m a t c h i n g i n Q(m, n), we m a y assume m is even. T h e n | W | — \B\ — For any S C W, the neighbor set of S in Q(m,n), —- m n = —-. N(S), denoted by is the set of all vertices adjacent to the vertices i n S. Since all the vertices adjacent to S are black, then Given N{S) C S U N(S) B. T h e surplus of S is 1^(5)1 - | 5 | . is connected, the di = max{xi : (xi,x ,... ,x ) 2 where i = n side lengths G Sl)N(S)} - of S U N(S) min{xj : (xi,X2,, are • • ,x ) n G S U N(S)}, 1,2, . . . . , n . W e define the distance of two vertices (x\,X2, • • • ,x ) n - 22 and ( '\i 2i x x • • • ' 'n) X a S n d{(xi,X2, • • •, x ), (x'i,x , • • •,a;')) = n \xi — x[\. 2 1=1 Choose k £ {1,2,..., m}. Then fix Xi — k and define a complete plane by ^{xi=k} = {(xi,x ,... ,Xi-i,k,x i,... 2 ,x ) : Xj i+ n = 1,2,... ,m for j ^ i}. A complete plane 7 r / . j contains all the points where X{ = k. Otherwise, we say a x = f c plane is incomplete. In particular, when n — 2, fix i, the set -K{ =i} = {(i,x ) :x Xl 2 = 2 l,2,...,m} gives a complete column C{ (we use the word column as it is more appropriate in 2 dimensions). Similarly, we can define a complete row. We define the surplus of column C (not necessarily complete) as | C f l N(S) \ — \C f l S\. Let B' be the set of deleted black vertices in B, and W be the set of deleted white vertices i n W. 3.4 A Result in the 2-D Case The following Theorem is a result of Aldred, Anstee and Locke [1]. Theorem 3.2 Assume m is an even integer. Let Q(m, 2) be a 2-dimensional lattice graph with bipartition B,W. Choose any sets B' C B,W C W. If B',W have the following three properties: (a) \B'\ = \W'\, (b) d((xi,x ),(x[,x' )) > d, for (xi,X2),(x' ,x' ) e B', (c) d((x ,x ),{x' ,x )) > d, for (xi,x ),(x' ,x ) G W, 2 1 2 2 l 2 1 2 1 23 2 2 where d — 4\^/m} + 8, then the graph Q(m,2) - (B' U W) has a perfect matching. * Theorem 3.2 gives a result for the 2-dimensional case. We try to get some similar results in higher dimensions in next chapter. 24 Chapter 4 Main Result for n-dimensional Lattice Graphs 4.1 Statement of Theorem 4.1 Theorem 4.1 is a nontrivial analogue of Theorem 3.2 for higher dimensions. We will use some proof ideas from the proof of Themreom 3.2 [1], but the overall proof of Theorem 4.1 is quite different from that of Theorem 3.2. In this whole chapter, we assume m,n are natural numbers and m is even, n > 2. Theorem 4.1 Let Let Q(m,n) B,W. be an n-dimensional lattice graph with bipartition Choose any sets B' C B,W C W. If B',W have the following three properties: (a) \B'\ = \W'\, (b) d^x^xi,... ,x ),(x[,x' ,... n 2 (c) d((xi,X2 ...,x ),(x' x'2,...,x' )) t n lt n ,x' )) > d ,y n n (xi,x ,. 2 •.,x ), n > d ,V (xi,x ,...,x ), n 25 2 n (x[,x' ,... ,x' ) G B', 2 n (x' ,x' ,...,x' ) 1 2 n G W, where d n — 4n(n + l)\y/m~\, then the graph Q(m,n) — (B' U W) has a perfect matching. Before proving the theorem, we will prove 4 lemmas. The proofs of Lemma 4.2 and 4.3 are loosely based on arguments in [1]. The results of Lemma 4.4 and 4.5 are original, and the proofs are quite different from those of Lemma 4.2 and 4.3. Recall that if S U N(S) is connected, the side lengths of S U N(S) are ai = max{x; : (xi ,£2, • • • ,x ) € SliN(S)} - min{a:; : (x\,X2, • • • ,x ) G S U N(S)}, n n where i = 1, 2 , . . . , n. Without loss of generality, we may assume a\ > a > • • • > a . 2 n We first expand the region S U N(S) to an a\ x 02 x • • • x a grid. Then we expand n the a i x 02 x • • • x a grid to an (ai + d ) x (02 + d ) x • • • x (a„ + d ) grid by adding n n n n d /2 at each of 2n directions, where d is even. For any x in the a\ x 02 x • • • x a n n n grid, we define B (x,d) n = {y e Q(m,n) : d(x,y) < d}. Then B (x, d /2) is contained in the (a\ + d ) x (02 + d ) x • • • x (a + d ) grid n n n since any point of B (x,d /2) n n n n n is at most d /2 from x and hence at most d /2 from n n the ai x a x • • • x a grid. 2 n Lemma 4.2 For any vertex x in Q(m,n), we have Proof: We prove it by induction. When n = 2, ^2(^,^2/2) gives a 2-dimensional "diamond". See Figure 4.1, the vertices which belong to the diamond are indicated by thick dots. The number of vertices in such a diamond is 26 16 11 6 1 6 11 16 Figure 4.1: A 2-D diamond with d = 8 in the checkerboard with m = 20. When n = 3, B^(x, d /2) gives a 3-dimensional "diamond". We may consider 3 the origin point as the center and d as the diameter of the diamond in 3 dimensions. See Figure 4.2 for a sketch of a 3-dimensional diamond. We only count vertices in the upper half of the diamond. So, Bs(x,d /2)\ 3 > i|s (M /2)|(d3/2 3 2 + l) >l±- /2 d( 3^\ )2^ 3 / 2 + 1) > 2 ( | ) . 3 For general n, we have B (x,d /2) n n > > > 1 B -i(x,d /2)|(d /2 n n dn n \2(n-l) + 1) n n-l (d /2 + 1) n ,(dny 2 \2nJ only count the upper half ' 27 by induction Figure 4.2: A sketch of a 3-D diamond. The result \B (x,d /2)\ n > 2^^) n is enough to prove Theorem 4.1, where d — 4 n ( n + 1 ) [ \ / m ] . Actually, we can count \B (x,d /2)\ n n Ba(x,|) exactly for small n, e.g., n = - 2 - + d2 + l > - 2 i - and 5s(x,|) It is easy to see that B»-i(i,y)| + 2 £ n(x, y ) B |i?„-i(x,i) i=0 i i s even Thus approximately, d /2)\ > n However, even if we could show \B (x, d /2)\ > n ^ V , this would only improve d by a constant factor in Theorem 4.1. n 28 n 4.2 Proof of Theorem 4.1 We first consider a special case in 2 dimensions when |5u7V(5)| < \m . The 2 main proof idea of Lemma 4.3 is from the proof of Theorem 3.2 [1]. Lemma 4.3 Let Q(m,2) be a 2-dimensional lattice graph with bipartition Choose any sets S C W, B' C B. If B',W (a) \SUN(S)\ < have the following two properties: lm , 2 (b) d{{xi,x ), {x' ,x' )) > d = 2 4 [ / m ] , for (x x ), 2 B,W. x 2 2 v 1} 2 (x' ,x' ) G B', x 2 then l - B ' n N(S)\ < \N(S)\ - \S\. Proof: (4.1) First we consider the case when S U N(S) is connected. Then we can construct the (a\ + d ) x (a + d ) grid as described earlier. 2 2 2 If a < m, then there is no complete column. Note that the surplus of every 2 column is at least 0 since in any column the number of black vertices is > the number of white vertices. Every two adjacent incomplete nonempty columns have a surplus of at least 1, since in only these two columns, the number of black vertices is more than the number of white vertices at least by 1. Now we pair all the columns from left to right. If a\ is even, we have totally a\/2 pairs and so the surplus is at least a i / 2 ; if a\ is odd, we have (a\ — l ) / 2 pairs (1 column left) and so the surplus is at least (ai — l ) / 2 . Hence, the surplus of the a\ incomplete nonempty columns is at least L i/2Ja If a = m, then a = a = m. Since | S U i V ( S ) | < | m , SUN(S) 2 2 x 2 has at most [ | m / m j = [3m/4j complete columns. Hence, there are at least m — [3m/4j = 2 [m/4] incomplete nonempty columns. Again, pair all the columns from left to 29 right and we obtain a\/2 = m/2 pairs. There are 3 different types of pairs: a pair of two complete columns, a pair of one complete column with one incomplete nonempty columns and a pair of two incomplete nonempty columns. The first type pair has a surplus at least 0; the second type has a surplus at least 1 and the third type has a surplus at least 1. Since we have at least fm/4] incomplete nonempty columns, then the surplus is at least [ \ /^ j > |_^y^J = L / 8 J = L i / ^ J - Therefore, m m a |tf(S)|-|S|>Lai/8j. We want to show \B' C\N(S)\ < |_ai/8j. If a\ < 0*2/2 then at most one black vertex can be deleted. So we only need to consider the cases when ci\ > (I2/2, i.e. d < 2 a i . Note that for x,y £ B', B(x, d /2) n B(y, d /2) = 0. Thus the number of 2 2 2 deleted black vertices \B'nN{S)\ < (Qi + d )(a2 + d ) B (x,d /2) (ai + d) 2 2 2 2 2 < 2 d /8 2 2 < (3ai) 2 d /8j 2 2 _ 72 2 a i Ld J 2 2 Now d2 = 2 4 [ \ / m ] , so d2 > 576m > 576ai and so 2 72aV d 2 < ax/8. Thus, 2 \B'nN{S)\ < \N(S)\ - \S\. Second we consider the case that S U N(S) is disconnected, we may write Sl)N(S) = JT{Si{JN{Si)), where every SiUN(Si) is connected and (Sil)N(Si))n (Sj U N(Sj)) = 0 for i ^ j. B y the above proof, we get \B' n N(S)\ = £ \B' n i=i N(Si)\ < E(\N(Si)\ - \S \) = E WSi)\t z=l i=l We use the complete plane 7T{x„=i} = {(xi,x ,. 2 E \Si\ = \N(S)\ - \s\. i=l • .,x -i,i) :xj n 30 = l,2,...,m for j n} to cut S U N(S). Denote the intersection by layer L^. Li = (SUN(S))f) = . n{Xn i} L e m m a 4.4 Let Q(m,n) be an n-dimensional lattice graph with bipartition B, W. Choose any set S C.W. (a) If S has the following two properties: \SUN(S)\<^^m , n (b) there exists some layer Li such that | L j | > " _1[ m ~ , 2 1 n 1 then \N(S)\-\S\> Proof: Let a\, a ,. •., a 2 0,2 > ... > a . If a n L " " 2 2 + l m n 1 n + 1 m"" 1 be the side lengths of S U N(S). We may assume a\ > < m, then we can show that surplus |iV(5)| — \S\ > | _ ^ J = n " ~ J by * 1 2 ^ ** * * n e a c n a n e number of black vertices > the number of white vertices in any layer and the following "projection line" idea. then at least one of the two layers L i - a n d L Since a is empty. Assume L n m m < m, = 0. F i x _ , the vertex set 1 {(xi, x° ,..., 2 x° _ J)J n = i, i + 1 , . . . , m) n (5 U N(S)) 1 defines a projection line. A n y projection line that starts with a black vertex has surplus > 1; any projection line that starts with a white vertex has surplus > 0. There are at least [^4] = \ " n m ~] 2 +l 2 n l black vertices in Li and so the projection lines which start from Li give surplus > | " " ^ m ~ ] . Note that the number of 2 + 1 n 1 2 black vertices > the number of white vertices in any other layers below Li , so \N(S)\-\S\>\ -^±±m^]. 2 31 *n m, If a = ra, then ai = a = ... = a = m . Since \S U iV(5)| < n 2 2 L " l m"~ j. 2 then there exists some layer Lj such that \Lj\ < +1 x 2 +1 n 2 n Then we can show that |AI(5)| - \S\ > \- -^ m ~ ] by the following "projection segment" idea. We n 2 1 fI may assume i < j. F i x x\, x®, • • •, a;°_i, the vertex set { « xl..., Xn-i,k),i < k<j}D(SU N(S)) defines a projection segment between layer L , and Lj. Now we first count the surplus between layer L j and Lj, inclusive. We have two cases which depend on the parity of i + j. Case 1: i + j = 0 (mod 2). 1. Every projection segment which starts with a black vertex in L j (or Lj) has surplus > 1. 2. Every projection segment which starts with a white vertex in L j (or Lj) and ends with a white vertex in Lj (or Lj) has surplus > —1. 3. Every projection segment which starts with a white vertex in L j (or Lj) and doesn't reach Lj (or Lj) has surplus > 0. There are at least [ ^ l ^ m " ' - 1 ] black vertices in L j and at most L^n+t "^" 1 - 1 ] white vertices in Lj . So we have surplus at least 1X in—2 + 1 n-l 2" in—1 + (-l)x + 1 n - l 2 n+l Case 2: i + j = l (mod 2). 1. Every projection segment which starts with a black vertex in L j (or Lj) and ends with a white vertex in Lj (or Lj) has surplus > 0. 32 2. Every projection segment which starts with a white vertex in L j (or Lj) has surplus > 0 . 3. Every projection segment which starts with a black vertex in L j (or Lj) and doesn't reach Lj (or Lj) has surplus > 1. So the surplus is 1 x fon-2 + i n - 1 1 -ra n - l + 2n+l n - l 1 2n+l m n - l Therefore, the surplus between layers L j and Lj inclusive is at least \ -^frra ~ ]. n 1 2 Since the number of black vertices > the number of white vertices in any other layers above Lj or below L j , we have at least [ o ^ p - m ™ ] surplus. • -1 L e m m a 4.5 Let Q(m,n) Choose any set S CW. Proof: Note that d n be an n-dimensional lattice graph with bipartition If S satisfies \SUN(S)\ = 4n(n + l ) | \ / m l > < "~l 2 d _i m , then (4.1) holds. n 4(n — ^ n f y ? ™ ] . 7 = n + 1 B,W. We prove it by induction. Lemma 4.3 showed the case when n = 2. In the n-dimension, if \Li\ < ^ n - i ^ r a " " " for a l i i = 1 , 2 , . . . , m, then we are done by induction. Otherwise, 1 there exists some L j such that | L , | > ^ ~ ! , t T n " ~ . B y Lemma 4.4, we have |iV(S)| — 2 We want to show \B' n N(S)\ 1 < r^FT 1 7 7 1 " - 1 !- If m < d /n n then at most one black vertex can be deleted. So we only need to consider the cases when m > i.e. d n < nm. Note that for x,y € B', B(x,d /2) n 33 n B(y,d /2) n d /n, n = 0. Thus the number of deleted black vertices \B'nN(S)\ (ai + d )(a,2 + d ) • • • (a + d ) < n n n n B {x,d /2) n n (m + d ) n n < 2{d /2n) n n (m + nm) 7 < . 2(d /2n) J n n (2n(n+ l)) m n 2d7 Now d = 4n(n + > n 4 n n ( +l)N n 1 / n ] > 4n(n + ^ m / " , so d 1 n n > (4n(n + l ) ) " m and so (2n(n + l ) ) m n 2d n (2n(n + l ) ) m ' n-l < 24n(n + l ) m ~ 2™+!-m n n n n Thus, | B ' n AT(5)| < \N(S)\- \S\. • From the proof of Lemma 4.5, we see that if there is some layer L j such that | L j | > ^7r=T^-m ~ , then d = 4n(n+ l ) [ m 2 n 1 1 / , n n ] is sufficient to guarantee (4.1). However, when every layer is small (< - -^r rn ~ ), 2 L n we rely on induction. A n d 1 2 we start the induction with n = 2, so we require d = 4n(n + l ) [ m ] for every / n n. d n v Although we don't know how to prove it, we believe that the best possible — where f(n) is a function of n. Here is an example to show that f{n)\'rn l ~\, l n why the bound m / " is best possible. 1 We choose 5 = E n W, where E | ( x i , x , ••• ,x ) \ x e {1,2, • • • , y } , Xi £ {1,2, • • • , m) for i ^ n j . 2 n n Since the number of white vertices = the number of black vertices in E, the only surplus are those black vertices above E, then |iV(S)| - \S\ = m \ . Every deleted 1 black vertex takes up a space of size at most d , then the maximum number of n n 34 black vertices which can be deleted is \B'nN(S)\>— 2 ' /d " n n 2d ' n n Remark that we can choose W in the other half. In order to make the resulting graph (after deletion) still have a perfect matching, it is necessary that \B> n N{S)\ < \N(S)\ - | 5 | , i.e., ^ < ^ =• d > m ^ 1 n Next, we give the proof of Theorem 4.1. P r o o f o f T h e o r e m 4 . 1 : We prove Theorem 4.1 by using Hall's Theorem on Q(m, n) — (B' U W). Choose any subset S C W. We need to show that \N{S)-B'\>\S\, (4.2) which is equivalent to (4.1). Lemma 4.5 proves (4.1) for | S U N(S)\ < holds for |5 U N(S)\ < \m n since \m n < 2 "^ + 1 V " " 1 t i s eas y t 0 s e e C-) 4 1 n n n l m . Next, we show (4.1) for \S U N(S)\ > \m . \T U iV(T)| < \m . 1 Let T = B - N(S), then Interchanging the roles of W and B, we obtain \W n N(T)\ < \N(T)\ - \T\. Denote W - S - N(T) = A, Using the facts that \B'\ - \W'\ and |J3| = \W\, we have \B'nN{S)\ [ < \B'\ = \W'\ = \W n(N(T)l)A)\ = \W C)N(T)\ + \A\ < |iV(T)| — | T | + | W - .S — '= \N(T)\-\B- - MS)\-\s\. N(S)\ + \W\ - \S\ - We have shown (4.1) for any S C W. \N(T)\ • 35 Bibliography [1] R . E . L . Aldred, R . P . Anstee and S.C. Locke, Perfect matchings after vertex deletions, Preprint. [2] R . P . Anstee, A polynomial algorithm for 6-matching: A n alternative approach, Information Processing Letters 24 (1987), 153-157. [3] R . P . Anstee, Matching theory: fractional to integral, New Zealand J. Math. 21 (1991), 17-32. [4] T . Asano, M . Edahiro, H . Imai, M . Iri. and K . Murota, Practical use of bucketing techniques in computational geometry, Computational Geometry (1985), 153-195. [5] C . Berge, Two theorems in graph theory, Proc. Nat. Acad. Sci. U.S.A. 43 (1957), 842-844. [6] U . Derigs, Programming in networks and graphs, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, 300 (1988). [7] E . W . Dijkstra, A note on two problems in connexion with graphs, Numer. Math. 1 (1959), 269-271. 36 [8] J . Edmonds, A n introduction to matching, Lecture notes, University of Michigan, A n n Arbor (1967). [9] J . Edmonds and E . Johnson, Matchings, Euler tours, and the Chinese postman, Math. Programming 5 (1973), 88-124. [10] E . Egervary, On combinatorial properties of matrices, Math. Lapok 38 (1931), 16-28. [11] P. Elias, A . Feinstein and C . E . Shannon, Note on maximum flow through a network, IRE Trans, on Information Theory IT-2 (1956) 117-119. [12] L . R . Jr. Ford and D . R . Fulkerson, Maximal flow through a network, Canad. J. Math. 8 (1956) 399-404. [13] R . H . Fowler and G.S. Rushbrooke, Trans. Faraday Soc. 33 (1937), 1272. [14] D . R . Fulkerson, A . J . Hoffman and M . H . McAndrew, Some properties, of graphs with multiple edges, Canad. J. Math. 17 (1965), 166-177. [15] M . Guan, Graphic programming using odd and even points, Chinese Math. 1 (1962), 273-277. [16] P. Hall, On representation of subsets, J. Lond. Math. Soc. 10 (1935), 26-30. [17] R . E . Jamison, N . Lochner, Tiling fringed chessboards with dominoes, 34th Southeastern International Conference on Combinatorics, Graph Theory and Computing. [18] P . W . Kasteleyn, The statistics of dimers on a lattice, Physica 27 (1961), 1209-, 1225. 37 [19] P . W . Kasteleyn, Graph theory and crystal physics, Graph Theory and Theoretical Physics, Academcis Press, New York (1967), 43-110. [20] D . Konig, Graphen und matrizen, Math. Lapok 38 (1931) 116-119. [21] H . W . Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly 2 (1955), 83-97. [22] S.M. Lee and J.P. Shim, Micro Management Science, A l l y n and Bacon, second edition, 1990, 218-219. [23] K . Menger, Zur allgemeinen Kurventheorie, Fund. Math. 10 (1927), 95-115. [24] D . L . Miller and J . F . Pekny, A staged primal-dual algorithm for perfect bmatching with edge capacities, ORSA J. of Computing 7 (1995), 298-320. [25] J . Munkres, Algorithms for the assignment and transportation problems, J . Soc. Indust. Appl. Math. 5 (1957), 32-38. [26] M . Miiller-Hannemann, Quadrilateral Mesh Generation in Computer-Aided De- sign, Cuvillier Verlag Gottingen, 1997. [27] J . Petersen, Die theorie der regularen graphen, Acta Math. 15 (1891), 193-220. [28] W . R . Pulleyblank, Faces of matching polyhedra, P h . D . thesis, Faculty of Mathematics, University of Waterloo (1973). [29] J . K . Roberts, Proc. Roy. Soc. (London) A, 161 (1935), 141. [30] W . T . Tutte, The factorization of linear graphs, J. Lond. Math. Soc. 22 (1947), 107-111. [31] D . B . West, Introduction to Graph Theory, Prentice Hall, 1996. 38
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Perfect matchings after vertex deletions in n-dimensional...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Perfect matchings after vertex deletions in n-dimensional lattice graphs Yang, Hangjun 2005
pdf
Page Metadata
Item Metadata
Title | Perfect matchings after vertex deletions in n-dimensional lattice graphs |
Creator |
Yang, Hangjun |
Date | 2005 |
Date Issued | 2009-12-18T20:16:56Z |
Description | This thesis studies lattice graphs which are readily seen to have many perfect matchings and considers whether if we delete vertices the resulting graphs continue to have perfect matchings. It is clear that one can destroy the property of having a perfect matching by deleting an odd number of vertices, by deleting all the neighbours of a given vertex, etc. Besides these trivial "destructions", in order to guarantee the resulting graph still have perfect matchings, we require the deleted vertices to be mutually far apart. In this thesis, we consider an n-dimensional lattice graph Q(m, n) with bipartition of black and white vertices, where m is even. If the distance of any two deleted black (or white) vertices is greater than 4n(n + l)y/m, then the resulting graph (after vertex deletions) continues to have a perfect matching. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2009-12-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080077 |
URI | http://hdl.handle.net/2429/16911 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2005-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- ubc_2005-0708.pdf [ 1.57MB ]
- Metadata
- JSON: 1.0080077.json
- JSON-LD: 1.0080077+ld.json
- RDF/XML (Pretty): 1.0080077.xml
- RDF/JSON: 1.0080077+rdf.json
- Turtle: 1.0080077+rdf-turtle.txt
- N-Triples: 1.0080077+rdf-ntriples.txt
- Original Record: 1.0080077 +original-record.json
- Full Text
- 1.0080077.txt
- Citation
- 1.0080077.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
China | 10 | 5 |
United States | 5 | 0 |
France | 3 | 0 |
Russia | 1 | 0 |
Thailand | 1 | 0 |
Japan | 1 | 0 |
City | Views | Downloads |
---|---|---|
Beijing | 7 | 0 |
Ashburn | 4 | 0 |
Unknown | 4 | 0 |
Shenzhen | 3 | 5 |
Huai Khwang | 1 | 0 |
Piscataway | 1 | 0 |
Tokyo | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
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"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080077/manifest