A linear-time algorithm for the longest path problem in rectangular grid graphs

The longest path problem is a well-known NP-hard problem and so far it has been solved polynomially only for a few classes of graphs. In this paper, we give a linear-time algorithm for finding a longest path between any two given vertices in a rectangular grid graph.     

Region merging with topological control

This paper presents a region merging process controlled by topological features on regions in three-dimensional (3D) images. Betti numbers, a well-known topological invariant, are used as criteria. Classical and incremental algorithms to compute the Betti numbers using information represented by the topological map of an image are provided. The region merging algorithm, which merges any number of connected components of regions together, is explained. A topological control of the merging process is implemented using Betti numbers to control the topology of an evolving 3D image partition. The interest in incremental approaches of the computation of Betti numbers is established by providing a processing time comparison. A visual example showing the result of the algorithm and the impact of topological control is also given.     

The Hamiltonian connectivity of rectangular supergrid graphs

A Hamiltonian path of a graph is a simple path which visits each vertex of the graph exactly once. The Hamiltonian path problem is to determine whether a graph contains a Hamiltonian path. A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. In this paper, we will study the Hamiltonian connectivity of rectangular supergrid graphs. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as subgraphs. The Hamiltonian path problem for grid graphs and triangular grid graphs was known to be NP-complete. Recently, we have proved that the Hamiltonian path problem for supergrid graphs is also NP-complete. The Hamiltonian paths on supergrid graphs can be applied to compute the stitching traces of computer sewing machines. Rectangular supergrid graphs form a popular subclass of supergrid graphs, and they have strong structure. In this paper, we provide a constructive proof to show that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. Based on the constructive proof, we present a linear-time algorithm to construct a longest path between any two given vertices in a rectangular supergrid graph.     

A solitaire game played on 2-colored graphs

We introduce a solitaire game played on a graph. Initially one disk is placed at each vertex, one face green and the other red, oriented with either color facing up. Each move of the game consists of selecting a vertex whose disk shows green, flipping over the disks at neighboring vertices, and deleting the selected vertex. The game is won if all vertices are eliminated. We derive a simple parity-based necessary condition for winnability of a given game instance. By studying graph operations that construct new graphs from old ones, we obtain broad classes of graphs where this condition also suffices, thus characterizing the winnable games on such graphs. Concerning two familiar (but narrow) classes of graphs, we show that for trees a game is winnable if and only if the number of green vertices is odd, and for n-cubes a game is winnable if and only if the number of green vertices is even and not all vertices have the same color. We provide a linear-time algorithm for deciding winnability for games on maximal outerplanar graphs. We reduce the decision problem for winnability of a game on an arbitrary graph G to winnability of games on its blocks, and to winnability on homeomorphic images of G obtained by contracting edges at 2-valent vertices.     

A Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs

A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in seriesparallel graphs and present a linear-time exact algorithm to solve it.     

Recognizing bull-free perfect graphs

A bull is the graph obtained from a triangle by adding two pendant vertices adjacent to distinct vertices of the triangle. Chvátal and Sbihi showed that the strong perfect graph conjecture holds for Bull-free graphs. We give a polynomial time recognition algorithm for Bull-free perfect graphs.     

Minimal split completions

We study the problem of adding an inclusion minimal set of edges to a given arbitrary graph so that the resulting graph is a split graph, called a minimal split completion of the input graph. Minimal completions of arbitrary graphs into chordal and interval graphs have been studied previously, and new results have been added recently. We extend these previous results to split graphs by giving a linear-time algorithm for computing minimal split completions. We also give two characterizations of minimal split completions, which lead to a linear time algorithm for extracting a minimal split completion from any given split completion.We prove new properties of split graph that are both useful for our algorithms and interesting on their own. First, we present a new way of partitioning the vertices of a split graph uniquely into three subsets. Second, we prove that split graphs have the following property: given two split graphs on the same vertex set where one is a subgraph of the other, there is a sequence of edges that can be removed from the larger to obtain the smaller such that after each edge removal the modified graph is split.     

Heavy fans, cycles and paths in weighted graphs of large connectivity

A set of paths joining a vertex y and a vertex set L is called (y,L)-fan if any two of the paths have only y in common, and its width is the number of paths forming it. In weighted graphs, it is known that the existence of heavy fan is useful to find a heavy cycle containing some specified vertices.In this paper, we show the existence of heavy fans with large width containing some specified vertices in weighted graphs of large connectivity, which is a weighted analogue of Perfect's theorem. Using this, in 3-connected weighted graphs, we can find heavy cycles containing three specified vertices, and also heavy paths joining two specified vertices containing two more specified vertices. These results extend the previous results in 2-connected weighted graphs to 3-connected weighted graphs.     

The disjunctive domination number of a graph

Abstract

For a positive integer b, we define a set S of vertices in a graph G as a b-disjunctive dominating set if every vertex not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it. The b-disjunctive domination number is the minimum cardinality of such a set. This concept is motivated by the concepts of distance domination and exponential domination. In this paper, we start with some simple results, then establish bounds on the parameter especially for regular graphs and claw-free graphs. We also show that determining the parameter is NP-complete, and provide a linear-time algorithm for trees.     

A graph for which the inertia bound is not tight

The inertia bound gives an upper bound on the independence number of a graph by considering the inertia of matrices corresponding to the graph. The bound is known to be tight for graphs on 10 or fewer vertices as well as for all perfect graphs. It is natural to question whether the bound is always tight. We show that the bound is not tight for the Paley graph on 17 vertices as well as its induced subgraph on 16 vertices.     

Counting the number of independent sets in chordal graphs

We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.     

The inertia of unicyclic graphs and the implications for closed-shells

The inertia of a graph is an integer triple specifying the number of negative, zero, and positive eigenvalues of the adjacency matrix of the graph. A unicyclic graph is a simple connected graph with an equal number of vertices and edges. This paper characterizes the inertia of a unicyclic graph in terms of maximum matchings and gives a linear-time algorithm for computing it. Chemists are interested in whether the molecular graph of an unsaturated hydrocarbon is (properly) closed-shell, having exactly half of its eigenvalues greater than zero, because this designates a stable electron configuration. The inertia determines whether a graph is closed-shell, and hence the reported result gives a linear-time algorithm for determining this for unicyclic graphs.     

Efficient algorithms for the recognition of topologically conjugate gradient-like diffeomorhisms

It is well known that the topological classification of structurally stable flows on surfaces as well as the topological classification of some multidimensional gradient-like systems can be reduced to a combinatorial problem of distinguishing graphs up to isomorphism. The isomorphism problem of general graphs obviously can be solved by a standard enumeration algorithm. However, an efficient algorithm (i. e., polynomial in the number of vertices) has not yet been developed for it, and the problem has not been proved to be intractable (i. e., NPcomplete). We give polynomial-time algorithms for recognition of the corresponding graphs for two gradient-like systems. Moreover, we present efficient algorithms for determining the orientability and the genus of the ambient surface. This result, in particular, sheds light on the classification of configurations that arise from simple, point-source potential-field models in efforts to determine the nature of the quiet-Sun magnetic field.     

Optimal Parametric Search on Graphs of Bounded Tree-Width

We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar graphs.     

On the structure of bull-free perfect graphs

A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi showed that the Strong Perfect Graph Conjecture holds for bull-free graphs. We show that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. Our proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphsPartially supported by CNPq, grant 30 1160/91.0     

The integral stable allocation problem on graphs

As a generalisation of the stable matching problem Baïou and Balinski (2002) [1] defined the stable allocation problem for bipartite graphs, where both the edges and the vertices may have capacities. They constructed a so-called inductive algorithm, that always finds a stable allocation in strongly polynomial time. Here, we generalise their algorithm for non-bipartite graphs with integral capacities. We show that the algorithm does not remain polynomial, although we also present a scaling technique that makes the algorithm weakly polynomial.     

A Simple Linear-Time Recognition Algorithm for Weakly Quasi-Threshold Graphs

Weakly quasi-threshold graphs form a proper subclass of the well-known class of cographs by restricting the join operation. In this paper we characterize weakly quasi-threshold graphs by a finite set of forbidden subgraphs: the class of weakly quasi-threshold graphs coincides with the class of {P ₄, co-(2P ₃)}-free graphs. Moreover we give the first linear-time algorithm to decide whether a given graph belongs to the class of weakly quasi-threshold graphs, improving the previously known running time. Based on the simplicity of our recognition algorithm, we can provide certificates of membership (a structure that characterizes weakly quasi-threshold graphs) or non-membership (forbidden induced subgraphs) in additional ${{\mathcal O}(n)}$ time. Furthermore we give a linear-time algorithm for finding the largest induced weakly quasi-threshold subgraph in a cograph.     

Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

The bondage number of graphs on topological surfaces and Teschner’s conjecture

The bondage number of a graph is the smallest number of its edges whose removal results in a graph having a larger domination number. We provide constant upper bounds for the bondage number of graphs on topological surfaces, and improve upper bounds for the bondage number in terms of the maximum vertex degree and the orientable and non-orientable genera of graphs. Also, we present stronger upper bounds for graphs with no triangles and graphs with the number of vertices larger than a certain threshold in terms of graph genera. This settles Teschner’s Conjecture in affirmative for almost all graphs. As an auxiliary result, we show tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus.     

Unique Maximum Matching Algorithms

We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(m log⁴ n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. For the special case of planar graphs, we improve the algorithm to run in O(n log n) time. Second, given one perfect matching, we can test for the existence of another in linear time. This algorithm is a modification of Edmonds' blossom-shrinking algorithm implemented using depth-first search. A generalization of Kotzig's theorem proved by Jackson and Whitty allows us to give a modification of the first algorithm that tests whether a given graph has a unique f-factor, and find it if it exists. We also show how to modify the second algorithm to check whether a given f-factor is unique. Both extensions have the same time bounds as their perfect matching counterparts. For the weighted case, we can test in linear time whether a maximum-weight matching is unique, given the output from Edmonds' algorithm for computing such a matching. The method is an extension of our algorithm for the unweighted case.