Perfect matchings in claw-free cubic graphs.
Displaying 341 – 360 of 455
Perfect matchings in -regular graphs.
Alon, Noga, Rödl, Vojtěch, Ruciński, Andrzej (1998)
The Electronic Journal of Combinatorics [electronic only]
Perfect Set of Euler Tours of Kp,p,p
T. Govindan, A. Muthusamy (2016)
Discussiones Mathematicae Graph Theory
Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G, is Hamilton cycle decomposable. In this paper, we construct a perfect set of Euler tours for the complete tripartite graph Kp,p,p for any prime p and hence prove Bermond’s conjecture for G = Kp,p,p.
Perfect transversal in some graph products.
Olaru, Elefterie, Mandrescu, Eugen, Ion, Cristian, Anastasoaei, Vasile (2005)
Acta Universitatis Apulensis. Mathematics - Informatics
Perfectly balanced partitions of smoothed graphs.
Ben-Eliezer, Ido, Krivelevich, Michael (2009)
The Electronic Journal of Combinatorics [electronic only]
Perfectly matchable subgraph problem on a bipartite graph
Firdovsi Sharifov (2010)
RAIRO - Operations Research
We consider the maximum weight perfectly matchable subgraph problem on a bipartite graph G=(UV,E) with respect to given nonnegative weights of its edges. We show that G has a perfect matching if and only if some vector indexed by the nodes in UV is a base of an extended polymatroid associated with a submodular function defined on the subsets of UV. The dual problem of the separation problem for the extended polymatroid is transformed to the special maximum flow problem on G. In this paper, we give...
Permanents, Pfaffian orientations, and even directed circuits.
Robertson, Neil, Seymour, P.D., Thomas, Robin (1999)
Annals of Mathematics. Second Series
Permutation separations and complete bipartite factorisations of .
Martin, Nigel, Stong, Richard (2003)
The Electronic Journal of Combinatorics [electronic only]
Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs.
Lin, Feng-Gen, Zhang, Lian-Zhu (2009)
The Electronic Journal of Combinatorics [electronic only]
Placing bipartite graphs of small size II
Beata Orchel (1996)
Discussiones Mathematicae Graph Theory
In this paper we give all pairs of non mutually placeable (p,q)-bipartite graphs G and H such that 2 ≤ p ≤ q, e(H) ≤ p and e(G)+e(H) ≤ 2p+q-1.
Point partition numbers and generalized Nordhaus-Gaddum problems
Mieczysław Borowiecki (1984)
Colloquium Mathematicae
Poisson matching
Alexander E. Holroyd, Robin Pemantle, Yuval Peres, Oded Schramm (2009)
Annales de l'I.H.P. Probabilités et statistiques
Suppose that red and blue points occur as independent homogeneous Poisson processes in ℝd. We investigate translation-invariant schemes for perfectly matching the red points to the blue points. For any such scheme in dimensions d=1, 2, the matching distance X from a typical point to its partner must have infinite d/2th moment, while in dimensions d≥3 there exist schemes where X has finite exponential moments. The Gale–Shapley stable marriage is one natural matching scheme, obtained by iteratively...
Polynomial-time partition of a graph into cliques.
Plotnikov, Anatoly D. (1996)
Southwest Journal of Pure and Applied Mathematics [electronic only]
Primal-dual approximation algorithms for a packing-covering pair of problems
Sofia Kovaleva, Frits C. R. Spieksma (2002)
RAIRO - Operations Research - Recherche Opérationnelle
We consider a special packing-covering pair of problems. The packing problem is a natural generalization of finding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of finding a (weighted) minimum clique cover in an interval graph. The problem pair involves weights and capacities; we consider the case of unit weights and the case of unit capacities. In each case we describe a simple algorithm that outputs a solution to the packing problem and...
Primal-dual approximation algorithms for a packing-covering pair of problems
Sofia Kovaleva, Frits C.R. Spieksma (2010)
RAIRO - Operations Research
We consider a special packing-covering pair of problems. The packing problem is a natural generalization of finding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of finding a (weighted) minimum clique cover in an interval graph. The problem pair involves weights and capacities; we consider the case of unit weights and the case of unit capacities. In each case we describe a simple algorithm that outputs a solution to the packing problem and...
Problem presented at the workshop in Krynica 2004
Michael Kubesa, Dalibor Froncek (2006)
Discussiones Mathematicae Graph Theory
Problème de la bipartition minimale d'un graphe
Catherine Roucairol, Pierre Hansen (1987)
RAIRO - Operations Research - Recherche Opérationnelle
Rainbow -factors.
Yuster, Raphael (2006)
The Electronic Journal of Combinatorics [electronic only]
Rainbow -factors of complete -uniform -partite hypergraphs.
Chen, Ailian, Zhang, Fuji, Li, Hao (2008)
The Electronic Journal of Combinatorics [electronic only]
Rainbow matching in edge-colored graphs.
LeSaulnier, Timothy D., Stocker, Christopher, Wenger, Paul S., West, Douglas B. (2010)
The Electronic Journal of Combinatorics [electronic only]