Search

A family of sets is (p , q) - intersecting if every nonempty subfamily of p or fewer sets has at least q elements in its total intersection. A family of sets has the (p , q) - Helly property if every nonempty (p , q) -intersecting subfamily has total intersection of cardinality at least q. The (2 , 1) -Helly property is the usual Helly property. A hypergraph is (p , q) - Helly if its edge family has the (p , q) -Helly property and hereditary (p , q) -Helly if each of its subhypergraphs has the (p , q) -Helly property. A graph is (p , q) - clique-Helly if the family of its maximal cliques has the (p , q) -Helly property and hereditary (p , q) -clique-Helly if each of its induced subgraphs is (p , q) -clique-Helly. The classes of (p , q) - biclique-Helly and hereditary (p , q) -biclique-Helly graphs are defined analogously. In this work, we prove several characterizations of hereditary (p , q) -Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. On the algorithmic side, we give an improved time bound for the recognition of (p , q) -Helly hypergraphs for each fixed q and show that the recognition of hereditary (p , q) -Helly hypergraphs can be solved in polynomial time if p and q are fixed and co-NP-complete if p is part of the input. In addition, we generalize the characterization of p -clique-Helly graphs in terms of expansions to (p , q) -clique-Helly graphs and give different characterizations of hereditary (p , q) -clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of (p , q) -clique-Helly graphs and prove that the recognition problem of hereditary (p , q) -clique-Helly graphs is polynomial-time solvable for p and q fixed and NP-hard if p or q is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (p , q) -biclique-Helly graphs and hereditary (p , q) -biclique-Helly graphs which are analogous to those for (p , q) -clique-Helly and hereditary (p , q) -clique-Helly graphs. [ABSTRACT FROM AUTHOR]

Let G be a connected graph on n vertices and D (G) be 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 of any graph whose block decomposition consists of edges, unicyclic and bicyclic graphs. [ABSTRACT FROM AUTHOR]

A graph G is a probe unit interval graph if its vertex set can be partitioned into a set P of probe vertices and a stable set N of nonprobe vertices, so that a unit interval graph can be obtained by adding a set of edges whose endpoints belong to N. A partitioned graph is a graph having a prescribed partition into P and N. In this article we present structural characterizations for those partitioned interval graphs and unpartitioned interval graphs which are probe unit interval graphs, in terms of certain characteristics of their interval models. These characterizations lead to characterizations of probe unit interval graphs within the class of interval graphs by minimal forbidden induced subgraphs. [ABSTRACT FROM AUTHOR]

A normal Helly circular-arc graph is the intersection graph of a set of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. (2013) characterized circular-arc graphs that are not normal Helly circular-arc graphs, and used them to develop the first recognition algorithm for this graph class. As open problems, they ask for the forbidden subgraph characterization and a direct recognition algorithm for normal Helly circular-arc graphs, both of which are resolved by the current paper. Moreover, when the input is not a normal Helly circular-arc graph, our recognition algorithm finds in linear time a minimal forbidden induced subgraph as a certificate. Our approach yields also a considerably simpler algorithm for the certifying recognition of proper Helly circular-arc graphs, a subclass of normal Helly circular-arc graphs. [ABSTRACT FROM AUTHOR]

We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers k and ℓ such that the k th powers of the graphs are of clique-width at most ℓ . We give sufficient and necessary conditions for this property. As our main results, we characterize graph classes of power-bounded clique-width within classes defined by either one forbidden induced subgraph, or by two connected forbidden induced subgraphs. We also show that for every positive integer k , there exists a graph class such that the k th powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power. [ABSTRACT FROM AUTHOR]

A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X . We prove that for fixed p ≥ 1 , all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time. [ABSTRACT FROM AUTHOR]

• Rank behavior of distance matrices. • Nullity of the distance matrix of threshold graphs. • Nullity of the distance matrix of trivially perfect graphs. Let G be a connected graph with V (G) = { v 1 , ... , v n }. The (i , j) -entry of the distance matrix D (G) of G is the distance between v i and v j. In this article, using the well-known Ramsey's theorem, we prove that for each integer k ≥ 2 , there is a finite amount of graphs whose distance matrices have rank k. We exhibit the list of graphs with distance matrices of rank 2 and 3. Besides, we study the rank of the distance matrices of graphs belonging to a family of graphs with their diameters at most two, the trivially perfect graphs. We show that for each η ≥ 1 there exists a trivially perfect graph with nullity η. We also show that for threshold graphs, which are a subfamily of the family of trivially perfect graphs, the nullity is bounded by one. [ABSTRACT FROM AUTHOR]

Abstract: Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are the intersection graphs of chords on a circle. These graph classes have been the subject of much study for many years and numerous interesting results have been reported. Many subclasses of both circular-arc graphs and circle graphs have been defined and different characterizations formulated. In this survey, we summarize the most important structural results related to circular-arc graphs and circle graphs and present the main open problems. [Copyright &y& Elsevier]

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]

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]

Let B (n , q) be the class of block graphs on n vertices having all their blocks of the same size. We prove that if G ∈ B (n , q) has at most three pairwise adjacent cut vertices then the minimum spectral radius ρ (G) is attained at a unique graph. In addition, we present a lower bound for ρ (G) when G ∈ B (n , q). [ABSTRACT FROM AUTHOR]

Let G (n , α) be the class of block graphs on n vertices and prescribed independence number α. In this article we prove that the maximum spectral radius ρ (G) , among all graphs G ∈ G (n , α) , is reached at a unique graph. As a byproduct we obtain an upper for ρ (G) , when G ∈ G (n , α). [ABSTRACT FROM AUTHOR]

In this paper, we study the most basic domination invariants in graphs, in which number 2 is intrinsic part of their definitions. We classify them upon three criteria, two of which give the following previously studied invariants: the weak 2 -domination number, γ w 2 ( G ) , the 2 -domination number, γ 2 ( G ) , the { 2 } -domination number, γ { 2 } ( G ) , the double domination number, γ × 2 ( G ) , the total { 2 } -domination number, γ t { 2 } ( G ) , and the total double domination number, γ t × 2 ( G ) , where G is a graph in which the corresponding invariant is well defined. The third criterion yields rainbow versions of the mentioned six parameters, one of which has already been well studied, and three other give new interesting parameters. Together with a special, extensively studied Roman domination, γ R ( G ) , and two classical parameters, the domination number, γ ( G ) , and the total domination number, γ t ( G ) , we consider 13 domination invariants in graphs. In the main result of the paper we present sharp upper and lower bounds of each of the invariants in terms of every other invariant, a large majority of which are new results proven in this paper. As a consequence of the main theorem we obtain new complexity results regarding the existence of approximation algorithms for the studied invariants, matched with tight or almost tight inapproximability bounds, which hold even in the class of split graphs. [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]

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König–Egerváry property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász’s result to a characterization of all graphs having the König–Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König–Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs. [ABSTRACT FROM AUTHOR]