几类凝聚图的轮廓

PROFILES OF SOME CONDENSABLE GRAPHS

设Ｇ是个图，｜Ｖ（Ｇ）＝ｎ｜对Ｇ上的任一个标号ｆ：Ｖ（Ｇ）→｛１，…，ｎ｝记，且当ｊ≠ｉ时，Ｇ中有边以ｆ（－１）（ｊ）及ｆ（－１）（ｉ）为两端点｝）．称Ｐ（Ｇ）＝ｍｉｎ｛Ｐ（ｆ）：ｆ是Ｇ上的标号｝为图Ｇ的轮廓．对以Ｗ表示Ｇ中Ｗ的边界．本文证明：ｉ）若Ｇ是凝聚图，ｆ及ｆ是Ｇ上一对互逆标号，则Ｐ（Ｇ）＝Ｐ（ｆ）的充要条件是ｆ为凝聚标号，且此时若Ｇ，Ｈ均是凝聚图，则存在阶梯标号。使得路、回、完全留之间的下列乘积图也是凝聚图。

Let G be a graph,and |V(G)| = n. For any labeling f: V(G) → {1,…,n}on G, write then f-1 (f) and f-1(i) are adjacent in G}). Define P(G)= min{p(f): f is a labeling on G} and call P(G) the profile of graph G.For W C V(G), denote the boundary of W in G by W. In this paper we prove: 1) If G is a condensable graph, and f and f are mutually inverse labelings on G, then P(G) ￣ p(f) if andonly if f is a condensable labeling. And in this case If both G and H are condensable grabs, then there is a staircase labeling ψ such that P(G ×H)= p(ψ);iii) The following products involving paths, cycles and complete graphs are also condensable graphs, and their profiles are P(Pm ×Kn) = (m-1/2)n2-n/2, P(Cm × Km) =(2m-3)n2 (m >4),P(Cm × Cn) = [(2m -2n/3 + 1/2)n2-16n/3 + 3-min {1,m--n} (m > n >2> 3); iv)P(C3 × Km) = [(13n2-2n)/4.