A structure theorem for maximum internal matchings in graphs

A counterpart of the Gallai-Edmonds Structure Theorem is proved for matchings that are not required to cover the external vertices of graphs. The appropriate counterpart of Tutte's Theorem is derived from this result for the existence of perfect internal matchings in graphs.     

Fault diameter of Cartesian product graphs

The (k−1)-fault diameter Dk(G) of a k-connected graph G is the maximum diameter of G−F for any F⊂V(G) with |F|<k. Krishnamoorthy and Krishnamurthy first proposed this concept and gave Dκ(G₁)+κ(G₂)(G₁×G₂)?Dκ(G₁)(G₁)+Dκ(G₂)(G₂) when κ(G₁×G₂)=κ(G₁)+κ(G₂), where κ(G) is the connectivity of G. This paper gives a counterexample to this bound and establishes Dk₁+k₂(G₁×G₂)?Dk₁(G₁)+Dk₂(G₂)+1 for any ki-connected graph Gi and ki?1 for i=1,2.     

Perfect stables in graphs

A perfect stable in a graph G is a stable S with the property that any vertex of G is either in S or adjacent with at least two vertices which are in S. This concept is an obvious generalization of the notion of perfect matching. In this note, the problem of deciding if a given graph has a perfect stable is considered. This problem is shown to be in general NP-complete, but polynomial for K_1,3-free graphs.     

The number of spanning trees in a new lexicographic product of graphs

The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only.     

Strong matching preclusion

The matching preclusion problem, introduced by Brigham et al. [R.C. Brigham, F. Harary, E.C. Violin, and J. Yellen, Perfect-matching preclusion, Congressus Numerantium 174 (2005) 185-192], studies how to effectively make a graph have neither perfect matchings nor almost perfect matchings by deleting as small a number of edges as possible. Extending this concept, we consider a more general matching preclusion problem, called the strong matching preclusion, in which deletion of vertices is additionally permitted. We establish the strong matching preclusion number and all possible minimum strong matching preclusion sets for various classes of graphs.     

Local colourings of Cartesian product graphs

A local colouring of a graph G is a function c: V(G)→? such that for each S ? V(G), 2≤|S|≤3, there exist u, v∈S with |c(u)?c(v)| at least the number of edges in the subgraph induced by S. The maximum colour assigned by c is the value χ_?(c) of c, and the local chromatic number of G is χ_?(G)=min {χ_?(c): c is a local colouring of G}. In this note the local chromatic number is determined for Cartesian products G □ H, where G and GH are 3-colourable graphs. This result in part corrects an error from Omoomi and Pourmiri [On the local colourings of graphs, Ars Combin. 86 (2008), pp. 147–159]. It is also proved that if G and H are graphs such that χ(G)≤? χ_?(H)/2 ?, then χ_?(G □ H)≤χ_?(H)+1.     

Fault diameter of product graphs

The (k−1)-fault diameter Dk(G) of a k-connected graph G is the maximum diameter of an induced subgraph by deleting at most k−1 vertices from G. This paper considers the fault diameter of the product graph G₁∗G₂ of two graphs G₁ and G₂ and proves that Dk₁+k₂(G₁∗G₂)?Dk₁(G₁)+Dk₂(G₂)+1 if G₁ is k₁-connected and G₂ is k₂-connected. This generalizes some known results such as Bani? and ?erovnik [I. Bani?, J. ?erovnik, Fault-diameter of Cartesian graph bundles, Inform. Process. Lett. 100 (2) (2006) 47-51].     

Strong orientations of complete k-partite graphs achieving the strong diameter

In this paper, we consider each integer d between the lower and upper orientable strong diameter of the complete k-partite graph K(m₁,m₂,…,mk), and show that there does exist a strong orientation of K(m₁,m₂,…,mk) such that sdiam(K)=d.     

Matching preclusion and conditional matching preclusion for pancake and burnt pancake graphs

The matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion destroys all perfect matchings in the graph. The optimal matching preclusion sets are often precisely those which are induced by a single vertex of minimum degree. To look for obstruction sets beyond these, the conditional matching preclusion number was introduced, which is defined similarly with the additional restriction that the resulting graph has no isolated vertices. In this paper we find the matching preclusion and conditional matching preclusion numbers and classify all optimal sets for the pancake graphs and burnt pancake graphs.     

Perfect matchings and extended polymatroid

The classical conditions of the existence of a perfect matching in bipartite graphs are used directly or indirectly to solve the assignment problem by the well-known algorithms. In the paper, we define a vector and an extended polymatroid for a bipartite graph so that the bipartite graph has a perfect matching if and only if the vector is the basis of the extended polymatroid. The study was partially sponsored by INTAS, grant 06-1000017-8909. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 173–179, May–June 2008.     

Conditional matching preclusion for the alternating group graphs and split-stars

The matching preclusion number of a graph is the minimum number of edges the deletion of which 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 the deletion of which results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this article, we find this number and classify all optimal sets for the alternating group graphs, one of the most popular interconnection networks, and their companion graphs, the split-stars. Moreover, some general results on the conditional matching preclusion problems are also presented.     

Recognition of shapes by attributed skeletal graphs

In this paper, we propose a framework to address the problem of generic 2-D shape recognition. The aim is mainly on using the potential strength of skeleton of discrete objects in computer vision and pattern recognition where features of objects are needed for classification. We propose to represent the medial axis characteristic points as an attributed skeletal graph to model the shape. The information about the object shape and its topology is totally embedded in them and this allows the comparison of different objects by graph matching algorithms. The experimental results demonstrate the correctness in detecting its characteristic points and in computing a more regular and effective representation for a perceptual indexing. The matching process, based on a revised graduated assignment algorithm, has produced encouraging results, showing the potential of the developed method in a variety of computer vision and pattern recognition domains. The results demonstrate its robustness in the presence of scale, reflection and rotation transformations and prove the ability to handle noise and occlusions.