Abstract:

         This paper presents two neighborhood intersection conditions for λ₄-optimality in a graphs. Let G be a λ₄connected graph of order greater than 11. If the inequality |N(u)∩N(v)|≥5 holds and neither u nor v lies on a triangle(u and v are nonadjacent vertices),or the inequality |N(u)∩N(v)|≥7 holds and either u or v lies on a triangle,then G is λ₄-optimal.If the inequality |N(u)∩N(v)|≥5 holds and any one edge xy holds the inequality |N(x)∩N(y)|≤2,then G is also λ4optimal.These results can be applied to the analysis of network reliability.

Key words: graph, 4-restricted edge connectivity, λ₄-optimality