On the number of increasing paths in labeled cycles and stars

A labeled graph is an ordered pair (G, L) consisting of a graph G and its labeling L: V (G) → {1, 2,..., n}, where n = V(G) . An increasing nonconsecutive path in a labeled graph (G, L) is either a path (u₁, u₂,..., u_k) (k ≥ 2) in G such that L(u_i) + 2 ≤ L (u_i+1) for all i = 1, 2,..., k - 1 or a path of order 1. The total number of increasing nonconsecutive paths in (G, L) is denoted by d (G, L). A labeling L is optimal if the labeling L produces the largest d (G, L). In this paper, a method simpler than that in Zverovich (2004) to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.