On perfectly two-edge connected graphs

This paper studies the graphs for which the 2-edge connected spanning subgraph polytope is completely described by the trivial inequalities and the so-called cut inequalities. These graphs are called perfectly 2-edge connected. The class of perfectly 2-edge connected graphs contains for instance the class of series-parallel graphs. We introduce a new class of perfectly 2-edge connected graphs. We discuss some structural properties of graphs which are (minimally with respect to some reduction operations) nonperfectly 2-edge connected. Using this we give sufficient conditions for a graph to be perfectly 2-edge connected.     

Tree loop graphs

Many problems involving DNA can be modeled by families of intervals. However, traditional interval graphs do not take into account the repeat structure of a DNA molecule. In the simplest case, one repeat with two copies, the underlying line can be seen as folded into a loop. We propose a new definition that respects repeats and define loop graphs as the intersection graphs of arcs of a loop. The class of loop graphs contains the class of interval graphs and the class of circular-arc graphs. Every loop graph has interval number 2. We characterize the trees that are loop graphs. The characterization yields a polynomial-time algorithm which given a tree decides whether it is a loop graph and, in the affirmative case, produces a loop representation for the tree.     

Algorithms for recognition of regular properties and decomposition of recursive graph families

This paper focuses on two themes within the broad context of recursively definable graph classes. First, we generalize the series-parallel operations and establish exactly how far they can be extended subject to some consistency conditions. We show explicitly how Halin graphs are included in the extension. Second, for recursively constructed graphs in general, we construct a predicate calculus within which graph problems can be stated and for those so stated, a linear time algorithm exists and can be automatically generated. We discuss some issues related to practical automatic generation.     

Laplacian Spectrum of Weakly Quasi-threshold Graphs

In this paper we study the class of weakly quasi-threshold graphs that are obtained from a vertex by recursively applying the operations (i) adding a new isolated vertex, (ii) adding a new vertex and making it adjacent to all old vertices, (iii) disjoint union of two old graphs, and (iv) adding a new vertex and making it adjacent to all neighbours of an old vertex. This class contains the class of quasi-threshold graphs. We show that weakly quasi-threshold graphs are precisely the comparability graphs of a forest consisting of rooted trees with each vertex of a tree being replaced by an independent set. We also supply a quadratic time algorithm in the the size of the vertex set for recognizing such a graph. We completely determine the Laplacian spectrum of weakly quasi-threshold graphs. It turns out that weakly quasi-threshold graphs are Laplacian integral. As a corollary we obtain a closed formula for the number of spanning trees in such graphs. A conjecture of Grone and Merris asserts that the spectrum of the Laplacian of any graph is majorized by the conjugate of the degree sequence of the graph. We show that the conjecture holds for cographs. Prof. Bapat and Prof. Pati take this opportunity to thank the Indian Institute of Technology Kanpur for the invitation. The authors also wish to thank the Department of Science and Technology, New Delhi for the project grant.     

Graph theoretic approach to parallel gene assembly

We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or −. In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs can be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic.     

Absolute retracts and varieties generated by chordal graphs

Graphs that are retracts of each supergraph in which they are isometric are called absolute retracts with respect to isometry, and their structure is well understood; for instance, in terms of building blocks (paths) and operations (products and retractions). We investigate the larger class of graphs that are retracts of each supergraph in which all of their holes are left unfilled. These are the absolute retracts with respect to holes, and we investigate their structure in terms of the same operations of products and retractions. We focus on a particular kind of hole (called a stretched hole), and describe a class of simple building blocks of the corresponding absolute retracts. Surprisingly, these also turn out to be precisely those absolute retracts that can be built from chordal graphs. Monophonic convexity is used to analyse holes on chordal graphs.     

On Spin Models,Triply Regular Association Schemes,and Duality

Motivated by the construction of invariants of links in 3-space, we study spin models on graphs for which all edge weights (considered as matrices) belong to the Bose-Mesner algebra of some association scheme. We show that for series-parallel graphs the computation of the partition function can be performed by using series-parallel reductions of the graph appropriately coupled with operations in the Bose-Mesner algebra. Then we extend this approach to all plane graphs by introducing star-triangle transformations and restricting our attention to a special class of Bose-Mesner algebras which we call exactly triply regular. We also introduce the following two properties for Bose-Mesner algebras. The planar duality property (defined in the self-dual case) expresses the partition function for any plane graph in terms of the partition function for its dual graph, and the planar reversibility property asserts that the partition function for any plane graph is equal to the partition function for the oppositely oriented graph. Both properties hold for any Bose-Mesner algebra if one considers only series-parallel graphs instead of arbitrary plane graphs. We relate these notions to spin models for link invariants, and among other results we show that the Abelian group Bose-Mesner algebras have the planar duality property and that for self-dual Bose-Mesner algebras, planar duality implies planar reversibility. We also prove that for exactly triply regular Bose-Mesner algebras, to check one of the above properties it is sufficient to check it on the complete graph on four vertices. A number of applications, examples and open problems are discussed.     

Partitionable graphs,circle graphs,and the berge strong perfect graph conjecture

Partitionable graphs have been studied by a number of authors in conjunction with attempts at proving the Berge Strong Perfect Graph Conjecture (SPGC). We give some new properties of partitionable graphs which can be used to give a new proof that the SPGC holds for K_1,3-free graphs. Finally, we will show that the SPGC also holds for the class of circle graphs.     

Graphs with a common eigenvalue deck

In this paper, we consider graphs whose deck consists of cards (which are the vertex-deleted subgraphs) that share the same eigenvalue, say μ. We show that, the characteristic polynomial can be reconstructed from the deck, providing a new proof of Tutte’s result for this class of graphs. Moreover, for the subclass of non-singular graphs, the graph can be uniquely reconstructed from the eigenvectors of the cards associated with the eigenvalue μ. The remaining graphs in this class are shown to be μ-cores graphs.     

Cubic Bridgeless Graphs and Braces

There are many long-standing open problems on cubic bridgeless graphs, for instance, Jaeger’s directed cycle double cover conjecture. On the other hand, many structural properties of braces have been recently discovered. In this work, we bijectively map the cubic bridgeless graphs to braces which we call the hexagon graphs, and explore the structure of hexagon graphs. We show that hexagon graphs are braces that can be generated from the ladder on 8 vertices using two types of McCuaig’s augmentations. In addition, we present a reformulation of Jaeger’s directed cycle double cover conjecture in the class of hexagon graphs.     

Feasibility of motion planning on acyclic and strongly connected directed graphs

Motion planning is a fundamental problem of robotics with applications in many areas of computer science and beyond. Its restriction to graphs has been investigated in the literature, for it allows one to concentrate on the combinatorial problem abstracting from geometric considerations. In this paper, we consider motion planning over directed graphs, which are of interest for asymmetric communication networks. Directed graphs generalize undirected graphs, while introducing a new source of complexity to the motion planning problem: moves are not reversible. We first consider the class of acyclic directed graphs and show that the feasibility can be solved in time linear in the product of the number of vertices and the number of arcs. We then turn to strongly connected directed graphs. We first prove a structural theorem for decomposing strongly connected directed graphs into strongly biconnected components. Based on the structural decomposition, we show that the feasibility of motion planning on strongly connected directed graphs can be decided in linear time.     

Solving the canonical representation and Star System Problems for proper circular-arc graphs in logspace

We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where canonical means that isomorphic graphs receive identical models. This implies that the recognition and the isomorphism problems for these graphs are solvable in logspace. For the broader class of concave-round graphs, which still possess (not necessarily proper) circular-arc models, we show that a canonical circular-arc model can also be constructed in logspace. As a building block for these results, we design a logspace algorithm for computing canonical circular-arc models of circular-arc hypergraphs. This class of hypergraphs corresponds to matrices with the circular ones property, which play an important role in computational genomics. Our results imply that there is a logspace algorithm that decides whether a given matrix has this property.Furthermore, we consider the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We show that this problem is solvable in logarithmic space for the classes of proper circular-arc, concave-round, and co-convex graphs.Note that solving a problem in logspace implies that it is solvable by a parallel algorithm of the class AC¹. For the problems under consideration, at most AC² algorithms were known earlier.     

On the energy of some circulant graphs

We give an explicit construction of circulant graphs of very high energy. This construction is based on Gauss sums. We also show the Littlewood conjecture can be used to establish new result for a certain class of circulant graphs.     

On a disparity between relative cliquewidth and relative NLC-width

Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by certain terms of operations. Many hard problems on graphs become solvable in polynomial-time if the inputs are restricted to graphs of bounded clique- or NLC-width. Cliquewidth and NLC-width differ at most by a factor of two.The relative counterparts of these parameters are defined to be the minimum number of labels necessary to create a graph while the tree-structure of the term is fixed. We show that Relative Cliquewidth and Relative NLC-width differ significantly in computational complexity. While the former problem is NP-complete the latter is solvable in polynomial time. The relative NLC-width can be computed in O(n³) time, which also yields an exact algorithm for computing the NLC-width in time O(3ⁿn). Additionally, our technique enables a combinatorial characterisation of NLC-width that avoids the usual operations on labelled graphs.     

Completion of the mixed unit interval graphs hierarchy

We describe the missing class of the hierarchy of mixed unit interval graphs. This class is generated by the intersection graphs of families of unit intervals that are allowed to be closed, open, and left‐closed‐right‐open. (By symmetry, considering closed, open, and right‐closed‐left‐open unit intervals generates the same class.) We show that this class lies strictly between unit interval graphs and mixed unit interval graphs. We give a complete characterization of this new class, as well as quadratic‐time algorithms that recognize graphs from this class and produce a corresponding interval representation if one exists. We also show that the algorithm from Shuchat et al. [8] directly extends to provide a quadratic‐time algorithm to recognize the class of mixed unit interval graphs.     

Solving Partition Problems with Colour-Bipartitions

Polar, monopolar, and unipolar graphs are defined in terms of the existence of certain vertex partitions. Although it is polynomial to determine whether a graph is unipolar and to find whenever possible a unipolar partition, the problems of recognizing polar and monopolar graphs are both NP-complete in general. These problems have recently been studied for chordal, claw-free, and permutation graphs. Polynomial time algorithms have been found for solving the problems for these classes of graphs, with one exception: polarity recognition remains NP-complete in claw-free graphs. In this paper, we connect these problems to edge-coloured homomorphism problems. We show that finding unipolar partitions in general and finding monopolar partitions for certain classes of graphs can be efficiently reduced to a polynomial-time solvable 2-edge-coloured homomorphism problem, which we call the colour-bipartition problem. This approach unifies the currently known results on monopolarity and extends them to new classes of graphs.     

Information theoretic measures of UHG graphs with low computational complexity

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples.     

Balanced group-labeled graphs

A group-labeled graph is a graph whose vertices and edges have been assigned labels from some abelian group. The weight of a subgraph of a group-labeled graph is the sum of the labels of the vertices and edges in the subgraph. A group-labeled graph is said to be balanced if the weight of every cycle in the graph is zero. We give a characterization of balanced group-labeled graphs that generalizes the known characterizations of balanced signed graphs and consistent marked graphs. We count the number of distinct balanced labellings of a graph by a finite abelian group $\Gamma$ and show that this number depends only on the order of $\Gamma$ and not its structure. We show that all balanced labellings of a graph can be obtained from the all-zero labeling using simple operations. Finally, we give a new constructive characterization of consistent marked graphs and markable graphs, that is, graphs that have a consistent marking with at least one negative vertex.     

Competitive inheritance and limitedness of graphs

The study of competition number of graphs has brought many interesting problems to graph theory and combinatorics. However, little is known about what makes the competition number of a graph small or large. In this paper, we introduce competitive inheritance and limitedness of graphs. We show that most graphs studied in the literature of competition graphs possess the inheritance property on their competition number. We characterize the limitedness of graphs on competition number by forbidden induced subgraphs. Our results also prove a conjecture of Opsut on competition number for a new class of graphs. © 1995 John Wiley & Sons, Inc.     

Completing orientations of partially oriented graphs

We initiate a general study of what we call orientation completion problems. For a fixed class of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in by orienting the (nonoriented) edges in P. Orientation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k‐arc‐strong oriented graphs, k‐strong oriented graphs, quasi‐transitive‐oriented graphs, local tournaments, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in‐tournaments, and oriented graphs that have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP‐complete. We also show that some of the NP‐complete problems become polynomial time solvable when the input‐oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable. The latter generalizes a previous result.