<p>Let <i>G</i> be a nontrivial connected graph with an edge coloring, and let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(u,v \in V(G)\)</EquationSource> </InlineEquation>. A <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(u-v\)</EquationSource> </InlineEquation> path in <i>G</i> is said to be a <i>rainbow path</i> if no color is repeated on the edges of the path. Similarly, we define a <i>rainbow geodesic</i>. A <i>rainbow connected graph</i> <i>G</i> is a graph with an edge coloring such that every two vertices in <i>G</i> are connected by a rainbow path. Further, a <i>strong rainbow connected graph</i> <i>G</i> is a graph with an edge coloring such that every two vertices in <i>G</i> is connected by a rainbow geodesic. The minimum number of colors needed to make a graph rainbow connected is called the <i>rainbow connection number</i>, denoted <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\({{\,\textrm{rc}\,}}(G)\)</EquationSource> </InlineEquation>, and the minimum number of colors needed to make a graph strong rainbow connected is called the <i>strong rainbow connection number</i>, denoted <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\({{\,\textrm{src}\,}}(G)\)</EquationSource> </InlineEquation>. In this paper we determine <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\({{\,\textrm{rc}\,}}(G)\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\({{\,\textrm{src}\,}}(G)\)</EquationSource> </InlineEquation> when <i>G</i> is a <i>n</i>-dimensional rectangular grid graph, triangular grid graph, hexagonal grid graph, and a (weak) Bruhat graph, respectively. We show for all these families that <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\({{\,\textrm{src}\,}}(G)={{\,\textrm{diam}\,}}(G)\)</EquationSource> </InlineEquation>.</p>

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

The rainbow connected number of several infinite graph families

  • Liam B. Baker,
  • Jonathan Kariv,
  • Ronald J. Maartens

摘要

Let G be a nontrivial connected graph with an edge coloring, and let \(u,v \in V(G)\) . A \(u-v\) path in G is said to be a rainbow path if no color is repeated on the edges of the path. Similarly, we define a rainbow geodesic. A rainbow connected graph G is a graph with an edge coloring such that every two vertices in G are connected by a rainbow path. Further, a strong rainbow connected graph G is a graph with an edge coloring such that every two vertices in G is connected by a rainbow geodesic. The minimum number of colors needed to make a graph rainbow connected is called the rainbow connection number, denoted \({{\,\textrm{rc}\,}}(G)\) , and the minimum number of colors needed to make a graph strong rainbow connected is called the strong rainbow connection number, denoted \({{\,\textrm{src}\,}}(G)\) . In this paper we determine \({{\,\textrm{rc}\,}}(G)\) and \({{\,\textrm{src}\,}}(G)\) when G is a n-dimensional rectangular grid graph, triangular grid graph, hexagonal grid graph, and a (weak) Bruhat graph, respectively. We show for all these families that \({{\,\textrm{src}\,}}(G)={{\,\textrm{diam}\,}}(G)\) .