Narrow Results

We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O*(1.8494^m) time for 3-regular graphs, and O*(1.9706^m) time for unit interval graphs, where m is the number of edges in the graph and O*-notation ignores a polynomial factor. The algorithms can be generalized to the Tutte polynomial computation.

We consider the question of which right-angled Artin groups contain closed hyperbolic surface subgroups. It is known that a right-angled Artin group A(K) has such a subgroup if its defining graph K contains an n-hole (i.e. an induced cycle of length n) with n ≥ 5. We construct another eight "forbidden" graphs and show that every graph K on ≤ 8 vertices either contains one of our examples, or contains a hole of length ≥ 5, or has the property that A(K) does not contain hyperbolic closed surface subgroups. We also provide several sufficient conditions for a right-angled Artin group to contain no hyperbolic surface subgroups.

We prove that for one of these "forbidden" subgraphs P₂(6), the right-angled Artin group A(P₂(6)) is a subgroup of a (right-angled Artin) diagram group. Thus we show that a diagram group can contain a non-free hyperbolic subgroup answering a question of Guba and Sapir. We also show that fundamental groups of non-orientable surfaces can be subgroups of diagram groups. Thus the first integral homology of a subgroup of a diagram group can have torsion (all homology groups of all diagram groups are free Abelian by a result of Guba and Sapir).

A binomial f belonging to a toric ideal I is indispensable if, for any system of binomial generators of I, either f or -f belongs to . In the present paper, we study indispensable binomials of the toric ideals I_G arising from a finite graph G. First, we show that the toric ideal I_G arising from a finite graph G whose complementary graph is weakly chordal is generated by the indispensable binomials if and only if no complete graph of order ≥4 is a subgraph of G. Second, we completely classify indispensable binomials of the toric ideal I_G arising from a finite graph G satisfying the odd cycle condition. Finally, the existence of indispensable binomials of I_G will be discussed.

The graphs in which every minimal vertex separator induces a complete or an edgeless subgraph are shown to be the edge sums of graphs of the two extreme types: (i) when every minimal vertex separator induces a complete subgraph — these are precisely the well-studied chordal graphs — and (ii) when every minimal vertex separator induces an edgeless subgraph — these have appeared in several recent papers.

A subset L ⊆ V of a graph G = (V, E) is called a connected liar's dominating set of G if (i) for all v ∈ V, |N_G[v] ∩ L| ≥ 2, (ii) for every pair u, v ∈ V of distinct vertices, |(N_G[u]∪N_G[v])∩L| ≥ 3, and (iii) the induced subgraph of G on L is connected. In this paper, we initiate the algorithmic study of minimum connected liar's domination problem by showing that the corresponding decision version of the problem is NP-complete for general graph. Next we study this problem in subclasses of chordal graphs where we strengthen the NP-completeness of this problem for undirected path graph and prove that this problem is linearly solvable for block graphs. Finally, we propose an approximation algorithm for minimum connected liar's domination problem and investigate its hardness of approximation in general graphs.

Although the notion of a two-pair (a pair of vertices between which all induced paths have length 2) was invented for the class of weakly chordal graphs, two-pairs can also play a fundamental role for smaller graph classes. Indeed, two-pairs and chords of cycles can collaborate symmetrically to give parallel characterizations of weakly chordal, chordal, and strongly chordal graphs (and of distance-hereditary graphs).

An $i$-chord of a cycle $C$ is a chord that forms a new cycle with a length-$i$ subpath of $C$ when $i$ is at most half the length of $C$. Define a graph to be $s$-strongly chordal if, for every $i\in \{2,\dots ,s+2\}$, every cycle long enough to have an $i$-chord always has an $i$-chord. The $0$-strongly chordal and $1$-strongly chordal graphs are, respectively, the chordal and strongly chordal graphs. Several characterizations of $s$-strongly chordal graphs are proved, along with details of the class of $2$-strongly chordal graphs.

Define a new class of graphs by cycles of length 5 or more always having adjacent chords. This is equivalent to cycles of length 5 or more always having noncrossing chords, which is a property that has a known forbidden induced subgraph characterization. Another characterization comes from viewing the graphs in this class in contrast to distance-hereditary graphs (which are characterized by cycles of length 5 or more always having crossing chords). Moreover, the graphs in the new class are those in which every edge of every cycle $C$ of length 5 or more forms a triangle with a third vertex of $C$ (generalizing that a graph is chordal if and only if every edge of every cycle $C$ of length 4 or more forms a triangle with a third vertex of $C$). This leads to a strategically-required subgraph characterization of the new class.

A $k$ vertex coloring of a graph $G=(V,E)$ partitions the vertex set into $k$ color classes (or independent sets). In minimum vertex coloring problem, the aim is to minimize the number of colors used in a given graph. Here, we consider three variations of vertex coloring problem in which (i) each vertex in $G$ dominates a color class, (ii) each color class is dominated by a vertex and (iii) each vertex is dominating a color class and each color class is dominated by a vertex. These minimization problems are known as Min-Dominator-Coloring, Min-CD-Coloring and Min-Domination-Coloring, respectively. In this paper, we present approximation hardness results for these problems for some restricted class of graphs.

Given finite simple graph one can associate the edge ideal. In this paper we discuss the non-vanishingness of the graded Betti numbers of edge ideals in terms of the original graph. In particular, we give a necessary and sufficient condition for a chordal graph on which the graded Betti number does not vanish and characterize the graded Betti number for a forest. Moreover we characterize the projective dimension for a chordal graph.