<p>A line digraph <i>L</i>(<i>D</i>) of a directed multigraph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(D=(V(D),A(D))\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> has as its vertex-set being <i>A</i>(<i>D</i>), the set of arcs of <i>D</i>, where (<i>a</i>,&#xa0;<i>b</i>) is an arc of <i>L</i>(<i>D</i>) if and only if there are vertices <i>u</i>,&#xa0;<i>v</i>, and <i>w</i> in <i>D</i> such that <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(a=(u,v)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>a</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(b=(v,w)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>b</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>v</mi> <mo>,</mo> <mi>w</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> are in <i>A</i>(<i>D</i>). In this paper, we obtain sufficient and necessary conditions for a line digraph <i>L</i>(<i>D</i>) to be supereulerian and to have a spanning trail, respectively, in terms of certain types of path-cycle covers of <i>D</i>. These results will be applied to show each of the following for a digraph <i>D</i>. (i) If <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(|A(D)|\geqslant (|V(D)|-1)^2+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mi>A</mi> <mrow> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> </mrow> <mo>⩾</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mo stretchy="false">|</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, then <i>L</i>(<i>D</i>) is supereulerian. The lower bound on |<i>A</i>(<i>D</i>)| is best possible in the sense that there exists an infinite family of digraphs each of which satisfies <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(|A(D)| = (|V(D)|-1)^2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mi>A</mi> <mrow> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> </mrow> <mo>=</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mo stretchy="false">|</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> </mrow> </math></EquationSource> </InlineEquation> without a supereulerian line digraph. (ii) There exists a well-characterized digraph family <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\mathcal {M}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">M</mi> </math></EquationSource> </InlineEquation> such that if <i>D</i> is strong with <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(|A(D)|\leqslant |V(D)|+2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>A</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>⩽</mo> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, then <i>L</i>(<i>D</i>) is supereulerian if and only if <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(D\not \in \mathcal {M}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo>∉</mo> <mi mathvariant="script">M</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Spanning Eulerian Subdigraph in Line Digraphs

  • Juan Liu,
  • Hong Yang,
  • Xindong Zhang,
  • Hong-Jian Lai

摘要

A line digraph L(D) of a directed multigraph \(D=(V(D),A(D))\) D = ( V ( D ) , A ( D ) ) has as its vertex-set being A(D), the set of arcs of D, where (ab) is an arc of L(D) if and only if there are vertices uv, and w in D such that \(a=(u,v)\) a = ( u , v ) and \(b=(v,w)\) b = ( v , w ) are in A(D). In this paper, we obtain sufficient and necessary conditions for a line digraph L(D) to be supereulerian and to have a spanning trail, respectively, in terms of certain types of path-cycle covers of D. These results will be applied to show each of the following for a digraph D. (i) If \(|A(D)|\geqslant (|V(D)|-1)^2+1\) | A ( D ) | ( | V ( D ) | - 1 ) 2 + 1 , then L(D) is supereulerian. The lower bound on |A(D)| is best possible in the sense that there exists an infinite family of digraphs each of which satisfies \(|A(D)| = (|V(D)|-1)^2\) | A ( D ) | = ( | V ( D ) | - 1 ) 2 without a supereulerian line digraph. (ii) There exists a well-characterized digraph family \(\mathcal {M}\) M such that if D is strong with \(|A(D)|\leqslant |V(D)|+2\) | A ( D ) | | V ( D ) | + 2 , then L(D) is supereulerian if and only if \(D\not \in \mathcal {M}\) D M .