共查询到20条相似文献,搜索用时 15 毫秒
1.
Dong Ye 《Discrete Mathematics》2018,341(5):1195-1198
It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph with has a maximum matching such that any two -unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for -regular graphs with . All counterexamples for -regular graphs given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all -regular simple graphs and also -regular multigraphs with . 相似文献
2.
Denis Naddef 《Mathematical Programming》1982,22(1):52-70
The matching polytope is the convex hull of the incidence vectors of all (not necessarily perfect) matchings of a graphG. We consider here the problem of computing the dimension of the face of this polytope which contains the maximum cardinality matchings ofG and give a good characterization of this quantity, in terms of the cyclomatic number of the graph and families of odd subsets of the nodes which are always nearly perfectly matched by every maximum matching.This is equivalent to finding a maximum number of linearly independent representative vectors of maximum matchings ofG; the size of such a set is called thematching rank ofG.
We also give in the last section a way of computing that rank independently of those parameters.Note that this gives us a good lower bound on the number of those matchings. 相似文献
3.
Jan Harm van der Walt 《Quaestiones Mathematicae》2016,39(2):167-178
The closed graph theorem is one of the cornerstones of linear functional analysis in Fréchet spaces, and the extension of this result to more general topological vector spaces is a di?cult problem comprising a great deal of technical difficulty. However, the theory of convergence vector spaces provides a natural framework for closed graph theorems. In this paper we use techniques from convergence vector space theory to prove a version of the closed graph theorem for order bounded operators on Archimedean vector lattices. This illustrates the usefulness of convergence spaces in dealing with problems in vector lattice theory, problems that may fail to be amenable to the usual Hausdorff-Kuratowski-Bourbaki concept of topology. 相似文献
4.
5.
In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G=Kk(K1+Kn−k−1), the join of Kk, the complete graph on k vertices, with the disjoint union of K1 and Kn−k−1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum. 相似文献
6.
7.
The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte [28] in terms of self-conjugate flows in antisymmetrical digraphs. He showed that for these objects there are natural analogs of classical theoretical results on usual network flows, such as the flow decomposition, augmenting path, and max-flow min-cut theorems. We give unified and shorter proofs for those theoretical results. We then extend to MSFP the shortest augmenting path method of Edmonds and Karp [7] and the blocking flow method of Dinits [4], obtaining algorithms with similar time bounds in general case. Moreover, in the cases of unit arc capacities and unit node capacities our blocking skew-symmetric flow algorithm has time bounds similar to those established in [8, 21] for Dinits algorithm. In particular, this implies an algorithm for finding a maximum matching in a nonbipartite graph in time, which matches the time bound for the algorithm of Micali and Vazirani [25]. Finally, extending a clique compression technique of Feder and Motwani [9] to particular skew-symmetric graphs, we speed up the implied maximum matching algorithm to run in time, improving the best known bound for dense nonbipartite graphs. Also other theoretical and algorithmic results on skew-symmetric flows and their applications are presented.Mathematics Subject Classification (1991): 90C27, 90B10, 90C10, 05C85 相似文献
8.
G. Mazzuoccolo 《Discrete Mathematics》2013,313(20):2292-2296
9.
Maximum induced matchings in graphs 总被引:2,自引:0,他引:2
We provide a formula for the number of edges of a maximum induced matching in a graph. As applications, we give some structural properties of (k + 1)K2-free graphs, construct all 2K2-free graphs, and count the number of labeled 2K2-free connected bipartite graphs. 相似文献
10.
Zhongyuan Che 《Czechoslovak Mathematical Journal》2010,60(2):489-494
We give a necessary and sufficient condition for the existence of perfect matchings in a plane bipartite graph in terms of
elementary edge-cut, which extends the result for the existence of perfect matchings in a hexagonal system given in the paper
of F. Zhang, R. Chen and X. Guo (1985). 相似文献
11.
Let be a finite simple graph. For , the difference of , where is the neighborhood of and is called the critical difference of . is called a critical set if equals the critical difference and is the intersection of all critical sets. is the union of all critical independent sets. An independent set is an inclusion minimal set with if no proper subset of has positive difference.A graph is called a König–Egerváry graph if the sum of its independence number and matching number equals .In this paper, we prove a conjecture which states that for any graph the number of inclusion minimal independent set with is at least the critical difference of the graph.We also give a new short proof of the inequality .A characterization of unicyclic non-König–Egerváry graphs is also presented and a conjecture which states that for such a graph , the critical difference equals , is proved.We also make an observation about using Edmonds–Gallai Structure Theorem as a concluding remark. 相似文献
12.
We prove that in all regular robust expanders , every edge is asymptotically equally likely contained in a uniformly chosen perfect matching . We also show that given any fixed matching or spanning regular graph in , the random variable is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders. 相似文献
13.
14.
P. Hall, [2], gave necessary and sufficient conditions for a bipartite graph to have a perfect matching. Koning, [3], proved that such a graph can be decomposed intok edge-disjoint perfect matchings if and only if it isk-regular. It immediately follows that in ak-regular bipartite graphG, the deletion of any setS of at mostk – 1 edges leaves intact one of those perfect matchings. However, it is not known what happens if we delete more thank – 1 edges. In this paper we give sufficient conditions so that by deleting a setS ofk + r edgesr 0, stillG – S has a perfect matching. Furthermore we prove that our result, in some sense, is best possible. 相似文献
15.
16.
Min Aung 《Journal of Graph Theory》1989,13(2):149-155
It is proved that a 4-connected, δ-regular graph G either is Hamiltonian, or has at least 3δ + 1 vertices and contains a cycle of length at least min{4δ - 4, 1/2 (|G| + 3δ - 2)}. Examples supplied by B. Jackson and H.A. Jung show that min{4δ - 4, 1/2(|G| + 3δ - 2)} cannot be replaced by 4δ + 1. 相似文献
17.
Cycles through specified vertices of a graph 总被引:1,自引:0,他引:1
We prove that ifS is a set ofk−1 vertices in ak-connected graphG, then the cycles throughS generate the cycle space ofG. Moreover, whenk≧3, each cycle ofG can be expressed as the sum of an odd number of cycles throughS. On the other hand, ifS is a set ofk vertices, these conclusions do not necessarily hold, and we characterize the exceptional cases. As corollaries, we establish
the existence of odd and even cycles through specified vertices and deduce the existence of long odd and even cycles in graphs
of high connectivity. 相似文献
18.
19.
20.
For every fixedk≥3 there exists a constantc
k
with the following property. LetH be ak-uniform,D-regular hypergraph onN vertices, in which no two edges contain more than one common vertex. Ifk>3 thenH contains a matching covering all vertices but at mostc
k
ND
−1/(k−1). Ifk=3, thenH contains a matching covering all vertices but at mostc
3
ND
−1/2ln3/2
D. This improves previous estimates and implies, for example, that any Steiner Triple System onN vertices contains a matching covering all vertices but at mostO(N
1/2ln3/2
N), improving results by various authors.
Research supported in part by a USA-Israel BSF grant.
Research supported in part by a USA-Israel BSF Grant. 相似文献