论文标题
图形的边缘连接松动
Loose edge-connection of graphs
论文作者
论文摘要
在过去的几年中，诸如彩虹连接和正确连接之类的连接概念出现在图理论中，并引起了很多关注。在本文中，我们研究了图的松散边缘连接。连接的边缘颜色的图$ g $如果其两个顶点之间的长度为一路，则是一条长度为2的双色路径，或长度为2的路径至少三种，其边缘上使用至少三种颜色，则是宽松的边缘连接。 $ g $的松散边缘色中使用的最小颜色数量称为松散的边缘连接数，并表示为$ \ lec（g）$。我们为任何简单的图表的直径$ g $至少3 $ 3确定了此参数的确切值。我们表明，决定是否$ \ lec（g）= 2 $ for Graphs $ g $直径2的$ g $是NP完整问题。此外，我们用$ \ lec（k_ {r，s}）= 2 $来表征所有完整的双分图$ k_ {r，s} $。
In the last years, connection concepts such as rainbow connection and proper connection appeared in graph theory and obtained a lot of attention. In this paper, we investigate the loose edge-connection of graphs. A connected edge-coloured graph $G$ is loose edge-connected if between any two of its vertices there is a path of length one, or a bi-coloured path of length two, or a path of length at least three with at least three colours used on its edges. The minimum number of colours, used in a loose edge-colouring of $G$, is called the loose edge-connection number and denoted $\lec(G)$. We determine the precise value of this parameter for any simple graph $G$ of diameter at least 3. We show that deciding, whether $\lec(G) = 2$ for graphs $G$ of diameter 2, is an NP-complete problem. Furthermore, we characterize all complete bipartite graphs $K_{r,s}$ with $\lec(K_{r,s}) = 2$.
