Search

A graph is called split if its vertex set can be partitioned into a stable set and a clique. In this article, we studied two variants of split graphs. A graph G is polar if its vertex set can be partitioned into two sets A and B such that G[A] is a complete multipartite graph and G[B] is a disjoint union of complete graphs. A 2-unipolar graph is a polar graph G such that G[A] is a clique and G[B] is the disjoint union of complete graphs with at most two vertices. We present a minimal forbidden induced subgraph characterization for 2-unipolar graphs. In addition, we show that they can be represented as an intersection of substars of special cacti. Let G be a graph class, the G-width of a graph G is the minimum positive integer k such that there exist k independent sets N1, ... , Nk such that a set F of nonedges of G, whose endpoints belong to some Ni with i = 1, ... , k, can be added so that the resulting graph G′ belongs to G. We say that a graph G is k-probe-G if it has G-width at most k and when G is the class of split graphs it is denominated k-probe-split. We prove that deciding, given a graph G and a positive integer k, whether G is a h-probe-split graph for some h ≤ k is NP-complete. Besides, a characterization by minimal forbidden induced subgraphs for 2-probe-split cographs is presented. [ABSTRACT FROM AUTHOR]

Two graphs having the same spectrum are said to be cospectral. A pair of singularly cospectral graphs is formed by two graphs such that the absolute values of their nonzero eigenvalues coincide. Clearly, a pair of cospectral graphs is also singularly cospectral but the converse may not be true. Two graphs are almost cospectral if their nonzero eigenvalues and their multiplicities coincide. In this paper, we present necessary and sufficient conditions for a pair of graphs to be singularly cospectral, giving an answer to a problem posted by Nikiforov. In addition, we construct an infinite family of pairs of noncospectral singularly cospectral graphs with unbounded number of vertices. It is clear that almost cospectral graphs are also singularly cospectral but the converse is not necessarily true, we present families of graphs where both concepts: almost cospectrality and singularly cospectrality agree. [ABSTRACT FROM AUTHOR]

A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non-(probe 풢) graphs with disconnected complement for every graph class 풢 with a companion. [ABSTRACT FROM AUTHOR]

Abstract: A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, -tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property. [Copyright &y& Elsevier]