Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices

This paper shows that any planar graph with n vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that any number of planar graphs admit a simultaneous embedding without mapping with at most one bend per edge.     

Distance Between α-Orientations of Plane Graphs by Facial Cycle Reversals

Cycle reversal had been shown as a powerful method to deal with the relation among orientations of a graph since it preserves the out-degree of each vertex and the connectivity of the orientations. A facial cycle reversal on an orientation of a plane graph is an operation that reverses all the directions of the edges of a directed facial cycle. An orientation of a graph is called an α-orientation if each vertex admits a prescribed out-degree. In this paper, we give an explicit formula for the minimum number of the facial cycle reversals needed to transform one α-orientation into another for plane graphs.     

A Measure of Non-convexity in the Plane and the Minkowski Sum

In this paper a measure of non-convexity for a simple polygonal region in the plane is introduced. It is proved that for “not far from convex” regions this measure does not decrease under the Minkowski sum operation, and guarantees that the Minkowski sum has no “holes”.     

The Moduli Space of Complex Geodesics in the Complex Hyperbolic Plane

We consider the space M\mathcal{M} of ordered m-tuples of distinct complex geodesics in complex hyperbolic 2-space, H_\mathbbC²{\rm\bf H}_{\mathbb{C}}^{2}, up to its holomorphic isometry group PU(2,1). One of the important problems in complex hyperbolic geometry is to construct and describe the moduli space for M\mathcal{M}. This is motivated by the study of the deformation space of groups generated by reflections in complex geodesics. In the present paper, we give the complete solution to this problem.     

A 3-color Theorem on Plane Graphs without 5-circuits

In this paper, we prove that every plane graph without 5-circuits and without triangles of distance less than 3 is 3-colorable. This improves the main result of Borodin and Raspaud [Borodin, O. V., Raspaud, A.： A sufficient condition for planar graphs to be 3-colorable. Journal of Combinatorial Theory, Ser. B, 88, 17-27 （2003）], and provides a new upper bound to their conjecture.     

Fluctuation Identities Applied to the Hitting Time of a Half-line in the Plane

We study asymptotic estimates that contain the hitting time and the hitting place of a half-line by a two-dimensional random walk. Fluctuation identities are used without resorting to pair annihilation but by interchanging summation and integration. The same method applies to the hitting of the half-space by a one-dimensional random walk. The author was supported by a grant (no. 18740053) of Japan Society for the Promotion of Science.     

Applications of Automata and Graphs: Labeling-Operators in Hilbert Space I

We show that certain representations of graphs by operators on Hilbert space have uses in signal processing and in symbolic dynamics. Our main result is that graphs built on automata have fractal characteristics. We make this precise with the use of Representation Theory and of Spectral Theory of a certain family of Hecke operators. Let G be a directed graph. We begin by building the graph groupoid $\Bbb{G}$ induced by G, and representations of  $\Bbb{G}$ . Our main application is to the groupoids defined from automata. By assigning weights to the edges of a fixed graph G, we give conditions for $\Bbb{G}$ to acquire fractal-like properties, and hence we can have fractaloids or G-fractals. Our standing assumption on G is that it is locally finite and connected, and our labeling of G is determined by the “out-degrees of vertices”. From our labeling, we arrive at a family of Hecke-type operators whose spectrum is computed. As applications, we are able to build representations by operators on Hilbert spaces (including the Hecke operators); and we further show that automata built on a finite alphabet generate fractaloids. Our Hecke-type operators, or labeling operators, come from an amalgamated free probability construction, and we compute the corresponding amalgamated free moments. We show that the free moments are completely determined by certain scalar-valued functions.     

The Linear Arboricity of Graphs

Inthispaper,allgraphsarefinite,simpleandundirected.Forarealnumberx,[x]istheleastintegernotlessthanx.LetG＝(V(G),E(G))beagraph.Weuse△(G)andδ(G)todenotethemaximum(vertex)degreeandtheminimum(vertex)degreeofG.Letw(G)＝min{d(u) d(v):uv∈E(G)}.Thegirthg(G)ofGistheminimumlengthofcycles.Thedensitymad(G)ofagraphGisthemaximumvalueof2|E(H)|/|V(H)|takenoverallsubgraphsHofG.Ifv6V(G),N(v)denotesthesetofvenicesadjacenttov,thedegreedG(v)isING(v)landNc(v)={aluEN(v)andd(u)=k}.Avertexofdegreekisc…     

Quasi-I-Hamilton Connectedness of Tree Graphs

For any graph G, Γ(G) is uniformly hamiltonian whenever it contains at least two cycles [1] and is either a hypercube or hamilton connected [2].In this paper, a further investigation to the hamiltonian property of tree graphs will be made.     

A Polynomial Bound for Untangling Geometric Planar Graphs

To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos (Discrete Comput. Geom. 28(4): 585–592, 2002) asked if every n-vertex geometric planar graph can be untangled while keeping at least n ^ε vertices fixed. We answer this question in the affirmative with ε=1/4. The previous best known bound was \(\Omega(\sqrt{\log n/\log\log n})\). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least \(\Omega(\sqrt{n})\) vertices fixed, while the best upper bound was \(\mathcal{O}((n\log n)^{2/3})\). We answer a question of Spillner and Wolff (http://arxiv.org/abs/0709.0170) by closing this gap for untangling trees. In particular, we show that for infinitely many values of n, there is an n-vertex geometric tree that cannot be untangled while keeping more than \(3(\sqrt{n}-1)\) vertices fixed.     

Globally Convergent Cutting Plane Method for Nonconvex Nonsmooth Minimization

Nowadays, solving nonsmooth (not necessarily differentiable) optimization problems plays a very important role in many areas of industrial applications. Most of the algorithms developed so far deal only with nonsmooth convex functions. In this paper, we propose a new algorithm for solving nonsmooth optimization problems that are not assumed to be convex. The algorithm combines the traditional cutting plane method with some features of bundle methods, and the search direction calculation of feasible direction interior point algorithm (Herskovits, J. Optim. Theory Appl. 99(1):121–146, 1998). The algorithm to be presented generates a sequence of interior points to the epigraph of the objective function. The accumulation points of this sequence are solutions to the original problem. We prove the global convergence of the method for locally Lipschitz continuous functions and give some preliminary results from numerical experiments.     

The Maximum Size and Related Extremal Graphs of Critically h-Edge-Connected Graphs

Let G be a simple graph.The edge-connectivity of G is denoted by λ(G). For a given positive integer h,G is said to be critically h-edge-connected ifλ(G)=h and λ(G-χ)相似文献   

Pancyclism and Bipancyclism of Hamiltonian Graphs

A graph G on n vertices is called pancyclic if it contains cycles of everylength k, for 3≤k≤n. A bipartite graph on 2n vertices is called bipancyclicif it contains cycles of every even length 2k, for 2≤k≤n. In this paper,we consider only finite, undirected graphs without loops ormultipie edges. We shall give a new sufficient condition ensuring a Hamiltonian graph tobe pancyclic(or bipancyclic), The main results are the following two theorems.Theorem A. Let G be a Hamiltonian graph of order n. If there exisis a     

The Entire Coloring of Series-Parallel Graphs

The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6.     

Asymptotic Properties of Orthogonal Polynomials with Respect to a Non-discrete Jacobi-Sobolev Inner Product

Let {Q _n ^(α,β) (x)} _n=0 ^∞ denote the sequence of polynomials orthogonal with respect to the non-discrete Sobolev inner product

$\langle f,g\rangle=\int_{-1}^{1}f(x)g(x)d\mu_{\alpha,\beta}(x)+\lambda\int_{-1}^{1}f'(x)g'(x)d\nu_{\alpha,\beta}(x)$

where λ>0 and d μ _α,β(x)=(x?a)(1?x)^α?1(1+x)^β?1 dx, d ν _α,β(x)=(1?x) ^α (1+x) ^β dx with aα,β>0. Their inner strong asymptotics on (?1,1), a Mehler-Heine type formula as well as some estimates of the Sobolev norms of Q _n ^(α,β) are obtained.

     

Super-edge-graceful Labelings of Some Cubic Graphs

The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are super-edge-graceful. A conjecture is proposed.     

Sampling, Filtering and Sparse Approximations on Combinatorial Graphs

In this paper we address sampling and approximation of functions on combinatorial graphs. We develop filtering on graphs by using Schrödinger’s group of operators generated by combinatorial Laplace operator. Then we construct a sampling theory by proving Poincare and Plancherel-Polya-type inequalities for functions on graphs. These results lead to a theory of sparse approximations on graphs and have potential applications to filtering, denoising, data dimension reduction, image processing, image compression, computer graphics, visualization and learning theory.     

Equitable Coloring of Complete r-partite Graphs

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets of as near equal sizes as possible. In this paper, we determine a sufficient and necessary condition for which a complete r-partite graph is equitably k-colorable. From this result, we can provide another way to prove some previous results.