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.     

On the 2-rainbow domination in graphs

The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K₂. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k) this number is between ⌈4n/5⌉ and n with both bounds being sharp.     

Cyclicity of graphs

The cyclicity of a graph is the largest integer n for which the graph is contractible to the cycle on n vertices. By analyzing the cycle space of a graph, we establish upper and lower bounds on cyclicity. These bounds facilitate the computation of cyclicity for several classes of graphs, including chordal graphs, complete n-partite graphs, n-cubes, products of trees and cycles, and planar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 160–170, 1999     

Enumeration of labelled threshold graphs and a theorem of frobenius involving eulerian polynomials

We enumerate labelled threshold graphs by the number of vertices, the number of isolated vertices, and the number of distinct vertex-degrees and we give the exact asymptotics for the number of labelled threshold graphs withn vertices. We obtain the appropriate generating function and point out a combinatorial interpretation relating its coefficients to the Stirling numbers of the second kind. We use these results to derive a new proof of a theorem of Frobenius expressing the Eulerian polynomials in terms of the Stirling numbers.     

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²).     

Some algebraic properties of hypergraphs

We consider Stanley-Reisner rings k[x ₁, …, x _n ]/I(H) where I(H) is the edge ideal associated to some particular classes of hypergraphs. For instance, we consider hypergraphs that are natural generalizations of graphs that are lines and cycles, and for these we compute the Betti numbers. We also generalize some known results about chordal graphs and study a weak form of shellability.     

A New Class of Graphs That Satisfies the Chen‐Chvátal Conjecture

A well‐known combinatorial theorem says that a set of n non‐collinear points in the plane determines at least n distinct lines. Chen and Chvátal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work, we prove a slightly stronger version of Chen and Chvátal conjecture for a family of graphs containing chordal graphs and distance‐hereditary graphs.     

Alternating cycle-free matchings

The investigation of alternating cycle-free matchings is motivated by the Jump-number problem for partially ordered sets and the problem of counting maximum cardinality matchings in hexagonal systems.We show that the problem of deciding whether a given chordal bipartite graph has an alternating cycle-free matching of a given cardinality is NP-complete. A weaker result, for bipartite graphs only, has been known for some time. Also, the alternating cycle-free matching problem remains NP-complete for strongly chordal split graphs of diameter 2.In contrast, we give algorithms to solve the alternating cycle-free matching problem in polynomial time for bipartite distance hereditary graphs (time O(m ²) on graphs with m edges) and distance hereditary graphs (time O(m ⁵)).     

Fast algorithms for generating all maximal independent sets of interval,circular-arc and chordal graphs

In this paper we give fast algorithms for generating all maximal independent sets of three special classes of graphs—interval, circular-arc, and chordal graphs. The worst-case running times of our algorithms are O(n² + β) for interval and circular-arc graphs, and $\text{O((n + e)}{}^1\text{α)}$ for chordal graphs, where n, e, and α are the numbers of vertexes, edges, and maximal independent sets of a graph, and β is the sum of the numbers of vertexes of all maximal independent sets. Our algorithms compare favorably with the fastest known algorithm for general graphs which has a worst-case running time of $\text{O(n}{}^1\text{e}{}^1\text{α)}$.     

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.     

Dirac’s Theorem on Simplicial Matroids

We introduce the notion of k-hyperclique complexes, i.e., the largest simplicial complexes on the set [n] with a fixed k-skeleton. These simplicial complexes are a higher-dimensional analogue of clique (or flag) complexes (case k = 2) and they are a rich new class of simplicial complexes. We show that Dirac’s theorem on chordal graphs has a higher-dimensional analogue in which graphs and clique complexes get replaced, respectively, by simplicial matroids and k-hyperclique complexes. We prove also a higher-dimensional analogue of Stanley’s reformulation of Dirac’s theorem on chordal graphs.      

Random graphs on surfaces

Counting labelled planar graphs, and typical properties of random labelled planar graphs, have received much attention recently. We start the process here of extending these investigations to graphs embeddable on any fixed surface S. In particular we show that the labelled graphs embeddable on S have the same growth constant as for planar graphs, and the same holds for unlabelled graphs. Also, if we pick a graph uniformly at random from the graphs embeddable on S which have vertex set {1,…,n}, then with probability tending to 1 as n→∞, this random graph either is connected or consists of one giant component together with a few nodes in small planar components.     

Independent packings in structured graphs

Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. Our results apply more generally to independent packings by members of any family of connected graphs. Research of both authors is supported by the Natural Sciences and Engineering Research Council of Canada.     

A separation property of planar triangulations

Every planar triangulation G has the property that each induced cycle C of length at least 4 in G separates G, but no proper subgraph of C does. This property is trivially shared by all chordal graphs since these contain no such cycles at all. We ask to what extent maximally planar graphs and chordal graphs are unique with this property — or how much larger the class of graphs is that it determines. The answer is given in the form of a characterization of this class in terms of the simplicial decompositions of its elements. The theory of simplicial decompositions appears to be a very interesting, but still largely unexploited, method of characterization in graph theory, which seems tailor-made for problems like the one discussed.     

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.     

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.     

Bounding the Clique‐Width of H‐Free Chordal Graphs

A graph is H‐free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique‐width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co‐gem are the only two 1‐vertex P₄‐extensions H for which the class of H‐free chordal graphs has bounded clique‐width. In fact we prove that bull‐free chordal and co‐chair‐free chordal graphs have clique‐width at most 3 and 4, respectively. In particular, we find four new classes of H‐free chordal graphs of bounded clique‐width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H‐free chordal graphs has bounded clique‐width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of ‐free graphs has bounded clique‐width via a reduction to K₄‐free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique‐width of H‐free weakly chordal graphs.     

Asymptotic enumeration of sparse 2‐connected graphs

We determine an asymptotic formula for the number of labelled 2‐connected (simple) graphs on n vertices and m edges, provided that m ‐ n →∞ and m = O(nlog n) as n →∞. This is the entire range of m not covered by previous results. The proof involves determining properties of the core and kernel of random graphs with minimum degree at least 2. The case of 2‐edge‐connectedness is treated similarly. We also obtain formulae for the number of 2‐connected graphs with given degree sequence for most (“typical”) sequences. Our main result solves a problem of Wright from 1983. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.     

A generalization of Eagon–Reiner’s theorem and a characterization of bi-CMt bipartite and chordal graphs

We give a generalization of Eagon-Reiner’s theorem relating Betti numbers of the Stanley-Reisner ideal of a simplicial complex and the CM_t property of its Alexander dual. Then we characterize bi-CM_t bipartite graphs and bi-CM_t chordal graphs. These are generalizations of recent results due to Herzog and Rahimi.