Re: enumeration of matching


Francois Delbot

On Jun 9, 12:53 am, Francois Delbot <francois.del...@xxxxxxxxx> wrote:
dear all,
i need to know how many maximal matching we can do in a graph.
i call maximal the fact that we cannot add anymore edge in a matching.

is there any papers about this ?

i thank you for the time you will accord to me.
best regards

francois delbot


More precisely, I am interested in counting the matching in a graph
class, for example in a grid, an hypercube, a tree etc...

more, i am very interested in the average size of a matching. did
someone know about that ?

best regards
francois
Here has two papers, which is about perfect mathcing relation with
Hamiltonian cycle problem.

http://front.math.ucdavis.edu/0704.0309
http://front.math.ucdavis.edu/0706.2725

I hope that you could find more strength results on this kind of
relation.
---------------------------------
Best regards,
Zhu

.

Relevant Pages

  • enumeration of matching
    ... i need to know how many maximal matching we can do in a graph. ... i call maximal the fact that we cannot add anymore edge in a matching. ...
    (comp.theory)
  • Re: enumeration of matching
    ... i need to know how many maximal matching we can do in a graph. ... i call maximal the fact that we cannot add anymore edge in a matching. ... I am interested in counting the matching in a graph ...
    (comp.theory)
  • Graph Matching Genetic Algorithms
    ... I m planning to develop a genetic algo based graph matching. ... the input graph is a region adjacency graphwith feature vector ...
    (comp.ai.genetic)
  • entering matching data for line charts
    ... In Excel 2003 I'm trying to construct a line graph ... in which there is is more than one set of matching x and y values. ... If I were drawing a scatter plot, I could enter matching x and y values, but ...
    (microsoft.public.excel.charting)
  • Re: Finding the Maximum Number of Node-disjoint Cycles
    ... What format should I use to describe the graph? ... in principle it's easy to read and convert other formats. ... >G has a disjoint cycle cover if and only if H has a perfect matching. ...
    (comp.theory)