Markov chains, Hamiltonian cycles and volumes of convex bodies

In this note the Hamiltonian cycle problem is mapped into an infinite horizon discounted cost constrained Markov decision problem. The occupation measure based linear polytope associated with this control problem defines a convex set which either strictly contains or is equal to another convex set, depending on whether the underlying graph has a Hamiltonian cycle or not. This allows us to distinguish Hamiltonian graphs from non-Hamiltonian graphs by comparing volumes of two convex sets.     

Application of inverse finite element method in tube hydroforming modeling

In tube hydroforming, the inverse finite element method (IFEM) has been used for estimating the initial length of tube, axial feeding and fluid pressure. The already developed IFEM algorithm used in this work is based on the total deformation theory of plasticity. Although the nature of tube hydroforming is three-dimensional deformation, in this paper a modeling technique has been used to perform the computations in two-dimensional space. Therefore, compared with conventional forward finite element methods, the present computations are quite fast with no trial and error process. In addition, the solution provides all the components of strain. Using the forming limit diagram (FLD), the components of strain can lead us to measure the potentials for failures or wrinkles during the deformation. The results of analysis for free bulging and square bulging have been compared with some published experimental data and the results obtained by conventional commercial software.     

Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

Null sets of harmonic measure on NTA domains: Lipschitz approximation revisited

We show the David–Jerison construction of big pieces of Lipschitz graphs inside a corkscrew domain does not require surface measure be upper Ahlfors regular. Thus we can study absolute continuity of harmonic measure and surface measure on NTA domains of locally finite perimeter using Lipschitz approximations. A partial analogue of the F. and M. Riesz Theorem for simply connected planar domains is obtained for NTA domains in space. As one consequence every Wolff snowflake has infinite surface measure.     

Scaled Gromov hyperbolic graphs

In this article, the δ‐hyperbolic concept, originally developed for infinite graphs, is adapted to very large but finite graphs. Such graphs can indeed exhibit properties typical of negatively curved spaces, yet the traditional δ‐hyperbolic concept, which requires existence of an upper bound on the fatness δ of the geodesic triangles, is unable to capture those properties, as any finite graph has finite δ. Here the idea is to scale δ relative to the diameter of the geodesic triangles and use the Cartan–Alexandrov–Toponogov (CAT) theory to derive the thresholding value of δdiam below which the geometry has negative curvature properties. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 157–180, 2008     

The Index of a Periodic Graph

For periodic graphs, a special class of infinite, but locally finite graphs, an index theory is developed that can serve in classifying these graphs and that enables connections with various graph invariants as in the case of finite graphs. The index is defined with the aid of certain finite matrices that result rather canonically from reductions of the infinite adjacency operator due to the periodicity. As a central result we derive a sharp global lower bound for the index of any periodic graph.     

Generalized Irreducible Divisor Graphs

In 1988, Beck introduced the notion of a zero-divisor graph of a commutative rings with 1. There have been several generalizations in recent years. In particular, in 2007 Coykendall and Maney developed the irreducible divisor graph. Much work has been done on generalized factorization, especially τ-factorization. The goal of this paper is to synthesize the notions of τ-factorization and irreducible divisor graphs in domains. We will define a τ-irreducible divisor graph for nonzero non unit elements of a domain. We show that, by studying τ-irreducible divisor graphs, we find equivalent characterizations of several finite τ-factorization properties.     

Hypersurfaces and Their Singularities in Partial Correlation Testing

An asymptotic theory is developed for computing volumes of regions in the parameter space of a directed Gaussian graphical model that are obtained by bounding partial correlations. We study these volumes using the method of real log canonical thresholds from algebraic geometry. Our analysis involves the computation of the singular loci of correlation hypersurfaces. Statistical applications include the strong-faithfulness assumption for the PC algorithm and the quantification of confounder bias in causal inference. A detailed analysis is presented for trees, bow ties, tripartite graphs, and complete graphs.     

On-line arbitrarily vertex decomposable suns

We give a complete characterization of on-line arbitrarily vertex decomposable graphs in the family of unicycle graphs called suns. A sun is a graph with maximum degree three, such that deleting vertices of degree one results in a cycle. This result has already been used in another paper to prove some Ore-type conditions for on-line arbitrarily decomposable graphs.     

Classification Problem for Graphs and Lattices is Wild

The classification problem for finite and infinite algebraic lattices has also been extensively addressed. A wild classification problem contains the classification problem of pairs of matrices up to simultaneous similarity. In this paper, we prove that the classification problem for graphs is wild by reducing the classification problem for finite 2-nilpotent p-groups to the classification problem for graphs.     

对称群上Cayley图的DNA计算

有一类图称为Cayley图或群图.猜想每个Cayley图都是Hamilton图.求Cayley图和有向Cayley图中的Hamilton圈和路自然产生在计算科学里.这篇文章研究了对称群上Cayley图的DNA计算和给出了求它的Hamilton圈的DNA算法.     

On geodesic structures of weakly median graphs I. Decomposition and octahedral graphs

We prove that the non-trivial (finite or infinite) weakly median graphs which are undecomposable with respect to gated amalgamation and Cartesian multiplication are the 5-wheels, the subhyperoctahedra different from K₁, the path K_1,2 and the 4-cycle K_2,2, and the two-connected K₄- and K_1,1,3-free bridged graphs. These prime graphs are exactly the weakly median graphs which do not have any proper gated subgraphs other than singletons. For finite graphs, these results were already proved in [H.-J. Bandelt, V.C. Chepoi, The algebra of metric betweenness I: subdirect representation, retracts, and axiomatics of weakly median graphs, preprint, 2002]. A graph G is said to have the half-space copoint property (HSCP) if every non-trivial half-space of the geodesic convexity of G is a copoint at each of its neighbors. It turns out that any median graph has the HSCP. We characterize the weakly median graphs having the HSCP. We prove that the class of these graphs is closed under gated amalgamation and Cartesian multiplication, and we describe the prime and the finite regular elements of this class.     

On the hamiltonicity of line graphs of locally finite, 6‐edge‐connected graphs

The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a weaker version of this result for infinite graphs: The line graph of locally finite, 6‐edge‐connected graph with a finite number of ends, each of which is thin, is hamiltonian.     

Graphs of finite mass which cannot be approximated in area by smooth graphs

In this note we shall show that there are obstructions of homotopic and not just of homological nature to the approximability in area of graphs of finite mass by graphs of smooth maps. We shall present a class of closed graphs with finite mass which cannot be approximated weakly and in area by smooth graphs. This work has been partially supported by the Ministero dell'Universitá e della Ricerca Scientifica, by C.N.R. contract n. 91.01343.CT01, and by the European Research Project GADGET     

Schrödinger operators on periodic discrete graphs

We consider Schrödinger operators with periodic potentials on periodic discrete graphs. The spectrum of the Schrödinger operator consists of an absolutely continuous part (a union of a finite number of non-degenerated bands) plus a finite number of flat bands, i.e., eigenvalues of infinite multiplicity. We obtain estimates of the Lebesgue measure of the spectrum in terms of geometric parameters of the graph and show that they become identities for some class of graphs. Moreover, we obtain stability estimates and show the existence and positions of large number of flat bands for specific graphs. The proof is based on the Floquet theory and the precise representation of fiber Schrödinger operators, constructed in the paper.     

On normal radical extensions of the rationals

Lower bounds on the bandwidth, the size of a vertex separator of general undirected graphs, and the largest common subgraph of two undirected (weighted) graphs are obtained. The bounds are based on a projection technique developed for the quadratic assignment problem, and once more demonstrate the importance of the extreme eigenvalues of the Laplacian. They will be shown to be strict for certain classes of graphs and compare favourably to bounds already known in literature. further improvement is gained by applying nonlinear optimization methods.     

A spectral approach to bandwidth and separator problems in graphs

Lower bounds on the bandwidth, the size of a vertex separator of general undirected graphs, and the largest common subgraph of two undirected (weighted) graphs are obtained. The bounds are based on a projection technique developed for the quadratic assignment problem, and once more demonstrate the importance of the extreme eigenvalues of the Laplacian. They will be shown to be strict for certain classes of graphs and compare favourably to bounds already known in literature. further improvement is gained by applying nonlinear optimization methods.     

Hedetniemi's Conjecture and the Retracts of a Product of Graphs

We show that every core graph with a primitive automorphism group has the property that whenever it is a retract of a product of connected graphs, it is a retract of a factor. The example of Kneser graphs shows that the hypothesis that the factors are connected is essential. In the case of complete graphs, our result has already been shown in [4, 17], and it is an instance where Hedetniemi's conjecture is known to hold. In fact, our work is motivated by a reinterpretation of Hedetniemi's conjecture in terms of products and retracts.