Odd subgraphs and matchings

Let G be a graph and f : V(G)→{1,3,5,…}. Then a subgraph H of G is called a (1,f)-odd subgraph if deg_H(x){1,3,…,f(x)} for all xV(H). If f(x)=1 for all xV(G), then a (1,f)-odd subgraph is nothing but a matching. A (1,f)-odd subgraph H of G is said to be maximum if G has no (1,f)-odd subgraph K such that |K|>|H|. We show that (1,f)-odd subgraphs have some properties similar to those of matchings, in particular, we give a formula for the order of a maximum (1,f)-odd subgraph, which is similar to that for the order of a maximum matching.     

Problems on matchings and independent sets of a graph

Let $G$ be a finite simple graph. For $X?V\left(G\right)$, the difference of $X$, $d\left(X\right)?\left|X\right|?\left|N\left(X\right)\right|$ where $N\left(X\right)$ is the neighborhood of $X$ and $max\{d\left(X\right):X?V\left(G\right)\}$ is called the critical difference of $G$. $X$ is called a critical set if $d\left(X\right)$ equals the critical difference and $\ker \left(G\right)$ is the intersection of all critical sets. $\mathrm{diadem}\left(G\right)$ is the union of all critical independent sets. An independent set $S$ is an inclusion minimal set with$d\left(S\right)>0$ if no proper subset of $S$ has positive difference.A graph $G$ is called a König–Egerváry graph if the sum of its independence number $\alpha \left(G\right)$ and matching number $\mu \left(G\right)$ equals $\left|V\left(G\right)\right|$.In this paper, we prove a conjecture which states that for any graph the number of inclusion minimal independent set $S$ with $d\left(S\right)>0$ is at least the critical difference of the graph.We also give a new short proof of the inequality $\left|\ker \left(G\right)\right|+\left|\mathrm{diadem}\left(G\right)\right|\le 2\alpha \left(G\right)$.A characterization of unicyclic non-König–Egerváry graphs is also presented and a conjecture which states that for such a graph $G$, the critical difference equals $\alpha \left(G\right)?\mu \left(G\right)$, is proved.We also make an observation about $\ker \left(G\right)$ using Edmonds–Gallai Structure Theorem as a concluding remark.     

Objective Bayesian analysis of the Frechet stress–strength model

Several reference priors and a general form of matching priors are derived for a stress–strength system, and it is concluded that none of the reference priors is a matching prior. The study shows that the matching prior performs better than Jeffreys prior and reference priors in meeting the target coverage probabilities.     

Five-torsion in the homology of the matching complex on 14 vertices

J.L. Andersen proved that there is 5-torsion in the bottom nonvanishing homology group of the simplicial complex of graphs of degree at most two on seven vertices. We use this result to demonstrate that there is 5-torsion also in the bottom nonvanishing homology group of the matching complex on 14 vertices. Combining our observation with results due to Bouc and to Shareshian and Wachs, we conclude that the case n=14 is exceptional; for all other n, the torsion subgroup of the bottom nonvanishing homology group has exponent three or is zero. The possibility remains that there is other torsion than 3-torsion in higher-degree homology groups of when n≥13 and n≠14. Research of J. Jonsson was supported by European Graduate Program “Combinatorics, Geometry, and Computation”, DFG-GRK 588/2.     

Matching Points with Squares

Given a class of geometric objects and a point set P, a -matching of P is a set of elements of such that each C _i contains exactly two elements of P and each element of P lies in at most one C _i . If all of the elements of P belong to some C _i , M is called a perfect matching. If, in addition, all of the elements of M are pairwise disjoint, we say that this matching M is strong. In this paper we study the existence and characteristics of -matchings for point sets in the plane when is the set of isothetic squares in the plane. A consequence of our results is a proof that the Delaunay triangulations for the L _∞ metric and the L ₁ metric always admit a Hamiltonian path.     

The clique operator on matching and chessboard graphs

Given positive integers m,n, we consider the graphs G_n and G_m,n whose simplicial complexes of complete subgraphs are the well-known matching complex M_n and chessboard complex M_m,n. Those are the matching and chessboard graphs. We determine which matching and chessboard graphs are clique-Helly. If the parameters are small enough, we show that these graphs (even if not clique-Helly) are homotopy equivalent to their clique graphs. We determine the clique behavior of the chessboard graph G_m,n in terms of m and n, and show that G_m,n is clique-divergent if and only if it is not clique-Helly. We give partial results for the clique behavior of the matching graph G_n.     

图T1,1,m与Q(3,n)中有路因子的充分必要条件及T1,1,m的匹配等价类

如果一个图的匹配多项式可以被一个路的匹配多项式整除,我们就称此路是该图的一个路因子,路因子在刻画图的匹配等价类,研究匹配唯一性方面有很重要的作用.本文得到了图T1,1.m与图Q(3,n)中有路因子的充分必要条件.