Every Planar Graph with Maximum Degree 7 Is of Class 1

V.G. Vizing conjectured in 1968 that every planar graph with maximum degree 6 or 7 is of class 1. This paper shows that, for planar graphs with maximum degree 7, Vizing's conjecture is true. Revised: November 24, 1999     

The Odd-Distance Plane Graph

The vertices of the odd-distance graph are the points of the plane ℝ². Two points are connected by an edge if their Euclidean distance is an odd integer. We prove that the chromatic number of this graph is at least five. We also prove that the odd-distance graph in ℝ² is countably choosable, while such a graph in ℝ³ is not. The research of J. Maňuch was supported in part by MITACS (Mathematics of Information Technology and Complex Systems). The research of M. Rosenfeld was supported in part by the Chancellor Research Grant and the Institute of Technology, UWT. The research of S. Shelah was supported by the United States-Israel Binational Science Foundation (Grant no. 2002323), and by NSF grant No. NSF-DMS 0600940. No. 923 on Shelah’s publication list. The research of L. Stacho was supported in part by NSERC (Natural Science and Engineering Research Council of Canada) grant.     

On Integral Well-rounded Lattices in the Plane

We investigate distribution of integral well-rounded lattices in the plane, parameterizing the set of their similarity classes by solutions of the family of Pell-type Diophantine equations of the form x ²+Dy ²=z ² where D>0 is squarefree. We apply this parameterization to the study of the greatest minimal norm and the highest signal-to-noise ratio on the set of such lattices with fixed determinant, also estimating cardinality of these sets (up to rotation and reflection) for each determinant value. This investigation extends previous work of the first author in the specific cases of integer and hexagonal lattices and is motivated by the importance of integral well-rounded lattices for discrete optimization problems. We briefly discuss an application of our results to planar lattice transmitter networks.     

Every 4-Connected Line Graph of a Planar Graph is Hamiltonian

Let G be a graph withE(G) $#x2260;ø. The line graph of G, written L(G) hasE(G) as its vertex set, where two vertices are adjacent in L(G) if and only if the corresponding edges are adjacent inG. Thomassen conjectured that all 4-connected line graphs are hamiltonian [2]. We show that this conjecture holds for planar graphs.     

Plane Embeddings of Planar Graph Metrics

Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular reconstruction, we consider the natural problem of embedding shortest-path metrics of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known that, in the special case of shortest-path metrics of trees, embedding into the plane requires distortion in the worst case [M1], [BMMV], and surprisingly, this worst-case upper bound provides the best known approximation algorithm for minimizing distortion. We answer an open question posed in this work and highlighted by Matousek [M3] by proving that some planar graph metrics require distortion in any embedding into the plane, proving the first separation between these two types of graph metrics. We also prove that some planar graph metrics require distortion in any crossing-free straight-line embedding into the plane, suggesting a separation between low-distortion plane embedding and the well-studied notion of crossing-free straight-line planar drawings. Finally, on the upper-bound side, we prove that all outerplanar graph metrics can be embedded into the plane with distortion, generalizing the previous results on trees (both the worst-case bound and the approximation algorithm) and building techniques for handling cycles in plane embeddings of graph metrics.     

Some Integral Representations and Singular Integral over Plane in Clifford Analysis

In this paper, Cauchy type integral and singular integral over hyper-complex plane \({\prod}\) are considered. By using a special Möbius transform, an equivalent relation between \({\widehat{H}^\mu}\) class functions over \({\prod}\) and \({H^\mu}\) class functions over the unit sphere is shown. For \({\widehat{H}^\mu}\) class functions over \({\prod}\) , we prove the existence of Cauchy type integral and singular integral over \({\prod}\) . Cauchy integral formulas as well as Poisson integral formulas for monogenic functions in upper-half and lower-half space are given respectively. By using Möbius transform again, the relation between the Cauchy type integrals and the singular integrals over \({\prod}\) and unit sphere is built.     

Convex Sets in the Plane with Three of Every Four Meeting

Dedicated to the memory of Paul Erdős Suppose we have a finite collection of closed convex sets in the plane, (which without loss of generality we can take to be polygons). Suppose further that among any four of them, some three have non-empty intersection. We show that 13 points are sufficient to meet every one of the convex sets. Received October 27, 1999/Revised April 11, 2000 RID="*" ID="*" Supported by grant OTKA-T-029074. RID="†" ID="†" Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F-22234.     

空间平面内整点n边形上的整点个数

本文给出了计算空间平面内整点n边形上的整点个数的一个公式。     

和图、整和图及模和图的几个结果

Let N denote the set of positive integers.The sum graph G (S) of a finite subset S (C) N is the graph (S,E) with uv ∈ E if and only if u v ∈ S.A graph G is said to be a sum graph if it is isomorphic to the sum graph of some S С N.By using the set Z of all integers instead of N,we obtain the definition of the integral sum graph.A graph G=(V,E) is a mod sum graph if there exists a positive integer z and a labelling,λ,of the vertices of G with distinct elements from {0,1,2,...,z-1} so that uv ∈ E if and only if the sum,modulo z,of the labels assigned to u and v is the label of a vertex of G.In this paper,we prove that flower tree is integral sum graph.We prove that Dutch m-wind-mill (Dm) is integral sum graph and mod sum graph,and give the sum number of Dm.     

Integral Geometry of Real Surfaces in the Complex Projective Plane

We give a Poincaré formula for any real surfaces in the complex projective plane which states that the mean value of the intersection numbers of two real surfaces is equal to the integral of some terms of their Kähler angles.     

最大平面图GM的孪生图GTM和对角线变换DT

提出了最大平面图GM的孪生图GTM和孪生图对的概念和定义,探讨了孪生图对的特性,分析了孪生图对的四色着色方案彼此间的关系,并由此形成了最大平面图着色的对角线变换法.文中以二个实例(正二十面体的平面嵌入图;Appel和Haken的例子)验证了研究的结果,同时也显示了孪生图GTM可被应用的场合及其实用性.     

具有最大度距离的单圈图

设U (n)是具有n个顶点的所有单圈图的集合,G(3; n- 3)是由一个三角形C3粘上一条悬挂路P_(n-3)得到的单圈图.本文将证明当n 5时具有最大度距离的单圈图是G(3; n - 3).     

Every Biregular Function Is a Biholomorphic Map

We study Fueter-biregular functions of one quaternionic variable. We consider left-regular functions in the kernel of the Cauchy–Riemann operator

The Reeb Graph Edit Distance is Universal

Foundations of Computational Mathematics - We consider the setting of Reeb graphs of piecewise linear functions and study distances between them that are stable, meaning that functions which are...     

Bounds on the Distance Two-Domination Number of a Graph

 For a graph G = (V, E), a subset D⊆V(G) is said to be distance two-dominating set in G if for each vertex u∈V−D, there exists a vertex v∈D such that d(u,v)≤2. The minimum cardinality of a distance two-dominating set in G is called a distance two-domination number and is denoted by γ₂(G). In this note we obtain various upper bounds for γ₂(G) and characterize the classes of graphs attaining these bounds. Received: May 31, 1999 Final version received: July 13, 2000     

On an Integral Equation in the Problem of Diffraction of a Plane Wave on a Transparent Circular Cone

The problem of diffraction on a transparent convex cone is studied. A uniqueness theorem is proved for the case where the cone is illuminated by a compact source. For a circular cone, the solution is obtained in the form of Kontorovich-Lebedev integrals and Fourier series expansions. A singular integral equation is deduced for the Fourier coefficients, and its regularization is carried out. Bibliography: 13 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 308, 2004, pp. 101–123.     

每个算子都是两个强不可约算子的和

本文证明了可分无穷维 Hilbert空间上每个有界线性算子均可写成两个强不可约算子之和 .这回答了文献 [9]中提出一个公开问题