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 a path (u 1, u 2, ..., u k)...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 a path (u 1, u 2, ..., u k), k≥1, in G such that L(u i)+1<L(u i+1) for all i=1, 2, ..., k?1. The total number of increasing nonconsecutive paths in (G, L) is denoted by d(G, L). The following open problem was proposed by Gargano, Lewinter and Malerba: obtaining a labeling L that produces the largest d(P n, L), where P n is a path of order n. Such a labeling is called optimal. The author have solved this problem. For each n ≥ 5 and for n=3, there are exactly four optimal labelings. Either of P 2, P 4 has exactly two optimal labelings. MR Subject Classification 05C38 Keywords labeled graph - increasing nonconsecutive paths展开更多
文摘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 a path (u 1, u 2, ..., u k), k≥1, in G such that L(u i)+1<L(u i+1) for all i=1, 2, ..., k?1. The total number of increasing nonconsecutive paths in (G, L) is denoted by d(G, L). The following open problem was proposed by Gargano, Lewinter and Malerba: obtaining a labeling L that produces the largest d(P n, L), where P n is a path of order n. Such a labeling is called optimal. The author have solved this problem. For each n ≥ 5 and for n=3, there are exactly four optimal labelings. Either of P 2, P 4 has exactly two optimal labelings. MR Subject Classification 05C38 Keywords labeled graph - increasing nonconsecutive paths
