Paper Info
Title
Maximum Matchings And Minimum Blocking Sets In Theta(6)-Graphs
Abstract
Theta(6)-graphs are important geometric graphs that have many applications especially in wireless sensor networks. They are equivalent to Delaunay graphs where empty equilateral triangles take the place of empty circles. We investigate lower bounds on the size of maximum matchings in these graphs. The best known lower bound is n/3, where n is the number of vertices of the graph, which comes from half-Theta(6)-graphs that are subgraphs of Theta(6)-graphs. Babu et al. (2014) conjectured that any Theta(6)-graph has a (near-)perfect matching (as is true for standard Delaunay graphs). Although this conjecture remains open, we improve the lower bound to (3n - 8)/7.We also relate the size of maximum matchings in Theta(6)-graphs to the minimum size of a blocking set. Every edge of a Theta(6)-graph on point set P corresponds to an empty triangle that contains the endpoints of the edge but no other point of P. A blocking set has at least one point in each such triangle. We prove that the size of a maximum matching is at least beta(n)/2 where beta(n) is the minimum, over all Theta(6)-graphs with n vertices, of the minimum size of a blocking set. In the other direction, lower bounds on matchings can be used to prove bounds on beta, allowing us to show that beta(n) >= 3n/4 - 2.
Year
DOI
Venue
2019
10.1007/978-3-030-30786-8_20
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019)
Keywords
Field
DocType
Theta-six graphs, Proximity graphs, Maximum matching, Minimum blocking set, Triangular-distance, Delaunay graph
Discrete mathematics,Graph,Combinatorics,Equilateral triangle,Vertex (geometry),Upper and lower bounds,Computer science,Matching (graph theory),Conjecture,Delaunay triangulation
Conference
Volume
ISSN
Citations 
11789
0302-9743
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Therese Biedl1902106.36
Ahmad Biniaz24420.67
Veronika Irvine300.34
Kshitij Jain400.68
Philipp Kindermann56311.87
Anna Lubiw675395.36