Rainbow Connection Number and Radius

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) ≤  r(r + 2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K _1,n for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) ≤  rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 ? 1, where n is order of the graph (Caro et al. in Electron J Comb 15(1):Research paper 57, 13, 2008). It is known that computing rc(G) is NP-Hard (Chakraborty and fischer in J Comb Optim 1–18, 2009). Here, we present a (r + 3)-factor approximation algorithm which runs in O(nm) time and a (d + 3)-factor approximation algorithm which runs in O(dm) time to rainbow colour any connected graph G on n vertices, with m edges, diameter d and radius r.     

Rainbow Connection Number and Independence Number of a Graph

A path in an edge-colored graph is called rainbow if any two edges of the path have distinct colors. An edge-colored graph is called rainbow connected if there exists a rainbow path between every two vertices of the graph. For a connected graph G, the minimum number of colors that are needed to make G rainbow connected is called the rainbow connection number of G, denoted by rc(G). In this paper, we investigate the relation between the rainbow connection number and the independence number of a graph. We show that if G is a connected graph without pendant vertices, then \(\mathrm{rc}(G)\le 2\alpha (G)-1\). An example is given showing that the upper bound \(2\alpha (G)-1\) is equal to the diameter of G, and so the upper bound is sharp since the diameter of G is a lower bound of \(\mathrm{rc}(G)\).     

Total Rainbow Connection Number and Complementary Graph

A vertex-colored graph G is rainbow vertex connected if any two distinct vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex connected. In this paper, we prove that for a connected graph G, if \({{\rm diam}(\overline{G}) \geq 3}\), then \({{\rm rvc}(G) \leq 2}\), and this bound is tight. Next, we obtain that for a triangle-free graph \({\overline{G}}\) with \({{\rm diam}(\overline{G}) = 2}\), if G is connected, then \({{\rm rvc}(G) \leq 2}\), and this bound is tight. A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc(G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we prove that for a triangle-free graph \({\overline{G}}\) with \({{\rm diam}(\overline{G}) = 3}\), if G is connected, then trc\({(G) \leq 5}\), and this bound is tight. Next, a Nordhaus–Gaddum-type result for the total rainbow connection number is provided. We show that if G and \({\overline{G}}\) are both connected, then \({6 \leq {\rm trc} (G) + {\rm trc}(\overline{G}) \leq 4n - 6.}\) Examples are given to show that the lower bound is tight for \({n \geq 7}\) and n = 5. Tight lower bounds are also given for n = 4, 6.     

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) ≤ 2r(G) + c, where r(G) denotes the radius of G and \({c \in \{0, 1, 2\}}\) . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius [1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time \({(2 + \frac{2}{r(G)})}\) -factor approximation algorithms.     

The Rainbow Connection Number of the Power Graph of a Finite Group

This paper studies the rainbow connection number of the power graph \(\Gamma _G\) of a finite group G. We determine the rainbow connection number of \(\Gamma _G\) if G has maximal involutions or is nilpotent, and show that the rainbow connection number of \(\Gamma _G\) is at most three if G has no maximal involutions. The rainbow connection numbers of power graphs of some nonnilpotent groups are also given.     

Rainbow Connection and Graph Products

A path in an edge colored graph G is called a rainbow path if all its edges have pairwise different colors. Then G is rainbow connected if there exists a rainbow path between every pair of vertices of G and the least number of colors needed to obtain a rainbow connected graph is the rainbow connection number. If we demand that there must exist a shortest rainbow path between every pair of vertices, we speak about strongly rainbow connected graph and the strong rainbow connection number. In this paper we study the (strong) rainbow connection number on the direct, strong, and lexicographic product and present several upper bounds for these products that are attained by many graphs. Several exact results are also obtained.     

Rainbow Connection in Some Digraphs

An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. This concept was introduced by Chartrand et al. (Math Bohemica 133(1):85–98, 2008), and it was extended to oriented graphs by Dorbec et al. (Discrete Appl Math 179(31):69–78, 2014). In this paper we present some results regarding this extension, mostly for the case of circulant digraphs.     

Rainbow Connection in 3-Connected Graphs

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we proved that rc(G) ≤ 3(n + 1)/5 for all 3-connected graphs.     

Conflict-free Connection Number and Independence Number of a Graph

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path,which contains a color used on exactly one of its edges.The conflict-free connection number of a connected graph G,denoted by cf c(G),is defined as the minimum number of colors that are required in order to make G conflict-free connected.In this paper,we investigate the relation between the conflict-free connection number and the independence number of a graph.We firstly show that cf c(G)≤α(G)for any connected graph G,and give an example to show that the bound is sharp.With this result,we prove that if T is a tree with?(T)≥(α(T)+2)/2,then cf c(T)=?(T).     

基于复数理论的同异型联系数及其应用

虽然联系数中的i与复数中的i有不同的含义,但所定义的同异型联系数与复数在形式上完全相同.为此,依据复数理论给出了同异型联系数的三角函数与指数函数两种表述形式及其互相转换,举例说明其应用,从而为发展联系数理论提供了新的途径.     

Upper Bounds for the Rainbow Connection Numbers of Line Graphs

A path in an edge-colored graph G, where adjacent edges may be colored the same, is called a rainbow path if no two edges of it are colored the same. A nontrivial connected graph G is rainbow connected if for any two vertices of G there is a rainbow path connecting them. The rainbow connection number of G, denoted rc(G), is defined as the smallest number of colors such that G is rainbow connected. In this paper, we mainly study the rainbow connection number rc(L(G)) of the line graph L(G) of a graph G which contains triangles. We get two sharp upper bounds for rc(L(G)), in terms of the number of edge-disjoint triangles of G. We also give results on the iterated line graphs.     

可拓集联系数的势及其关系

在可拓集联系数的基础上,提出了可拓集集对势的概念,并且对集合型可拓集联系数的关系做了定义.这使得可拓集合与集对分析的结合更加紧密,而且可以在实际中得到更好的应用.     

用拉普拉斯谱半径定序给定阶和匹配数的树

Let T（n,i） be the set of all trees with order n and matching number i.We determine the third to sixth trees in T（2i ＋ 1,i） and the third to fifth trees in T（n,i） for n ≥ 2i ＋ 2 with the largest Laplacian spectral radius.     

区间型联系数及其在多属性决策中的应用

在联系数的基础上定义了区间型联系数,并讨论了相应的运算法则,然后将区间型联系数应用于区间型多属性决策问题,在文中为了便于对决策结果的排序定义了区间型联系数的相对贴近度及关于区间型正理想解的投影等概念,并通过实例分析验证了该方法的有效性和实用性.     

基于误差传递和联系数的动态区间型多属性决策方法

提出了一种基于误差传递和联系数的动态区间型多属性决策方法。该方法从区间数型属性值的误差视角出发,运用误差传递模型确定了属性权重区间;兼顾多时间段内信息“累积存量”和“增长速率”,确定时间变权;利用UDWA算子集结所有决策时间段的属性权重区间,获得综合属性权重区间;利用IWAA算子集结不同属性下决策信息,得到属性综合决策矩阵;根据集对分析理论,利用联系数和投影隶属度得到备选方案的优劣性排序。以高专利密集型企业研发伙伴选择为例,验证了该方法的可行性和有效性。     

基于投影的联系数多属性决策方法

针对属性权重和属性值均以联系数形式给出的区间型多属性决策问题,提出了一种基于投影的决策方法.方法依据一般投影分析方法的基本思路,给出了解决属性取值为联系数的多属性决策问题的计算步骤,核心是通过构建并求解每个方案在虚拟正、负理想方案上的投影,进而计算出每个方案对虚拟正、负理想方案的相对一致度,即可得到所有方案的排序结果,     

On a Connection of Number Theory with Graph Theory

We assign to each positive integer n a digraph whose set of vertices is H = {0, 1, ..., n – 1} and for which there is a directed edge from a H to b H if a ² b (mod n). We establish necessary and sufficient conditions for the existence of isolated fixed points. We also examine when the digraph is semiregular. Moreover, we present simple conditions for the number of components and length of cycles. Two new necessary and sufficient conditions for the compositeness of Fermat numbers are also introduced.     

A Characterization of Graphs Where the Independence Number Equals the Radius

In a classical 1986 paper by Erdös, Saks and Saós every graph of radius r has an induced path of order at least 2r ? 1. This result implies that the independence number of such graphs is at least r. In this paper, we use a result of S. Fajtlowicz about radius-critical graphs to characterize graphs where the independence number is equal to the radius, for all possible values of the radius except 2, 3, and 4. We briefly discuss these remaining cases as well.