Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

Vertex insertion approximates the crossing number of apex graphs

An apex graph is a graph G from which only one vertex v has to be removed to make it planar. We show that the crossing number of such G can be approximated up to a factor of Δ(G−v)⋅d(v)/2 by solving the vertex inserting problem, i.e. inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Since the latter problem can be solved in polynomial time, this establishes the first polynomial fixed-factor approximation algorithm for the crossing number problem of apex graphs with bounded degree.Furthermore, we extend this result by showing that the optimal solution for inserting multiple edges or vertices into a planar graph also approximates the crossing number of the resulting graph.     

Asymptotic Solutions for Australian Options with Low Volatility

Abstract

In this paper we derive asymptotic expansions for Australian options in the case of low volatility using the method of matched asymptotics. The expansion is performed on a volatility scaled parameter. We obtain a solution that is of up to the third order. In case that there is no drift in the underlying, the solution provided is in closed form, for a non-zero drift, all except one of the components of the solutions are in closed form. Additionally, we show that in some non-zero drift cases, the solution can be further simplified and in fact written in closed form as well. Numerical experiments show that the asymptotic solutions derived here are quite accurate for low volatility.     

On region crossing change and incidence matrix

In a recent work of Ayaka Shimizu, she studied an operation named region crossing change on link diagrams, which was proposed by Kishimoto, and showed that a region crossing change is an unknotting operation for knot diagrams. In this paper, we prove that the region crossing change on a 2-component link diagram is an unknotting operation if and only if the linking number of the diagram is even. Besides, we define an incidence matrix of a link diagram via its signed planar graph and its dual graph. By studying the relation between region crossing change and incidence matrix, we prove that a signed planar graph represents an n-component link diagram if and only if the rank of the associated incidence matrix equals c n + 1, where c denotes the size of the graph.     

Recursive formulation of the relativistic law of superposition of multiple collinear velocities

We study the recursive formulation of the law of superposition of multiple collinear velocities. We start with the non-linear equation, transform it into two linear coupled difference equations with variable cofficients, and then decouple these latter equations. The coupled difference equations are solved by three different, but interrelated, methods: (i) via the graph theoretic discrete path approach, (ii) by using the general closed form solution of two coupled first order difference equations with variable coefficients, and (iii) in terms of the symmetric functions via the pochhammers of 2 × 2 non-autonomous matrices. The solutions of the decoupled equations are factorial polynomials.     

Momentum and heat transfer of the Falkner–Skan flow with algebraic decay: An analytical solution

In this paper, an analytical solution of the Falkner–Skan equation with mass transfer and wall movement is obtained for a special case, namely a velocity power index of ?1/3, with an algebraically decaying velocity profile. The solution is given in a closed form. Under different values of the mass transfer parameter, the wall can be fixed, moving in the same direction as the free stream, or opposite to the free stream (reversal flow near the wall). The thermal boundary layer solution is also presented with a closed form for a prescribed power-law wall temperature, which is expressed by the confluent hypergeometric function of the second kind. The temperature profiles and the wall temperature gradients are plotted. Interesting but complicated variation trends for certain combinations of controlling parameters are observed. Under certain parameter combinations, there exist singular points or poles for the wall temperature gradients, namely wall heat flux. With poles, the temperature profiles can cross the zero temperature line and become negative. From the results, it is also found empirically that under certain given values of the Prandtl number (Pr) and flow controlling parameter (b), the number of times for the temperature profiles crossing the zero line is the same as the number of poles when the wall temperature power index varies between zero and a given value n. The current result provides a new analytical solution for the Falkner–Skan equation with algebraic decay and greatly enriches the understanding of this important equation as well as the heat transfer characteristics for this flow.     

*—BI—IDEALS IN RADICAL THEORY OF INVOLUTION RINGS

Abstract

If a radical class is closed under involution in every ring with involution then the radical theoretic conditions involving *-bi-ideals are equivalent to the corresponding conditions concerning bi-ideals without involution.     

On the Pseudolinear Crossing Number

A drawing of a graph is pseudolinear if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The pseudolinear crossing number of a graph G is the minimum number of pairwise crossings of edges in a pseudolinear drawing of G. We establish several facts on the pseudolinear crossing number, including its computational complexity and its relationship to the usual crossing number and to the rectilinear crossing number. This investigation was motivated by open questions and issues raised by Marcus Schaefer in his comprehensive survey of the many variants of the crossing number of a graph.     

A policy-improvement type algorithm for solving zero-sum two-person stochastic games of perfect information

 We give a policy-improvement type algorithm to locate an optimal pure stationary strategy for discounted stochastic games with perfect information. A graph theoretic motivation for our algorithm is presented as well. Received: January 1998 / Accepted: May 2002 Published online: February 14, 2003 Key words. stochastic games – MDP – perfect information – policy iteration Partially Funded by NSF Grant DMS 930-1052 and DMS 970-4951     

ON A RESULT OF ROSENLICHT

ABSTRACT

We prove a model theoretic result about orthogonality in the theory of differentially closed fields. Using that, we deduce a result of Rosenlicht (Proposition 1).     

Hamiltonian cycles in bipartite quadrangulations on the torus

In this article, we shall prove that every bipartite quadrangulation G on the torus admits a simple closed curve visiting each face and each vertex of G exactly once but crossing no edge. As an application, we conclude that the radial graph of any bipartite quadrangulation on the torus has a hamiltonian cycle. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69:143‐151, 2012     

The Crossing Number of C(mk;{1, k})

Calculating the crossing number of a given graph is, in general, an elusive problem. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the the crossing number of graphs with good interconnection properties, such as the circulant graphs. In this paper we study the crossing number of the circulant graph C(mk;{1,k}) for m3, k3, give an upper bound of cr(C(mk;{1,k})), and prove that cr(C(3k;{1,k}))=k.Research supported by Chinese Natural Science Foundation     

Odd Crossing Number and Crossing Number Are Not the Same

The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps (graphs with rotation systems).     

Graphs as navigational infrastructure for high dimensional data spaces

We propose using graph theoretic results to develop an infrastructure that tracks movement from a display of one set of variables to another. The illustrative example throughout is the real-time morphing of one scatterplot into another. Hurley and Oldford (J Comput Graph Stat 2010) made extensive use of the graph having variables as nodes and edges indicating a paired relationship between them. The present paper introduces several new graphs derivable from this one whose traversals can be described as particular movements through high dimensional spaces. These are connected to known results in graph theory and the graph theoretic results applied to the problem of visualizing high-dimensional data.     

Gauge symmetries and percolation in ±J Ising spin glasses

We consider the ±J spin glass on a finite graph G=(V,E), with i.i.d. couplings. Our approach considers the Z ₂ local gauge invariance of the system. We see the gauge group as a graph theoretic linear code ? over GF(2). The gauge is fixed by choosing a convenient linear supplement of ?. Assuming some relation between the disorder parameter p and the inverse temperature of the thermal bath β _pb , we study percolation in the random interaction random cluster model, and extend the results to dilute spin glasses. Received: 5 May 1997 / Revised version: 9 April 1998     

Bounds for Generalized Thrackles

A thrackle (resp. generalized thrackle) is a drawing of a graph in which each pair of edges meets precisely once (resp. an odd number of times). For a graph with n vertices and m edges, we show that, for drawings in the plane, m≤ (2/3)(n-1) for thrackles, while m≤ 2n-2 for generalized thrackles. This improves theorems of Lovász, Pach, and Szegedy. The paper also examines thrackles in the more general setting of drawings on closed surfaces. The main result is: a bipartite graph G can be drawn as a generalized thrackle on a closed orientable connected surface if and only if G can be embedded in that surface. Received July 23, 1998, and in revised form January 1, 1999.     

Skewness of generalized Petersen graphs and related graphs

The skewness of a graph G is the minimum number of edges in G whose removal results in a planar graph. In this paper, we determine the skewness of the generalized Petersen graph P(4k, k) and hence a lower bound for the crossing number of P(4k, k). In addition, an upper bound for the crossing number of P(4k, k) is also given.     

Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem

We study the integral uniform (multicommodity) flow problem in a graph G and construct a fractional solution whose properties are invariant under the action of a group of automorphisms Γ<Aut(G). The fractional solution is shown to be close to an integral solution (depending on properties of Γ), and in particular becomes an integral solution for a class of graphs containing Cayley graphs. As an application we estimate asymptotically (up to additive error terms) the edge congestion of an optimal integral uniform flow (edge forwarding index) in the cube-connected cycles and the butterfly. Moreover, we derive the best-known lower bound on the crossing number of a butterfly.     

Compensations in the Shapley value and the compensation solutions for graph games

We consider an alternative expression of the Shapley value that reveals a system of compensations: each player receives an equal share of the worth of each coalition he belongs to, and has to compensate an equal share of the worth of any coalition he does not belong to. We give a representation in terms of formation of the grand coalition according to an ordering of the players and define the corresponding compensation vector. Then, we generalize this idea to cooperative games with a communication graph in order to construct new allocation rules called the compensation solutions. Firstly, we consider cooperative games with arbitrary graphs and construct rooted spanning trees (see Demange, J Political Econ 112:754–778, 2004) instead of orderings of the players by using the classical algorithms DFS and BFS. If the graph is complete, we show that the compensation solutions associated with DFS and BFS coincide with the Shapley value and the equal surplus division respectively. Secondly, we consider cooperative games with a forest (cycle-free graph) and all its rooted spanning trees. The compensation solution is characterized by component efficiency and relative fairness. The latter axiom takes into account the relative position of a player with respect to his component in the communication graph.