Narrow Results

In this paper, we generalize virtual knot theory to multi-virtual knot theory where there are a multiplicity of virtual crossings. Each virtual crossing type can detour over the other virtual crossing types, and over classical or immersed crossings. New invariants of multi-virtual knots and links are introduced and new problems that arise are described. We show how the extensions of the Penrose coloring evaluation for trivalent plane graphs and our generalizations of this to non-planar graphs and arbitrary numbers of colors acts as a motivation for the construction of the multi-virtual theory.

Counting maximum matchings in a graph is of great interest in statistical mechanics, solid-state chemistry, theoretical computer science, mathematics, among other disciplines. However, it is a challengeable problem to explicitly determine the number of maximum matchings of general graphs. In this paper, using Gallai–Edmonds structure theorem, we derive a computing formula for the number of maximum matchings in a graph. According to the formula, we obtain an algorithm to enumerate maximum matchings of a graph. In particular, the formula implies that computing the number of maximum matchings of a graph is converted to computing the number of perfect matchings of some induced subgraphs of the graph.

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.

In this paper we consider the computational complexity of deciding the existence of a perfect matching in certain classes of dense k-uniform hypergraphs. It has been known that the perfect matching problem for the classes of hypergraphs H with minimum ((k - 1)–wise) vertex degreeδ(H) at least c|V(H)| is NP-complete for and trivial for c ≥ ½, leaving the status of the problem with c in the interval widely open. In this paper we show, somehow surprisingly, that ½ is not the threshold for tractability of the perfect matching problem, and prove the existence of an ε > 0 such that the perfect matching problem for the class of hypergraphs H with δ(H) ≥ (½ - ε)|V(H)| is solvable in polynomial time. This seems to be the first polynomial time algorithm for the perfect matching problem on hypergraphs for which the existence problem is nontrivial. In addition, we consider parallel complexity of the problem, which could be also of independent interest.

We bring into attention the interplay between model theory of committed graphs (1-regular graphs) and their palindromic characteristic in the domain of formal languages. We prove some model theoretic properties of committed graphs and then give a characterization of them in the formal language domain using palindromes. We show in the first part of the paper that the theory of committed graphs and the theory of infinite committed graphs differ in terms of completeness. We give the observation that theories of finite and infinite committed graphs are both decidable. The former is finitely axiomatizable, whereas the latter is not. We note that every committed graph is isomorphic to the structure of integers. In the second part, as our main focus of the paper and using some of the results in the first section, we give a characterization of committed graphs based on the notion of finite and infinite palindrome strings.

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 this paper, we find the matching preclusion number and the conditional matching preclusion number with the classification of the optimal sets for the class of crossed cubes, an important variant of the class of hypercubes. Indeed, we will establish more general results on the matching preclusion and the conditional matching preclusion problems for a larger class of interconnection networks.

In this paper, we prove that the wrapped Butterfly graph WBF(d,n) of degree d and dimension n is decomposable into Hamilton cycles. This answers a conjecture of Barth and Raspaud who solved the case d = 2.

We present au intuitive and simple O(log² n log Φ) time, O(n² 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.

This paper presents an algorithm to construct a weighted adjacency matrix of a plane bipartite graph obtained from a pretzel knot diagram. The determinant of this matrix after evaluation is shown to be the Jones polynomial of the pretzel knot by way of perfect matchings (or dimers) of this graph. The weights are Tutte's activity letters that arise because the Jones polynomial is a specialization of the signed version of the Tutte polynomial. The relationship is formalized between the familiar spanning tree setting for the Tait graph and the perfect matchings of the plane bipartite graph above. Evaluations of these activity words are related to the chain complex for the Champanerkar–Kofman spanning tree model of reduced Khovanov homology.

Simplicial complexes are a popular tool used to model higher-order interactions between elements of complex social and biological systems. In this paper, we study some combinatorial aspects of a class of simplicial complexes created by a graph product, which is an extension of the pseudo-fractal scale-free web. We determine explicitly the independence number, the domination number, and the chromatic number. Moreover, we derive closed-form expressions for the number of acyclic orientations, the number of root-connected acyclic orientations, the number of spanning trees, as well as the number of perfect matchings for some particular cases.

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 this paper, we find this number and classify all optimal sets for the augmented cubes, a class of networks designed as an improvement of the hypercubes.

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.¹⁵ 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 K₂ (an edge) to obtain the corresponding results for split-stars.

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.

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 matching preclusion sets of these graphs.

The matching preclusion number of graph G is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching or almost-perfect matching. The strong matching preclusion number of a graph G is the minimum number of vertices and edges whose deletion leaves the resulting graph without a perfect matching or an almost-perfect matching. The conditional matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph with no isolated vertices and without a perfect matching or almost-perfect matching. In this paper, we study the matching preclusion number of radix triangular mesh with an odd number of vertices, and strong matching preclusion number and conditional matching preclusion number of radix triangular mesh. Also, we obtained the radix triangular mesh with an even number of vertices is super strongly matched and conditionally super matched.

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.

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 CF_n is $\frac{3n-3}{2}\left(\frac{3n-3}{2}\right)$ for odd n and $\frac{3n-4}{2}\left(\frac{3n-4}{2}\right)$ for even n; (2) CF_n is super edge-connected; (3) the matching preclusion number of CF_n is $\frac{3n-3}{2}$ for odd n and $\frac{3n-4}{2}$ for even n; (4) the conditional matching preclusion number of CF_n is 3n – 5 for odd n and n ≥ 3, and 3n – 6 for even n and n ≥ 4.

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 denoted by EPM(n). In this paper, we prove that the matching preclusion number of EPM(n) is 9 where n ≥ 4.

For a group G and a non-empty subset Ω of G, the commuting graph $\mathcal{C}(G,\Omega )$ of Ω is a graph whose vertex set is Ω and any two vertices are adjacent if and only if they commute in G. Define $T_{4n}=⟨a,b\mid a^{2n}=b^4=1,a^n=b^2,b^{-1}ab=a^{-1}⟩$, the dicyclic group of order $4n$ $(n\ge 3)$, which is also known as the generalized quaternion group. We mainly investigate the properties and metric dimension of the commuting graphs on the dicyclic group $T_{4n}$.

Lovász and Plummer conjectured that: for k ≥ 3 there exist constants c₁(k) > 1 and c₂(k) > 0 such that every k-regular elementary graph on 2n vertices, without forbidden edges, contains at least c₂(k)⋅c₁(k)ⁿ perfect matchings. Furthermore c₁(k) → ∞ as k → ∞. In this paper, for some Cartesian products of graphs, we obtain a lower bound of their number of perfect matchings which is similar to that of Lovász and Plummer's conjecture. Furthermore, we compute the genus of some Cartesian products of graphs.