The Genus of a Digital Image Boundary Is Determined by Its Foreground,Background, and Reeb Graphs

We prove that the genus of the boundary of a digital image is precisely half of the sum of the cycle ranks of three particular graphs: the "foreground graph" and "background graph," which capture topological information about the digital image and its complement, respectively, and the Reeb graph, relative to the natural height function, associated with the digital image's boundary. We prove several additional results, including a characterization of when the cycle rank of the Reeb graph fails to equal the genus of the digital image's boundary (which can happen by virtue of the failure of the natural height function on the boundary of the digital image to be a Morse function).     

Loops in Reeb Graphs of 2-Manifolds

Given a Morse function f over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on the number of loops in the Reeb graph that depend on the genus, the number of boundary components, and whether or not the 2-manifold is orientable. We also give an algorithm that constructs the Reeb graph in time O(n log n), where n is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.     

Coherent orientations in symplectic field theory

We study the coherent orientations of the moduli spaces of holomorphic curves in Symplectic Field Theory, generalizing a construction due to Floer and Hofer. In particular we examine their behavior at multiple closed Reeb orbits under change of the asymptotic direction. The orientations are determined by a certain choice of orientation at each closed Reeb orbit, that is similar to the orientation of the unstable tangent spaces of critical points in finite–dimensional Morse theory.in final form: 22 October 2003     

Reeb graph and quasi-states on the two-dimensional torus

This note deals with quasi-states on the two-dimensional torus. Quasistates are certain quasi-linear functionals (introduced by Aarnes) on the space of continuous functions. Grubb constructed a quasi-state on the torus, which is invariant under the group of area-preserving diffeomorphisms, and which moreover vanishes on functions having support in an open disk. Knudsen asserted the uniqueness of such a quasi-state; for the sake of completeness, we provide a proof. We calculate the value of Grubb’s quasi-state on Morse functions with distinct critical values via their Reeb graphs. The resulting formula coincides with the one obtained by Py in his work on quasi-morphisms on the group of area-preserving diffeomorphisms of the torus. Included is a short introduction to the link between quasi-states and quasi-morphisms in symplectic geometry.     

On the editing distance of graphs

An edge‐operation on a graph G is defined to be either the deletion of an existing edge or the addition of a nonexisting edge. Given a family of graphs , the editing distance from G to is the smallest number of edge‐operations needed to modify G into a graph from . In this article, we fix a graph H and consider Forb(n, H), the set of all graphs on n vertices that have no induced copy of H. We provide bounds for the maximum over all n‐vertex graphs G of the editing distance from G to Forb(n, H), using an invariant we call the binary chromatic number of the graph H. We give asymptotically tight bounds for that distance when H is self‐complementary and exact results for several small graphs H. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:123–138, 2008     

Reeb Graphs: Approximation and Persistence

Given a continuous function f:X→? on a topological space X, its level set f ^?1(a) changes continuously as the real value a changes. Consequently, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of f summarizes this information into a graph structure. Previous work on Reeb graph mainly focused on its efficient computation. In this paper, we initiate the study of two important aspects of the Reeb graph, which can facilitate its broader applications in shape and data analysis. The first one is the approximation of the Reeb graph of a function on a smooth compact manifold M without boundary. The approximation is computed from a set of points P sampled from M. By leveraging a relation between the Reeb graph and the so-called vertical homology group, as well as between cycles in M and in a Rips complex constructed from P, we compute the H ₁-homology of the Reeb graph from P. It takes O(nlogn) expected time, where n is the size of the 2-skeleton of the Rips complex. As a by-product, when M is an orientable 2-manifold, we also obtain an efficient near-linear time (expected) algorithm for computing the rank of H ₁(M) from point data. The best-known previous algorithm for this problem takes O(n ³) time for point data. The second aspect concerns the definition and computation of the persistent Reeb graph homology for a sequence of Reeb graphs defined on a filtered space. For a piecewise-linear function defined on a filtration of a simplicial complex K, our algorithm computes all persistent H ₁-homology for the Reeb graphs in $O(n n_{e}^{3})$ time, where n is the size of the 2-skeleton and n _e is the number of edges in K.     

Improved bounds for interatomic distance in Morse clusters

We improve the best known lower bounds on the distance between two points of an optimal Morse cluster, with ρ[4.967,15]. We develop a generalization of a method previously applied to the Lennard-Jones potential, that also leads to improvements of lower bounds for the Morse potential.     

Distance–regular graphs having the M-property

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.     

Locally s‐distance transitive graphs

We give a unified approach to analyzing, for each positive integer s, a class of finite connected graphs that contains all the distance transitive graphs as well as the locally s‐arc transitive graphs of diameter at least s. A graph is in the class if it is connected and if, for each vertex v, the subgroup of automorphisms fixing v acts transitively on the set of vertices at distance i from v, for each i from 1 to s. We prove that this class is closed under forming normal quotients. Several graphs in the class are designated as degenerate, and a nondegenerate graph in the class is called basic if all its nontrivial normal quotients are degenerate. We prove that, for s≥2, a nondegenerate, nonbasic graph in the class is either a complete multipartite graph or a normal cover of a basic graph. We prove further that, apart from the complete bipartite graphs, each basic graph admits a faithful quasiprimitive action on each of its (1 or 2) vertex‐orbits or a biquasiprimitive action. These results invite detailed additional analysis of the basic graphs using the theory of quasiprimitive permutation groups. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:176‐197, 2012     

Conditional extremals in complete Riemannian manifolds

Conditional extremal curves in a complete Riemannian manifold M are defined as the critical points of the squared L² distance between the tangent vector field of a curve and a so-called prior vector field. We prove that this L² distance satisfies the Palais-Smale condition on the space of absolutely continuous curves joining two submanifolds of M, and thus establish the existence of critical points. We also prove a Morse index theorem in the case where the two submanifolds are single points, and use the Morse inequalities to place lower bounds on the number of critical points of each index.     

On perturbations of almost distance-regular graphs

In this paper we show that certain almost distance-regular graphs, the so-called h-punctually walk-regular graphs, can be characterized through the cospectrality of their perturbed graphs. A graph G with diameter D is called h-punctually walk-regular, for a given h≤D, if the number of paths of length ? between a pair of vertices u,v at distance h depends only on ?. The graph perturbations considered here are deleting a vertex, adding a loop, adding a pendant edge, adding/removing an edge, amalgamating vertices, and adding a bridging vertex. We show that for walk-regular graphs some of these operations are equivalent, in the sense that one perturbation produces cospectral graphs if and only if the others do. Our study is based on the theory of graph perturbations developed by Cvetkovi?, Godsil, McKay, Rowlinson, Schwenk, and others. As a consequence, some new characterizations of distance-regular graphs are obtained.     

Distance Integral Complete Multipartite Graphs with s=5, 6

Let D(G) = (dij )n×n denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vertices vi and vj in G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In 2014, Yang and Wang gave a su?cient and necessary condition for complete r-partite graphs Kp1,p2,··· ,pr =Ka1·p1,a2·p2,··· ,as···ps to be distance integral and obtained such distance integral graphs with s = 1, 2, 3, 4. However distance integral complete multipartite graphs Ka1·p1,a2·p2,··· ,as·ps with s>4 have not been found. In this paper, we find and construct some infinite classes of these distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with s = 5, 6. The problem of the existence of such distance integral graphs Ka1·p1,a2·p2,··· ,as·ps with arbitrarily large number s remains open.     

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...     

Proximity‐preserving labeling schemes

This article considers informative labeling schemes for graphs. Specifically, the question introduced is whether it is possible to label the vertices of a graph with short labels in such a way that the distance between any two vertices can be inferred from inspecting their labels. A labeling scheme enjoying this property is termed a proximity‐preserving labeling scheme. It is shown that, for the class of n‐vertex weighted trees with M‐bit edge weights, there exists such a proximity‐preserving labeling scheme using O(M log n + log²n) bit labels. For the family of all n‐vertex unweighted graphs, a labeling scheme is proposed that using O(log² n · κ · n^1/κ) bit labels can provide approximate estimates to the distance, which are accurate up to a factor of In particular, using O(log³n) bit labels, the scheme can provide estimates accurate up to a factor of $\sqrt{2 \log n}$. (For weighted graphs, one of the log n factors in the label size is replaced by a factor logarithmic in the network's diameter.) © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 167–176, 2000     

On codimension one foliations with Morse singularities on three-manifolds

A closed, connected oriented three-manifold supporting a codimension one oriented smooth foliation with Morse singularities having more centers than saddles and without saddle connections is diffeomorphic to the three-sphere. The use of the Reeb Stability theorem in place of the Poincaré-Bendixson theorem paves the way to a three-dimensional version, for foliations with singularities of Morse type, of a classical result of Haefliger. Finally, we give an example of a codimension one C^∞ foliation in the closed ball , with only one singularity which is of saddle type 2-2 and transverse to the boundary S³=∂B⁴.     

Discrete Morse theory on graphs

We characterize the topology of a graph in terms of the critical elements of a discrete Morse function defined on it. Besides, we study the structure and some properties of the gradient vector field induced by a discrete Morse function defined on a graph. Finally, we get results on the number of non-homologically equivalent excellent discrete Morse functions defined on some kind of graphs.     

电阻-距离谱的若干结果

对连通图$G$的顶点$u$和$v$, $u$与$v$在$G$中的电阻距离$r_G(u,v)$等于相邻顶点之间的电阻为单位电阻的$G$对应的电网中$u$与$v$之间的等效电阻. 图$G$的电阻-距离特征值是$G$的电阻-距离矩阵$R(G)=(r_G(u,v))_{u,v\in V(G)}$的特征值. 我们分别确定了不同于完全图与完全图删去一条边后得到的图及给定割边数目的使得最大电阻-距离特征值取得最小值的唯一的连通图, 还讨论了最小电阻-距离特征值的性质.     

New bounds for Morse clusters

This paper presents new, simple arguments improving the lower bounds for the total energy and the minimal inter-particle distance in minimal energy atom cluster problems with interactions given by a Morse potential, where the atom separation problem is difficult due to the finite energy at zero atom separation. Apart from being sharper than previously known bounds, they also apply for a wider range ρ ≥ 4.967 of the parameter in the Morse potential. Most results also hold for more general pair potentials.     

Planar unit-distance graphs having planar unit-distance complement

A graph G=(V,E) is called a unit-distance graph in the plane if there is an embedding of V into the plane such that every pair of adjacent vertices are at unit distance apart. If an embedding of V satisfies the condition that two vertices are adjacent if and only if they are at unit distance apart, then G is called a strict unit-distance graph in the plane. A graph G is a (strict) co-unit-distance graph, if both G and its complement are (strict) unit-distance graphs in the plane. We show by an exhaustive enumeration that there are exactly 69 co-unit-distance graphs (65 are strict co-unit-distance graphs), 55 of which are connected (51 are connected strict co-unit-distance graphs), and seven are self-complementary.