<p>A spanning tree <i>T</i> of a connected graph <i>G</i> is a subgraph of <i>G</i> that is a tree covering all vertices of <i>G</i>. The leaf distance of <i>T</i> is defined as the minimum of distances between any two leaves of <i>T</i>. A fractional matching of a graph <i>G</i> is a function <i>h</i> assigning every edge a real number in [0,&#xa0;1] so that <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\sum \limits _{e\in E_G(v)}{h(e)}\le 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <munder> <mo movablelimits="false">∑</mo> <mrow> <mi>e</mi> <mo>∈</mo> <msub> <mi>E</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </munder> <mrow> <mi>h</mi> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for any <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(v\in V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(E_G(v)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>E</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> denotes the set of edges incident with <i>v</i> in <i>G</i>. A fractional matching of <i>G</i> is called a fractional perfect matching if <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\sum \limits _{e\in E_G(v)}{h(e)}=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <munder> <mo movablelimits="false">∑</mo> <mrow> <mi>e</mi> <mo>∈</mo> <msub> <mi>E</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </munder> <mrow> <mi>h</mi> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for any <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(v\in V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. A graph <i>G</i> with at least <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(2k+2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> vertices is said to be fractional <i>k</i>-extendable if every <i>k</i>-matching <i>M</i> in <i>G</i> is included in a fractional perfect matching <i>h</i> of <i>G</i> such that <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(h(e)=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>h</mi> <mo stretchy="false">(</mo> <mi>e</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> for any <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(e\in M\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>e</mi> <mo>∈</mo> <mi>M</mi> </mrow> </math></EquationSource> </InlineEquation>. This paper considers a lower bound on the spectral radius of <i>G</i> to guarantee that <i>G</i> has a spanning tree with leaf distance at least <i>d</i>. At the same time, we obtain a lower bound on the spectral radius of <i>G</i> to ensure that <i>G</i> is fractional <i>k</i>-extendable.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Spanning subgraphs and spectral radius in graphs

  • Sizhong Zhou

摘要

A spanning tree T of a connected graph G is a subgraph of G that is a tree covering all vertices of G. The leaf distance of T is defined as the minimum of distances between any two leaves of T. A fractional matching of a graph G is a function h assigning every edge a real number in [0, 1] so that \(\sum \limits _{e\in E_G(v)}{h(e)}\le 1\) e E G ( v ) h ( e ) 1 for any \(v\in V(G)\) v V ( G ) , where \(E_G(v)\) E G ( v ) denotes the set of edges incident with v in G. A fractional matching of G is called a fractional perfect matching if \(\sum \limits _{e\in E_G(v)}{h(e)}=1\) e E G ( v ) h ( e ) = 1 for any \(v\in V(G)\) v V ( G ) . A graph G with at least \(2k+2\) 2 k + 2 vertices is said to be fractional k-extendable if every k-matching M in G is included in a fractional perfect matching h of G such that \(h(e)=1\) h ( e ) = 1 for any \(e\in M\) e M . This paper considers a lower bound on the spectral radius of G to guarantee that G has a spanning tree with leaf distance at least d. At the same time, we obtain a lower bound on the spectral radius of G to ensure that G is fractional k-extendable.