Search

A graph is called K1,p-restricted (p ≥ 3) if for every vertex of the graph there are at least p − 2 edges between any p of its neighbours. We establish sufficient conditions for the existence of a perfect matching in K1,p-restricted graphs in terms of their connectivity and vertex degrees. These conditions imply, in particular, the classical Petersen’s result: any 2-edge-connected 3-regular graph contains a perfect matching.

Let G be an undirected bipartite graph with positive integer weights on the edges. We refine the existing decomposition theorem originally proposed by Kao et al., for computing maximum weight bipartite matching. We apply it to design an efficient version of the decomposition algorithm to compute the weight of a maximum weight bipartite matching of G in O(\sqrt{|V|}W'/k(|V|,W'/N))-time by employing an algorithm designed by Feder and Motwani as a subroutine, where |V| and N denote the number of nodes and the maximum edge weight of G, respectively and k(x,y)=log(x) /log(x^2/y). The parameter W' is smaller than the total edge weight W, essentially when the largest edge weight differs by more than one from the second-largest edge weight in the current working graph in any decomposition step of the algorithm. In best the case, W'=O(|E|) where |E| is the number of edges of G and in the worst case, W'=W, that is, |E| \leq W' \leq W. In addition, we talk about a scaling property of the algorithm and research a better bound of the parameter W'. Experimental evaluations of randomly generated data show that the proposed improvement is significant in general.

Graph matching is a fundamental problem in theoretical computer science and artificial intelligence, and lays the foundation for many computer vision and machine learning tasks. Approximate algorithms are necessary for graph matching due to its NP-complete nature. Inspired by the usage in network-related tasks, random walk is generalized to graph matching as a type of approximate algorithm. However, it may be inappropriate for the previous random walk-based graph matching algorithms to utilize continuous techniques without considering the discrete property. In this paper, we propose a novel random walk-based graph matching algorithm by incorporating both continuous and discrete constraints in the optimization process. Specifically, after interpreting graph matching by random walk, the continuous constraints are directly embedded in the random walk constraint in each iteration. Further, both the assignment matrix (vector) and the pairwise similarity measure between graphs are iteratively updated according the discrete constraints, which automatically leads the continuous solution to the discrete domain. Comparisons on both synthetic and real-world data demonstrate the effectiveness of the proposed algorithm.

A graph is called K1,p-restricted (p ≥ 3) if for every vertex of the graph there are at least p - 2 edges between any p neighbours of the vertex. In this article, new sufficient conditions for existence of a perfect matching in K1,p-restricted graphs are established. In particular, J. Petersen’s classical result that every 2-edge connected 3-regular graph contains a perfect matching follows from these conditions.

Komlos [Tiling Turan theorems, Combinatorica, 20,2 (2000), 203{218] determined the asymptotically optimal minimum degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph. We show that the minimum degree condition can be relaxed in the sense that we require only a given fraction of vertices to have the prescribed degree., Comment: 13 pages, 1 figure, accepted to the European Journal of Combinatorics

The classical Dirac theorem asserts that every graph G on n ≥ 3 vertices with minimum degree δ ( G ) ≥ ⌈ n ∕ 2 ⌉ is Hamiltonian. The lower bound of ⌈ n ∕ 2 ⌉ on the minimum degree of a graph is tight. In this paper, we extend the classical Dirac theorem to the case where δ ( G ) ≥ ⌊ n ∕ 2 ⌋ by identifying the only non-Hamiltonian graph families in this case. We first present a short and simple proof. We then provide an alternative proof that is constructive and self-contained. Consequently, we provide a polynomial-time algorithm that constructs a Hamiltonian cycle, if exists, of a graph G with δ ( G ) ≥ ⌊ n ∕ 2 ⌋ , or determines that the graph is non-Hamiltonian. Finally, we present a self-contained proof for our algorithm which provides insight into the structure of Hamiltonian cycles when δ ( G ) ≥ ⌊ n ∕ 2 ⌋ and is promising for extending the results of this paper to the cases with smaller degree bounds.

Graph matching aims at establishing correspondences between graph elements, and is widely used in many computer vision tasks. Among recently proposed graph matching algorithms, those utilizing the path following strategy have attracted special research attentions due to their exhibition of state-of-the-art performances. However, the paths computed in these algorithms often contain singular points, which could hurt the matching performance if not dealt properly. To deal with this issue, we propose a novel path following strategy, named branching path following (BPF), to improve graph matching accuracy. In particular, we first propose a singular point detector by solving a KKT system, and then design a branch switching method to seek for better paths at singular points. Moreover, to reduce the computational burden of the BPF strategy, an adaptive path estimation (APE) strategy is integrated into BPF to accelerate the convergence of searching along each path. A new graph matching algorithm named ABPF-G is developed by applying APE and BPF to a recently proposed path following algorithm named GNCCP (Liu & Qiao 2014). Experimental results reveal how our approach consistently outperforms state-of-the-art algorithms for graph matching on five public benchmark datasets.

Correspondence problems are challenging due to the complexity of real-world scenes. One way to solve this problem is to improve the graph matching (GM) process, which is flexible for matching non-rigid objects. GM can be classified into three categories that correspond with the variety of object functions: first-order, second-order, and high-order matching. Graph and hypergraph matching have been proposed separately in previous works. The former is equivalent to the second-order GM, and the latter is equivalent to high-order GM, but we use the terms second- and high-order GM to unify the terminology in this paper. Second- and high-order GM fit well with different types of problems; the key goal for these processes is to find better-optimized algorithms. Because the optimal problems for second- and high-order GM are different, we propose two novel optimized algorithms for them in this paper. (1) For the second-order GM, we first introduce a $K$ -nearest-neighbor-pooling matching method that integrates feature pooling into GM and reduces the complexity. Meanwhile, we evaluate each matching candidate using discriminative weights on its $k$ -nearest neighbors by taking locality as well as sparsity into consideration. (2) High-order GM introduces numerous outliers, because precision is rarely considered in related methods. Therefore, we propose a sub-pattern structure to construct a robust high-order GM method that better integrates geometric information. To narrow the search space and solve the optimization problem, a new prior strategy and a cell-algorithm-based Markov Chain Monte Carlo framework are proposed. In addition, experiments demonstrate the robustness and improvements of these algorithms with respect to matching accuracy compared with other state-of-the-art algorithms.

Recently, people, devices, processes, and other entities have been more connected than at any other point in history. In general, a graph is a natural, neat, and flexible structure to model the complex relationships, interactions, and interdependencies between objects (Fig. 4.1). In particular, each graph consists of nodes (or vertices) that represent objects and edges (or links) that represent the relationships among the graph nodes. Graphs have been widely used to represent datasets in a wide range of application domains such as social science, astronomy, computational biology, telecommunications, computer networks, semantic Web, protein networks, and many others (Sakr and Pardede, Graph Data Management: Techniques and Applications, 2011 [73]).

The Turan number ex ( n , H ) is the maximum number of edges in a graph on n vertices which does not contain H as a subgraph. Gorgol gives a lower bound for ex ( n , H ) when H is the disjoint union of k copies of P 3 and conjectures this bound is tight. In this paper, we give an algorithmic proof of Gorgol’s Conjecture.

A caterpillar is a connected graph such that the removal of all its vertices with degree 1 results in a path. Given a graph G , a caterpillar-packing of G is a set of vertex-disjoint (not necessarily induced) subgraphs of G such that each subgraph is a caterpillar. In this work we consider the set of caterpillar-packings of a graph, which corresponds to feasible solutions of the 2-schemes strip cutting problem with a sequencing constraint (2-SSCPsc) presented by F. Rinaldi and A. Franz in 2007. We study the polytope associated with a natural integer programming formulation of this problem. We explore basic properties of this polytope, including a lifting lemma and several facet-preserving operations on the graph. These results allow us to introduce several families of facet-inducing inequalities.

A spanning subgraph F of a graph G is called a { P 2 , C 2 i + 1 : i ≥ k } -factor if each component of F is isomorphic to either a path of order 2 or a cycle of order 2 i + 1 for some i ≥ k . In this paper, we obtain the following two results (here c i ( G − X ) is the number of components C of G − X with | V ( C ) | = i ): (i) If a graph G satisfies c 1 ( G − X ) + c 3 ( G − X ) ≤ 1 2 | X | for all X ⊆ V ( G ) , then G has a { P 2 , C 2 i + 1 : i ≥ 2 } -factor. (ii) For k ≥ 3 , if a graph G satisfies ∑ 0 ≤ j ≤ k − 1 c 2 j + 1 ( G − X ) ≤ 2 5 ( k 2 − 1 ) | X | for all X ⊆ V ( G ) , then G has a { P 2 , C 2 i + 1 : i ≥ k } -factor.

A graph G = ( V , E ) is weighted- k -antimagic if for each w : V → R , there is an injective function f : E → { 1 , … , | E | + k } such that the following sums are all distinct: for each vertex u , ∑ v : u v ∈ E f ( u v ) + w ( u ) . When such a function f exists, it is called a ( w , k ) -antimagic labeling of G . A connected graph G is antimagic if it has a ( w 0 , 0 ) -antimagic labeling, for w 0 ( u ) = 0 , for each u ∈ V . In this work, we prove that all the complete bipartite graphs K p , q , are weighted- 0 -antimagic when 2 ≤ p ≤ q and q ≥ 3 . Moreover, an algorithm is proposed that computes in polynomial time a ( w , 0 ) -antimagic labeling of the graph. Our result implies that if H is a complete partite graph, with H ≠ K 1 , q , K 2 , 2 , then any connected graph G containing H as a spanning subgraph is antimagic.

A strong edge coloring of a graph is a proper edge coloring in which every color class is an induced matching. The strong chromatic index $\chi_s'(G)$ of a graph $G$ is the minimum number of colors in a strong edge coloring of $G$. Let $\Delta \geq 4$ be an integer. In this note, we study the odd graphs and show the existence of some special walks. By using these results and Chang's ideas in [Discuss. Math. Graph Theory 34 (4) (2014) 723--733], we show that every planar graph with maximum degree at most $\Delta$ and girth at least $10 \Delta - 4$ has a strong edge coloring with $2\Delta - 1$ colors. In addition, we prove that if $G$ is a graph with girth at least $2\Delta - 1$ and mad$(G) < 2 + \frac{1}{3\Delta - 2}$, where $\Delta$ is the maximum degree and $\Delta \geq 4$, then $\chi_s'(G) \leq 2\Delta - 1$, if $G$ is a subcubic graph with girth at least $8$ and mad$(G) < 2 + \frac{2}{23}$, then $\chi_s'(G) \leq 5$., Comment: 7 pages

We first prove that for every vertex x of a 4-connected graph G there exists a subgraph H in G isomorphic to a subdivision of the complete graph K4 on four vertices such that G-V(H) is connected and contains x. This implies an affirmative answer to a question of W. Kuehnel whether every 4-connected graph G contains a subdivision H of K4 as a subgraph such that G-V(H) is connected. The motor for our induction is a result of Fontet and Martinov stating that every 4-connected graph can be reduced to a smaller one by contracting a single edge, unless the graph is the square of a cycle or the line graph of a cubic graph. It turns out that this is the only ingredience of the proof where 4-connectedness is used. We then generalize our result to connected graphs of minimum degree at least 4, by developing the respective motor: A structure theorem for the class of simple connected graphs of minimum degree at least 4.

Using a single commodity computational node to partition big graph is very difficult. This work studies how to partition a big graph with respect to arbitrary proportions in a streaming manner. To meet diverse requirements of big graph partitioning scenarios, we first devise 3 measurement schemes for measuring the graph vertex count, graph workload, and graph processing time, respectively. These schemes are the bases and prerequisites for big graph partitioning. Due to the difficulty in acquiring full big graph information, we then design 8 streaming heuristics to partitioning a big graph during the process of loading its data from external disks into memory. Each of these heuristics decides where to assign every vertex in the stream based on the information calculated by one of the above 3 schemes. At last, we demonstrate the performance and flexibility of our heuristics in partitioning real and synthetic graph datasets on a medium-sized cluster. The characteristics of arbitrary proportions of our approach makes it have a wide range of applications.

For a 2-connected cubic graph G, the perfect matching polytope P(G) of G contains a special point xc=(13,13,…,13)$x^c = \left( {{1 \over 3},{1 \over 3}, \ldots ,{1 \over 3}} \right)$ . The core index ϕ(P(G)) of the polytope P(G) is the minimum number of vertices of P(G) whose convex hull contains xc. The Fulkerson’s conjecture asserts that every 2-connected cubic graph G has six perfect matchings such that each edge appears in exactly two of them, namely, there are six vertices of P(G) such that xc is the convex combination of them, which implies that ϕ(P(G)) ≤ 6. It turns out that the latter assertion in turn implies the Fan-Raspaud conjecture: In every 2-connected cubic graph G, there are three perfect matchings M1, M2, and M3 such that M1 ∩ M2 ∩ M3 = ∅. In this paper we prove the Fan-Raspaud conjecture for ϕ(P(G)) ≤ 12 with certain dimensional conditions.

An independent set of a graph is a set of pairwise non-adjacent vertices. The independence polynomial of a graph is defined as a polynomial in which the coefficient is the number of the independent set in the graph. Meanwhile, a graph of a group G is called conjugate graph if the vertices are non-central elements of G and two distinct vertices are adjacent if they are conjugate. The noncommuting graph is defined as a graph whose vertex set is non-central elements in which two vertices are adjacent if and only if they do not commute. In this research, the independence polynomial of the conjugate graph and noncommuting graph are found for three nonabelian groups of order at most eight.

A matching M in a graph G is said to be extendable if there exists a perfect matching of G containing M . In 1989, it was shown that every connected planar graph with at least 8 vertices has a matching of size three which is not extendable. In contrast, the study of extending certain matchings of size three or more has made progress in the past decade when the given graph is 5 -connected planar triangulation or 5 -connected plane graphs with few non-triangular faces. In this paper, we prove that if G is a 5 -connected plane graph of even order in which at most two faces are not triangular and M is a matching of size four in which the edges lie pairwise distance at least three apart, then M is extendable. A related result concerning perfect matching with proscribed edges is shown as well.

In interconnection networks, matching preclusion is a measure of robustness when there is a link failure. Let G be a graph with an even number of vertices. The matching preclusion number of G is the minimum number of edges whose deletion leaves the resulting graph without a perfect matching, and the conditional matching preclusion number of G is the minimum number of edges whose deletion results in a graph with no isolated vertices and without a perfect matching. In this paper, we study these problems for undirected binary de Bruijn graph U B ( n ) . As an essential preparation, we obtain conditional edge-fault Hamiltonicity of binary de Bruijn graph B ( n ) . Then we obtain matching preclusion number and conditional matching preclusion number of U B ( n ) for n ⩾ 4 and classify all optimal matching preclusion sets and optimal conditional matching preclusion sets.

A sequence of vertices in a graph is called a (total) legal dominating sequence if every vertex in the sequence (totally) dominates at least one vertex not dominated by the ones that precedes it, and at the end all vertices of the graph are (totally) dominated. The Grundy (total) domination number of a graph is the size of the largest (total) legal dominating sequence. In this work, we present integer programming formulations for obtaining the Grundy (total) domination number of a graph, we study some aspects of the polyhedral structure of one of them and we test the performance of some new valid inequalities as cuts. Fil: Campêlo, Manoel. Universidade Federal Do Ceará; Brasil Fil: Severin, Daniel Esteban. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina

With the emerging of large scale complex networks, graph computation, such as community detection, meets new technology challenges of extremely large computational cost. In order to deal with these challenges, the parallelism is becoming necessary. Graph partition is a fundamental problem of parallel computing for big graph data. The challenges of graph partition include large numbers of communications between partitions, extreme replication of vertices, and unbalanced partition. In this paper, we propose a feasible graph partition framework for parallel computing of big graph. The framework is based on an objective optimization problem to reduce the bandwidth, memory and storage cost on condition that the load balance could be guaranteed. In this framework, three greedy graph partition algorithms are proposed. By running the algorithms on the different kinds of graphs, including real-world graphs and synthetic graphs, the experimental results show that our algorithms surpass the state of the art heuristic algorithms. For example, running time is reduced more than 21.56% and the communication cost is decreased by more than 17.90% for weighted graph. The adequate experiments verify that our algorithms are capable of solving the problem of graph partition with different needs.

A connected graph G is said to be a factor-critical graph if G −v has a perfect matching for every vertex v of G. In this paper, the 2-connected factor-critical graph G which has exactly |E(G)| + 1 maximum matchings is characterized.

This paper studies exact algorithms for the Maximum Induced Matching problem, in which an n-vertex graph is given and we are asked to find a set of maximum number of edges in the graph such that no pair of edges in the set have a common endpoint or are adjacent by another edge. This problem has applications in many different areas. We give several structural properties of the problem and show that the problem can be solved in O⁎(1.4231n) time and polynomial space or O⁎(1.3752n) time and exponential space.

A fullerene graph is a 3-connected cubic plane graph whose all faces are bounded by 5- or 6-cycles. In this paper, we show that a matching M of a fullerene graph can be extended to a perfect matching if the following hold: (i) three faces around each vertex in $$\{x,y:xy\in M\}$$ are bounded by 6-cycles and (ii) the edges in M lie at distance at least 13 pairwise.

A mixed graph is obtained by orienting some edges of G, where G is the underlying graph of . Let denote the Hermitian adjacency matrix of and m(G) be the matching number of G. The H-rank of , written as , is the rank of . Denoted by d(G) the dimension of cycle spaces of G, that is , where respectively, denotes the size, order and the number of connected components of G. In this paper, we concentrate on the relation between the H-rank of and the matching number of G. Firstly, it is proved that for every connected mixed graph . Secondly, the mixed graphs that attain the upper and lower bounds are characterized, respectively. By these obtained results in the current paper, as a unified approach, all those main results obtained in [Linear Algebra Appl. 465 (2015) 363–375; J. Inequal. Appl. 20 (2016) 71; Eur. J. Combin. 54 (2016) 76–86; Discrete Appl. Math. 215 (2016) 171–176] can be deduced consequently.

In this paper, we consider the k-Depots Hamiltonian Path Problem (k-DHPP) of searching k paths in a graph G, starting from k fixed vertices and spanning all the vertices of G. We propose an approximation algorithm for solving the k-DHPP, where the underlying graph is cubic and 2-vertex-connected. Then, we prove the existence of a 5 3 -approximation algorithm that gives a solution with total cost at most 5 3 n - 4 k - 2 3 . In this case, the proposed method is based upon searching for a perfect matching, constructing an Eulerian graph and finally a k paths solution, following the process of removing/adding edges. We also present an approximation algorithm for finding a shortest tour passing through all vertices in a factor-critical and 2-vertex connected graph. The proposed algorithm achieves a 7 6 -approximation ratio where the principle of the method is based on decomposing the graph into a series of ears.

Let d 1 , d 2 , … , d k be k non-negative integers. A graph G is ( d 1 , d 2 , … , d k ) -colorable, if the vertex set of G can be partitioned into subsets V 1 , V 2 , … , V k such that the subgraph G [ V i ] induced by V i has maximum degree at most d i for i = 1 , 2 , … , k . In this paper, we prove that every planar graph without cycles of length 4 or 9 is ( 1 , 1 , 0 ) -colorable.

In Constraint Programming, global constraints allow to model and solve many combinatorial problems. Among these constraints, three sortedness constraints have been proposed, which define interesting and not so easy graph matching problems. In this paper, we formulate one of these problems as a marriage scheduling problem, which is a special perfect matching problem in a bipartite graph. We show that the marriage scheduling problem is NP-complete, and we explain the relationships between this graph problem and the sortedness constraints. As a consequence, we deduce that the sort ( U , V ) constraint (Older et al., 1995), the sort ( U , V , P ) constraint (Zhou, 1996) and the recently introduced keysorting ( U , V , Keys , P ) constraint (Carlsson et al., 2014) are intractable (assuming P ≠ NP) for integer variables whose domains are not limited to intervals.

It is shown that any graph has a perfect matching if and only if a specially defined vector is the base of extended polymatroid associated with submodular function defined on subsets of vertex set. Based on this fact, different algorithms for testing flow feasibility can be used to find some perfect matching in a given graph.

We show that for any e > 0 , and any integer k ≥ 2 , there is a C 2 k -free graph G which does not contain a bipartite subgraph of girth greater than 2k with more than ( 1 − 1 2 2 k − 2 ) 2 2 k − 1 ( 1 + e ) fraction of the edges of G. Győri et al. showed that if c denotes the largest constant such that every C 6 -free graph G contains a bipartite subgraph which is C 4 -free having c fraction of edges of G, then 3 8 ≤ c ≤ 2 5 . Putting k = 3, our result implies that c = 3 8 . Our proof uses the following statement, which we prove using probabilistic ideas, generalizing a theorem of Erdős: For any e > 0 , and any integers a , b , k ≥ 2 , there exists an a-uniform hypergraph H of girth greater than k which does not contain any b-colorable subhypergraph with more than ( 1 − 1 b a − 1 ) ( 1 + e ) fraction of the hyperedges of H. Kuhn and Osthus showed that every bipartite C 2 l -free graph G contains a C 4 -free subgraph with at least 1 / ( l − 1 ) fraction of the edges of G. We give a new and simple proof of this result. In the same paper Kuhn and Osthus also showed that a C 2 l -free graph which is obtained by pasting together C 4 's has average degree at most 16l and asked whether there exists a number d = d ( l ) such that every C 2 l -free graph which is obtained by pasting together C 2 k 's has average degree at most d if l > k ≥ 3 are given integers. We answer this question negatively.

A set D ⊆ V ( G ) is a 2 -point set dominating set (2-psd set) of a graph G if for any subset S ⊆ V − D , there exists a non-empty subset T ⊆ D containing at most two vertices such that the induced subgraph 〈 S ∪ T 〉 is connected. In this paper we characterize minimal 2-psd sets for a general graph. Based on the structure we examine 2-psd sets in a separable graph and discuss the criterion for a 2-psd set to be minimal.

The subgraph of a 5-connected graph G induced by the set of degree 5 vertices is said to be the 5-subgraph of G. An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. We show that there are exact two graphs with order 5 which can be a component of the 5-subgraph of a contraction-critically 5-connected graph.

A coloring of the vertex set in a graph is called perfect if all its identically colored vertices have identical multisets of colors of their neighbors. Refer as the infinite circulant graph with continuous set of n distances to the Cayley graph of the group ℤ with generator set {1, 2,..., n}. We obtain a description of all perfect colorings with an arbitrary number of colors of this graph with distances 1 and 2. In 2015, there was made a conjecture characterizing perfect colorings for the infinite circulant graphs with a continuous set of n distances. The obtained result confirms the conjecture for n = 2. The problem is still open in the case of n > 2.

A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence ( n 1 , … , n k ) of positive integers with n 1 + … + n k = n , there exists a partition ( V 1 , … , V k ) of the vertex set V ( G ) such that V i induces a connected subgraph of order n i , for i = 1 , … , k . In this paper we consider the on-line version of this notion, defined in a natural way. We prove that if G is a connected graph such with the independence number at most ⌈ n 2 ⌉ and the degree sum of any pair of non-adjacent vertices is at least n − 3 , then G is on-line arbitrarily partitionable except for two graphs of small orders. We also prove that if G is a connected graph of order n and size ‖ G ‖ > n − 3 2 + 6 , then G is on-line AP unless n is even and G is a spanning subgraph of a unique exceptional graph. These two results imply that dense AP graphs satisfying one of the above two assumptions are also on-line AP. This is in contrast to sparse graphs where only few AP graphs are also on-line AP.

A connected signed graph with n vertices is said to be unicyclic if its number of edges is n . The energy of a signed graph S of order n with eigenvalues x 1 , x 2 , … , x n is defined as E ( S ) = ∑ j = 1 n | x j | . We obtain the integral representations for the energy of a signed graph. We show that even and odd coefficients of the characteristic polynomial of a unicyclic signed graph respectively alternate in sign. As an application of integral representation, we compute and compare the energy of unicyclic signed graphs. Finally, we characterize unicyclic signed graphs with minimal energy.

In this paper, we study graphs whose matching polynomials have only integer zeros. A graph is matching integral if the zeros of its matching polynomial are all integers. We characterize all matching integral traceable graphs. We show that apart from K7(E(C3)E(C4)) there is no connected k-regular matching integral graph if k2. It is also shown that if G is a graph with a perfect matching, then its matching polynomial has a zero in the interval (0,1]. Finally, we describe all claw-free matching integral graphs.