| Gargano,Lewinter and Malerba问题的解 |
| |
| 引用本文： | Zverovich I E. Gargano,Lewinter and Malerba问题的解[J]. 高校应用数学学报(英文版), 2004, 19(3): 239-244. DOI: 10.1007/s11766-004-0030-0 |
| |
| 作者姓名： | Zverovich I E |
| |
| 作者单位： | RUTCOR—Rutgers Center |
| |
| 摘 要： | §1 IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1
|
| 关 键 词： | 小直径图 图表 应用数学 标签 次序 |
| 收稿时间： | 2003-12-04 |
A solution to a problem of Gargano,Lewinter and Malerba |
| |
| Zverovich IE. A solution to a problem of Gargano,Lewinter and Malerba[J]. Applied Mathematics A Journal of Chinese Universities, 2004, 19(3): 239-244. DOI: 10.1007/s11766-004-0030-0 |
| |
| Authors: | Zverovich IE |
| |
| Affiliation: | (1) RUTCOR—Rutgers Center for Operations Research, Rutgers, the State University of New Jersey, 640 Bartholomew Rd, 08854-8003 Piscataway, NJ, USA |
| |
| Abstract: | 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. |
| |
| Keywords: | labeled graph increasing nonconsecutive paths. |
| 本文献已被 CNKI 万方数据 SpringerLink 等数据库收录！ |
|
