Hamiltonian decomposition of lexicographic product

In this paper we prove the conjecture of J.-C. Bermond (Ann. Discrete Math.36 (1978), 21–28): If two graphs are decomposable into Hamiltonian cycles, then their lexicographic product is decomposable, too.     

The Riesz decomposition property for the space of regular operators

If and are Banach lattices such that is separable and has the countable interpolation property, then the space of all continuous regular operators has the Riesz decomposition property. This result is a positive answer to a conjecture posed by A. W. Wickstead.

     

Quotients of partial abelian monoids and the Riesz decomposition property

Partial abelian monoids (PAMs) are structures (), where is a partially defined binary operation with domain , which is commutative and associative in a restricted sense, and 0 is the neutral element. PAMs with the Riesz decomposition properties and binary relations with special properties on PAMs are studied. Relations with abelian groups, dimension equivalence and K ₀ for AF C^*-algebras are discussed. Received September 17, 2000; accepted in final form March 13, 2002.     

The geodetic number of the lexicographic product of graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in an interval between two vertices from S. The size of a minimum geodetic set in G is the geodetic number g(G) of G. We find that the geodetic number of the lexicographic product G°H for a non-complete graph H lies between 2 and 3g(G). We characterize the graphs G and H for which g(G°H)=2, as well as the lexicographic products T°H that enjoy g(T°H)=3g(G), when T is isomorphic to a tree. Using a new concept of the so-called geodominating triple of a graph G, a formula that expresses the exact geodetic number of G°H is established, where G is an arbitrary graph and H a non-complete graph.     

When the cartesian product of two directed cycles is hypo-Hamiltonian

We show that the Cartesian product Z_a × Z_b of two directed cycles is hypo-Hamiltonian (Hamiltonian) if and only if there is a pair of relatively prime positive integers m and n with ma + nb = ab - 1 (ma + nb = ab). The result for hypo-Hamiltonian is new; that for Hamiltonian is known. These are special cases of the fact that there is a simple circuit of length p in Z_a × Z_b if and only if there is a pair of relatively prime non-negative integers m and n with ma + nb = p ≤ ab.     

When the cartesian product of two directed cycles is hyperhamiltonian

We say a digraph G is hyperhamiltonian if there is a spanning closed walk in G which passes through one vertex exactly twice and all others exactly once. We show the cartesian product Z_a × Z_b of two directed cycles is hyperhamiltonian if and only if there are positive integers m and n with ma + nb = ab + 1 and gcd(m, n) = 1 or 2. We obtain a similar result for the vertex-deleted subdigraphs of Z_a × Z_b.     

Some results on the lexicographic product of vertex-transitive graphs

Many large graphs can be constructed from existing smaller graphs by using graph operations, for example, the Cartesian product and the lexicographic product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the lexicographic products of vertex-transitive and of edge-transitive graphs. In particular, we show that the lexicographic product of Cayley graphs is a Cayley graph.     

Some remarks on the Krein-Milman property and lexicographic maxima

A Banach space has thelexicographic property if each bounded closed convex subsetC is the closed convex hull of the lexicographic maxima ofC. The relationships between this property and the Radon-Nikodym and Krein-Milman properties are provided. A example inl ¹ contrasts these concepts. The main result states that a Banach space which is anr-space has the lexicographic property. Several questions relating to these topics and also flat spaces are posed.     

广义字典序积的自同态幺半群

讨论了图的广义字典序积的自同态幺半群的性质,给出了广义字典序积图X[Yz|x∈V（X）]的自同态幺半群与X,Yx(x∈V(X))的自同态幺半群的圈积相等的充要条件。     

Toll number of the Cartesian and the lexicographic product of graphs

Toll convexity is a variation of the so-called interval convexity. A tolled walk $T$ between two non-adjacent vertices $u$ and $v$ in a graph $G$ is a walk, in which $u$ is adjacent only to the second vertex of $T$ and $v$ is adjacent only to the second-to-last vertex of $T$. A toll interval between $u,v\in V\left(G\right)$ is a set $T_G(u,v)=\{x\in V\left(G\right):x\text{ lies on a tolled walk between }u\text{ and }v\}$. A set $S?V\left(G\right)$ is toll convex, if $T_G(u,v)?S$ for all $u,v\in S$. A toll closure of a set $S?V\left(G\right)$ is the union of toll intervals between all pairs of vertices from $S$. The size of a smallest set $S$ whose toll closure is the whole vertex set is called a toll number of a graph $G$, $tn\left(G\right)$. The first part of the paper reinvestigates the characterization of convex sets in the Cartesian product of two graphs. It is proved that the toll number of the Cartesian product of two graphs equals 2. In the second part, the toll number of the lexicographic product of two graphs is studied. It is shown that if $H$ is not isomorphic to a complete graph, $tn(G°H)\le 3?tn\left(G\right)$. We give some necessary and sufficient conditions for $tn(G°H)=3?tn\left(G\right)$. Moreover, if $G$ has at least two extreme vertices, a complete characterization is given. Furthermore, graphs with $tn(G°H)=2$ are characterized. Finally, the formula for $tn(G°H)$ is given — it is described in terms of the so-called toll-dominating triples or, if $H$ is complete, toll-dominating pairs.     

The chromatic number and other functions of the lexicographic product

The values of the chromatic and achromatic number, point- and line-connectivity, and point independence number of the lexicographic product of two graphs are examined in relation to the values of the respective parameters on the factor graphs.     

The Riesz decomposition of finely superharmonic functions

This paper answers a question of Fuglede about minimal positive harmonic functions associated with irregular boundary points. As a consequence, an old and central problem of fine potential theory, concerning the Riesz decomposition, is resolved. Namely, it is shown that, on certain fine domains, there exist positive finely superharmonic functions which do not admit any positive finely harmonic minorant and yet are not fine potentials.     

Decomposition tree of a lexicographic product of binary structures

Given a set S and a positive integer k, a binary structure is a function . The set S is denoted by V(B) and the integer k is denoted by . With each subset X of V(B) associate the binary substructure B[X] of B induced by X defined by B[X](x,y)=B(x,y) for any x≠y∈X. A subset X of V(B) is a clan of B if for any x,y∈X and v∈V(B)?X, B(x,v)=B(y,v) and B(v,x)=B(v,y). A subset X of V(B) is a hyperclan of B if X is a clan of B satisfying: for every clan Y of B, if X∩Y≠0?, then X⊆Y or Y⊆X. With each binary structure B associate the family Π(B) of the maximal proper and nonempty hyperclans under inclusion of B. The decomposition tree of a binary structure B is constituted by the hyperclans X of B such that Π(B[X])≠0? and by the elements of Π(B[X]). Given binary structures B and C such that , the lexicographic product B⌊C⌋ of C by B is defined on V(B)×V(C) as follows. For any (x,y)≠(x^′,y^′)∈V(B)×V(C), B⌊C⌋((x,x^′),(y,y^′))=B(x,y) if x≠y and B⌊C⌋((x,x^′),(y,y^′))=C(x^′,y^′) if x=y. The decomposition tree of the lexicographic product B⌊C⌋ is described from the decomposition trees of B and C.     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,…,k}的G的一个正常边染色.用w_σ（x）表示顶点x关联边的颜色之和,即w_σ（x）=∑_e∋x σ（e）,并称w_σ（x）关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为χ'_∑（G）.现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.