Ear-Slicing for Matchings in Hypergraphs
- PDF / 199,008 Bytes
- 5 Pages / 439.37 x 666.142 pts Page_size
- 1 Downloads / 230 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
Ear-Slicing for Matchings in Hypergraphs }1 Andra´s Sebo Received: 23 December 2019 / Revised: 28 July 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract We study when a given edge of a factor-critical graph is contained in a matching avoiding exactly one, pregiven vertex of the graph. We then apply the results to always partition the vertex-set of a 3-regular, 3-uniform hypergraph into at most one triangle (hyperedge of size 3) and edges (subsets of size 2 of hyperedges), corresponding to the intuition, and providing new insight to triangle and edge packings of Cornue´jols’ and Pulleyblank’s. The existence of such a packing can be considered to be a hypergraph variant of Petersen’s theorem on perfect matchings, and leads to a simple proof for a sharpening of Lu’s theorem on antifactors of graphs. Keywords Matching Factor-critical Ear-theorem Packing and covering for hypergraphs Antifactor General factor
1 Introduction Given a hypergraph H ¼ ðV; EÞ, ðE PðVÞ; where PðVÞ is the power-set of V) we will call the elements of V vertices, and those of E hyperedges, n :¼ jVj. We say that a hypergraph is k-uniform if all of its hyperedges have k elements, and it is k-regular if all of its vertices are contained in k hyperedges. Hyperedges may be present with multiplicicities, for instance the hypergraph H ¼ ðV; EÞ with V ¼ fa; b; cg consisting of the hyperedge fa; b; cg with multiplicity 3 is a 3-uniform, 3-regular hypergraph. The hereditary closure of the hypergraph H ¼ ðV; EÞ is H h ¼ ðV; Eh Þ where Eh :¼ fX e : e 2 Eg, and H is hereditary, if H h ¼ H. For the new edges of the hereditary closure we do not need to define multiplicities, we will consider them all to be 1. Hyperedges of cardinality 1 will be called singletons, those of cardinality 2 and 3 are called edges and triangles respectively. Deleting a vertex v of the hypergraph & Andra´s Seb} o [email protected] 1
CNRS, Laboratoire G-SCOP, Univ. Grenoble Alpes, Grenoble, France
123
Graphs and Combinatorics
H results in the hypergraph H v ¼ ðV n fvg; fe 2 E; v 62 EgÞ. For hereditary hypergraphs this is the same as deleting v from all hyperedges. The degree dH ðvÞ of v 2 V in H is the number of hyperedges containing v. Given a hypergraph H ¼ ðV; EÞ, denote by E2 the set of edges (of size two) in Eh , H2 :¼ ðV; E2 Þ. We do not need parallel edges in H2 , so we suppose H2 is a graph without parallel edges, and it is by definition without singletons (loops). The (connected) components of H are defined as those of H2 . These form a partition of V, and correspond to the usual hypergraph components: H is connected if H2 is connected. Abusing terminology, the vertex-set of a component is also called component. We define a graph as a hypergraph H with H ¼ H2 . A matching in a graph is a set of pairwise vertex-disjoint edges. A matching is perfect if it partitions the vertex-set of the graph. A graph G ¼ ðV; EÞ is called factor-critical if G v has a perfect matching (al
Data Loading...
