2022/06/23 by Christoph Brause, Brause, Christoph, Stanislav Jendrol′ +3
Computer Science · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2 #Graph Labeling and Dimension Problems #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2206.11604
openalex publication_date 2022/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Kr,s with \lec(Kr,s) = 2.