PARTITION A GRAPH WITH SMALL DIAMETER INTO TWO INDUCED MATCHINGS

Given a simple graph G and a positive integer k, the induced matching k-partition problem asks whether there exists a k-partition (V 1, V 2, ..., V k) of V(G) such that for each i(1≤i≤k), G[V i] is 1-regular. This paper studies the computational complexity of this problem for graphs with small diameters. The main results are as follows: Induced matching 2-partition problem of graphs with diameter 6 and induced matching 3-partition problem of graphs with diameter 2 are NP-complete; induced matching 2-partition problem of graphs with diameter 2 is polynomially solvable.

Perfect matchings on a type of lattices with toroidal boundary

Enumeration of perfect matchings on graphs has a longstanding interest in combinatorial mathematics. In this paper, we obtain some explicit expressions of the number of perfect matchings for a type of Archimedean lattices with toroidal boundary by applying Tesler's crossing orientations to obtain some Pfaffan orientations and enumerating their Pfaffans.

ON MAXIMAL MATCHINGS OF CONNECTED GRAPHS

Let I with |I| = k be a matching of a graph G (briefly, I is called a k-matching). If I is not a proper subset of any other matching of G, then I is a maximal k-matching and m(gk, G) is used to denote the number of maximal k-matchings of G. Let gk be a k-matching of G, if there exists a subset {e1, e2,…, ei} of E(G) \ gk, i (?)1, such that (1) for any j ∈ {1, 2,…,i}, gk + {ej} is a (k + l)-matching of G; (2) for any f ∈ E(G) \ (gk ∪ {e1,e2,…,ei}), gk + {f} is not a matching of G; then gk, is called an i wings k-matching of G and mi(gk,G) is used to denote the number of i wings k-matchings of G. In this paper, it is proved that both mi(gk,G) and m(gk,G) are edge reconstructible for every connected graph G, and as a corollary, it is shown that the matching polynomial is edge reconstructible.

Cover a 3-regular Claw-free Graph by Induced Matchings

The induced matching cover number of a graph G without isolated vertices, denoted by imc(G),is the minimum integer k such that G has k induced matchings {M1,M2,···,Mk}such that,V(M1)∪V(M2)∪···∪V(Mk)covers V(G).This paper shows that,if G is a 3-regular claw-free graph,then imc(G)∈{2,3}.

Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Matching Energies

In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let wi?be a non-isolated vertex of graph Gi?where i=1, 2, …, k. We use Gu(k)?(respectively, Hv(k)) to denote the graph which is the coalescence of G (respectively, H) and G1, G2,…, Gk?by identifying the vertices u (respectively, v) and w1, w2,…, wk. In this paper, we first present a new technique of directly comparing the matching energies of Gu(k)?and Hv(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n≥211.

An o(n^2.5) Algorithm: For Maximum Matchings in General Graphs

This article extend the John E. Hopcroft and Richart M. Karp Algorithm (HK Algorithm) for maximum matchings in bipartite graphs to the non-bipartite case by providing a new approach to deal with the blossom in alternating paths in the process of searching for augmenting paths, which different from well-known “shrinking” way of Edmonds and makes the algorithm for maximum matchings in general graphs more simple.

Rainbow Matchings in Properly Colored Bipartite Graphs

Let G be a properly colored bipartite graph. A rainbow matching of G is such a matching in which no two edges have the same color. Let G be a properly colored bipartite graph with bipartition (X,Y) and . We show that if , then G has a rainbow coloring of size at least .

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).

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.

An improved particle filter indoor fusion positioning approach based on Wi-Fi/PDR/geomagnetic field

The existing indoor fusion positioning methods based on Pedestrian Dead Reckoning(PDR)and geomagnetic technology have the problems of large initial position error,low sensor accuracy,and geomagnetic mismatch.In this study,a novel indoor fusion positioning approach based on the improved particle filter algorithm by geomagnetic iterative matching is proposed,where Wi-Fi,PDR,and geomagnetic signals are integrated to improve indoor positioning performances.One important contribution is that geomagnetic iterative matching is firstly proposed based on the particle filter algorithm.During the positioning process,an iterative window and a constraint window are introduced to limit the particle generation range and the geomagnetic matching range respectively.The position is corrected several times based on geomagnetic iterative matching in the location correction stage when the pedestrian movement is detected,which made up for the shortage of only one time of geomagnetic correction in the existing particle filter algorithm.In addition,this study also proposes a real-time step detection algorithm based on multi-threshold constraints to judge whether pedestrians are moving,which satisfies the real-time requirement of our fusion positioning approach.Through experimental verification,the average positioning accuracy of the proposed approach reaches 1.59 m,which improves 33.2%compared with the existing particle filter fusion positioning algorithms.

Interface Engineering of Titanium Nitride Nanotube Composites for Excellent Microwave Absorption at Elevated Temperature

Currently,the microwave absorbers usually suffer dreadful electromagnetic wave absorption(EMWA)performance damping at elevated temperature due to impedance mismatching induced by increased conduction loss.Consequently,the development of high-performance EMWA materials with good impedance matching and strong loss ability in wide temperature spectrum has emerged as a top priority.Herein,due to the high melting point,good electrical conductivity,excellent environmental stability,EM coupling effect,and abundant interfaces of titanium nitride(TiN)nanotubes,they were designed based on the controlling kinetic diffusion procedure and Ostwald ripening process.Benefiting from boosted heterogeneous interfaces between TiN nanotubes and polydimethylsiloxane(PDMS),enhanced polarization loss relaxations were created,which could not only improve the depletion efficiency of EMWA,but also contribute to the optimized impedance matching at elevated temperature.Therefore,the TiN nanotubes/PDMS composite showed excellent EMWA performances at varied temperature(298-573 K),while achieved an effective absorption bandwidth(EAB)value of 3.23 GHz and a minimum reflection loss(RLmin)value of−44.15 dB at 423 K.This study not only clarifies the relationship between dielectric loss capacity(conduction loss and polarization loss)and temperature,but also breaks new ground for EM absorbers in wide temperature spectrum based on interface engineering.

Understanding the Relationship Between Shrinking Cities and Land Prices:Spatial Pattern,Effectiveness,and Policy Implications

Urban shrinkage has emerged as a widespread phenomenon globally and has a significant impact on land,particularly in terms of land use and price.This study focuses on 2851 county-level cities in China in 2005–2018(excluding Hong Kong,Macao,Taiwan,and‘no data’areas in Qinhai-Tibet Plateau)as the fundamental units of analysis.By employing nighttime light(NTL)data to identify shrinking cities,the propensity score matching(PSM)model was used to quantitatively examine the impact of shrinking cities on land prices,and evaluate the magnitude of this influence.The findings demonstrate the following:1)there were 613 shrinking cities in China,with moderate shrinkage being the most prevalent and severe shrinkage being the least.2)Regional disparities are evident in the spatial distribution of shrinking cities,especially in areas with diverse terrain.3)The spatial pattern of land price exhibits a significant correlated to the economic and administrative levels.4)Shrinking cities significantly negatively impact on the overall land price(ATT=–0.1241,P<0.05).However,the extent of the effect varies significantly among different spatial regions.This study contributes novel insights into the investigation of land prices and shrinking cities,ultimately serving as a foundation for government efforts to promote the sustainable development of urban areas.

From VIB‑to VB‑Group Transition Metal Disulfides:Structure Engineering Modulation for Superior Electromagnetic Wave Absorption

The laminated transition metal disulfides(TMDs),which are well known as typical two-dimensional(2D)semiconductive materials,possess a unique layered structure,leading to their wide-spread applications in various fields,such as catalysis,energy storage,sensing,etc.In recent years,a lot of research work on TMDs based functional materials in the fields of electromagnetic wave absorption(EMA)has been carried out.Therefore,it is of great significance to elaborate the influence of TMDs on EMA in time to speed up the application.In this review,recent advances in the development of electromagnetic wave(EMW)absorbers based on TMDs,ranging from the VIB group to the VB group are summarized.Their compositions,microstructures,electronic properties,and synthesis methods are presented in detail.Particularly,the modulation of structure engineering from the aspects of heterostructures,defects,morphologies and phases are systematically summarized,focusing on optimizing impedance matching and increasing dielectric and magnetic losses in the EMA materials with tunable EMW absorption performance.Milestones as well as the challenges are also identified to guide the design of new TMDs based dielectric EMA materials with high performance.

Shared genetic architecture highlights the bidirectional association between major depressive disorder and fracture risk

Background There is limited evidence suggesting that osteoporosis might exacerbate depressive symptoms,while more studies demonstrate that depression negatively affects bone density and increases fracture risk.Aims To explore the relationship between major depressive disorder(MDD)and fracture risk.Methods We conducted a nested case-control analysis(32670 patients with fracture and 397017 individuals without fracture)and a matched cohort analysis(16496 patients with MDD and 435492 individuals without MDD)in the same prospective UK Biobank data set.Further,we investigated the shared genetic architecture between MDD and fracture with linkage disequilibrium score regression and the MiXeR statistical tools.We used the conditional/conjunctional false discovery rate approach to identify the specific shared loci.We calculated the weighted genetic risk score for individuals in the UK Biobank and logistic regression was used to confirm the association observed in the prospective study.Results We found that MDD was associated with a 14%increase in fracture risk(hazard ratio(HR)1.14,95%CI 1.14 to 1.15,p<0.001)in the nested case-control analysis,while fracture was associated with a 72%increase in MDD risk(HR 1.72,95%CI 1.64 to 1.79,p<0.001)in the matched cohort analysis,suggesting a longitudinal and bidirectional relationship.Further,genetic summary data suggested a genetic overlap between MDD and fracture.Specifically,we identified four shared genomic loci,with the top signal(rs7554101)near SGIP1.The protein encoded by SGIP1 is involved in cannabinoid receptor type 1 signalling.We found that genetically predicted MDD was associated with a higher risk of fracture and vice versa.In addition,we found that the higher expression level of SGIP1 in the spinal cord and muscle was associated with an increased risk of fracture and MDD.Conclusions The genetic pleiotropy between MDD and fracture highlights the bidirectional association observed in the epidemiological analysis.The shared genetic components(such as SGIP1)between the diseases suggest that modulating the endocannabinoid system could be a potential therapeutic strategy for both MDD and bone loss.

A photogrammetric approach for quantifying the evolution of rock joint void geometry under varying contact states

Accurate measurement of the evolution of rock joint void geometry is essential for comprehending the distribution characteristics of asperities responsible for shear and seepage behaviors.However,existing techniques often require specialized equipment and skilled operators,posing practical challenges.In this study,a cost-effective photogrammetric approach is proposed.Particularly,local coordinate systems are established to facilitate the alignment and precise quantification of the relative position between two halves of a rock joint.Push/pull tests are conducted on rock joints with varying roughness levels to induce different contact states.A high-precision laser scanner serves as a benchmark for evaluating the photogrammetry method.Despite certain deviations exist,the measured evolution of void geometry is generally consistent with the qualitative findings of previous studies.The photogrammetric measurements yield comparable accuracy to laser scanning,with maximum errors of 13.2%for aperture and 14.4%for void volume.Most joint matching coefficient(JMC)measurement errors are below 20%.Larger measurement errors occur primarily in highly mismatched rock joints with JMC values below 0.2,but even in cases where measurement errors exceed 80%,the maximum JMC error is only 0.0434.Thus,the proposed photogrammetric approach holds promise for widespread application in void geometry measurements in rock joints.

TiN/Fe_(2)N/C composite with stable and broadband high-temperature microwave absorption

Facing the complex variable high-temperature environment,electromagnetic wave(EMW)absorbing materials maintaining high stability and satisfying absorbing properties is essential.This study focused on the synthesis and EMW absorbing performance evaluation of TiN/Fe_(2)N/C composite materials,which were prepared using electrostatic spinning followed by a high-temperature nitridation process.The TiN/Fe_(2)N/C fibers constructed a well-developed conductive network that generates considerable conduction loss.The heterogeneous interfaces between different components generated a significant level of interfacial polarization.Thanks to the synergistic effect of stable dielectric loss and optimized impedance matching,the TiN/Fe_(2)N/C composite materials demonstrated excellent and stable absorption performance across a wide temperature range(293-453 K).Moreover,TiN/Fe_(2)N/C-15 achieved a minimum reflection loss(RL)of−48.01 dB and an effective absorption bandwidth(EAB)of 3.64 GHz at 2.1 mm and 373 K.This work provides new insights into the development of high-efficiency and stabile EMW absorbing materials under complex variable high-temperature conditions.

Flexible ultrasound arrays with embossed polymer structures for medical imaging

In recent years,the application of flexible electronic technology[1−3]combined with ultrasonic imaging[4]has blossomed,resulting in a shift in the application place of ultrasonic imaging technology from medical institutions to households.The utilization of this application has expanded from the physician’s positioning and guidance to real-time patient monitoring[5],while the range of application scenarios continues to widen.The transformative changes have made possible through the development of flexible transducer arrays[6,7].Prof.Sheng Xu's team at the University of California San Diego has pioneered the development of various flexible transducer arrays based on island-bridge structures[8]and serpentine electrodes[9].These transducer arrays incorporate rigid 1−3 composite piezoelectric transducers on an island,featuring thin electrodes between the islands to provide mechanical flexibility,metallic electrodes of serpentine structure to provide stretchability of the device,and elastomer materials are used to encapsulate the overall structure,ensuring structural stability and impedance matching to the skin tissue[10].These flexible transducer arrays have found extensive applications in human blood pressure detection[11],cardiac imaging[12],blood flow doppler imaging[13],tissue modulus detection[14],and tissue deep hemoglobin detection[15].

Distributed Matching Theory-Based Task Re-Allocating for Heterogeneous Multi-UAV Edge Computing

Many efforts have been devoted to efficient task scheduling in Multi-Unmanned Aerial Vehicle(UAV)edge computing.However,the heterogeneity of UAV computation resource,and the task re-allocating between UAVs have not been fully considered yet.Moreover,most existing works neglect the fact that a task can only be executed on the UAV equipped with its desired service function(SF).In this backdrop,this paper formulates the task scheduling problem as a multi-objective task scheduling problem,which aims at maximizing the task execution success ratio while minimizing the average weighted sum of all tasks’completion time and energy consumption.Optimizing three coupled goals in a realtime manner with the dynamic arrival of tasks hinders us from adopting existing methods,like machine learning-based solutions that require a long training time and tremendous pre-knowledge about the task arrival process,or heuristic-based ones that usually incur a long decision-making time.To tackle this problem in a distributed manner,we establish a matching theory framework,in which three conflicting goals are treated as the preferences of tasks,SFs and UAVs.Then,a Distributed Matching Theory-based Re-allocating(DiMaToRe)algorithm is put forward.We formally proved that a stable matching can be achieved by our proposal.Extensive simulation results show that Di Ma To Re algorithm outperforms benchmark algorithms under diverse parameter settings and has good robustness.

Minimalistic approach to left atrial appendage occlusion guided by cardiac computed tomography angiography

OBJECTIVE To assess the feasibility and safety of the minimalistic approach to left atrial appendage occlusion(LAAO) guided by cardiac computed tomography angiography(CCTA).METHODS Ninety consecutive patients who underwent LAAO, with or without CCTA-guided, were matched(1:2). Each step of the LAAO procedure in the computed tomography(CT) guidance group(CT group) was directed by preprocedural CT planning. In the control group, LAAO was performed using the standard method. All patients were followed up for 12 months, and device surveillance was conducted using CCTA.RESULTS A total of 90 patients were included in the analysis, with 30 patients in the CT group and 60 matched patients in the control group. All patients were successfully implanted with Watchman devices. The mean ages for the CT group and the control group were 70.0 ± 9.4 years and 68.4 ± 11.9 years(P = 0.52), respectively. The procedure duration(45.6 ± 10.7 min vs. 58.8 ± 13.0 min,P < 0.001) and hospital stay(7.5 ± 2.4 day vs. 9.6 ± 2.8 day, P = 0.001) in the CT group was significantly shorter compared to the control group. However, the total radiation dose was higher in the CT group compared to the control group(904.9 ± 348.0 m Gy vs.711.9 ± 211.2 m Gy, P = 0.002). There were no significant differences in periprocedural pericardial effusion(3.3% vs. 6.3%, P = 0.8) between the two groups. The rate of postprocedural adverse events(13.3% vs. 18.3%, P = 0.55) were comparable between both groups at 12 months follow-up.CONCLUSIONS CCTA is capable of detailed LAAO procedure planning. Minimalistic LAAO with preprocedural CCTA planning was feasible and safe, with shortened procedure time and acceptable increased radiation and contras consumption. For patients with contraindications to general anesthesia and/or transesophageal echocardiography, this promising method may be an alternative to conventional LAAO.

Feature Matching via Topology-Aware Graph Interaction Model

Feature matching plays a key role in computer vision. However, due to the limitations of the descriptors, the putative matches are inevitably contaminated by massive outliers.This paper attempts to tackle the outlier filtering problem from two aspects. First, a robust and efficient graph interaction model,is proposed, with the assumption that matches are correlated with each other rather than independently distributed. To this end, we construct a graph based on the local relationships of matches and formulate the outlier filtering task as a binary labeling energy minimization problem, where the pairwise term encodes the interaction between matches. We further show that this formulation can be solved globally by graph cut algorithm. Our new formulation always improves the performance of previous localitybased method without noticeable deterioration in processing time,adding a few milliseconds. Second, to construct a better graph structure, a robust and geometrically meaningful topology-aware relationship is developed to capture the topology relationship between matches. The two components in sum lead to topology interaction matching(TIM), an effective and efficient method for outlier filtering. Extensive experiments on several large and diverse datasets for multiple vision tasks including general feature matching, as well as relative pose estimation, homography and fundamental matrix estimation, loop-closure detection, and multi-modal image matching, demonstrate that our TIM is more competitive than current state-of-the-art methods, in terms of generality, efficiency, and effectiveness. The source code is publicly available at http://github.com/YifanLu2000/TIM.