For a graph G, we denote by <InlineEquation ID="IEq1"> <EquationSource Format="TEX">${Z}(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Z</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> the number of matchings, including the empty edge set, in G. In this paper we focus on the determination of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">${Z}(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Z</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for the maximal outerplanar graphs G of given order in each of which all vertices lie on the boundary of the outer face but the addition of any edge will destroy its outerplanar property. By constructing the injection from the matching set of one graph to the other, we show that, among all maximal outerplanar graphs G of given order <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$n\ge 9$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>9</mn> </mrow> </math></EquationSource> </InlineEquation>, the maximum and the minimum of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">${Z}(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Z</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> are uniquely attained at the square <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$P_n^2$</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>P</mi> <mi>n</mi> <mn>2</mn> </msubsup> </math></EquationSource> </InlineEquation> of path <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$P_n$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> and the fan <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$FA_n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>F</mi> <msub> <mi>A</mi> <mi>n</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>, respectively. Finally two relevant problems are proposed to the number of matchings of maximal outerplanar graphs.

On the number of matchings in maximal outerplanar graphs

期刊论文
发表日期：

2026年3月3日

查看全文

Kexiang Xu,
Lihua Wei

摘要

For a graph G, we denote by ${Z}(G)$ $Z (G)$ the number of matchings, including the empty edge set, in G. In this paper we focus on the determination of ${Z}(G)$ $Z (G)$ for the maximal outerplanar graphs G of given order in each of which all vertices lie on the boundary of the outer face but the addition of any edge will destroy its outerplanar property. By constructing the injection from the matching set of one graph to the other, we show that, among all maximal outerplanar graphs G of given order $n\ge 9$ $n \geq 9$ , the maximum and the minimum of ${Z}(G)$ $Z (G)$ are uniquely attained at the square $P_n^2$ $P_{n}^{2}$ of path $P_n$ $P_{n}$ and the fan $FA_n$ $F A_{n}$ , respectively. Finally two relevant problems are proposed to the number of matchings of maximal outerplanar graphs.