The Maximum Number of Spanning Trees of a Graph with Given Matching Number

Muhuo Liu; Guangliang Zhang; Kinkar Chandra Das

doi:10.1007/s40840-021-01142-7

The Maximum Number of Spanning Trees of a Graph with Given Matching Number

Muhuo Liu, Guangliang Zhang, Kinkar Chandra Das

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. Feng et al. determined the maximum number of spanning trees in the class of connected graphs with n vertices and matching number β for 2 ≤ β≤ n/ 3 and β= ⌊ n/ 2 ⌋. They also pointed out that it is still an open problem to the case of n/ 3 < β≤ ⌊ n/ 2 ⌋ - 1. In this paper, we solve this problem completely.

Original language	English
Pages (from-to)	3725-3732
Number of pages	8
Journal	Bulletin of the Malaysian Mathematical Sciences Society
Volume	44
Issue number	6
DOIs	https://doi.org/10.1007/s40840-021-01142-7
State	Published - Nov 2021

Keywords

Graph
Matching number
Spanning tree

Access to Document

10.1007/s40840-021-01142-7

Cite this

@article{9feabee495754516813c2dfd18ce8442,

title = "The Maximum Number of Spanning Trees of a Graph with Given Matching Number",

abstract = "The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. Feng et al. determined the maximum number of spanning trees in the class of connected graphs with n vertices and matching number β for 2 ≤ β≤ n/ 3 and β= ⌊ n/ 2 ⌋. They also pointed out that it is still an open problem to the case of n/ 3 < β≤ ⌊ n/ 2 ⌋ - 1. In this paper, we solve this problem completely.",

keywords = "Graph, Matching number, Spanning tree",

author = "Muhuo Liu and Guangliang Zhang and Das, \{Kinkar Chandra\}",

note = "Publisher Copyright: {\textcopyright} 2021, Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia.",

year = "2021",

month = nov,

doi = "10.1007/s40840-021-01142-7",

language = "English",

volume = "44",

pages = "3725--3732",

journal = "Bulletin of the Malaysian Mathematical Sciences Society",

issn = "0126-6705",

publisher = "Springer Singapore",

number = "6",

}

TY - JOUR

T1 - The Maximum Number of Spanning Trees of a Graph with Given Matching Number

AU - Liu, Muhuo

AU - Zhang, Guangliang

AU - Das, Kinkar Chandra

PY - 2021/11

Y1 - 2021/11

N2 - The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. Feng et al. determined the maximum number of spanning trees in the class of connected graphs with n vertices and matching number β for 2 ≤ β≤ n/ 3 and β= ⌊ n/ 2 ⌋. They also pointed out that it is still an open problem to the case of n/ 3 < β≤ ⌊ n/ 2 ⌋ - 1. In this paper, we solve this problem completely.

AB - The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. Feng et al. determined the maximum number of spanning trees in the class of connected graphs with n vertices and matching number β for 2 ≤ β≤ n/ 3 and β= ⌊ n/ 2 ⌋. They also pointed out that it is still an open problem to the case of n/ 3 < β≤ ⌊ n/ 2 ⌋ - 1. In this paper, we solve this problem completely.

KW - Graph

KW - Matching number

KW - Spanning tree

UR - https://www.scopus.com/pages/publications/85106406283

U2 - 10.1007/s40840-021-01142-7

DO - 10.1007/s40840-021-01142-7

M3 - Article

AN - SCOPUS:85106406283

SN - 0126-6705

VL - 44

SP - 3725

EP - 3732

JO - Bulletin of the Malaysian Mathematical Sciences Society

JF - Bulletin of the Malaysian Mathematical Sciences Society

IS - 6

ER -

The Maximum Number of Spanning Trees of a Graph with Given Matching Number

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this