Equivalences and the complete hierarchy of intersection graphs of paths in a tree

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex in G, such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at most s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted by [h,s,t]. It is well known that the class of chordal graphs corresponds to the class [3, 3, 1]. Moreover, it was proved by Jamison and Mulder that chordal graphs correspond to orthodox-[3, 3, 1] graphs defined below.In this paper, we investigate the class of [h,2,t] graphs, i.e., the intersection graphs of paths in a tree. The [h,2,1] graphs are also known as path graphs [F. Gavril, A recognition algorithm for the intersection graphs of paths in trees, Discrete Math. 23 (1978) 211-227] or VPT graphs [M.C. Golumbic, R.E. Jamison, Edge and vertex intersection of paths in a tree, Discrete Math. 55 (1985) 151-159], and [h,2,2] graphs are known as the EPT graphs. We consider variations of [h,2,t] by three main parameters: h, t and whether the graph has an orthodox representation. We give the complete hierarchy of relationships between the classes of weakly chordal, chordal, [h,2,t] and orthodox-[h,2,t] graphs for varied values of h and t.     

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.     

The intersection graphs of subtrees in trees are exactly the chordal graphs

The intersection graph of a family of subtrees in an undirected tree is called a subtree graph. A graph is called chordal if every simple circuit with more than three vertices has an edge connecting two non-consecutive vertices. In this paper, we prove that, for a graph G, the following conditions are equivalent: (i) G is a chordal graph; (ii) G is a subtree graph; (iii) G is a proper subtree graph.Consider a chordal graph G. We give an efficient algorithm for constructing a representation of G by a family of subtrees in a tree.     

Some properties of edge intersection graphs of single bend paths on a grid

We consider the family of intersection graphs G of paths on a grid, where every vertex v in G corresponds to a single bend path P_v on a grid, and two vertices are adjacent in G if and only if the corresponding paths share an edge on the grid. We first show that these graphs have the Erdös-Hajnal property. Then we present some properties concerning the neighborhood of a vertex in these graphs, and finally we consider some subclasses of chordal graphs for which we give necessary and sufficient conditions to be edge intersection graphs of single bend paths in a grid.     

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a treet-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4 and is linearly solvable for t≤2. The case t=3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a−b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners. This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed.     

Edge and vertex intersection of paths in a tree

In this paper we continue the investigation of the class of edge intersection graphs of a collection of paths in a tree (EPT graphs) where two paths edge intersect if they share an edge. The class of EPT graphs differs from the class known as path graphs, the latter being the class of vertex intersection graphs of paths in a tree. A characterization is presented here showing when a path graph is an EPT graph. In particular, the classes of path graphs and EPT graphs coincide on trees all of whose vertices have degree at most 3. We then prove that it is an NP-complete problem to recognize whether a graph is an EPT graph.     

On the interval number of a chordal graph

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum clique size ω(G) = m, then i(G) ? [1 + o(1)]m/log₂ m and this result is best possible, even for split graphs (chordal graphs whose complement is also chordal).     

On the diameter of the intersection graph of a finite simple group

Let G be a finite group. The intersection graph Δ_G of G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of G, and two distinct vertices X and Y are adjacent if X ∩ Y ≠ 1, where 1 denotes the trivial subgroup of order 1. A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters of intersection graphs of finite non-abelian simple groups have an upper bound 28. In particular, the intersection graph of a finite non-abelian simple group is connected.     

Shellable graphs and sequentially Cohen-Macaulay bipartite graphs

Associated to a simple undirected graph G is a simplicial complex ΔG whose faces correspond to the independent sets of G. We call a graph G shellable if ΔG is a shellable simplicial complex in the non-pure sense of Björner-Wachs. We are then interested in determining what families of graphs have the property that G is shellable. We show that all chordal graphs are shellable. Furthermore, we classify all the shellable bipartite graphs; they are precisely the sequentially Cohen-Macaulay bipartite graphs. We also give a recursive procedure to verify if a bipartite graph is shellable. Because shellable implies that the associated Stanley-Reisner ring is sequentially Cohen-Macaulay, our results complement and extend recent work on the problem of determining when the edge ideal of a graph is (sequentially) Cohen-Macaulay. We also give a new proof for a result of Faridi on the sequentially Cohen-Macaulayness of simplicial forests.     

Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction

A spanning tree T of a graph G is called a treet-spanner, if the distance between any two vertices in T is at most t-times their distance in G. A graph that has a tree t-spanner is called a treet-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t≥4, and is linearly solvable for t=1 and t=2. The case t=3 still remains open. A directed path graph is called a 2-sep directed path graph if all of its minimal a−b vertex separator for every pair of non-adjacent vertices a and b are of size two. Le and Le [H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (2) (1999) 81-87] showed that directed path graphs admit tree 3-spanners. However, this result has been shown to be incorrect by Panda and Das [B.S. Panda, Anita Das, On tree 3-spanners in directed path graphs, Networks 50 (3) (2007) 203-210]. In fact, this paper observes that even the class of 2-sep directed path graphs, which is a proper subclass of directed path graphs, need not admit tree 3-spanners in general. It, then, presents a structural characterization of tree 3-spanner admissible 2-sep directed path graphs. Based on this characterization, a linear time recognition algorithm for tree 3-spanner admissible 2-sep directed path graphs is presented. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep directed path graph is proposed.     

Boxicity of Halin graphs

A k-dimensional box is the Cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if G is a Halin graph that is not isomorphic to K₄, then . In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless G is isomorphic to K₄ (in which case its boxicity is 1).     

A characterization of triangle-free tolerance graphs

We prove that a triangle-free graph G is a tolerance graph if and only if there exists a set of consecutively ordered stars that partition the edges of G. Since tolerance graphs are weakly chordal, a tolerance graph is bipartite if and only if it is triangle-free. We, therefore, characterize those tolerance graphs that are also bipartite. We use this result to show that in general, the class of interval bigraphs properly contains tolerance graphs that are triangle-free (and hence bipartite).     

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.     

Connectivity of intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper, we classify finite solvable groups whose intersection graphs are not 2-connected and finite nilpotent groups whose intersection graphs are not 3-connected. Our methods are elementary.     

A vertex incremental approach for maintaining chordality

For a chordal graph G=(V,E), we study the problem of whether a new vertex u∉V and a given set of edges between u and vertices in V can be added to G so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with u, or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge uv, a characterization of the set of edges incident to u that also must be added to G along with uv. We propose a data structure that can compute and add each such set in O(n) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O(nm) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.     

On the Structure of Contractible Vertex Pairs in Chordal Graphs

An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph.     

Clique-critical graphs: Maximum size and recognition

The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K^-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete.     

SC-Hamiltonian graphs and digraphs: New necessary conditions and their impacts

A graph G on n vertices is said to be separable cost constant Hamiltonian (SC-Hamiltonian) if and only if G is Hamiltonian and for any cost matrix C=(c_(i,j)) associated with G where all tours have the same cost, there exist vectors a=(a₁,…,a_n) and b=(b₁,…,b_n) such that . In this paper we show that for symmetric digraphs strong Hamiltonicity is a necessary condition for SC-Hamiltonicity. As a surprising consequence, we prove that the symmetric digraph obtained from an undirected SC-Hamiltonian graph by edge duplication need not be SC-Hamiltonian. This settles a conjecture of Kabadi and Punnen. We then show that an undirected graph on an even number of nodes having an edge that appears in every Hamiltonian cycle cannot be SC-Hamiltonian. Using this we establish that multiple subdivision of an edge need not preserve SC-Hamiltonicity, disproving a previous claim. Further, we identify other necessary conditions for SC-Hamiltonicity and obtain new classes of SC-Hamiltonian graphs.     

Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree

Let T = (V, A) be a directed tree. Given a collection P{\mathcal{P}} of dipaths on T, we can look at the arc-intersection graph I(P,T){I(\mathcal{P},T)} whose vertex set is P{\mathcal{P}} and where two vertices are connected by an edge if the corresponding dipaths share a common arc. Monma and Wei, who started their study in a seminal paper on intersection graphs of paths on a tree, called them DE graphs (for directed edge path graphs) and proved that they are perfect. DE graphs find one of their applications in the context of optical networks. For instance, assigning wavelengths to set of dipaths in a directed tree network consists in finding a proper coloring of the arc-intersection graph. In the present paper, we give

Independent domination in chordal graphs

A graph chordal if it does not contain any cycle of length greater than three as an induced subgraph. A set of S of vertices of a graph G = (V,E) is independent if not two vertices in S are adjacent, and is dominating if every vertex in V?S is adjacent to some vertex in S. We present a linear algorithm to locate a minimum weight independent dominating set in a chordal graph with 0–1 vertex weights.