Results 51 to 60 of about 2,022 (201)
The cost of perfection for matchings in graphs
Discrete Applied Mathematics, 2016 Perfect matchings and maximum weight matchings are two fundamental combinatorial structures. We consider the ratio between the maximum weight of a perfect matching and the maximum weight of a general matching. Motivated by the computer graphics application in triangle meshes, where we seek to convert a triangulation into a quadrangulation by merging ...
Emilio Vital Brazil +3 more
openaire +3 more sources
Determinants and perfect matchings
Journal of Combinatorial Theory, Series A, 2013 15 pages, terminology improved, exposition tightened, "deranged matchings" example ...
openaire +4 more sources
Coronoid systems with perfect matchings
, 1996 A hexagonal system is a finite 2-connected plane graph in which every interior face is bounded by a regular hexagon. A coronoid system is obtained from a hexagonal system by deleting some interior vertices and/or interior edges such that a unique ...
Rong-si, Chen
core +1 more source
Core Index of Perfect Matching Polytope for a 2-Connected Cubic Graph
Discussiones Mathematicae Graph Theory, 2018 For a 2-connected cubic graph G, the perfect matching polytope P(G) of G contains a special point xc=(13,13,…,13)$x^c = \left( {{1 \over 3},{1 \over 3}, \ldots ,{1 \over 3}} \right)$ . The core index ϕ(P(G)) of the polytope P(G) is the minimum number of
Wang Xiumei, Lin Yixun
doaj +1 more source
Rook Theory for Perfect Matchings
Advances in Applied Mathematics, 2001 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
James Haglund, Jeffrey B. Remmel
openaire +1 more source
The hyper-Zagreb index of cacti with perfect matchings
AKCE International Journal of Graphs and Combinatorics, 2020 Let be a simple connected graph. The hyper-Zagreb index is defined as . A connected graph is a cacti if all blocks of are either edges or cycles. Let be the set of cacti of order with a perfect matching and cycles. In this paper, we determine sharp upper
Hechao Liu, Zikai Tang
doaj +1 more source
Trees maximizing the number of almost-perfect matchings
, 2022 We characterize the extremal trees that maximize the number of almost-perfect matchings, which are matchings covering all but one or two vertices, and those that maximize the number of strong almost-perfect matchings, which are matchings missing only one
Sharma, Gunjan +4 more
core
All Pairs of Pentagons in Leapfrog Fullerenes Are Nice
Mathematics, 2020 A subgraph H of a graph G with perfect matching is nice if G−V(H) has perfect matching. It is well-known that all fullerene graphs have perfect matchings and that all fullerene graphs contain some small connected graphs as nice subgraphs.
Tomislav Došlić
doaj +1 more source
Perfect matchings in planar cubic graphs
, 2012 A well-known conjecture of Lovasz and Plummer from the mid-1970’s, still open, asserts that for every cubic graph G with no cutedge, the number of perfect matchings in G is exponential in |V (G)|.
Seymour, Paul D., Chudnovsky, Maria
core +1 more source
Perfect Matchings in Claw-free Cubic Graphs
, 2009 Lovasz and Plummer conjectured that there exists a fixed positive constant c such that every cubic n-vertex graph with no cutedge has at least 2^(cn) perfect matchings.
Oum, Sang-il, Sang-il Oum
core +1 more source