On the number of matchings of graphs formed by a graph operation

Let G be a simple graph. Define R(G) to be the graph obtained from G by adding a new vertex e* corresponding to each edge e = (a,b) of G and by joining each new vertex e* to the end vertices a and b of the edge e corresponding to it. In this paper, we prove that the number of matchings of R(G) is completely determined by the degree sequence of vertices of G.     

Ultrasonic transcutaneous energy transfer for powering implanted devices

This paper investigates ultrasonic transcutaneous energy transfer (UTET) as a method for energizing implanted devices at power level up to a few 100 mW. We propose a continuous wave 673 kHz single frequency operation to power devices implanted up to 40 mm deep subcutaneously. The proposed UTET demonstrated an overall peak power transfer efficiency of 27% at 70 mW output power (rectified DC power at the load).The transducers consisted of PZT plane discs of 15 mm diameter and 1.3 mm thick acoustic matching layer made of graphite. The power rectifier on the implant side attained 88.5% power transfer efficiency.The proposed approach is analyzed in detail, with design considerations provided to address issues such as recommended operating frequency range, acoustic link matching, receiver’s rectifying electronics, and tissue bio-safety concerns. Global optimization and design considerations for maximum power transfer are presented and verified by means of finite element simulations and experimental results.     

Rainbow number of matchings in planar graphs

The rainbow number$rb(G,H)$ for the graph $H$ in $G$ is defined to be the minimum integer $c$ such that any $c$-edge-coloring of $G$ contains a rainbow $H$. As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching $k{K}_2$ in the plane triangulations, where the gap between the lower and upper bounds is $O\left(k^3\right)$. In this paper, we show that the rainbow number of the matching $k{K}_2$ in maximal outerplanar graphs of order $n$ is $n+O\left(k\right)$. Using this technique, we show that the rainbow number of the matching $k{K}_2$ in some subfamilies of plane triangulations of order $n$ is $2n+O\left(k\right)$. The gaps between our lower and upper bounds are only $O\left(k\right)$.     

Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

Graphs in which some and every maximum matching is uniquely restricted

A matching M in a graph G is uniquely restricted if there is no matching in G that is distinct from M but covers the same vertices as M. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.     

Supereulerian bipartite digraphs

A digraph D is supereulerian if D has a spanning closed ditrail. Bang‐Jensen and Thomassé conjectured that if the arc‐strong connectivity of a digraph D is not less than the independence number , then D is supereulerian. A digraph is bipartite if its underlying graph is bipartite. Let be the size of a maximum matching of D. We prove that if D is a bipartite digraph satisfying , then D is supereulerian. Consequently, every bipartite digraph D satisfying is supereulerian. The bound of our main result is best possible.     

Hyperuniform and rigid stable matchings

We study a stable partial matching τ of the d‐dimensional lattice with a stationary determinantal point process Ψ on R^d with intensity α>1. For instance, Ψ might be a Poisson process. The matched points from Ψ form a stationary and ergodic (under lattice shifts) point process Ψ^τ with intensity 1 that very much resembles Ψ for α close to 1. On the other hand Ψ^τ is hyperuniform and number rigid, quite in contrast to a Poisson process. We deduce these properties by proving more general results for a stationary point process Ψ, whose so‐called matching flower (a stopping set determining the matching partner of a lattice point) has a certain subexponential tail behavior. For hyperuniformity, we also additionally need to assume some mixing condition on Ψ. Furthermore, if Ψ is a Poisson process then Ψ^τ has an exponentially decreasing truncated pair correlation function.     

Maximally resonant polygonal systems

A benzenoid system G is k-resonant if any set F of no more than k disjoint hexagons is a resonant pattern, i.e, G−F has a perfect matching. In 1990’s M. Zheng constructed the 3-resonant benzenoid systems and showed that they are maximally resonant, that is, they are k-resonant for all k≥1. Recently, the equivalence of 3-resonance and maximal resonance has been shown to be valid also for coronoid systems, carbon nanotubes, polyhexes in tori and Klein bottles, and fullerene graphs. So our main problem is to investigate the extent of graphs possessing this interesting property. In this paper, by replacing the above hexagons with even faces, we define k-resonance of graphs in surfaces, possibly with boundary, in a unified way. Some exceptions exist. For plane polygonal systems tessellated with polygons of even size at least six such that all inner vertices have the same degree three and the others have degree two or three, we show that such 3-resonant polygonal systems are indeed maximally resonant. They can be constructed by gluing and lapping operations on three types of basic graphs.     

Optimizing the marriage market: An application of the linear assignment model

Research shows that the success of marriages and other intimate partnerships depends on objective attributes such as differences in age, cultural background, and educational level. This article proposes a mathematical approach to optimizing marriage by allocating spouses in such a way as to reduce the likelihood of divorce or separation. To produce our optimization model, we use the assumption of a central “agency” that would coordinate the matching of couples. Based on a representative and longitudinal sample of 1074 cohabiting and married couples living in Switzerland, we estimate various objective functions corresponding to age, education, ethnicity, and prior divorce concerning every possible combination of men and women. Our results show that the current state of marriages or partnerships is well below the social optimum. We reallocate approximately 68% of individuals (7 out of 10) to a new couple that we posit has a higher likelihood of survival. From this selection of new partners, we obtain our final “optimal” solutions, with a 21% reduction in the objective function.     

Fast algorithms for placing large entries along the diagonal of a sparse matrix

Solving a sparse system of linear equations Ax=b is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix A are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix A so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g., Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). Duff (2009) [3] has formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from O(|V|+|E|) to O(|V|), where |V| is the order of the matrix A and |E| is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duff’s algorithm) for sparse matrices with at least a million non-zeros.