Computation of a (canonical) doubly perfect elimination ordering of a doubly chordal graph

The class ofdoubly chordal graphs is a subclass ofchordal graphs and a superclass ofstrongly chordal graphs, which arise in so many application areas. Many optimization problems like domination and Steiner tree are NP-complete on chordal graphs but can be solved in polynomial time on doubly chordal graphs. The central to designing efficient algorithms for doulby chordal graphs is the concept of(canonical) doubly perfect elimination orderings. We present linear time algorithms to compute a(canonical) doubly perfect elimination ordering of adoubly chordal graph.     

Algorithms on clique separable graphs

We define a family of graphs, called the clique separable graphs, characterized by the fact that they have completely connected cut sets by which we decompose them into parts such that when no further decomposition is possible we have a set of simple subgraphs. For example the chordal graphs and the i-triangulated graphs are clique separable graphs.The purpose of this paper is to describe polynomial time algorithms for the recognition of the clique separable graphs and for finding them a minimum coloring and a maximum clique.     

Optimization problems in multiple subtree graphs

We study various optimization problems in t-subtree graphs, the intersection graphs of t-subtrees, where a t-subtree is the union of t disjoint subtrees of some tree. This graph class generalizes both the class of chordal graphs and the class of t-interval graphs, a generalization of interval graphs that has recently been studied from a combinatorial optimization point of view. We present approximation algorithms for the Maximum Independent Set, Minimum Coloring, Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique problems.     

Upper Maximal Graphs of Posets

We introduce and study a class of simple graphs, the upper-maximal graphs (UM-graphs), associated to finite posets. The vertices of the UM-graph of a given poset P are the elements of P, and edges are formed by those vertices x and y whenever any maximal element of P that is greater than x is also greater than y or vise versa. We show that the class of UM-graphs constitutes a subclass of comparability graphs. We further provide a characterization of chordal UM-graphs, and compare UM-graphs with known bound graphs of posets.     

The elliptic matrix completion problem

Completions of partial elliptic matrices are studied. Given an undirected graph G, it is shown that every partial elliptic matrix with graph G can be completed to an elliptic matrix if and only if the maximal cliques of G are pairwise disjoint. Further, given a partial elliptic matrix A with undirected graph G, it is proved that if G is chordal and each specified principal submatrix defined by a pair of intersecting maximal cliques is nonsingular, then A can be completed to an elliptic matrix. Conversely, if G is nonchordal or if the regularity condition is relaxed, it is shown that there exist partial elliptic matrices which are not completable to an elliptic matrix. In the process we obtain several results concerning chordal graphs that may be of independent interest.     

Introducing subclasses of basic chordal graphs

Basic chordal graphs arose when comparing clique trees of chordal graphs and compatible trees of dually chordal graphs. They were defined as those chordal graphs whose clique trees are exactly the compatible trees of its clique graph.In this work, we consider some subclasses of basic chordal graphs, like hereditary basic chordal graphs, basic DV and basic RDV graphs, we characterize them and we find some other properties they have, mostly involving clique graphs.     

Completion problem with partial correlation vines

This paper extends the results in [D. Kurowicka, R.M. Cooke, A parametrization of positive definite matrices in terms of partial correlation vines, Linear Algebra Appl. 372 (2003) 225-251]. We show that a partial correlation vine represents a factorization of the determinant of the correlation matrix. We show that the graph of an incompletely specified correlation matrix is chordal if and only if it can be represented as an m-saturated incomplete vine, that is, an incomplete vine for which all edges corresponding to membership-descendents (m-descendents for short) of a specified edge are specified. This enables us to find the set of completions, and also the completion with maximal determinant for matrices corresponding to chordal graphs.     

Maximum induced matching problem on hhd-free graphs

We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m²) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m³). Then, we consider a technique used by Brandstädt and Hoàng (2008) [4] to solve the problem on chordal graphs. Extending this, we show that for a subclass of hhd-free graphs that is more general than chordal graphs the problem can be solved in linear time. We also present examples to demonstrate the tightness of our results.     

Variations of maximum-clique transversal sets on graphs

A maximum-clique transversal set of a graph G is a subset of vertices intersecting all maximum cliques of G. The maximum-clique transversal set problem is to find a maximum-clique transversal set of G of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we introduce the concept of maximum-clique perfect and some variations of the maximum-clique transversal set problem such as the {k}-maximum-clique, k-fold maximum-clique, signed maximum-clique, and minus maximum-clique transversal problems. We show that balanced graphs, strongly chordal graphs, and distance-hereditary graphs are maximum-clique perfect. Besides, we present a unified approach to these four problems on strongly chordal graphs and give complexity results for the following classes of graphs: split graphs, balanced graphs, comparability graphs, distance-hereditary graphs, dually chordal graphs, doubly chordal graphs, chordal graphs, planar graphs, and triangle-free graphs.     

Variations of Y-dominating functions on graphs

Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:V→Y such that for all vertices v∈V, where N_G[v]={v}∪{u|(u,v)∈E}. Let for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as {k}-domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the {k}-domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.     

Clique trees of chordal graphs: leafage and 3-asteroidals

Chordal graphs were characterized as those graphs having a tree, called clique tree, whose vertices are the cliques of the graph and for every vertex in the graph, the set of cliques that contain it form a subtree of clique tree. In this work, we study the relationship between the clique trees of a chordal graph and its subgraphs. We will prove that clique trees can be described locally and all clique trees of a graph can be obtained from clique trees of subgraphs. In particular, we study the leafage of chordal graphs, that is the minimum number of leaves among the clique trees of the graph. It is known that interval graphs are chordal graphs without 3-asteroidals. We will prove a generalization of this result using the framework developed in the present article. We prove that in a clique tree that realizes the leafage, for every vertex of degree at least 3, and every choice of 3 branches incident to it, there is a 3−asteroidal in these branches.     

An implicit representation of chordal comparability graphs in linear time

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using O(n) integers so that, given two vertices, it can be determined in O(1) time whether they are adjacent, no matter how dense the graph is. We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n²).     

On the Number of Non-Hamiltonian Graphs

In this paper, maximal non-Hamiltonian graphs ( MNH graphs), i.e., non-Hamiltonian graphs such that the addition of any new edge violates their property of being non-Hamiltonian are studied. It is shown that the study of MNH graphs can be reduced to the study of the so-called simplified MNH graphs. Restrictions on the structure of maximal cliques of simplified MNH graphs are obtained, the orders and the number of such graphs are estimated.     

Segment representation of a subclass of co-planar graphs

A graph is a segment graph if its vertices can be mapped to line segments in the plane such that two vertices are adjacent if and only if their corresponding line segments intersect. Kratochvíl and Kuběna asked the question of whether the complements of planar graphs, called co-planar graphs, are segment graphs. We show here that the complements of all partial 2-trees are segment graphs.     

Chordal bipartite completion of colored graphs

Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449-473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete.     

On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E) and positive integer k≥1, an edge set M⊆E is a distance-k matching if the pairwise distance of edges in M is at least k in G. For k=1, this gives the usual notion of matching in graphs, and for general k≥1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k=2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)² of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.We show that, unlike for k=2, for a chordal graph G, L(G)³ is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) matching for k≥1, remains NP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k matching problem can be solved in polynomial time for every k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.     

Domination,independent domination,and duality in strongly chordal graphs

We present polynomial algorithms to locate minimum weight dominating sets and independent dominating sets in strongly chordal graphs. We utilize an intimate relationship between strongly chordal graphs and totally balanced matrices to show that the domatic number achieves its theoretical lower bound in strongly chordal graphs and to efficiently solve certain optimization problems for totally balanced matrices.     

Perfect elimination orderings for symmetric matrices

We introduce a new class of structured symmetric matrices by extending the notion of perfect elimination ordering from graphs to weighted graphs or matrices. This offers a common framework capturing common vertex elimination orderings of monotone families of chordal graphs, Robinsonian matrices and ultrametrics. We give a structural characterization for matrices that admit perfect elimination orderings in terms of forbidden substructures generalizing chordless cycles in graphs.

     

Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs

We show that the class of unit grid intersection graphs properly includes both of the classes of interval bigraphs and of P₆-free chordal bipartite graphs. We also demonstrate that the classes of unit grid intersection graphs and of chordal bipartite graphs are incomparable.     

Perfect Elimination and Chordal Bipartite Graphs

We define two types of bipartite graphs, chordal bipartite graphs and perfect elimination bipartite graphs, and prove theorems analogous to those of Dirac and Rose for chordal graphs (rigid circuit graphs, triangulated graphs). Our results are applicable to Gaussian elimination on sparse matrices where a sequence of pivots preserving zeros is sought. Our work removes the constraint imposed by Haskins and Rose that pivots must be along the main diagonal.