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 perfe...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.展开更多
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 inc...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.展开更多
We implemented a two-step Asymmetric Perfectly Matched Layer (APML) model in High-Order Finite Difference Time Domain (FDTD) algorithm for solving two-dimensional Maxwell’s equations. Initially, we applied the APML m...We implemented a two-step Asymmetric Perfectly Matched Layer (APML) model in High-Order Finite Difference Time Domain (FDTD) algorithm for solving two-dimensional Maxwell’s equations. Initially, we applied the APML method to the standard second-order FDTD algorithm to derive a two-step time-staggered APML (APML-2SS) and a two-step time-centered APML (APML-2SC) formulation for these equations, afterwards, we extended these formulations in high-order FDTD algorithm in order to derive a APML high-order FDTD (APML-HOFDTD) formulation for our Maxwell’s equations. To examine the performance and check out the accuracy of APML model, we conducted a numerical study using a 2D fluid where the three derived formulations were to analyze selected phenomena in terahertz radiation production by the filamentation of two femtosecond laser beams in air plasma. Numerical results illustrated that the two-step APML model is sufficiently accurate for solving our 2D Maxwell’s equations in high-order FDTD discretization and it demonstrated a great performance in studying the THz radiation production.展开更多
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...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.展开更多
A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with par...A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.展开更多
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 ...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).展开更多
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 no...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）!!].展开更多
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.A...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.展开更多
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 th...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）.展开更多
Let SI and S2 be two （k- 1）-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E（H） such that S1 ∩ e≠ 0 and S2 ∩ e ≠0 or e S1 ∪...Let SI and S2 be two （k- 1）-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E（H） such that S1 ∩ e≠ 0 and S2 ∩ e ≠0 or e S1 ∪ S2 or e S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. （1） For any n ≥ 2k2 - k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent （k - 1）-sets equal to 2n - 4（k - 1）, contains no perfect matching; （2） Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd＋ （k- 2）k. If the degree sum of any two middle independent （k- 1）-subsets is larger than 2（d- 1）, then H contains a d-matching; （3） For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent （k - 1）-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.展开更多
Let H=(V,E)be an n-balanced k-partite k-graph with partition classes V1,...,Vk.Suppose for every legal(k-1)-tuple f contained in V\V1 and for every legal(k-1)-tuple g contained in V\Vk such that f∪g■E(H),we have d(f...Let H=(V,E)be an n-balanced k-partite k-graph with partition classes V1,...,Vk.Suppose for every legal(k-1)-tuple f contained in V\V1 and for every legal(k-1)-tuple g contained in V\Vk such that f∪g■E(H),we have d(f)+d(g)≥n+1.In this paper,we prove that under this condition H must have a perfect matching.Another result of this paper is about the perfect matching in 3-uniform hm-bipartite hypergraphs.Let G be a 3-uniform hm-bipartite hypergraph with one of whose sides V1 has the size n,the another side V2 has size 2 n.If for all the legal 2-tuple f with|f∩V1|=1 and for all the legal 2-tuple g with|g∩V1|=0,we have d(f)≥n-2 and d(g)>n/2,then G has a perfect matching.展开更多
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 p...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.展开更多
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 equat...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.展开更多
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-eleme...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.展开更多
Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin g...Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).展开更多
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 refer...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.展开更多
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) appr...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.展开更多
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 t...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.展开更多
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. W...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.展开更多
基金Project supported by the National Natural Science Foundation of China (Grant Nos.11001166,10971131)the Shanghai Leading Academic Discipline Project (Grant No.S30104)
文摘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.
文摘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.
文摘We implemented a two-step Asymmetric Perfectly Matched Layer (APML) model in High-Order Finite Difference Time Domain (FDTD) algorithm for solving two-dimensional Maxwell’s equations. Initially, we applied the APML method to the standard second-order FDTD algorithm to derive a two-step time-staggered APML (APML-2SS) and a two-step time-centered APML (APML-2SC) formulation for these equations, afterwards, we extended these formulations in high-order FDTD algorithm in order to derive a APML high-order FDTD (APML-HOFDTD) formulation for our Maxwell’s equations. To examine the performance and check out the accuracy of APML model, we conducted a numerical study using a 2D fluid where the three derived formulations were to analyze selected phenomena in terahertz radiation production by the filamentation of two femtosecond laser beams in air plasma. Numerical results illustrated that the two-step APML model is sufficiently accurate for solving our 2D Maxwell’s equations in high-order FDTD discretization and it demonstrated a great performance in studying the THz radiation production.
基金supported by the National Natural Science Foundation of China under Grant No. 10331020.
文摘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.
文摘A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.
基金Supported by National Natural Science Foundation of China(11801148,11801149 and 11626089)the Foundation for the Doctor of Henan Polytechnic University(B2014-060)
文摘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).
基金Supported by the National Natural Science Foundation of China(No.10331020)
文摘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）!!].
基金Supported by National Natural Science Foundation of China (Grant No. 12271229)Gansu Provincial Department of Education:Youth Doctoral fund project (Grant No. 2021QB-090)。
文摘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.
文摘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）.
基金Supported by National Natural Science Foundation of China(Grant No.11771247)
文摘Let SI and S2 be two （k- 1）-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E（H） such that S1 ∩ e≠ 0 and S2 ∩ e ≠0 or e S1 ∪ S2 or e S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. （1） For any n ≥ 2k2 - k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent （k - 1）-sets equal to 2n - 4（k - 1）, contains no perfect matching; （2） Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd＋ （k- 2）k. If the degree sum of any two middle independent （k- 1）-subsets is larger than 2（d- 1）, then H contains a d-matching; （3） For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent （k - 1）-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.
基金supported in part by the National Natural Science Foundation of China (No. 61373019)
文摘Let H=(V,E)be an n-balanced k-partite k-graph with partition classes V1,...,Vk.Suppose for every legal(k-1)-tuple f contained in V\V1 and for every legal(k-1)-tuple g contained in V\Vk such that f∪g■E(H),we have d(f)+d(g)≥n+1.In this paper,we prove that under this condition H must have a perfect matching.Another result of this paper is about the perfect matching in 3-uniform hm-bipartite hypergraphs.Let G be a 3-uniform hm-bipartite hypergraph with one of whose sides V1 has the size n,the another side V2 has size 2 n.If for all the legal 2-tuple f with|f∩V1|=1 and for all the legal 2-tuple g with|g∩V1|=0,we have d(f)≥n-2 and d(g)>n/2,then G has a perfect matching.
基金This research was supported by Natural Science Foundation of China (No. 403740043).
文摘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.
基金supported by the 863 Program(Grant No.2006AA06Z202)Open Fund of the Key Laboratory of Geophysical Exploration of CNPC(Grant No.GPKL0802)+1 种基金CNPC Young Innovation Fund(Grant No.05E7028)the Program for New Century Excellent Talents in University(Grant No.NCET-07-0845)
文摘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.
基金sponsored by the National Natural Science Foundation of China Research(Grant No.41274138)the Science Foundation of China University of Petroleum(Beijing)(No.KYJJ2012-05-02)
文摘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.
基金Supported by the National Natural Science Foundation of China(Grant Nos.61702291,11801371)Key Research Project in Universities of Henan Province(Grant No.21B110004)。
文摘Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).
基金supported by the National Natural Science Foundation of China(No. 61072118)
文摘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.
基金Project(41174061) supported by the National Natural Science Foundation of ChinaProject(2011QNZT011) supported by the Free Exploration Program of Central South University,China
文摘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.
文摘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.
基金The Major State Research Development Program (2005CB321701) of Chinathe NSF(10801063) of China
文摘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.
