Search

Let $G$ be a graph having a vertex $v$ such that $H = G - v$ is a trivially perfect graph. We give a polynomial-time algorithm for the problem of deciding whether it is possible to add at most $k$ edges to $G$ to obtain a trivially perfect graph. This is a slight variation of the well-studied {\sc Edge Completion}, also known as {\sc Minimum Fill-In}, problem. We also show that if $H$ is a chordal graph, then the problem of deciding whether it is possible to add at most $k$ edges to $G$ to obtain a chordal graph is \NP-complete., Comment: 23 pages, 1 figures

The edge-connectivity of a graph is the minimum number of edges whose deletion disconnects the graph. Let $��(G)$ the maximum degree of a graph $G$ and let $��(G)$ be the spectral radius of $G$. In this article we present a lower bound for $��(G)-��(G)$ in terms of the edge connectivity of $G$, where $G$ is a nonregular distance-hereditary graph. We also prove that $��(G)$ reaches the maximum at a unique graph in $\mathcal G$, when $\vert V(G)\vert = n$, and $\mathcal G$ either is in the class of graphs with bounded tree-width or is in the class of block graphs with prescribed independence number.

Let $G$ be a connected graph on $n$ vertices and $D(G)$ its distance matrix. The formula for computing the determinant of this matrix in terms of the number of vertices is known when the graph is either a tree or {a} unicyclic graph. In this work we generalize these results, obtaining the determinant of the distance matrix for {all graphs} in a {class, including trees, unicyclic and bicyclic graphs. This class actually includes graphs with many cycles, provided that each block of the graph is at most bicyclic.}

An interval graph is the intersection graph of a finite set of intervals on a line and a circular-arc graph is the intersection graph of a finite set of arcs on a circle. While a forbidden induced subgraph characterization of interval graphs was found fifty years ago, finding an analogous characterization for circular-arc graphs is a long-standing open problem. In this work, we study the intersection graphs of finite sets of arcs on a circle no three of which cover the circle, known as normal Helly circular-arc graphs. Those circular-arc graphs which are minimal forbidden induced subgraphs for the class of normal Helly circular-arc graphs were identified by Lin, Soulignac, and Szwarcfiter, who also posed the problem of determining the remaining minimal forbidden induced subgraphs. In this work, we solve their problem, obtaining the complete list of minimal forbidden induced subgraphs for the class of normal Helly circular-arc graphs., Comment: 15 pages, 3 figures. This paper originally appeared in proceedings of the XVI Congreso Latino-Iberoamericano de Investigaci\'on Operativa and the XLIV Simp\'osio Brasileiro de Pesquisa Operacional, September 24-28, 2012, Rio de Janeiro, Brazil. Anais do XLIV Simposio Brasileiro de Pesquisa Operacional, SOBRAPO, Rio de Janeiro, Brazil, 2012, pages 4093--4104. http://www.din.uem.br/sbpo/sbpo2012/pdf/arq0518.pdf