Conditional matching preclusion for the arrangement graphs

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 this number and classify all optimal sets for the arrangement graphs, one of the most popular interconnection networks.     

Perfectly colorable graphs

We define a perfect coloring of a graph G as a proper coloring of G such that every connected induced subgraph H of G uses exactly ω(H) many colors where ω(H) is the clique number of H. A graph is perfectly colorable if it admits a perfect coloring. We show that the class of perfectly colorable graphs is exactly the class of perfect paw-free graphs. It follows that perfectly colorable graphs can be recognized and colored in linear time.     

Minimum dominating cycles in outerplanar graphs

Adominating cycle of a graph lies at a distance of at most one from all the vertices of the graph. The problem of finding the minimum size of such a cycle is proved to be difficult even when restricted to planar graphs. An efficient algorithm solving this problem is given for the class of two-connectedouterplanar graphs, in which all vertices lie on the exterior face in a plane embedding of the graph.On leave from Institute of Computer Science, University of Wrocaw, Wrocaw, Poland.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.     

Edge coloring of bipartite graphs with constraints

A classical result from graph theory states that the edges of an l-regular bipartite graph can be colored using exactly l colors so that edges that share an endpoint are assigned different colors. In this paper, we study two constrained versions of the bipartite edge coloring problem.

Full-size image

Quotients of Gaussian graphs and their application to perfect codes

A graph-based model of perfect two-dimensional codes is presented in this work. This model facilitates the study of the metric properties of the codes. Signal spaces are modeled by means of Cayley graphs defined over the Gaussian integers and denoted as Gaussian graphs. Codewords of perfect codes will be represented by vertices of a quotient graph of the Gaussian graph in which the signal space has been defined. It will be shown that any quotient graph of a Gaussian graph is indeed a Gaussian graph. This makes it possible to apply previously known properties of Gaussian graphs to the analysis of perfect codes. To illustrate the modeling power of this graph-based tool, perfect Lee codes will be analyzed in terms of Gaussian graphs and their quotients.     

Function-described graphs for modelling objects represented by sets of attributed graphs

We present in this article the model function-described graph (FDG), which is a type of compact representation of a set of attributed graphs (AGs) that borrow from random graphs the capability of probabilistic modelling of structural and attribute information. We define the FDGs, their features and two distance measures between AGs (unclassified patterns) and FDGs (models or classes) and we also explain an efficient matching algorithm. Two applications of FDGs are presented: in the former, FDGs are used for modelling and matching 3D-objects described by multiple views, whereas in the latter, they are used for representing and recognising human faces, described also by several views.     

Maximum matchings in planar graphs via gaussian elimination

We present a randomized algorithm for finding maximum matchings in planar graphs in timeO(n ^ω/2), whereω is the exponent of the best known matrix multiplication algorithm. Sinceω<2.38, this algorithm breaks through theO(n ^1.5) barrier for the matching problem. This is the first result of this kind for general planar graphs. We also present an algorithm for generating perfect matchings in planar graphs uniformly at random usingO(n ^ω/2) arithmetic operations. Our algorithms are based on the Gaussian elimination approach to maximum matchings introduced in [16]. This research was supported by KBN Grant 4T11C04425.     

The labeled perfect matching in bipartite graphs

In this paper, we deal with both the complexity and the approximability of the labeled perfect matching problem in bipartite graphs. Given a simple graph G=(V,E) with |V|=2n vertices such that E contains a perfect matching (of size n), together with a color (or label) function , the labeled perfect matching problem consists in finding a perfect matching on G that uses a minimum or a maximum number of colors.     

Addendum to: Maximum Weight Independent Sets in hole- and co-chair-free graphs

In Brandstädt and Giakoumakis [2], we reduce the Maximum Weight Independent Set (MWIS) problem on hole- and co-chair-free graphs to a corresponding problem on prime atoms. Here we refine these results by investigating atoms of prime graphs (avoiding the requirement that the graphs are prime and atoms) and also observe that the MWIS problem is solvable in polynomial time on (odd-hole, co-chair)-free graphs.     

On maximum induced matchings in bipartite graphs

The problem of finding a maximum induced matching is known to be NP-hard in general bipartite graphs. We strengthen this result by reducing the problem to some special classes of bipartite graphs such as bipartite graphs with maximum degree 3 or C₄-free bipartite graphs. On the other hand, we describe a new polynomially solvable case for the problem in bipartite graphs which deals with a generalization of bi-complement reducible graphs.     

On the structure of certain intersection graphs

Recently Gavril introduced a new class of intersection graphs called interval-filament graphs. These include co-comparability graphs and polygon-circle graphs (the intersection graphs of polygons inscribed in a circle), which include circular-arc graphs (the intersection graphs of arcs of a circle), circle graphs (the intersection graphs of chords of a circle), chordal graphs, and outerplanar graphs. We give a structural property of polygon-circle graphs. We prove a bound on the clique-covering number for interval-filament graphs in terms of the size of a largest independent set of nodes in the graph. We prove that complements of interval-filament graphs are 4-divisible in the sense of Hoàng and McDiarmid. Similar results are obtained for complements of other intersection graphs introduced by Gavril.     

给定匹配数的单圈图的最小值

图[G]的广义Randic指标定义为[Rα（G）=uv∈E（G）（dudv）α],其中[α]为任意实数,[du]为顶点[u]的度。顶点数等于边数的简单图称为单圈图。在匹配数等于边数的情况下,通过分类讨论,给出当[-1.39≤a≤-1]时,相应单圈图的广义Randic指标的最小值,并给出相应的结构图。     

Matching preclusion for the (n,k)-bubble-sort graphs

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 (n, k)-bubble-sort graphs and classify all the optimal solutions.     

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.     

Edge-colouring of join graphs

A join graph is the complete union of two arbitrary graphs. We give sufficient conditions for a join graph to be 1-factorizable. As a consequence of our results, the Hilton’s Overfull Subgraph Conjecture holds true for several subclasses of join graphs.     

A quadratic identity for the number of perfect matchings of plane graphs

We present a quadratic identity on the number of perfect matchings of plane graphs by the method of graphical condensation, which generalizes the results found by Propp [J. Propp, Generalized domino-shuffling, Theoret. Comput. Sci. 303 (2003) 267–301], Kuo [E.H. Kuo, Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci. 319 (2004) 29–57], and Yan, Yeh, and Zhang [W.G. Yan, Y.-N. Yeh, F.J. Zhang, Graphical condensation of plane graphs: A combinatorial approach, Theoret. Comput. Sci. 349 (2005) 452–461].     

Fast processing of graph queries on a large database of small and medium-sized data graphs

We propose a new way of indexing a large database of small and medium-sized graphs and processing exact subgraph matching (or subgraph isomorphism) and approximate (full) graph matching queries. Rather than decomposing a graph into smaller units (e.g., paths, trees, graphs) for indexing purposes, we represent each graph in the database by its graph signature, which is essentially a multiset. We construct a disk-based index on all the signatures via bulk loading. During query processing, a query graph is also mapped into its signature, and this signature is searched using the index by performing multiset operations. To improve the precision of exact subgraph matching, we develop a new scheme using the concept of line graphs. Through extensive evaluation on real and synthetic graph datasets, we demonstrate that our approach provides a scalable and efficient disk-based solution for a large database of small and medium-sized graphs.