DIKUL - logo
E-resources
Full text
Peer reviewed
  • The proper 2-connection num...
    Doan, Trung Duy; Schiermeyer, Ingo

    Discrete Applied Mathematics, 10/2022, Volume: 320
    Journal Article

    An edge-coloured graph G is called properlyk-connected if any two vertices are connected by at least k internally vertex-disjoint paths whose edges are properly coloured. The properk-connection number of a k-connected graph G, denoted by pck(G), is the minimum number of colours that are needed in order to make it properly k-connected. Let fk(n,r) be the minimum integer such that every k-connected graph of order n and size at least fk(n,r) has proper k-connection number at most r. Our main results are as follows: (1) Let G be a 2-connected graph of order n≥19. If |E(G)|≥n−32+7, then pc2(G)=2. (2) Let G be a hamiltonian graph G of order n≥50 and size |E(G)|>n24. Then pc2(G)=2. We also determine lower and upper bounds for f2(n,r).