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 Γ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 ：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.展开更多
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 T_(2k+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 tre...Let T_(2k+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 T_(2k+1).Specifically,10 trees T_(2),T_(3),...,T11 and two classes of trees T(1)and T(12)in T_(2k+1)are introduced.It is shown in this paper that for each tree T′_(1),T′_(11)∈T(1)and T^′_(12),T′_(11)2∈T(12)and each i,j with 2≤i〈j≤11,α(T′_(1))=α(T′_(11))〉α(Tj)〉α(T^′_(12))=α(T′_(11)2).It is also shown that for each tree T with T∈T_(2k+1)/(T(1)∪{T_(2),T_(3),…,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.展开更多
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.展开更多
In this study,the wave motion in elastodynamics for unbounded media is modeled using an unsplit-field perfectly matched layer(PML)formulation that is solved by employing an isogeometric analysis(IGA).In the adopted co...In this study,the wave motion in elastodynamics for unbounded media is modeled using an unsplit-field perfectly matched layer(PML)formulation that is solved by employing an isogeometric analysis(IGA).In the adopted combination,the non-uniform rational B-spline(NURBS)functions are employed as basis functions.Moreover,the unbounded and artificial domains,defined in the PML method,are contained in a single patch domain.Based on the proposed scheme,the approximation of the geometry problem is set in a new scheme in which the PML’s absorbing and attenuation properties and the description of traveling waves can be represented.This includes a higher continuity and smoother approximation of the computed domain.As high-order NURBS basis functions are non-interpolatory,a penalty method is present to apply a time-dependent displacement load.The performance of the NURBS-based PML is analyzed through numerical examples for 1D and 2D domains,considering homogeneous and heterogeneous media.Further,we verify the long-time numerical stability of the present method.The developed method can be used to simulate hypothetical stratified domains commonly encountered in soil-structure interaction analyses.展开更多
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.展开更多
As an efficient artificial truncating boundary condition, conformal perfectly matched layer (CPML) is a kind of multilayer anisotropic absorbing media. To reduce computing effort of CPML, this article proposes a layer...As an efficient artificial truncating boundary condition, conformal perfectly matched layer (CPML) is a kind of multilayer anisotropic absorbing media. To reduce computing effort of CPML, this article proposes a layer-oriented element integration algorithm. In this algorithm, the relative dielectric constant and permeability are considered as constants for each the very thin monolayer of CPML, and the element integration of multilayer along the normal direction is substituted by the element integration of m...展开更多
The （conditional） matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph （with no isolated vertices） that has neither perfect matchings nor almost perfect matc...The （conditional） matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph （with no isolated vertices） that has neither perfect matchings nor almost perfect matchings. In this paper, we find this number and classify all optimal sets for the augmented k-ary n-cubes with even k ≥ 4.展开更多
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.展开更多
基金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).
基金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.
基金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 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 T_(2k+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 T_(2k+1).Specifically,10 trees T_(2),T_(3),...,T11 and two classes of trees T(1)and T(12)in T_(2k+1)are introduced.It is shown in this paper that for each tree T′_(1),T′_(11)∈T(1)and T^′_(12),T′_(11)2∈T(12)and each i,j with 2≤i〈j≤11,α(T′_(1))=α(T′_(11))〉α(Tj)〉α(T^′_(12))=α(T′_(11)2).It is also shown that for each tree T with T∈T_(2k+1)/(T(1)∪{T_(2),T_(3),…,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.
文摘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.
文摘In this study,the wave motion in elastodynamics for unbounded media is modeled using an unsplit-field perfectly matched layer(PML)formulation that is solved by employing an isogeometric analysis(IGA).In the adopted combination,the non-uniform rational B-spline(NURBS)functions are employed as basis functions.Moreover,the unbounded and artificial domains,defined in the PML method,are contained in a single patch domain.Based on the proposed scheme,the approximation of the geometry problem is set in a new scheme in which the PML’s absorbing and attenuation properties and the description of traveling waves can be represented.This includes a higher continuity and smoother approximation of the computed domain.As high-order NURBS basis functions are non-interpolatory,a penalty method is present to apply a time-dependent displacement load.The performance of the NURBS-based PML is analyzed through numerical examples for 1D and 2D domains,considering homogeneous and heterogeneous media.Further,we verify the long-time numerical stability of the present method.The developed method can be used to simulate hypothetical stratified domains commonly encountered in soil-structure interaction analyses.
基金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.
基金National Natural Science Foundation of China (10477018) Science and Technology Innovation Foundation of North-western Polytechnical University (W016143)
文摘As an efficient artificial truncating boundary condition, conformal perfectly matched layer (CPML) is a kind of multilayer anisotropic absorbing media. To reduce computing effort of CPML, this article proposes a layer-oriented element integration algorithm. In this algorithm, the relative dielectric constant and permeability are considered as constants for each the very thin monolayer of CPML, and the element integration of multilayer along the normal direction is substituted by the element integration of m...
文摘The （conditional） matching preclusion number of a graph is the minimum number of edges whose deletion leaves a resulting graph （with no isolated vertices） that has neither perfect matchings nor almost perfect matchings. In this paper, we find this number and classify all optimal sets for the augmented k-ary n-cubes with even k ≥ 4.
基金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.
