Results 11 to 20 of about 67,442 (263)
On Eccentric Adjacency Index of Graphs and Trees [PDF]
Mathematics Interdisciplinary Research, 2023 Let $G=(V(G),E(G))$ be a simple and connected graph. The distance between any two vertices $x$ and $y$, denoted by $d_G(x,y)$, is defined as the length of a shortest path connecting $x$ and $y$ in $G$.The degree of a vertex $x$ in $G$, denoted by $\deg_G(
Reza Sharafdini +3 more
doaj +1 more source
Formalizing Randomized Matching Algorithms [PDF]
Logical Methods in Computer Science, 2012 Using Je\v{r}\'abek 's framework for probabilistic reasoning, we formalize the correctness of two fundamental RNC^2 algorithms for bipartite perfect matching within the theory VPV for polytime reasoning.
Dai Tri Man Le, Stephen A. Cook
doaj +1 more source
Polynomial reconstruction of the matching polynomial
Electronic Journal of Graph Theory and Applications, 2015 The matching polynomial of a graph is the generating function of the numbers of its matchings with respect to their cardinality. A graph polynomial is polynomial reconstructible, if its value for a graph can be determined from its values for the vertex ...
Xueliang Li, Yongtang Shi, Martin Trinks
doaj +1 more source
Extremal Values of Variable Sum Exdeg Index for Conjugated Bicyclic Graphs
Journal of Chemistry, 2021 A connected graph GV,E in which the number of edges is one more than its number of vertices is called a bicyclic graph. A perfect matching of a graph is a matching in which every vertex of the graph is incident to exactly one edge of the matching set ...
Muhammad Rizwan +3 more
doaj +1 more source
Eigenvalues and perfect matchings [PDF]
Linear Algebra and its Applications, 2005 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Brouwer, A.E., Haemers, W.H.
openaire +3 more sources
Fractional matching preclusion for butterfly derived networks
Theory and Applications of Graphs, 2019 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.
Xia Wang +4 more
doaj +1 more source
Planar cycle-extendable graphs [PDF]
Discrete Mathematics & Theoretical Computer ScienceFor most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs - that is, connected nontrivial graphs with the property that each edge belongs to some perfect matching.
Aditya Y Dalwadi +3 more
doaj +1 more source
Multi-path Summation for Decoding 2D Topological Codes [PDF]
Quantum, 2018 Fault tolerance is a prerequisite for scalable quantum computing. Architectures based on 2D topological codes are effective for near-term implementations of fault tolerance.
Ben Criger, Imran Ashraf
doaj +1 more source
Low Weight Perfect Matchings [PDF]
The Electronic Journal of Combinatorics, 2020 Answering a question posed by Caro, Hansberg, Lauri, and Zarb, we show that for every positive integer $n$ and every function $\sigma\colon E(K_{4n})\to\{-1,1\}$ with $\sigma\left(E(K_{4n})\right)=0$, there is a perfect matching $M$ in $K_{4n}$with $\sigma(M)=0$.
Stefan Ehard +2 more
openaire +3 more sources
Characterization of perfect matching transitive graphs
Electronic Journal of Graph Theory and Applications, 2018 A graph G is perfect matching transitive, shortly PM-transitive, if for any two perfect matchings M and N of G, there is an automorphism f : V(G) ↦ V(G) such that fe(M) = N, where fe(uv) = f(u)f(v). In this paper, the author proposed the definition of PM-
Ju Zhou
doaj +1 more source