Log in

Relevant bibliographies by topics / Perfekte Matchings / Journal articles

To see the other types of publications on this topic, follow the link: Perfekte Matchings.

Journal articles on the topic 'Perfekte Matchings'

Author: Grafiati

Published: 4 June 2021

Last updated: 7 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Perfekte Matchings.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

He, Jinghua, Erling Wei, Dong Ye, and Shaohui Zhai. "On perfect matchings in matching covered graphs." Journal of Graph Theory 90, no. 4 (2018): 535–46. http://dx.doi.org/10.1002/jgt.22411.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

LÜ, HUAZHONG, and TINGZENG WU. "Fractional Matching Preclusion for Restricted Hypercube-Like Graphs." Journal of Interconnection Networks 19, no. 03 (2019): 1940010. http://dx.doi.org/10.1142/s0219265919400103.

Full text

Abstract:

The restricted hypercube-like graphs, variants of the hypercube, were proposed as desired interconnection networks of parallel systems. The matching preclusion number of a graph is the minimum number of edges whose deletion results in the graph with neither perfect matchings nor almost perfect matchings. The fractional perfect matching preclusion and fractional strong perfect matching preclusion are generalizations of the matching preclusion. In this paper, we obtain fractional matching preclusion number and fractional strong matching preclusion number of restricted hypercube-like graphs, whic

APA, Harvard, Vancouver, ISO, and other styles

3

CHENG, EDDIE, and SACHIN PADMANABHAN. "MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION FOR CROSSED CUBES." Parallel Processing Letters 22, no. 02 (2012): 1250005. http://dx.doi.org/10.1142/s0129626412500053.

Full text

Abstract:

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In thi

APA, Harvard, Vancouver, ISO, and other styles

4

MAO, YAPING, and EDDIE CHENG. "A Concise Survey of Matching Preclusion in Interconnection Networks." Journal of Interconnection Networks 19, no. 03 (2019): 1940006. http://dx.doi.org/10.1142/s0219265919400061.

Full text

Abstract:

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. There are other related parameters and generalization including the strong matching preclusion number, the conditional matching preclusion number, the fractional matching preclusion number, and so on. In this survey, we give an introduction on the general topic of matching preclusion.

APA, Harvard, Vancouver, ISO, and other styles

5

Ma, Tianlong, Yaping Mao, Eddie Cheng, and Jinling Wang. "Fractional Matching Preclusion for (n, k)-Star Graphs." Parallel Processing Letters 28, no. 04 (2018): 1850017. http://dx.doi.org/10.1142/s0129626418500172.

Full text

Abstract:

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu introduced the concept of fractional matching preclusion number in 2017. The Fractional Matching Preclusion Number (FMP number) of G is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The Fractional Strong Matching Preclusion Number (FSMP number) of G is the minimum number of vertices and/or edges whose deletion leaves the resulting

APA, Harvard, Vancouver, ISO, and other styles

6

CHENG, EDDIE, DAVID LU, and BRIAN XU. "STRONG MATCHING PRECLUSION OF PANCAKE GRAPHS." Journal of Interconnection Networks 14, no. 02 (2013): 1350007. http://dx.doi.org/10.1142/s0219265913500072.

Full text

Abstract:

The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem that was introduced by Park and Ihm. In this paper, we examine the properties of pancake graphs by finding its strong matching preclusion number and categorizing all optimal solutions.

APA, Harvard, Vancouver, ISO, and other styles

7

Zhang, Shuangshuang, Yuzhi Xiao, Xia Liu, and Jun Yin. "A Short Note of Strong Matching Preclusion for a Class of Arrangement Graphs." Parallel Processing Letters 30, no. 01 (2020): 2050001. http://dx.doi.org/10.1142/s0129626420500012.

Full text

Abstract:

The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. The strong matching preclusion is a well-studied measure for the network invulnerability in the event of edge failure. In this paper, we obtain the strong matching preclusion number for a class of arrangement graphs and categorize their the strong matching preclusion set, which are a supplement of known results.

APA, Harvard, Vancouver, ISO, and other styles

8

Wang, Xia, Tianlong Ma, Jun Yin, and Chengfu Ye. "Fractional matching preclusion for radix triangular mesh." Discrete Mathematics, Algorithms and Applications 11, no. 04 (2019): 1950048. http://dx.doi.org/10.1142/s1793830919500484.

Full text

Abstract:

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. As a generalization, Liu and Liu recently introduced the concept of fractional matching preclusion number. The fractional matching preclusion number (FMP number) of [Formula: see text], denoted by [Formula: see text], is the minimum number of edges whose deletion leaves the resulting graph without a fractional perfect matching. The fractional strong matching preclusion number (FSMP number) of [Formula: see text], denoted by

APA, Harvard, Vancouver, ISO, and other styles

9

Anantapantula, Sai, Christopher Melekian, and Eddie Cheng. "Matching Preclusion for the Shuffle-Cubes." Parallel Processing Letters 28, no. 03 (2018): 1850012. http://dx.doi.org/10.1142/s0129626418500123.

Full text

Abstract:

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. A graph is maximally matched if its matching preclusion number is equal to its minimum degree, and is super matched if the matching preclusion number can only be achieved by deleting all edges incident to a single vertex. In this paper, we determine the matching preclusion number and classify the optimal matching preclusion sets for the shuffle-cube graphs, a variant of the well-known hypercubes.

APA, Harvard, Vancouver, ISO, and other styles

10

CHENG, EDDIE, RANDY JIA, and DAVID LU. "MATCHING PRECLUSION AND CONDITIONAL MATCHING PRECLUSION FOR AUGMENTED CUBES." Journal of Interconnection Networks 11, no. 01n02 (2010): 35–60. http://dx.doi.org/10.1142/s0219265910002726.

Full text

Abstract:

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those incident to a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those incident to a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In t

APA, Harvard, Vancouver, ISO, and other styles

11

WANG, XIUMEI, WEIPING SHANG, YIXUN LIN, and MARCELO H. CARVALHO. "A CHARACTERIZATION OF PM-COMPACT CLAW-FREE CUBIC GRAPHS." Discrete Mathematics, Algorithms and Applications 06, no. 02 (2014): 1450025. http://dx.doi.org/10.1142/s1793830914500256.

Full text

Abstract:

The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. This paper characterizes claw-free cubic graphs whose 1-skeleton graphs of perfect matching polytopes have diameter 1.

APA, Harvard, Vancouver, ISO, and other styles

12

Pálvölgyi, Dömötör. "Partitioning to three matchings of given size is NP-complete for bipartite graphs." Acta Universitatis Sapientiae, Informatica 6, no. 2 (2014): 206–9. http://dx.doi.org/10.1515/ausi-2015-0004.

Full text

Abstract:

Abstract We show that the problem of deciding whether the edge set of a bipartite graph can be partitioned into three matchings, of size k1, k2 and k3 is NP-complete, even if one of the matchings is required to be perfect. We also show that the problem of deciding whether the edge set of a simple graph contains a perfect matching and a disjoint matching of size k or not is NP-complete, already for bipartite graphs with maximum degree 3. It also follows from our construction that it is NP-complete to decide whether in a bipartite graph there is a perfect matching and a disjoint matching that co

APA, Harvard, Vancouver, ISO, and other styles

13

BONNEVILLE, PHILIP, EDDIE CHENG, and JOSEPH RENZI. "STRONG MATCHING PRECLUSION FOR THE ALTERNATING GROUP GRAPHS AND SPLIT-STARS." Journal of Interconnection Networks 12, no. 04 (2011): 277–98. http://dx.doi.org/10.1142/s0219265911003003.

Full text

Abstract:

The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem and has recently been introduced by Park and Ihm.15 In this paper, we examine properties of strong matching preclusion for alternating group graphs, by finding their strong matching preclusion numbers and categorizing all optimal solutions. More importantly, we prove a general result on taking a Cartesian product of a graph with K2 (an edge) to obtai

APA, Harvard, Vancouver, ISO, and other styles

14

CHENG, EDDIE, and OMER SIDDIQUI. "Strong Matching Preclusion of Arrangement Graphs." Journal of Interconnection Networks 16, no. 02 (2016): 1650004. http://dx.doi.org/10.1142/s0219265916500043.

Full text

Abstract:

The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph with neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem that was introduced by Park and Ihm. The class of arrangement graphs was introduced as a common generalization of the star graphs and alternating group graphs, and to provide an even richer class of interconnection networks. In this paper, the goal is to find the strong matching preclusion number of arrangement graphs and to categorize all optimal strong

APA, Harvard, Vancouver, ISO, and other styles

15

Han, Jie. "Perfect Matchings in Hypergraphs and the Erdös Matching Conjecture." SIAM Journal on Discrete Mathematics 30, no. 3 (2016): 1351–57. http://dx.doi.org/10.1137/16m1056079.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Giannopoulou, Archontia C., Stephan Kreutzer, and Sebastian Wiederrecht. "Matching Connectivity: On the Structure of Graphs with Perfect Matchings." Electronic Notes in Discrete Mathematics 61 (August 2017): 505–11. http://dx.doi.org/10.1016/j.endm.2017.06.080.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

CHENG, EDDIE, LINDA LESNIAK, MARC J. LIPMAN, and LÁSZLÓ LIPTÁK. "MATCHING PRECLUSION FOR ALTERNATING GROUP GRAPHS AND THEIR GENERALIZATIONS." International Journal of Foundations of Computer Science 19, no. 06 (2008): 1413–37. http://dx.doi.org/10.1142/s0129054108006364.

Full text

Abstract:

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number for the alternating group graphs, Cayley graphs generated by 2-trees and the (n,k)-arrangement graphs. Moreover, we classify all the optimal solutions.

APA, Harvard, Vancouver, ISO, and other styles

18

CHENG, EDDIE, and LÁSZLÓ LIPTÁK. "CONDITIONAL MATCHING PRECLUSION FOR (n,k)-STAR GRAPHS." Parallel Processing Letters 23, no. 01 (2013): 1350004. http://dx.doi.org/10.1142/s0129626413500047.

Full text

Abstract:

The matching preclusion number of an even graph G, denoted by mp (G), is the minimum number of edges whose deletion leaves the resulting graph without perfect matchings. The conditional matching preclusion number of an even graph G, denoted by mp 1(G), is the minimum number of edges whose deletion leaves the resulting graph with neither perfect matchings nor isolated vertices. The class of (n,k)-star graphs is a popular class of interconnection networks for which the matching preclusion number and the classification of the corresponding optimal solutions were known. However, the conditional ve

APA, Harvard, Vancouver, ISO, and other styles

19

Šándorová, Ľubica, and Marián Trenkler. "On a generalization of perfect $b$-matching." Mathematica Bohemica 116, no. 4 (1991): 380–84. http://dx.doi.org/10.21136/mb.1991.126032.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Zhu, Jianming. "Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Matching Energies." Open Journal of Discrete Mathematics 09, no. 01 (2019): 17–32. http://dx.doi.org/10.4236/ojdm.2019.91004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Doslic, Tomislav, and Taylor Short. "Maximal matchings in polyspiro and benzenoid chains." Applicable Analysis and Discrete Mathematics 15, no. 1 (2021): 179–200. http://dx.doi.org/10.2298/aadm161106003d.

Full text

Abstract:

A matching M of a graph G is maximal if it is not a proper subset of any other matching in G. Maximal matchings are much less known and researched than their maximum and perfect counterparts. In this paper we present the recurrences and generating functions for the sequences enumerating maximal matchings in two classes of chemically interesting linear polymers: polyspiro chains and benzenoid chains. We also analyze the asymptotic behavior of those sequences and determine the extremal cases.

APA, Harvard, Vancouver, ISO, and other styles

22

Wei, Shouliu, Niandong Chen, Xiaoling Ke, Guoliang Hao, and Jianwu Huang. "Perfect Matchings in Random Octagonal Chain Graphs." Journal of Mathematics 2021 (June 23, 2021): 1–5. http://dx.doi.org/10.1155/2021/2324632.

Full text

Abstract:

A perfect matching of a (molecule) graph G is a set of independent edges covering all vertices in G . In this paper, we establish a simple formula for the expected value of the number of perfect matchings in random octagonal chain graphs and present the asymptotic behavior of the expectation.

APA, Harvard, Vancouver, ISO, and other styles

23

Cooper, Colin, Alan Frieze, Michael Molloy, and Bruce Reed. "Perfect Matchings in Random r-regular, s-uniform Hypergraphs." Combinatorics, Probability and Computing 5, no. 1 (1996): 1–14. http://dx.doi.org/10.1017/s0963548300001796.

Full text

Abstract:

We show that r-regular, s-uniform hypergraphs contain a perfect matching with high probability (whp), provided The Proof is based on the application of a technique of Robinson and Wormald [7, 8]. The space of hypergraphs is partitioned into subsets according to the number of small cycles in the hypergraph. The difference in the expected number of perfect matchings between these subsets explains most of the variance of the number of perfect matchings in the space of hypergraphs, and is sufficient to prove existence (whp), using the Chebychev Inequality.

APA, Harvard, Vancouver, ISO, and other styles

24

Bampis, E., A. Giannakos, A. Karzanov, Y. Manoussakis, and I. Milis. "A Parallel Algorithm for Finding a Perfect Matching in a Planar Graph." Parallel Processing Letters 08, no. 03 (1998): 399–405. http://dx.doi.org/10.1142/s0129626498000407.

Full text

Abstract:

We present au intuitive and simple O( log 2 n log Φ) time, O(n2 M(n)) processor parallel algorithm for finding a perfect matching in a planar graph, where n is the order, Φ is the number of the distinct perfect matchings of the graph and M(n) is the best sequential complexity of matrix multiplication of size n. The algorithm runs on a CRCW PRAM. Clearly, our algorithm belongs to the class NC if the number of perfect matchings is polynomially bounded in the size of the input graph.

APA, Harvard, Vancouver, ISO, and other styles

25

WEI, XIAQI, SHURONG ZHANG, and WEIHUA YANG. "Matching Preclusion for Enhanced Pyramid Networks." Journal of Interconnection Networks 19, no. 03 (2019): 1940009. http://dx.doi.org/10.1142/s0219265919400097.

Full text

Abstract:

The matching preclusion number of a graph is the minimum number of edges whose deletion leaves the resulting graph that has neither perfect matchings nor almost perfect matchings. This concept was introduced as a measure of robustness in the event of edge failure in interconnection networks. The pyramid network is one of the important networks applied in parallel and distributed computer systems. Chen et al. in 2004 proposed a new hierarchy structure, called the enhanced pyramid network, by replacing each mesh in a pyramid network with a torus. An enhanced pyramid network of n layers is denote

APA, Harvard, Vancouver, ISO, and other styles

26

Došlić, Tomislav. "All Pairs of Pentagons in Leapfrog Fullerenes Are Nice." Mathematics 8, no. 12 (2020): 2135. http://dx.doi.org/10.3390/math8122135.

Full text

Abstract:

A subgraph H of a graph G with perfect matching is nice if G−V(H) has perfect matching. It is well-known that all fullerene graphs have perfect matchings and that all fullerene graphs contain some small connected graphs as nice subgraphs. In this contribution, we consider fullerene graphs arising from smaller fullerenes via the leapfrog transformation, and show that in such graphs, each pair of (necessarily disjoint) pentagons is nice. That answers in affirmative a question posed in a recent paper on nice pairs of odd cycles in fullerene graphs.

APA, Harvard, Vancouver, ISO, and other styles

27

WANG, SHIYING, YANLING WANG, and MUJIANGSHAN WANG. "Connectivity and Matching Preclusion for Leaf-Sort Graphs." Journal of Interconnection Networks 19, no. 03 (2019): 1940007. http://dx.doi.org/10.1142/s0219265919400073.

Full text

Abstract:

A multiprocessor system and interconnection network have a underlying topology, which is usually presented by a graph, where nodes represent processors and links represent communication links between processors. The (conditional) matching preclusion number of a graph is the minimum number of edges whose deletion leaves the resulting graph (with no isolated vertices) that has neither perfect matchings nor almost perfect matchings. In this paper, we prove that (1) the connectivity (edge connectivity) of the leaf-sort graph CFn is [Formula: see text] for odd n and [Formula: see text] for even n;

APA, Harvard, Vancouver, ISO, and other styles

28

Jockusch, William. "Perfect matchings and perfect squares." Journal of Combinatorial Theory, Series A 67, no. 1 (1994): 100–115. http://dx.doi.org/10.1016/0097-3165(94)90006-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Zhu, Bo, Tianlong Ma, Shuangshuang Zhang, and He Zhang. "Fractional Matching Preclusion for Data Center Networks." Parallel Processing Letters 30, no. 02 (2020): 2050010. http://dx.doi.org/10.1142/s0129626420500103.

Full text

Abstract:

An edge subset [Formula: see text] of [Formula: see text] is a fractional matching preclusion set (FMP set for short) if [Formula: see text] has no fractional perfect matchings. The fractional matching preclusion number (FMP number for short) of [Formula: see text], denoted by [Formula: see text], is the minimum size of FMP sets of [Formula: see text]. A set [Formula: see text] of edges and vertices of [Formula: see text] is a fractional strong matching preclusion set (FSMP set for short) if [Formula: see text] has no fractional perfect matchings. The fractional strong matching preclusion numb

APA, Harvard, Vancouver, ISO, and other styles

30

Zhu, Bo, Tianlong Ma, Shuangshuang Zhang, and He Zhang. "Fractional Matching Preclusion for Data Center Networks." Parallel Processing Letters 31, no. 03 (2021): 2150012. http://dx.doi.org/10.1142/s0129626421500122.

Full text

Abstract:

An edge subset [Formula: see text] of [Formula: see text] is a fractional matching preclusion set (FMP set for short) if [Formula: see text] has no fractional perfect matchings. The fractional matching preclusion number (FMP number for short) of [Formula: see text], denoted by [Formula: see text], is the minimum size of FMP sets of [Formula: see text]. A set [Formula: see text] of edges and vertices of [Formula: see text] is a fractional strong matching preclusion set (FSMP set for short) if [Formula: see text] has no fractional perfect matchings. The fractional strong matching preclusion numb

APA, Harvard, Vancouver, ISO, and other styles

31

LI, YALAN, CHENGFU YE, MIAOLIN WU, and PING HAN. "Fractional Matching Preclusion for Möbius Cubes." Journal of Interconnection Networks 19, no. 04 (2019): 1950007. http://dx.doi.org/10.1142/s0219265919500075.

Full text

Abstract:

Let F be an edge subset and F′ a subset of vertices and edges of a graph G. If G − F and G − F′ have no fractional perfect matchings, then F is a fractional matching preclusion (FMP) set and F′ is a fractional strong matching preclusion (FSMP) set of G. The FMP (FSMP) number of G is the minimum size of FMP (FSMP) sets of G. In this paper, we study the fractional matching preclusion number and the fractional strong matching preclusion number for the Möbius cube MQn. In adddition, all the optimal fractional strong preclusion sets of these graphs are categorized.

APA, Harvard, Vancouver, ISO, and other styles

32

Wang, Wen-Huan, and Chun-Xiang Zhai. "Minimal Estrada index of the trees without perfect matchings." Electronic Journal of Linear Algebra 35 (February 1, 2019): 408–17. http://dx.doi.org/10.13001/1081-3810.3355.

Full text

Abstract:

Trees possessing no Kekul Ìe structures (i.e., perfect matching) with the minimal Estrada index are considered. Let T_n be the set of the trees having no perfect matchings with n vertices. When n is odd and n â¥ 5, the trees with the smallest and the second smallest Estrada indices among T_n are obtained. When n is even and n â¥ 6, the tree with the smallest Estrada index in T_n is deduced.

APA, Harvard, Vancouver, ISO, and other styles

33

Bhat, K. Arathi, and G. Sudhakara. "Commuting decomposition of Kn1,n2,...,nk through realization of the product A(G)A(GPk )." Special Matrices 6, no. 1 (2018): 343–56. http://dx.doi.org/10.1515/spma-2018-0028.

Full text

Abstract:

Abstract In this paper, we introduce the notion of perfect matching property for a k-partition of vertex set of given graph. We consider nontrivial graphs G and GPk , the k-complement of graph G with respect to a kpartition of V(G), to prove that A(G)A(GPk ) is realizable as a graph if and only if P satis_es perfect matching property. For A(G)A(GPk ) = A(Γ) for some graph Γ, we obtain graph parameters such as chromatic number, domination number etc., for those graphs and characterization of P is given for which GPk and Γ are isomorphic. Given a 1-factor graph G with 2n vertices, we propose a p

APA, Harvard, Vancouver, ISO, and other styles

34

PERARNAU, GUILLEM, and ORIOL SERRA. "Rainbow Perfect Matchings in Complete Bipartite Graphs: Existence and Counting." Combinatorics, Probability and Computing 22, no. 5 (2013): 783–99. http://dx.doi.org/10.1017/s096354831300028x.

Full text

Abstract:

A perfect matchingMin an edge-coloured complete bipartite graphKn,nis rainbow if no pair of edges inMhave the same colour. We obtain asymptotic enumeration results for the number of rainbow perfect matchings in terms of the maximum number of occurrences of each colour. We also consider two natural models of random edge-colourings ofKn,nand show that if the number of colours is at leastn, then there is with high probability a rainbow perfect matching. This in particular shows that almost every square matrix of ordernin which every entry appearsntimes has a Latin transversal.

APA, Harvard, Vancouver, ISO, and other styles

35

PANDA, SWARUP. "Inverses of bicyclic graphs." Electronic Journal of Linear Algebra 32 (February 6, 2017): 217–31. http://dx.doi.org/10.13001/1081-3810.3322.

Full text

Abstract:

A graph G is said to be nonsingular (resp., singular) if its adjacency matrix A(G) is nonsingular (resp., singular). The inverse of a nonsingular graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A(G) via a diagonal matrix of Â±1s. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. In [C.D. Godsil. Inverses of trees. Combinatorica, 5(1):33â39, 1985.], Godsil proved that such graphs are invertible. He posed the question of characterizing

APA, Harvard, Vancouver, ISO, and other styles

36

Farrell, E. J. "Matchings in hexagonal cacti." International Journal of Mathematics and Mathematical Sciences 10, no. 2 (1987): 321–38. http://dx.doi.org/10.1155/s0161171287000395.

Full text

Abstract:

Explicit recurrences are derived for the matching polynomials of the basic types of hexagonal cacti, the linear cactus and the star cactus and also for an associated graph, called the hexagonal crown. Tables of the polynomials are given for each type of graph. Explicit formulae are then obtained for the number of defect-dmatchings in the graphs, for various values ofd. In particular, formulae are derived for the number of perfect matchings in all three types of graphs. Finally, results are given for the total number of matchings in the graphs.

APA, Harvard, Vancouver, ISO, and other styles

37

Chang, Hong, Yong-De Feng, Hong Bian, and Shou-Jun Xu. "Complete forcing numbers of rectangular polynominoes." Acta mathematica Spalatensia 1, no. 1 (2021): 87–96. http://dx.doi.org/10.32817/ams.1.1.7.

Full text

Abstract:

Let G be a graph with edge set E(G) that admits a perfect matching M. A forcing set of M is a subset of M contained in no other perfect matchings of G. A complete forcing set of G, recently introduced by Xu et al. [Complete forcing numbers of catacondensed hexagonal systems, J. Combin. Optim. 29(4) (2015) 803-814], is a subset of E(G) on which the restriction of any perfect matching M is a forcing set of M. The minimum possible cardinality of complete forcing sets of G is the complete forcing number of G. In this article, we discuss the complete forcing number of rectangular polyominoes (or gr

APA, Harvard, Vancouver, ISO, and other styles

38

Yang, Yunyun, and Gang Xie. "Maximum Matchings of a Digraph Based on the Largest Geometric Multiplicity." Mathematical Problems in Engineering 2016 (2016): 1–7. http://dx.doi.org/10.1155/2016/4702387.

Full text

Abstract:

Matching theory is one of the most forefront issues of graph theory. Based on the largest geometric multiplicity, we develop an efficient approach to identify maximum matchings in a digraph. For a given digraph, it has been proved that the number of maximum matched nodes has close relationship with the largest geometric multiplicity of the transpose of the adjacency matrix. Moreover, through fundamental column transformations, we can obtain the matched nodes and related matching edges. In particular, when a digraph contains a cycle factor, the largest geometric multiplicity is equal to one. In

APA, Harvard, Vancouver, ISO, and other styles

39

Rey, Joaquin Gomez, and Jose Heber Nieto. "Random Perfect Matchings: 10587." American Mathematical Monthly 106, no. 4 (1999): 365. http://dx.doi.org/10.2307/2589571.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Brouwer, Andries E., and Willem H. Haemers. "Eigenvalues and perfect matchings." Linear Algebra and its Applications 395 (January 2005): 155–62. http://dx.doi.org/10.1016/j.laa.2004.08.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Haglund, J., and J. B. Remmel. "Cycles and perfect matchings." Discrete Mathematics 274, no. 1-3 (2004): 93–108. http://dx.doi.org/10.1016/s0012-365x(03)00082-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Dourado, Mitre Costa, Dirk Meierling, Lucia D. Penso, Dieter Rautenbach, Fabio Protti, and Aline Ribeiro de Almeida. "Robust recoverable perfect matchings." Networks 66, no. 3 (2015): 210–13. http://dx.doi.org/10.1002/net.21624.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Lu, Hongliang, and Wei Wang. "On Perfect k-Matchings." Graphs and Combinatorics 30, no. 1 (2012): 229–35. http://dx.doi.org/10.1007/s00373-012-1259-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Ayyer, Arvind. "Determinants and perfect matchings." Journal of Combinatorial Theory, Series A 120, no. 1 (2013): 304–14. http://dx.doi.org/10.1016/j.jcta.2012.08.007.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Bartha, Miklós, and Miklós Krész. "On the König deficiency of zero-reducible graphs." Journal of Combinatorial Optimization 39, no. 1 (2019): 273–92. http://dx.doi.org/10.1007/s10878-019-00466-2.

Full text

Abstract:

Abstract A confluent and terminating reduction system is introduced for graphs, which preserves the number of their perfect matchings. A union-find algorithm is presented to carry out reduction in almost linear time. The König property is investigated in the context of reduction by introducing the König deficiency of a graph G as the difference between the vertex covering number and the matching number of G. It is shown that the problem of finding the König deficiency of a graph is NP-complete even if we know that the graph reduces to the empty graph. Finally, the König deficiency of graphs G

APA, Harvard, Vancouver, ISO, and other styles

46

BABENKO, MAXIM, ALEXEY GUSAKOV, and ILYA RAZENSHTEYN. "TRIANGLE-FREE 2-MATCHINGS REVISITED." Discrete Mathematics, Algorithms and Applications 02, no. 04 (2010): 643–54. http://dx.doi.org/10.1142/s1793830910000930.

Full text

Abstract:

A 2-matching in an undirected graph G = (VG, EG) is a function x: EG → {0, 1, 2} such that for each node v ∈ VG the sum of values x(e) for all edges e incident to v does not exceed 2. The size of x is the sum ∑e x(e). If {e ∈ EG|x(e) ≠ 0} contains no triangles then x is called triangle-free. Cornuéjols and Pulleyblank devised a combinatorial O(mn)-algorithm that finds a maximum triangle free 2-matching of size (hereinafter n ≔ |VG|, m ≔ |EG|) and also established a min-max theorem. We claim that this approach is, in fact, superfluous by demonstrating how these results may be obtained directly

APA, Harvard, Vancouver, ISO, and other styles

47

GREENHILL, CATHERINE, SVANTE JANSON, and ANDRZEJ RUCIŃSKI. "On the Number of Perfect Matchings in Random Lifts." Combinatorics, Probability and Computing 19, no. 5-6 (2010): 791–817. http://dx.doi.org/10.1017/s0963548309990654.

Full text

Abstract:

Let G be a fixed connected multigraph with no loops. A random n-lift of G is obtained by replacing each vertex of G by a set of n vertices (where these sets are pairwise disjoint) and replacing each edge by a randomly chosen perfect matching between the n-sets corresponding to the endpoints of the edge. Let XG be the number of perfect matchings in a random lift of G. We study the distribution of XG in the limit as n tends to infinity, using the small subgraph conditioning method.We present several results including an asymptotic formula for the expectation of XG when G is d-regular, d ≥ 3. The

APA, Harvard, Vancouver, ISO, and other styles

48

Molitierno, Jason J., and Michael Neumann. "On trees with perfect matchings." Linear Algebra and its Applications 362 (March 2003): 75–85. http://dx.doi.org/10.1016/s0024-3795(02)00454-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Gyárfás, A. "Perfect matchings in shadow colorings." Acta Mathematica Hungarica 161, no. 2 (2020): 397–400. http://dx.doi.org/10.1007/s10474-020-01031-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Cook, William, and André Rohe. "Computing Minimum-Weight Perfect Matchings." INFORMS Journal on Computing 11, no. 2 (1999): 138–48. http://dx.doi.org/10.1287/ijoc.11.2.138.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!