Let \(G\) be a \(2\)-connected graph with maximum degree \(\Delta(G) \geq d\), and let \(x\) and \(z\) be distinct vertices of \(G\). Let \(W\) be a subset of \(V(G) \setminus \{x, z\}\) such that \(|W| \leq d – 1\). Hirohata proved that if \(\max\{d_G(u), d_G(v)\} \geq d\) for every pair of vertices \(u, v \in V(G) \setminus \{x, z\} \cup W\) such that \(d_G(u, v) = 2\), then \(x\) and \(z\) are joined by a path of length at least \(d – |W|\). In this paper, we show that if \(G\) satisfies the conditions of Hirohata’s theorem, then for any given vertex \(y\) such that \(d_G(y) \geq d\), \(x\) and \(z\) are joined by a path of length at least \(d – |W|\) which contains \(y\).

For any positive integer \(k\), there exists a smallest positive integer \(N\), depending on \(k\), such that every \(2\)-coloring of \(1, 2, \ldots, N\) contains a monochromatic solution of the equation \(x + y + kz = 3w\). Based on computer checks, Robertson and Myers in \([5]\) conjectured values for \(N\) depending on the congruence class of \(k\) (mod \(9\)). In this note, we establish the values of \(N\) and find that in some cases they depend on the congruence class of \(k\) (mod \(27\)).

The support of a matrix \(M\) is the \((0, 1)\)-matrix with \(ij\)-th entry equal to \(1\) if the \(ij\)-th entry of \(M\) is non-zero, and equal to \(0\), otherwise. The digraph whose adjacency matrix is the support of \(M\) is said to be the digraph of \(M\). In this paper, we observe some general properties of digraphs of unitary matrices.

The \(k\)-restricted total domination number of a graph \(G\) is the smallest integer \(t_k\), such that given any subset \(U\) of \(k\) vertices of \(G\), there exists a total dominating set of \(G\) of cardinality at most \(t\), containing \(U\). Hence, the \(k\)-restricted total domination number of a graph \(G\) measures how many vertices are necessary to totally dominate a graph if an arbitrary set of \(k\) vertices are specified to be in the set. When \(k = 0\), the \(k\)-restricted total domination number is the total domination number. For \(1 \leq k \leq n\), we show that \(t_k \leq 4(n + k)/7\) for all connected graphs of order \(n\) and minimum degree at least two and we characterize the graphs achieving equality. These results extend earlier results of the author (J. Graph Theory \(35 (2000), 21-45)\). Using these results we show that if \(G\) is a connected graph of order \(n\) with the sum of the degrees of any two adjacent vertices at least four, then \(\gamma_t(G) \leq 4n/7\) unless \(G \in \{C_3, C_5, C_6, C_{10}\}\).

The Szeged index of a graph \(G\) is defined as \(\text{Sz}(G) = \sum_{e=uv \in E(G)} N_u(e|G) N_v(e|G)\), where \(N_u(e|G)\) is the number of vertices of \(G\) lying closer to \(u\) than to \(v\) and \(N_v(e|G)\) is the number of vertices of \(G\) lying closer to \(v\) than to \(u\). In this article, the Szeged index of some hexagonal systems applicable in nanostructures is computed.

In this paper, we consider the class of impartial combinatorial games for which the set of possible moves strictly decreases. Each game of this class can be considered as a domination game on a certain graph, called the move-graph. We analyze this equivalence for several families of combinatorial games, and introduce an interesting graph operation called iwin and match that preserves the Grundy value. We then study another game on graphs related to the dots and boxes game, and we propose a way to solve it.

Let \(C_n\) denote the cycle with \(n\) vertices, and \(C_n^{(t)}\) denote the graphs consisting of \(t\) copies of \(C_n\), with a vertex in common. Koh et al. conjectured that \(C_n^{(t)}\) is graceful if and only if \(nt \equiv 0,3 \pmod{4}\). The conjecture has been shown true for \(n = 3,5,6,7,9,11,4k\). In this paper, the conjecture is shown to be true for \(n = 13\).

This paper deals with a connection between the universal circuits matrix \([10]\) and the crossing relation \([1,5]\). The value of the universal circuits matrix obtained for \(\overline{\omega}\), where \(\omega\) is an arbitrary feedback function that generates de Bruijn sequences, forms the binary matrix that represents the crossing relation of \(\omega\). This result simplifies the design and study of the feedback functions that generate the de Bruijn sequences and allows us to decipher many inforrnations about the adjacency graphs of another feedback functions. For example, we apply these results to analyze the Hauge-Mykkeltveit classification of a family of de Bruijn sequences \([4]\).

A two-colored digraph \(D\) is primitive if there exist nonnegative integers \(h\) and \(k\) with \(h+k > 0\) such that for each pair \((i,j)\) of vertices there exists an \((h, k)\)-walk in \(D\) from \(i\) to \(j\). The exponent of the primitive two-colored digraph \(D\) is the minimum value of \(h + k\) taken over all such \(h\) and \(k\). In this paper, we consider the exponents of families of two-colored digraphs of order \(n\) obtained by coloring the digraph that has the exponent \((n – 1)^2\). We give the tight upper bound on the exponents, and the characterization of the extremal two-colored digraph.

A graceful labeling of a graph \(G\) with \(m\) edges is a function \(f: V(G) \to \{0, \ldots, m\}\) such that distinct vertices receive distinct numbers and \(\{|f(u) – f(v)|: uv \in E(G)\} = \{1, \ldots, m\}\). A graph is graceful if it has a graceful labeling. In \([1]\) this question was posed: “Is there an \(n\)-chromatic graceful graph for \(n \geq 6\)?”. In this paper it is shown that for any natural number \(n\), there exists a graceful graph \(G\) with \(\chi(G) = n\).

A connected graph \(G = (V, E)\) is said to be \((a, d)\)-antimagic, for some positive integers \(a\) and \(d\), if its edges admit a labeling by all the integers in the set \(\{1, 2, \ldots, |E(G)|\}\) such that the induced vertex labels, obtained by adding all the labels of the edges adjacent to each vertex, consist of an arithmetic progression with the first term \(a\) and the common difference \(d\). Mirka Miller and Martin Ba\'{e}a proved that the generalized Petersen graph \(P(n, 2)\) is \((\frac{3n+3}{2}, 3)\)-antimagic for \(n \equiv 0 \pmod{4}\), \(n \geq 8\) and conjectured that \(P(n, k)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n\) and \(2 \leq k \leq \frac{n}{2}-1\). The first author of this paper proved that \(P(n, 3)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for even \(n \geq 6\). In this paper, we show that the generalized Petersen graph \(P(n, 2)\) is \((\frac{3n+6}{2} , 3)\)-antimagic for \(n \equiv 2 \pmod{4}\), \(n \geq 10\).

Let \(0 \leq p \leq [\frac{r+1}{2}]\) and \(\sigma(K_{r+1}^{-p},n)\) be the smallest even integer such that each \(n\)-term graphic sequence with term sum at least \(\sigma(K_{r+1}^{-p},n)\) has a realization containing \(K_{r+1}^{-p}\) as a subgraph, where \(K_{r+1}^{-p}\) is a graph obtained from a complete graph \(K_{r+1}\) on \(r+1\) vertices by deleting \(p\) edges which form a matching. In this paper, we determine \(\sigma(K_{r+1}^{-p},n)\) for \(r \geq 2, 1 \leq p \leq [\frac{r+1}{2}]\) and \(n \geq 3r + 3\). As a corollary, we also determine \(\sigma(K_{1^*,2^t}n)\) for \(t \geq 1\) and \(n \geq 3s + 6t\), where \(K_{1^*,2^t}\) is an \(r_1\times r_2\times \ldots \times r_{s+t}\) complete \((s + t)\)-partite graph with \(r_1 = r_2 = \ldots = r_s = 1\) and \(r_{s+1} = r_{s+2} = \ldots = r_{s+t} = 2\) and \(\sigma(K_{1^*,2^t},n)\) is the smallest even integer such that each \(n\)-term graphic sequence with term sum at least \(\sigma(K_{1^*,2^t},n)\) has a realization containing \(K_{1^*,2^t}\) as a subgraph.

Let \(n, s_1\) and \(s_2\) be positive integers such that \(1 \leq s_1 \leq n/2, 1 \leq s_2 \leq n/2, s_1 \neq s_2\) and \(gcd(n, s_1, s_2) = 1\). An undirected double-loop network \(G(n;\pm s_1,\pm s_2)\) is a graph \((V, E)\), where \(V = \mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}\), and \(E = \{(i \to i+s_1 \mod n), (i\to i-s_1 \mod n), (i\to i+s_2 \mod n), (i\to i-s_2 \mod n) | i = 0, 1, 2, \ldots, n-1\}\). In this paper, a diameter formula is given for an undirected double-loop network \(G(n; \pm s_1, \pm s_2)\). As its application, two new optimal families of undirected double-loop networks are presented.

Anthony J. Macula constructed a \(d\)-disjunct matrix \(\delta(n,d,k)\) in \([1]\), and we now know it is determined by one type of pooling space. In this paper, we give some properties of \(\delta(n,d,k)\) and its complement \(\delta^c(n,d,k)\).

Let \(S\) be a primitive non-powerful signed digraph. The base \(l(S)\) of \(S\) is the smallest positive integer \(l\) such that for all ordered pairs of vertices \(i\) and \(j\) (not necessarily distinct), there exists a pair of \(SSSD\) walks of length \(t\) from \(i\) to \(j\) for each integer \(t \geq l\). In this work, we use \(PNSSD\) to denote the class of all primitive non-powerful signed symmetric digraphs of order \(n\) with at least one loop. Let \(l(n)\) be the largest value of \(l(S)\) for \(S \in\) \(PNSSD\), and \(L(n) = \{l(S) | S \in PNSSD\}\). For \(n \geq 3\), we show \(L(n) = \{2, 3, \ldots, 2n\}\). Further, we characterize all primitive non-powerful signed symmetric digraphs of order \(n\) with at least one loop whose bases attain \(l(n)\).

For a graph \(G = (V, E)\) and a binary labeling \(f : V(G) \to \mathbb{Z}_2\), let \(v_f(i) = |f^{-1}(1)|\). The labeling \(f\) is said to be friendly if \(|v_f(1) – v_f(0)| \leq 1\). Any vertex labeling \(f : V(G) \to \mathbb{Z}_2\) induces an edge labeling \(f^* : E(G) \to \mathbb{Z}_2\) defined by \(f^*(xy) =| f(x) – f(y)|\). Let \(e_f(i) = |f^{*-1}(i)|\). The friendly index set of the graph \(G\), denoted by \(FI(G)\), is defined by

\[FI(G) = \{|e_f(1) – e_f(0)| : f \text{ is a friendly vertex labeling of } G\}.\]

In \([15]\) Lee and Ng conjectured that the friendly index sets of trees will form an arithmetic progression. This conjecture has been mentioned in \([17]\) and other manuscripts. In this paper, we will first determine the friendly index sets of certain caterpillars of diameter four. Then we will disprove the conjecture by presenting an infinite number of trees whose friendly index sets do not form an arithmetic progression.

Let \(S\) be a primitive non-powerful signed digraph of order \(n\). The base of a vertex \(u\), denoted by \(l_S(u)\), is the smallest positive integer \(l\) such that there is a pair of SSSD walks of length \(i\) from \(u\) to each vertex \(v \in V(S)\) for any integer \(t \geq l\). We choose to order the vertices of \(S\) in such a way that \(l_S(1) \leq l_S(2) \leq \ldots \leq l_S(n)\), and call \(l_S(k)\) the \(k\)th local base of \(S\) for \(1 \leq k \leq n\). In this work, we use PNSSD to denote the class of all primitive non-powerful signed symmetric digraphs of order \(n\) with at least one loop. Let \(l(k)\) be the largest value of \(l_S(k)\) for \(S \in\) PNSSD, and \(L(k) = \{l_S(k) | S \in PNSSD\}\). For \(n \geq 3\) and \(1 \leq k \leq n-1\), we show \(I(k) = 2n – 1\) and \(L(k) = \{2, 3, \ldots, 2n-1\}\). Further, we characterize all primitive non-powerful signed symmetric digraphs whose \(k\)th local bases attain \(I(k)\).

Let \(\mathcal{U}_n(k)\) denote the set of all unicyclic graphs on \(n\) vertices with \(k\) (\(k \geq 1\)) pendant vertices. Let \(\diamondsuit_4^k\) be the graph on \(n\) vertices obtained from \(C_4\) by attaching \(k\) paths of almost equal lengths at the same vertex. In this paper, we prove that \(\diamondsuit_4^k\) is the unique graph with the largest Laplacian spectral radius among all the graphs in \(\mathcal{U}_n(k)\), when \(n \geq k + 4\).

For graphs \(G_1, G_2, \ldots, G_m\), the Ramsey number \(R(G_1, G_2, \ldots, G_m)\) is defined to be the smallest integer \(n\) such that any \(m\)-coloring of the edges of the complete graph \(K_n\) must include a monochromatic \(G_i\) in color \(i\), for some \(i\). In this note, we establish several lower and upper bounds for some Ramsey numbers involving quadrilateral \(C_4\), including:\(R(C_4, K_9) \leq 32,
19 \leq R(C_4, C_4, K_4)\leq 22, 31 \leq R(C_4, C_4, C_4, K_4) \leq 50, 52 \leq R(C_4, K_4, K_4) \leq 72, 42 \leq R(C_4, C_4, K_3, K_5) \leq 76, 87\leq R(C_4, C_4, K_4, K_4) \leq 179.\)

We consider the problem of determining the \(Q\)-integral graphs, i.e., the graphs with integral signless Laplacian spectrum. First, we determine some infinite series of such graphs having the other two spectra (the usual one and the Laplacian) integral. We also completely determine all \((2, s)\)-semiregular bipartite graphs with integral signless Laplacian spectrum. Finally, we give some results concerning \((3, 4)\) and \((3, 5)\)-semiregular bipartite graphs with the same property.

Let \(G\) be a connected graph. For any two vertices \(u\) and \(v\), let \(d(u, v)\) denote the distance between \(u\) and \(v\) in \(G\). The maximum distance between any pair of vertices is called the diameter of \(G\) and denoted by \(diam(G)\). A radio-labeling (or multi-level distance labeling) with span \(k\) for \(G\) is a function \(f\) that assigns to each vertex a label from the set \(\{0, 1, 2, \ldots, k\}\) such that the following holds for any vertices \(u\) and \(v\): \(|f(u) – f(v)| \geq diam(G) – d(u, v) + 1\). The radio number of \(G\) is the minimum span over all radio-labelings of \(G\). The square of \(G\) is a graph constructed from \(G\) by adding edges between vertices of distance two apart in \(G\). In this article, we completely determine the radio number for the square of any path.

Let \(G\) be a simple connected graph containing a perfect matching. \(G\) is said to be BM-extendable if every matching \(M\) whose induced subgraph is a bipartite graph extends to a perfect matching of \(G\). In this paper, for recognizing BM-extendable graphs, we present some conditions in terms of vertex degrees, including the degree sum conditions, the minimum degree conditions, and the Fan-type condition. Furthermore, we show that all these conditions are best possible in some sense.

Let \(u\) be an odd vertex of a bipartite graph \(B\) and suppose that \(f : V(B) \to \mathbb{N}\) is a function such that \(f(u) = \left\lceil d_B(u)/2 \right\rceil\) and \(f(v) = \left\lceil d_B(v)/2 \right\rceil + 1\) for \(v \in V(B) \setminus u\), where \(d_B(v)\) is the degree of \(v\) in \(B\). In this paper, we prove that \(B\) is \(f\)-choosable.

An arc-colored digraph \(D\) is called alternating whenever \(\{(u, v), (v, w)\} \subseteq A(D)\) implies that the color assigned to \((u, v)\) is different from the color of \((v, w)\). In arc-colored digraphs, a set of vertices \(N\) is said to be a kernel by alternating paths whenever it is an independent and dominating set by alternating directed paths (there is no alternating directed path between every pair of its vertices and for every vertex not in \(N\), there exists an alternating path from it to some vertex in \(N\)). With this new concept, we generalize the concept of kernel in digraphs. In this paper, we prove the existence of alternating kernels in possibly infinite arc-colored digraphs with some coloration properties. We also state a bilateral relation between the property of every induced subdigraph of an arc-colored digraph \(D\) of having a kernel by alternating paths and the property of every induced subdigraph of the non-colored digraph \(D\) of having a kernel, with this we enounce several sufficient conditions for \(D\) to have an alternating kernel. Previous results on kernels are generalized.

In this paper, we present a new simple linear-time algorithm for determining the number of spanning trees in the class of complement reducible graphs, also known as cographs. For a cograph \(G\) on \(n\) vertices and \(m\) edges, our algorithm computes the number of spanning trees of \(G\) in \(O(n + m)\) time and space, where the complexity of arithmetic operations is measured under the uniform cost criterion. The algorithm takes advantage of the cotree of the input cograph \(G\) and works by contracting it in a bottom-up fashion until it becomes a single node. Then, the number of spanning trees of \(G\) is computed as the product of a collection of values which are associated with the vertices of \(G\) and are updated during the contraction process. The correctness of our algorithm is established through the Kirchhoff matrix tree theorem, and also relies on structural and algorithmic properties of the class of cographs. We also extend our results to a proper superclass of cographs, namely the \(P_4\)-reducible graphs, and show that the problem of finding the number of spanning trees of a \(P_4\)-reducible graph has a linear-time solution.

This paper extends the concept of paving from finite matroids to matroids of arbitrary cardinality. Afterwards, a paving matroid of arbitrary cardinality is characterized in terms of its collection of closed sets, independent sets, and circuits, respectively.

A Hamiltonian walk in a connected graph \(G\) is a closed walk of minimum length which contains every vertex of \(G\). The Hamiltonian number \(h(G)\) of a connected graph \(G\) is the length of a Hamiltonian walk in \(G\). Let \(\mathcal{G}(n)\) be the set of all connected graphs of order \(n\), \(\mathcal{G}(n, \kappa = k)\) be the set of all graphs in \(\mathcal{G}(n)\) having connectivity \(\kappa = k\), and \(h(n,k) = \{h(G) : G \in \mathcal{G}(n, \kappa = k)\}\). We prove in this paper that for any pair of integers \(n\) and \(k\) with \(1 \leq k \leq n – 1\), there exist positive integers \(a := \min(h;n,k)) = \min\{h(G) : G \in \mathcal{G}(n, \kappa = k)\}\) and \(b := \max(h;n,k)) = \max\{h(G) : G \in \mathcal{G}(n, \kappa = k)\}\) such that \((h;n,k) = \{x \in \mathbb{Z} : a \leq x \leq b\}\). The values of \(\min(h;n,k))\) and \(\max(h(n,k))\) are obtained in all situations.

A well-known result on matchings of graphs is that the intersection of all maximal barriers is equal to the “set A” in the Gallai-Edmonds decomposition. In this paper, we give a generalization of this result to the framework of path-matchings introduced by Cunningham and Geelen. Furthermore, we present a sufficient condition for a graph to have a perfect path-matching.

This paper describes some new methods of constructing rectangular designs from balanced incomplete block (BIB) designs and Hadamard matrices. At the end of the paper, a table of rectangular designs in the range of \(r\),\(k \leq 15\) is given.

An \(n \times n\) sign pattern \(A\) is a spectrally arbitrary pattern if for any given real monic polynomial \(f(x)\) of degree \(n\), there is a real matrix \(B \in Q(A)\) having characteristic polynomial \(f(x)\). In this paper, we give two new classes of \(n \times n\) spectrally arbitrary sign patterns which are generalizations of the pattern \(W_{n}(k)\) defined in [T. Britz, J.J. McDonald, D.D. Olesky, P. van den Driessche, Minimal spectrally arbitrary sign patterns, SIAM Journal on Matrix Analysis and Applications, \(26(2004), 257-271]\).

We show that the power subgroups \(M^{6k}\) (\(k > 1\)) of the Modular group \(M = \text{PSL}(2, \mathbb{Z})\) are subgroups of the groups \(M'(6k, 6k)\). Here, the groups \(M'(6k, 6k)\) (\(k > 1\)) are subgroups of the commutator subgroup \(M’\) of \(M\) of index \(36k^2\) in \(M’\).

Let \(G\) be a simple graph. The double vertex graph \(U_2(G)\) of \(G\) is the graph whose vertex set consists of all \(2\)-subsets of \(V(G)\) such that two distinct vertices \(\{x,y\}\) and \(\{u,v\}\) are adjacent if and only if \(|\{x,y\} \cap \{u,v\}| = 1\) and if \(x = u\), then \(y\) and \(v\) are adjacent in \(G\). In this paper, we consider the exponents and primitivity relationships between a simple graph and its double vertex graph. A sharp upper bound on exponents of double vertex graphs of primitive simple graphs and the characterization of extremal graphs are obtained.

Let \(S_n\) be the set of permutations on \(\{1, \ldots, n\}\) and \(\pi \in S_n\). Let \(d(\pi)\) be the arithmetic average of \(\{|i – \pi(i)| : 1 \leq i \leq n\}\). Then \(d(\pi)/n \in [0, 1/2]\), the expected value of \(d(\pi)/n\) approaches \(1/3\) as \(n\) approaches infinity, and \(d(\pi)/n\) is close to \(1/3\) for most permutations. We describe all permutations \(\pi\) with maximal \(d(\pi)\).

Let \(s^+(\pi)\) and \(s^*(\pi)\) be the arithmetic and geometric averages of \(\{|\pi(i) – \pi(i + 1)| : 1 \leq i 1\). We describe all permutations \(\pi\),\(\sigma\) with maximal \(s^+(\pi)\) and \(s^*(\sigma)\).

A connected graph \(G = (V,E)\) is said to be \((a,d)\)-antimagic, for some positive integers \(a\) and \(d\), if its edges admit a labeling by all the integers in the set \(\{1, 2, \ldots, |E(G)|\}\) such that the induced vertex labels, obtained by adding all the labels of the edges adjacent to each vertex, consist of an arithmetic progression with the first term \(a\) and the common difference \(d\). Mirka Miller and Martin Bača proved that the generalized Petersen graph \(P(n,2)\) is \((\frac{3n+6}{2}, 3)\)-antimagic for \(n \equiv 0 \pmod{4}\), \(n \geq 8\), and conjectured that \(P(n, k)\) is \((\frac{5n+5}{2}, 2)\)-antimagic for odd \(n\) and \(2 \leq k \leq \frac{n}{2}-1\). In this paper, we show that the generalized Petersen graph \(P(n,2)\) is \((\frac{5n+5}{2}, 2)\)-antimagic for \(n \equiv 3 \pmod{4}\), \(n \geq 7\).

Sierpiński graphs \(S(n,k)\), \(n, k \in \mathbb{N}\), can be interpreted as graphs of a variant of the Tower of Hanoi with \(k \geq 3\) pegs and \(n \geq 1\) discs. In particular, it has been proved that for \(k = 3\) the graphs \(S(n, 3)\) are isomorphic to the Hanoi graphs \(H_3^n\). In this paper, we will determine the chromatic number, the diameter, the eccentricity of a vertex, the radius, and the centre of \(S(n,k)\). Moreover, we will derive an important invariant and a number-theoretical characterization of \(S(n,k)\). By means of these results, we will determine the complexity of Problem \(1\), that is, the complexity of getting from an arbitrary vertex \(v \in S(n,k)\) to the nearest and to the most distant extreme vertex. For the Hanoi graphs \(H_3^n\), some of these results are new.

In this paper, we will prove that there exist no \([n,k,d]_q\) codes of \(sq^{k-1}-(s+t)q^{k-2}-q^{k-4} \leq d \leq sq^{k-1}-(s+t)q^{k-2}\) attaining the Griesmer bound with \(k \geq 4, 1 \leq s \leq k-2, t \geq 1\), and \(s+t \leq (q+1)\backslash 2\). Furthermore, we will prove that there exist no \([n,k,d]_q\) codes for \(sq^{k-1}-(s+t)q^{k-2}-q^{k-3} \leq d \leq s\) attaining the Griesmer bound with \(k \geq 3\), \(1 \leq s \leq k-2\), \(t \geq 1\), and \(s+t \leq \sqrt{q}-1\). The results generalize the nonexistence theorems of Tatsuya Maruta (see \([7]\)) and Andreas Klein (see \([4]\)) to a larger class of codes.

Let \(G = (V(G), E(G))\) be a nonempty graph (may have parallel edges). The line graph \(L(G)\) of \(G\) is the graph with \(V(L(G)) = E(G)\), and in which two vertices \(e\) and \(e’\) are joined by an edge if and only if they have a common vertex in \(G\). We call the complement of \(L(G)\) as the jump graph. In this note, we give a simple sufficient and necessary condition for a jump graph to have a perfect matching.