On the number of increasing paths in labeled cycles and stars

被引：0

作者：

Chen L. ^{[1
]}

Lü C. ^{[1
,2
]}

Ye Y. ^{[3
]}

机构：

[1] Department of Mathematics, East China Normal University

[2] Institute of Theoretical Computing, East China Normal University

[3] Department of Mathematics, Huaibei Coal Industry Teachers College

来源：

Applied Mathematics-A Journal of Chinese Universities | 2007年 / 22卷 / 1期

关键词：

Cycle; Labeled graph; Path;

D O I：

10.1007/s11766-007-0001-3

中图分类号：

学科分类号：

摘要：

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. © Editorial Committee of Applied Mathematics 2007.

引用

页码：1 / 6

页数：5