Search

A network N on a finite set X, |X| ≥ 2, is a connected directed acyclic graph with leaf set X in which every root in N has outdegree at least 2 and no vertex in N has indegree and outdegree equal to 1; N is arboreal if the underlying unrooted, undirected graph of N is a tree. Networks are of interest in evolutionary biology since they are used, for example, to represent the evolutionary history of a set X of species whose ancestors have exchanged genes in the past. For M some arbitrary set of symbols, d : (2X) → M ∪ {ʘ} is a symbolic arboreal map if there exists some arboreal network N whose vertices with outdegree 2 or more are labeled by elements in M and so that d({x,y}), {x,y} ∈ (2X), is equal to the label of the least common ancestor of x and y in N if this exists, and ʘ otherwise. Important examples of symbolic arboreal maps include the symbolic ultrametrics, which arise in areas such as game theory, phylogenetics, and cograph theory. In this paper we show that a map d : (2X) → M ∪ {ʘ} is a symbolic arboreal map if and only if d satisfies certain 3- and 4-point conditions and the graph with vertex set X and edge set consisting of those pairs {x,y} ∈ (2X) with d({x,y}) ≠ ʘ is Ptolemaic (i.e., its shortest path distance satisfies Ptolemy's inequality). To do this, we introduce and prove a key theorem concerning the shared ancestry graph for a network N on X, where this is the graph with vertex set X and edge set consisting of those {x,y} ∈ (2X) such that x and y share a common ancestor in N. In particular, we show that for any connected graph G with vertex set X and edge clique cover K in which there are no two distinct sets in K with one a subset of the other, there is some network with |K| roots and leaf set X whose shared ancestry graph is G. [ABSTRACT FROM AUTHOR]

The interval function and the induced path function are two well studied class of set functions of a connected graph having interesting properties and applications to convexity, metric graph theory. Both these functions can be framed as special instances of a general set function termed as a transit function defined on the Cartesian product of a non-empty set \(V\) to the power set of \(V\) satisfying the expansive, symmetric and idempotent axioms. In this paper, we propose a set of independent first order betweenness axioms on an arbitrary transit function and provide characterization of the interval function of Ptolemaic graphs and the induced path function of chordal graphs in terms of an arbitrary transit function. This in turn gives new characterizations of the Ptolemaic and chordal graphs.

The interval function and the induced path function are two well studied class of set functions of a connected graph having interesting properties and applications to convexity, metric graph theory. Both these functions can be framed as special instances of a general set function termed as a transit function defined on the Cartesian product of a non-empty set V to the power set of V satisfying the expansive, symmetric and idempotent axioms. In this paper, we propose a set of independent first order betweenness axioms on an arbitrary transit function and provide characterization of the interval function of Ptolemaic graphs and the induced path function of chordal graphs in terms of an arbitrary transit function. This in turn gives new characterizations of the Ptolemaic and chordal graphs. [ABSTRACT FROM AUTHOR]

For a family of graphs F , Weighted F -Deletion is the problem for which the input is a vertex weighted graph G = (V , E) and the goal is to delete S ⊆ V with minimum weight such that G \ S ∈ F . Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs. In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when F is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolemaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of Feedback Vertex Set that exploits this relationship (named Feedback Vertex Set with Precedence Constraints), each of which may be of independent interest. [ABSTRACT FROM AUTHOR]

Cover-Incomparability graphs (C-I graphs) are graphs whose edge-set is the union of edge-sets of incomparability graph and the cover graph of some poset. We give a new characterization of Ptolemaic C-I graphs and prove that each C-I graph contains a Ptolemaic C-I graph as a spanning subgraph. This result is used to present several necessary conditions for a graph G being planar C-I graph. We present a hierarchy of subfamilies of chordal graphs in the class of C-I graphs and prove that many different graph families coincide in the class of C-I graphs. [ABSTRACT FROM AUTHOR]

Let G be a graph and lpt ( G ) be the size of the smallest set S ⊆ V ( G ) such that every longest path of G has at least one vertex in S . If lpt ( G ) = 1, then all longest paths of G have non-empty intersection. In this work, we prove that this holds for some graph classes, including ptolemaic graphs, P 4 -sparse graphs, and starlike graphs, generalizing the existing result for split graphs. [ABSTRACT FROM AUTHOR]

We give a complete characterization of bipartite graphs having tree-like Galois lattices. We prove that the poset obtained by deleting bottom and top elements from the Galois lattice of a bipartite graph is tree-like if and only if the graph is a bipartite distance hereditary graph. Relations with the class of Ptolemaic graphs are discussed and exploited to give an alternative proof of the result. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we deal with cover–incomparability graphs of posets, or briefly C–I graphs. These are graphs derived from posets as the edge-union of their cover graph and their incomparability graph. We answer two recently posed open questions. Which distance-hereditary graphs are C–I graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are C–I graphs? It follows that C–I graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing C–I graphs in general is known to be NP-complete. [Copyright &y& Elsevier]

Let G be a connected graph. A subset X of V(G) is g-convex (m-convex) if it contains all vertices on shortest (induced) paths between vertices in X. We state characteristic properties of graphs in which every g-convex set is m-convex, based on which we show that such graphs can be recognized in polynomial time. Moreover, we state a new convexity-theoretic characterization of Ptolemaic graphs. [ABSTRACT FROM AUTHOR]

Abstract: Leaf powers are a graph class which has been introduced to model the problem of reconstructing phylogenetic trees. A graph is called -leaf power if it admits a -leaf root, i.e., a tree with leaves such that is an edge in if and only if the distance between and in is at most . Moroever, a graph is simply called leaf power if it is a -leaf power for some . This paper characterizes leaf powers in terms of their relation to several other known graph classes. It also addresses the problem of deciding whether a given graph is a -leaf power. We show that the class of leaf powers coincides with fixed tolerance NeST graphs, a well-known graph class with absolutely different motivations. After this, we provide the largest currently known proper subclass of leaf powers, i.e, the class of rooted directed path graphs. Subsequently, we study the leaf rank problem, the algorithmic challenge of determining the minimum for which a given graph is a -leaf power. Firstly, we give a lower bound on the leaf rank of a graph in terms of the complexity of its separators. Secondly, we use this measure to show that the leaf rank is unbounded on both the class of ptolemaic and the class of unit interval graphs. Finally, we provide efficient algorithms to compute -leaf roots for given ptolemaic or (unit) interval graphs . [Copyright &y& Elsevier]

Abstract: In a graph, a vertex is simplicial if its neighborhood is a clique. For an integer , a graph is the -simplicial power of a graph ( a root graph of ) if is the set of all simplicial vertices of , and for all distinct vertices and in , if and only if the distance in between and is at most . This concept generalizes -leaf powers introduced by Nishimura, Ragde and Thilikos which were motivated by the search for underlying phylogenetic trees; -leaf powers are the -simplicial powers of trees. Recently, a lot of work has been done on -leaf powers and their roots as well as on their variants phylogenetic roots and Steiner roots. For , -leaf powers can be recognized in linear time, and for , structural characterizations are known. For , the recognition and characterization problems of -leaf powers are still open. Since trees and block graphs (i.e., connected graphs whose blocks are cliques) have very similar metric properties, it is natural to study -simplicial powers of block graphs. We show that leaf powers of trees and simplicial powers of block graphs are closely related, and we study simplicial powers of other graph classes containing all trees such as ptolemaic graphs and strongly chordal graphs. [Copyright &y& Elsevier]

Abstract: Ptolemaic graphs are those satisfying the Ptolemaic inequality for any four vertices. The graph class coincides with the intersection of chordal graphs and distance hereditary graphs. It can also be seen as a natural generalization of block graphs (and hence trees). In this paper, we first state a laminar structure of cliques, which leads to its canonical tree representation. This result is a translation of -acyclicity which appears in the context of relational database schemes. The tree representation gives a simple intersection model of ptolemaic graphs, and it is constructed in linear time from a perfect elimination ordering obtained by the lexicographic breadth first search. Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time. Using the tree representation, we also give an efficient algorithm for the Hamiltonian cycle problem. [Copyright &y& Elsevier]