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

34257

Most Maximum Matchings Tree 27

Kevin Ryde

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

Acyclic | Yes | Index | 2.449 |

Algebraic Connectivity | 0.051 | Laplacian Largest Eigenvalue | 5.543 |

Average Degree | 1.926 | Longest Induced Cycle | undefined |

Bipartite | Yes | Longest Induced Path | 8 |

Chromatic Index | 4 | Matching Number | 8 |

Chromatic Number | 2 | Maximum Degree | 4 |

Circumference | undefined | Minimum Degree | 1 |

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

Clique Number | 2 | Number of Components | 1 |

Connected | Yes | Number of Edges | 26 |

Density | 0.074 | Number of Triangles | 0 |

Diameter | 8 | Number of Vertices | 27 |

Edge Connectivity | 1 | Planar | Yes |

Eulerian | No | Radius | 4 |

Genus | 0 | Regular | No |

Girth | undefined | Second Largest Eigenvalue | 2.175 |

Hamiltonian | No | Smallest Eigenvalue | -2.449 |

Independence Number | 19 | 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:25 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=27. It has 5832 maximum matchings (of size matchnum 8).

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.