## Adjacency matrix[Too large to display] |
## Adjacency list[Too large to display] |

34265

Most Maximum Matchings Tree 31

Kevin Ryde

Invariant | Value | Invariant | Value |
---|---|---|---|

Acyclic | Yes | Index | 2.463 |

Algebraic Connectivity | 0.038 | Laplacian Largest Eigenvalue | 5.571 |

Average Degree | 1.935 | Longest Induced Cycle | undefined |

Bipartite | Yes | Longest Induced Path | 10 |

Chromatic Index | 4 | Matching Number | 9 |

Chromatic Number | 2 | Maximum Degree | 4 |

Circumference | undefined | Minimum Degree | 1 |

Claw-Free | No | Minimum Dominating Set | 9 |

Clique Number | 2 | Number of Components | 1 |

Connected | Yes | Number of Edges | 30 |

Density | 0.065 | Number of Triangles | 0 |

Diameter | 10 | Number of Vertices | 31 |

Edge Connectivity | 1 | Planar | Yes |

Eulerian | No | Radius | 5 |

Genus | 0 | Regular | No |

Girth | undefined | Second Largest Eigenvalue | 2.236 |

Hamiltonian | No | Smallest Eigenvalue | -2.463 |

Independence Number | 22 | Vertex Connectivity | 1 |

A table row rendered like this
indicates that the graph is marked as being *interesting* for that invariant.

Posted by Kevin Ryde at Feb 5, 2020 7:30 AM.

Heuberger and Wagner determine trees of n vertices with the most maximum matchings and show there is a unique such tree (except two each at n=6 and n=34). The present tree is n=31. It has 22140 maximum matchings (of size matchnum 9).

Clemens Heuberger and Stephan Wagner, "The Number of Maximum Matchings In a Tree", Discrete Mathematics, volume 311, issue 21, November 2011, pages 2512-2542. http://arxiv.org/abs/1011.6554

Clemens Heuberger and Stephan Wagner, "The Number of Maximum Matchings In a Tree", Discrete Mathematics, volume 311, issue 21, November 2011, pages 2512-2542. http://arxiv.org/abs/1011.6554

You need to be logged in to be able to add comments.