Connected graphs of fixed order and size with maximal index: Some spectral bounds

The index (or spectral radius) of a simple graph is the largest eigenvalue of its adjacency matrix. For connected graphs of fixed order and size the graphs with maximal index are not yet identified (in the general case). It is known (for a long time) that these graphs are nested split graphs (or threshold graphs). In this paper we use the eigenvector techniques for getting some new (lower and upper) bounds on the index of nested split graphs. Besides we give some computational results in order to compare these bounds.     

Minimal Classes of Graphs of Unbounded Clique-Width

In the present paper, we identify the first two minimal with respect to set-inclusion hereditary classes of graphs of unbounded clique-width: Bipartite permutation graphs and unit interval graphs.     

Threshold tolerance graphs

In this paper, we introduce a class of graphs that generalize threshold graphs by introducing threshold tolerances. Several characterizations of these graphs are presented, one of which leads to a polynomial-time recognition algorithm. It is also shown that the complements of these graphs contain interval graphs and threshold graphs, and are contained in the subclass of chordal graphs called strongly chordal graphs, and in the class of interval tolerance graphs.     

Polar permutation graphs are polynomial-time recognisable

Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP$\text{NP}$-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP$\text{NP}$-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

The principal Erdős–Gallai differences of a degree sequence

The Erd?s–Gallai criteria for recognizing degree sequences of simple graphs involve a system of inequalities. Given a fixed degree sequence, we consider the list of differences of the two sides of these inequalities. These differences have appeared in varying contexts, including characterizations of the split and threshold graphs, and we survey their uses here. Then, enlarging upon properties of these graph families, we show that both the last term and the maximum term of the principal Erd?s–Gallai differences of a degree sequence are preserved under graph complementation and are monotonic under the majorization order and Rao's order on degree sequences.     

Minimal split completions

We study the problem of adding an inclusion minimal set of edges to a given arbitrary graph so that the resulting graph is a split graph, called a minimal split completion of the input graph. Minimal completions of arbitrary graphs into chordal and interval graphs have been studied previously, and new results have been added recently. We extend these previous results to split graphs by giving a linear-time algorithm for computing minimal split completions. We also give two characterizations of minimal split completions, which lead to a linear time algorithm for extracting a minimal split completion from any given split completion.We prove new properties of split graph that are both useful for our algorithms and interesting on their own. First, we present a new way of partitioning the vertices of a split graph uniquely into three subsets. Second, we prove that split graphs have the following property: given two split graphs on the same vertex set where one is a subgraph of the other, there is a sequence of edges that can be removed from the larger to obtain the smaller such that after each edge removal the modified graph is split.     

Distance-Hereditary Comparability Graphs

We study the class of the distance-hereditary comparability graphs, that is, those graphs which admit a transitive orientation and are completely decomposable with respect to the split decomposition. We provide a characterization in terms of forbidden subgraphs. We also provide further characterizations and one of them, based on the split decomposition, is used to devise a recognizing algorithm working in linear time. Finally, we show how to build distance-hereditary comparability graphs.     

Graph Sandwich Problems

The graph sandwich problem for property Π is defined as follows: Given two graphs G¹ = (V, E¹) and G² = (V, E²) such that E¹ E², is there a graph G = (V, E) such that E¹ E E² which satisfies property Π? Such problems generalize recognition problems and arise in various applications. Concentrating mainly on properties characterizing subfamilies of perfect graphs, we give polynomial algorithms for several properties and prove the NP-completeness of others. We describe polynomial time algorithms for threshold graphs, split graphs, and cographs. For the sandwich problem for threshold graphs, the only case in which a previous algorithm existed, we obtain a faster algorithm. NP-completeness proofs are given for comparability graphs, permutation graphs, and several other families. For Eulerian graphs; one Version of the problem is polynomial and another is NP-complete.     

Rank‐tolerance graph classes

In this article we introduce certain classes of graphs that generalize ?‐tolerance chain graphs. In a rank‐tolerance representation of a graph, each vertex is assigned two parameters: a rank, which represents the size of that vertex, and a tolerance which represents an allowed extent of conflict with other vertices. Two vertices are adjacent if and only if their joint rank exceeds (or equals) their joint tolerance. This article is concerned with investigating the graph classes that arise from a variety of functions, such as min, max, sum, and prod (product), that may be used as the coupling functions ? and ρ to define the joint tolerance and the joint rank. Our goal is to obtain basic properties of the graph classes from basic properties of the coupling functions. We prove a skew symmetry result that when either ? or ρ is continuous and weakly increasing, the (?,ρ)‐representable graphs equal the complements of the (ρ,?)‐representable graphs. In the case where either ? or ρ is Archimedean or dual Archimedean, the class contains all threshold graphs. We also show that, for min, max, sum, prod (product) and, in fact, for any piecewise polynomial ?, there are infinitely many split graphs which fail to be representable. In the reflexive case (where ? = ρ), we show that if ? is nondecreasing, weakly increasing and associative, the class obtained is precisely the threshold graphs. This extends a result of Jacobson, McMorris, and Mulder [10] for the function min to a much wider class, including max, sum, and prod. We also give results for homogeneous functions, powers of sums, and linear combinations of min and max. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Some notes on the threshold graphs

In this paper we consider threshold graphs (also called nested split graphs) and investigate some invariants of these graphs which can be of interest in bounding the largest eigenvalue of some graph spectra.     

Canonical Antichains of Unit Interval and Bipartite Permutation Graphs

We study unit interval graphs and bipartite permutation graphs partially ordered by the induced subgraph relation. It is known that neither of these classes is well-quasi-ordered, since each of them contains an infinite antichain. We show that in both cases the antichains are canonical in the sense that any subclass of unit interval or bipartite permutation graphs containing only finitely many graphs from the respective antichain is well-quasi-ordered.     

Intersection Dimensions of Graph Classes

The intersection dimension of a graphG with respect to a classA of graphs is the minimumk such thatG is the intersection of at mostk graphs on vertex setV(G) each of which belongs toA. We consider the question when the intersection dimension of a certain family of graphs is bounded or unbounded. Our main results are (1) ifA is hereditary, i.e., closed on induced subgraphs, then the intersection dimension of all graphs with respect toA is unbounded, and (2) the intersection dimension of planar graphs with respect to the class of permutation graphs is bounded. We also give a simple argument based on [Ben-Arroyo Hartman, I., Newman, I., Ziv, R.:On grid intersection graphs, Discrete Math.87 (1991) 41-52] why the boxicity (i.e., the intersection dimension with respect to the class of interval graphs) of planar graphs is bounded. Further we study the relationships between intersection dimensions with respect to different classes of graphs.     

Some further bounds for the Q-index of nested split graphs

The Q-index of a simple graph is the largest eigenvalue of its signless Laplacian, or Q-matrix. In our previous paper [1] we gave three lower and three upper bounds for the Q-index of nested split graphs, also known as threshold graphs. In this paper, we give another two upper bounds, which are expressed as solutions of cubic equations (in contrast to quadratics from [1]). Some computational results are also included.     

Coloring permutation graphs in parallel

A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log² n) time using O(n²/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T^*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree.     

On superperfect noncomparability graphs

The class of superperfect graphs, which was previously studied by A. J. Hoffman, E. L. Johnson, and M. C. Golumbic, is a proper subclass of the class of perfect graphs; further, it properly contains the class of comparability graphs. In his book, Golumbic proves that, for split graphs, G is a comparability graph if and only if G is superperfect. Moreover, the fact that split graphs are exactly those graphs which are both triangulated and cotriangulated motivated Golumbic to ask if it is true or false that, for triangulated (or cotriangulated) graphs, G is a comparability graph if and only if G is superperfect. In the present paper, we determine those members of Gallai's list of minimal noncomparability graphs which are superperfect and, as a consequence, we find that the answer to the above question is “false” for triangulated and “true” for cotriangulated graphs.     

Linear Clique‐Width for Hereditary Classes of Cographs

The class of cographs is known to have unbounded linear clique‐width. We prove that a hereditary class of cographs has bounded linear clique‐width if and only if it does not contain all quasi‐threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.     

Connected signed graphs of fixed order,size, and number of negative edges with maximal index

In this paper we focus on connected signed graphs of fixed number of vertices, positive edges and negative edges that maximize the largest eigenvalue (also called the index) of their adjacency matrix. In the first step we determine these signed graphs in the set of signed generalized theta graphs. Concerning the general case, we use the eigenvector techniques for getting some structural properties of resulting signed graphs. In particular, we prove that positive edges induce nested split subgraphs, while negative edges induce double nested signed subgraphs. We observe that our concept can be applied when considering balancedness of signed graphs (the property that is extensively studied in both mathematical and non-mathematical context).     

On natural isomorphisms of cycle permutation graphs

Two problems are approached in this paper. Given a permutation onn elements, which permutations onn elements yield cycle permutation graphs isomorphic to the cycle permutation graph yielded by the given permutation? And, given two cycle permutation graphs, are they isomorphic? Here the author deals only with natural isomorphisms, those isomorphisms which map the outer and inner cycles of one cycle permutation graph to the outer and inner cycles of another cycle permutation graph. A theorem is stated which then allows the construction of the set of permutations which yield cycle permutation graphs isomorphic to a given cycle permutation graph by a natural isomorphism. Another theorem is presented which finds the number of such permutations through the use of groups of symmetry of certain drawings of cycles in the plane. These drawings are also used to determine whether two given cycle permutation graphs are isomorphic by a natural isomorphism. These two methods are then illustrated by using them to solve the first problem, restricted to natural isomorphism, for a certain class of cycle permutation graphs.     

On a generalized model of labeled graphs

Labeled graphs have applications in algorithms for reconstructing chains that have been split into smaller parts. Chain reconstruction is a common problem in biochemistry and bioinformatics, particularly for sequencing DNA or peptide chains. Labeled graphs (in the sense defined in this paper) have also the important structural property which allows to reduce the Hamiltonian path problem to Eulerian path problem. This work introduces a model and properties of a class of base-labeled graphs that unify the properties of labeled and free-labeled graphs (B?a?ewicz et al., 1999) [1]. It describes the basic relationships between those classes and some of their applications. It also introduces lexical graphs which are the superclass of de Bruijn graphs. Lexical graphs keep many properties of de Bruijn graphs which have a wide area of applications e.g. in mathematics, electronics and computing sciences.