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 (u1,u2, …,uk) (k ≥ 2) in G such that L(ui) 2 ≤ L(ui 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.