Perfect 1-k Matchings of Bipartite Graphs

Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.

A THEOREM CONCERNING PERFECT MATCHINGS IN HEXAGONAL SYSTEMS

In the present paper a theorem is established which offers some necessary and sufficient eonditionsfor a hexagonal system to have perfect matchings.

The Number of Perfect Matchings in (3,6)-Fullerene

A(3,6)-fullerene is a connected cubic plane graph whose faces are only triangles and hexagons,and has the connectivity 2 or 3.The(3,6)-fullerenes with connectivity 2 are the tubes consisting of l concentric hexagonal layers such that each layer consists of two hexangons,capped on each end by two adjacent triangles,denoted by T_(l)(l≥1).A(3,6)-fullerene Tl with n vertices has exactly 2n/4+1 perfect matchings.The structure of a(3,6)-fullerene G with connectivity 3 can be determined by only three parameters r,s and t,thus we denote it by G=(r,s,t),where r is the radius(number of rings),s is the size(number of spokes in each layer,s(≥4,s is even),and t is the torsion(0≤t<s,t≡r mod 2).In this paper,the counting formula of the perfect matchings in G=n+1,4,t)is given,and the number of perfect matchpings is obtained.Therefore,the correctness of the conclusion that every bridgeless cubic graph with p vertices has at least 2p/3656perfect matchings proposed by Esperet et al is verified for(3,6)-fullerene G=(n+1,4,t).

Ordering Trees with Nearly Perfect Matchings by Algebraic Connectivity

Let T2k＋1 be the set of trees on 2k＋1 vertices with nearly perfect matchings and α（T） be the algebraic connectivity of a tree T. The authors determine the largest twelve values of the algebraic connectivity of the trees in T2k＋1. Specifically, 10 trees T2,T3,... ,T11 and two classes of trees T（1） and T（12） in T2k＋1 are introduced. It is shown in this paper that for each tree T^′1,T^″1∈T（1）and T^′12,T^″12∈T（12） and each i,j with 2≤i〈j≤11,α（T^′1）=α（T^″1）〉α（Tj）〉α（T^′12）=α（T^″12）.It is also shown that for each tree T with T∈T2k＋1／（T（1）∪{T2,T3,…,T11}∪T（12））,α（T^′12）〉α（T）.

ON THE LAPLACIAN SPECTRAL RADII OF TREES WITH NEARLY PERFECT MATCHINGS

Let ：T2k＋1 be the set of trees on 2k＋ 1 vertices with nearly perfect matchings, and let S2k＋2 be the set of trees on 2k ＋ 2 vertices with perfect matchings. The largest Laplacian spectral radii of trees in ：T2k＋l and S2k＋2 and the corresponding trees were given by Guo （2003）. In this paper, the authors determine the second to the sixth largest Laplacian spectral radii among all trees in T2k＋1 and give the corresponding trees.

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ（G）, κ（G）, α（G）, χ（G）, cl（G）, diam（G） denote the number of perfect matchings, connectivity, independence number, chromatic number, clique number and diameter of a graph G, respectively. In this note, by constructing some extremal graphs, the following extremal problems are solved： 1. max {φ（G）： ｜V（G）｜ = 2n, κ（G）≤ k} = k[（2n - 3）!!], 2. max{φ（G）： ｜V（G）｜ = 2n,α（G） ≥ k} =[∏ i=0^k-1 （2n - k-i]（2n - 2k - 1）!!], 3. max{φ（G）： ｜V（G）｜=2n, χ（G） ≤ k} =φ（Tk,2n） Tk,2n is the Turán graph, that is a complete k-partitc graph on 2n vertices in which all parts are as equal in size as possible, 4. max{φ（G）： ｜V（G）｜ = 2n, cl（G） = 2} = n!, 5. max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥〉 2} = （2n - 2）（2n - 3）[（2n - 5）!!], max{φ（G）： ｜V（G）｜ = 2n, diam（G） ≥ 3} = （n - 1）^2[（2n - 5）!!].

Maximizing the Minimum and Maximum Forcing Numbers of Perfect Matchings of Graphs

Let G be a simple graph with 2n vertices and a perfect matching.The forcing number f(G,M) of a perfect matching M of G is the smallest cardinality of a subset of M that is contained in no other perfect matching of G.Among all perfect matchings M of G,the minimum and maximum values of f(G,M) are called the minimum and maximum forcing numbers of G,denoted by f(G) and F(G),respectively.Then f(G)≤F(G) ≤n-1.Che and Chen(2011) proposed an open problem:how to characterize the graphs G with f(G)=n-1.Later they showed that for a bipartite graph G,f(G)=n-1 if and only if G is complete bipartite graph K_(n,n).In this paper,we completely solve the problem of Che and Chen,and show that f(G)=n-1 if and only if G is a complete multipartite graph or a graph obtained from complete bipartite graph K_(n,n) by adding arbitrary edges in one partite set.For all graphs G with F(G)=n-1,we prove that the forcing spectrum of each such graph G forms an integer interval by matching 2-switches and the minimum forcing numbers of all such graphs G form an integer interval from [n/2] to n-1.

The Application of the Nonsplitting Perfectly Matched Layer in Numerical Modeling of Wave Propagation in Poroelastic Media

The nonsplitting perfectly matched layer （NPML） absorbing boundary condition （ABC） was first provided by Wang and Tang （2003） for the finite-difference simulation of elastic wave propagation in solids. In this paper, the method is developed to extend the NPML to simulating elastic wave propagation in poroelastic media. Biot＇s equations are discretized and approximated to a staggered-grid by applying a fourth-order accurate central difference in space and a second-order accurate central difference in time. A cylindrical twolayer seismic model and a borehole model are chosen to validate the effectiveness of the NPML. The results show that the numerical solutions agree well with the solutions of the discrete wavenumber （DW） method.

A study of perfectly matched layers for joint multicomponent reverse-time migration

Reverse-time migration in finite space requires effective boundary processing technology to eliminate the artificial truncation boundary effect in the migration result.On the basis of the elastic velocity-stress equations in vertical transversely isotropic media and the idea of the conventional split perfectly matched layer（PML）,the PML wave equations in reverse-time migration are derived in this paper and then the high order staggered grid discrete schemes are subsequently given.Aiming at the＂reflections＂from the boundary to the computational domain,as well as the effect of seismic event＇s abrupt changes at the two ends of the seismic array,the PML arrangement in reverse-time migration is given.The synthetic and real elastic,prestack,multi-component,reverse-time depth migration results demonstrate that this method has much better absorbing effects than other methods and the joint migration produces good imaging results.

Perfectly matched layer-absorbing boundary condition for finite-element time-domain modeling of elastic wave equations

The perfectly matched layer （PML） is a highly efficient absorbing boundary condition used for the numerical modeling of seismic wave equation. The article focuses on the application of this technique to finite-element time-domain numerical modeling of elastic wave equation. However, the finite-element time-domain scheme is based on the second- order wave equation in displacement formulation. Thus, the first-order PML in velocity-stress formulation cannot be directly applied to this scheme. In this article, we derive the finite- element matrix equations of second-order PML in displacement formulation, and accomplish the implementation of PML in finite-element time-domain modeling of elastic wave equation. The PML has an approximate zero reflection coefficients for bulk and surface waves in the finite-element modeling of P-SV and SH wave propagation in the 2D homogeneous elastic media. The numerical experiments using a two-layer model with irregular topography validate the efficiency of PML in the modeling of seismic wave propagation in geological models with complex structures and heterogeneous media.

A study of damping factors in perfectly matched layers for the numerical simulation of seismic waves

When simulating seismic wave propagation in free space, it is essential to introduce absorbing boundary conditions to eliminate reflections from artificially trtmcated boundaries. In this paper, a damping factor referred to as the Gaussian dmping factor is proposed. The Gaussian damping factor is based on the idea of perfectly matched layers （PMLs）. This work presents a detailed analysis of the theoretical foundations and advantages of the Gaussian damping factor. Additionally, numerical experiments for the simulation of seismic waves are presented based on two numerical models： a homogeneous model and a multi-layer model. The results show that the proposed factor works better. The Gaussian damping factor achieves a higher Signal-to-Noise Ratio （SNR） than previously used factors when using same number of PMLs, and requires less PMLs than other methods to achieve an identical SNR.

Borehole-GPR numerical simulation of full wave field based on convolutional perfect matched layer boundary

The absorbing boundary is the key in numerical simulation of borehole radar.Perfect match layer(PML) was chosen as the absorbing boundary in numerical simulation of GPR.But CPML(convolutional perfect match layer) approach that we have chosen has the advantage of being media independent.Beginning with the Maxwell equations in a two-dimensional structure,numerical formulas of finite-difference time-domain(FDTD) method with CPML boundary condition for transverse electric(TE) or transverse magnetic(TM) wave are presented in details.Also,there are three models for borehole-GPR simulation.By analyzing the simulation results,the features of targets in GPR are obtained,which can provide a better interpretation of real radar data.The results show that CPML is well suited for the simulation of borehole-GPR.

An Adaptive Uniaxial Perfectly Matched Layer Method for Time-Harmonic Scattering Problems

The uniaxial perfectly matched layer (PML) method uses rectangular domain to define the PML problem and thus provides greater flexibility and efficiency in deal- ing with problems involving anisotropic scatterers.In this paper an adaptive uniaxial PML technique for solving the time harmonic Helmholtz scattering problem is devel- oped.The PML parameters such as the thickness of the layer and the fictitious medium property are determined through sharp a posteriori error estimates.The adaptive finite element method based on a posteriori error estimate is proposed to solve the PML equa- tion which produces automatically a coarse mesh size away from the fixed domain and thus makes the total computational costs insensitive to the thickness of the PML absorb- ing layer.Numerical experiments are included to illustrate the competitive behavior of the proposed adaptive method.In particular,it is demonstrated that the PML layer can be chosen as close to one wave-length from the scatterer and still yields good accuracy and efficiency in approximating the far fields.

A Uniaxial Optimal Perfectly Matched Layer Method for Time-harmonic Scattering Problems

We develop a uniaxial optimal perfectly matched layer （opt PML） method for solving the time-harmonic scattering problems by choosing a particular absorbing function with unbounded integral in a rectangular domain. With this choice, the solution of the optimal PML problem not only converges exponentially to the solution of the original scatting problem, but also is insensitive to the thickness of the PML layer for sufficiently small parameter ε0. Numerical experiments are included to illustrate the competitive behavior of the proposed optimal method.

An improved convolution perfectly matched layer for elastic second-order wave equation

A convolution perfectly matched layer(CPML)can efficiently absorb boundary reflection in numerical simulation.However,the CPML is suitable for the first-order elastic wave equation and is difficult to apply directly to the second-order elastic wave equation.In view of this,based on the first-order CPML absorbing boundary condition,we propose a new CPML(NCPML)boundary which can be directly applied to the second-order wave equation.We first systematically extend the first-order CPML technique into second-order wave equations,neglecting the space-varying characteristics of the partial damping coefficient in the complex-frequency domain,avoiding the generation of convolution in the time domain.We then transform the technique back to the time domain through the inverse Fourier transform.Numerical simulation indicates that the space-varying characteristics of the attenuation factor have little influence on the absorption effect and increase the memory at the same time.A number of numerical examples show that the NCPML proposed in this study is effective in simulating elastic wave propagation,and this algorithm is more efficient and requires less memory allocation than the conventional PML absorbing boundary.

Perfectly matched layer implementation for ADI-FDTD in dispersive media

Alternating direction implicit finite difference time domain （ADI-FDTD） method is unconditionally stable and the maximum time step is not limited by the Courant stability condition, but rather by numerical error. Compared with the conventional FDTD method, the time step of ADI-FDTD can be enlarged arbitrarily and the CPU cost can be reduced. 2D perfectly matched layer （PML） absorbing boundary condition is proposed to truncate computation space for ADI-FDTD in dispersive media using recursive convolution（RC） method and the 2D PML formulations for dispersive media are derived. ADI-FDTD formulations for dispersive media can be obtained from the simplified PML formulations. The scattering of target in dispersive soil is simulated under sine wave and Gaussian pulse excitations and numerical results of ADI-FDTD with PML are compared with FDTD. Good agreement is observed. At the same time the CPU cost for ADI-FDTD is obviously reduced.

Application of perfectly matched layer to soil-foundation interaction analysis

Despite of the limitation in modeling infinite space, the finite element method(FEM) is one of the most used tools to numerically study the geotechnical problems regarding the capacity of simulating different geometries, conditions and material behaviors. A kind of absorbing layer named perfectly matched layer(PML) has been applied to modeling the radiation damping using FEM, which makes the dynamic analysis of soil-structure interaction more accurate. The PML is capable of absorbing incident waves under any angle and frequency, ensuring them to pass through the model boundaries without reflection.In this context, a new FEM program has been written and the PML formula has been implemented by rewriting the dynamic equation of motion and deriving new properties for the quadrilateral elements.The analysis of soil-foundation interaction by applying the PML is validated by the evaluation of impedance/compliance functions for different ground conditions. The results obtained from the PML model match the extended mesh results, even though the domain is small enough that other types of absorbing boundaries can reflect waves back to the foundation. The mechanism of the wave propagation in the region shows that the forced vibrations can be fully absorbed and damped by the boundaries surrounded by PMLs which is the role of radiation damping in FEM modeling.

Finite Element Analysis in Combination with Perfectly Matched Layer to the Numerical Modeling of Acoustic Devices in Piezoelectric Materials

The characterization of finite length Surface Acoustic Wave (SAW) and Bulk acoustic Wave (BAW) resonators is addressed here. The Finite Element Analysis (FEA) induces artificial wave reflections at the edges of the mesh. In fact, these ones do not contribute in practice to the corresponding experimental response. The Perfectly Matched Layer (PML) method, allows to suppress the boundary reflections. In this work, we first demonstrate the basis of PML adapted to FEA formalism. Next, the results of such a method are depicted allowing a discussion on the behavior of finite acoustic resonators.

A spherical higher-order finite-difference time-domain algorithm with perfectly matched layer

A higher-order finite-difference time-domain（HO-FDTD） in the spherical coordinate is presented in this paper. The stability and dispersion properties of the proposed scheme are investigated and an air-filled spherical resonator is modeled in order to demonstrate the advantage of this scheme over the finite-difference time-domain（FDTD） and the multiresolution time-domain（MRTD） schemes with respect to memory requirements and CPU time. Moreover, the Berenger＇s perfectly matched layer（PML） is derived for the spherical HO-FDTD grids, and the numerical results validate the efficiency of the PML.

Results on energies for trees with a given diameter having perfect matching

Let Γd2nbe the set of trees with a given diameter d having a perfect matching,where 2n is the number of vertex.For a tree T in Γd2n,let Pd＋1be a diameter of T and q = d m,where m is the number of the edges of perfect matching inPd＋1.It can be found that the trees with minimal energy in Γd2nfor four cases q = d 2,d 3,d 4,[d2],and two remarks aregiven about the trees with minimal energy in Γd2nfor2d 33q d 5 and [d2] ＋ 1 q2d 33 1.