A characterization of signed graphs with generalized perfect elimination orderings

An important property of chordal graphs is that these graphs are characterized by the existence of perfect elimination orderings on their vertex sets. In this paper, we generalize the notion of perfect elimination orderings to signed graphs, and give a characterization for graphs admitting such orderings, together with characterizations restricted to some subclasses and further properties of those graphs. The definition of our generalized perfect elimination orderings is motivated by a generalization of the classical result that a so-called graphic hyperplane arrangement is free if and only if the corresponding graph is chordal.     

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.     

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.

     

Maximal reflexive cacti with four cycles: The approach via Smith graphs

Cacti, or treelike graphs, are graphs whose all cycles are mutually edge-disjoint. Graphs with the property are called reflexive graphs, where λ₂ is the second largest eigenvalue of the corresponding (0, 1)-adjacency matrix. The property is a hereditary one, i.e. all induced subgraphs of a reflexive graph are also reflexive. This is why we represent reflexive graphs through the maximal graphs within a given class (such as connected cacti with a fixed number of cycles). In previous work we have determined all maximal reflexive cacti with four cycles whose cycles do not form a bundle and pointed out the role of so-called pouring of Smith graphs in their construction. In this paper, besides pouring, we show several other patterns of the appearance of Smith trees in those constructions. These include splitting of a Smith tree, adding an edge to a Smith tree and then splitting of the resulting graph, identifying two vertices of a Smith tree and then splitting the resulting graph. Our results show that the presence of Smith trees is evident in all such maximal reflexive cacti with four cycles and that in most of them Smith graphs appear in the described way.     

Algorithmic aspects of clique-transversal and clique-independent sets

A minimum clique-transversal set MCT(G) of a graph G=(V,E) is a set SV of minimum cardinality that meets all maximal cliques in G. A maximum clique-independent set MCI(G) of G is a set of maximum number of pairwise vertex-disjoint maximal cliques. We prove that the problem of finding an MCT(G) and an MCI(G) is NP-hard for cocomparability, planar, line and total graphs. As an interesting corollary we obtain that the problem of finding a minimum number of elements of a poset to meet all maximal antichains of the poset remains NP-hard even if the poset has height two, thereby generalizing a result of Duffas et al. (J. Combin. Theory Ser. A 58 (1991) 158–164). We present a polynomial algorithm for the above problems on Helly circular-arc graphs which is the first such algorithm for a class of graphs that is not clique-perfect. We also present polynomial algorithms for the weighted version of the clique-transversal problem on strongly chordal graphs, chordal graphs of bounded clique size, and cographs. The algorithms presented run in linear time for strongly chordal graphs and cographs. These mark the first attempts at the weighted version of the problem.     

Some aspects of perfect elimination orderings in chordal graphs

This paper studies properties of perfect elimination orderings in chordal graphs. Specific connections to convex subsets and quasiconcave functions in a graph are discussed. Several new schemes for generating all perfect elimination orderings are investigated and related to existing schemes.     

A Gröbner basis characterization for chordal comparability graphs

In this paper, we study toric ideals associated with multichains of posets. It is shown that the comparability graph of a poset is chordal if and only if there exists a quadratic Gröbner basis of the toric ideal of the poset. Strong perfect elimination orderings of strongly chordal graphs play an important role.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number

Asteroidal Triple‐free (AT‐free) graphs have received considerable attention due to their inclusion of various important graphs families, such as interval and cocomparability graphs. The asteroidal number of a graph is the size of a largest subset of vertices such that the removal of the closed neighborhood of any vertex in the set leaves the remaining vertices of the set in the same connected component. (AT‐free graphs have asteroidal number at most 2.) In this article, we characterize graphs of bounded asteroidal number by means of a vertex elimination ordering, thereby solving a long‐standing open question in algorithmic graph theory. Similar characterizations are known for chordal, interval, and cocomparability graphs.     

Strongly simplicial vertices of powers of trees

For a tree T and an integer k?1, it is well known that the kth power T^k of T is strongly chordal and hence has a strong elimination ordering of its vertices. In this note we obtain a complete characterization of strongly simplicial vertices of T^k, thereby characterizing all strong elimination orderings of the vertices of T^k.     

Walks and regular integral graphs

We establish a useful correspondence between the closed walks in regular graphs and the walks in infinite regular trees, which, after counting the walks of a given length between vertices at a given distance in an infinite regular tree, provides a lower bound on the number of closed walks in regular graphs. This lower bound is then applied to reduce the number of the feasible spectra of the 4-regular bipartite integral graphs by more than a half.Next, we give the details of the exhaustive computer search on all 4-regular bipartite graphs with up to 24 vertices, which yields a total of 47 integral graphs.     

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.     

On-line and first fit colorings of graphs

A graph coloring algorithm that immediately colors the vertices taken from a list without looking ahead or changing colors already assigned is called “on-line coloring.” The properties of on-line colorings are investigated in several classes of graphs. In many cases we find on-line colorings that use no more colors than some function of the largest clique size of the graph. We show that the first fit on-line coloring has an absolute performance ratio of two for the complement of chordal graphs. We prove an upper bound for the performance ratio of the first fit coloring on interval graphs. It is also shown that there are simple families resisting any on-line algorithm: no on-line algorithm can color all trees by a bounded number of colors.     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

弦图扩张与最优排序

弦图是一类特殊的完美图,以具有完美消去顺序为特征．由弦图扩张引出一系列序列性组合优化问题,沟通了图论、数值分析及最优排序等领域的若干研究课题．本文将论述我们的一些观点和研究结果．     

Some characterizations of doubly chordal graphs

Many optimization problems like domination and Steiner tree are NP-complete onchordal graphs but can be solved in polynomial time ondoubly chordal graphs. Investigating properties of doubly chordal graphs probably help to design efficient algorithms for the graphs. We present some characterizations of doubly chordal graphs, which are based on clique matrices and neighborhood matrices. It is also mentioned how adoubly perfect elimination ordering of a doubly chordal graph can be computed from the results.     

Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

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.     

An approximation result for the interval coloring problem on claw-free chordal graphs

We study the problem of finding an acyclic orientation of an undirected graph, such that each (oriented) path is covered by a limited number k of maximal cliques. This is equivalent to finding a k-approximate solution for the interval coloring problem on a graph. We focus our attention on claw-free chordal graphs, and show how to find an orientation of such a graph in linear time, which guarantees that each path is covered by at most two maximal cliques. This extends previous published results on other graph classes where stronger assumptions were made.     

Intersection models of weakly chordal graphs

We first present new structural properties of a two-pair in various graphs. A two-pair is used in a well-known characterization of weakly chordal graphs. Based on these properties, we prove the main theorem: a graph G is a weakly chordal ()-free graph if and only if G is an edge intersection graph of subtrees on a tree with maximum degree 4. This characterizes the so called [4, 4, 2] graphs. The proof of the theorem constructively finds the representation. Thus, we obtain an algorithm to construct an edge intersection model of subtrees on a tree with maximum degree 4 for such a given graph. This is a recognition algorithm for [4, 4, 2] graphs.