The profile of the Cartesian product of graphs

被引:1
作者
Kuo, David [1 ]
Yan, Jing-Ho [2 ]
机构
[1] Dong Hwa Univ, Dept Appl Math, Hualien 974, Taiwan
[2] Aletheia Univ, Dept Math, Tamsui 251, Taiwan
关键词
Profile; n-cube; Optimal labeling; Cartesian product; PMNL-graph; P-property;
D O I
10.1016/j.dam.2007.11.016
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Given a graph G, a proper labeling f of G is a one-to-one function from V (G) onto {1, 2, ... , vertical bar V(G)vertical bar}. For a proper labeling f of G, the profile width omega(f)(v) of a vertex v is the minimum value of f(v) - f(x), where x belongs to the closed neighborhood of v. The profile of a proper labeling f of G, denoted by P-f(G), is the sum of all the omega(f)(v), where v epsilon V(G). The profile of G is the minimum value of P-f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G x Q(n). This can be used to determine the profile of Q(n) and K-m x Q(n). (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码:2835 / 2845
页数:11
相关论文
共 13 条
  • [1] THE BANDWIDTH PROBLEM FOR GRAPHS AND MATRICES - A SURVEY
    CHINN, PZ
    CHVATALOVA, J
    DEWDNEY, AK
    GIBBS, NE
    [J]. JOURNAL OF GRAPH THEORY, 1982, 6 (03) : 223 - 254
  • [2] Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
  • [3] GIBBS NE, 1974, COMMUN ACM, V20, P20
  • [4] Harper L. H., 1966, J COMBINATORIAL THEO, V1, P385, DOI DOI 10.1016/S0021-9800(66)80059-5
  • [5] OPTIMAL ASSIGNMENTS OF NUMBERS TO VERTICES
    HARPER, LH
    [J]. JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1964, 12 (01): : 131 - 135
  • [6] THE PROFILE MINIMIZATION PROBLEM IN TREES
    KUO, D
    CHANG, GJ
    [J]. SIAM JOURNAL ON COMPUTING, 1994, 23 (01) : 71 - 81
  • [7] On the profile of the corona of two graphs
    Lai, YL
    Chang, GJ
    [J]. INFORMATION PROCESSING LETTERS, 2004, 89 (06) : 287 - 292
  • [8] Exact profile values of some graph compositions
    Lai, YL
    [J]. TAIWANESE JOURNAL OF MATHEMATICS, 2002, 6 (01): : 127 - 134
  • [9] Lai YL, 1999, J GRAPH THEOR, V31, P75, DOI 10.1002/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO
  • [10] 2-S