Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K_(7,n) when 7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C(x) denote the set of colors of vertex x and of the edges incident with x, we call C(x) the color set of x. If C(u)≠ C(v) for any two different vertices u and v of V(G), then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by χ_(vt)~e(G) and is called the VDET chromatic number of G. The VDET coloring of complete bipartite graph K_(7,n)(7 ≤ n ≤ 95) is discussed in this paper and the VDET chromatic number of K_(7,n)(7 ≤ n ≤ 95) has been obtained.     

A sufficient condition for asymptotically well behaved property of convex polynomials

In this paper, we employ an asymptotic assumption to show that the maximum of finitely many convex polynomials is an asymptotically well behaved function. We also give two examples to illustrate our main result. As an application, we reproduce some known results appeared recently in the literature.     

Collapsing and the convex hull property in a soap film capillarity model

Soap films hanging from a wire frame are studied in the framework of capillarity theory. Minimizers in the corresponding variational problem are known to consist of positive volume regions with boundaries of constant mean curvature/pressure, possibly connected by “collapsed” minimal surfaces. We prove here that collapsing only occurs if the mean curvature/pressure of the bulky regions is negative, and that, when this last property holds, the whole soap film lies in the convex hull of its boundary wire frame.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

Optimality for set functions with values in ordered vector spaces

Let (X, , ) be a finite atomless measure space,L a convex subfamily of , andY andZ locally convex Hausdorff topological vector spaces which are ordered by the conesC andD, respectively. LetF:LY beC-convex andG:LZ beD-convex set functions. Consider the following optimization problem (P): minimizeF(), subject to L andG() _D . The paper generalizes the Moreau-Rockafellar theorem with set functions. By applying this theorem, a Kuhn-Tucker type optimality condition and a Fritz John type optimality condition for problem (P) are established. The duality theorem for problem (P) is also studied.This work was partially supported by National Science Council, Taipei, Taiwan. This paper was written while the first author was visiting at the University of Iowa, 1987-88.The authors would like to express their gratitude to the two anonymous referees for their valuable comments. Also, they would like to thank Professor P. L. Yu for his encouragement and suggestions which improved the material presented here considerably.     

SC-Hamiltonian graphs and digraphs: New necessary conditions and their impacts

A graph G on n vertices is said to be separable cost constant Hamiltonian (SC-Hamiltonian) if and only if G is Hamiltonian and for any cost matrix C=(c_(i,j)) associated with G where all tours have the same cost, there exist vectors a=(a₁,…,a_n) and b=(b₁,…,b_n) such that . In this paper we show that for symmetric digraphs strong Hamiltonicity is a necessary condition for SC-Hamiltonicity. As a surprising consequence, we prove that the symmetric digraph obtained from an undirected SC-Hamiltonian graph by edge duplication need not be SC-Hamiltonian. This settles a conjecture of Kabadi and Punnen. We then show that an undirected graph on an even number of nodes having an edge that appears in every Hamiltonian cycle cannot be SC-Hamiltonian. Using this we establish that multiple subdivision of an edge need not preserve SC-Hamiltonicity, disproving a previous claim. Further, we identify other necessary conditions for SC-Hamiltonicity and obtain new classes of SC-Hamiltonian graphs.     

Distortion theorems for convex mappings on homogeneous balls

Let B be the open unit ball of a complex Banach space X and let B be homogeneous. We prove distortion results for normalized convex mappings f:B→X which generalize various finite dimensional distortion theorems and improve some infinite dimensional ones. In particular, our results are valid for the open unit balls of complex Hilbert spaces and the Cartan domains.     

On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcón, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269-277]. In this work, we consider the decision problems: given a graph G=(V,E) and an integer k≥0, we ask whether there exists a subset V^′⊆V with |V^′|≥k such that the induced subgraph G[V^′] of G is, variously, a clique, clique-Helly or hereditary clique-Helly graph. The first problem is clearly NP-complete, from the above reference; we prove that the other two decision problems mentioned are NP-complete, even for maximum degree 6 planar graphs. We consider the corresponding maximization problems of finding a maximum induced subgraph that is, respectively, clique, clique-Helly or hereditary clique-Helly. We show that these problems are Max SNP-hard, even for maximum degree 6 graphs. We show a general polynomial-time -approximation algorithm for these problems when restricted to graphs with fixed maximum degree Δ. We generalize these results to other graph classes. We exhibit a polynomial 6-approximation algorithm to minimize the number of vertices to be removed in order to obtain a hereditary clique-Helly subgraph.