Minimally 3-connected graphs

A constructive characterization of the class of minimally 3-connected graphs is presented. This yields a new characterization for the class of 3-connected graphs, which differs from the characterization provided by Tutte. Where Tutte's characterization requires the set of all wheels as a starting set, the new characterization requires only the graph K₄. The new characterization is based on the application of graph operations to appropriate vertex and edge sets in minimally 3-connected graphs.     

Lovász–Schrijver SDP-operator,near-perfect graphs and near-bipartite graphs

We study the Lovász–Schrijver lift-and-project operator (\({{\mathrm{\text {LS}}}}_+\)) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the \({{\mathrm{\text {LS}}}}_+\)-operator generates the stable set polytope in one step has been open since 1990. We call these graphs \({{{\mathrm{\text {LS}}}}}_+\)-perfect. In the current contribution, we pursue a full combinatorial characterization of \({{{\mathrm{\text {LS}}}}}_+\)-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among \({{{\mathrm{\text {LS}}}}}_+\)-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.     

Forbidden subgraphs and the Kőnig property

A graph has the Kőnig property if its matching number equals its transversal number. Lovász proved a characterization of graphs having the Kőnig property by forbidden subgraphs, restricted to 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 property in terms of forbidden configurations (certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the Kőnig property in terms of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. As a consequence of our characterization of graphs with the Kőnig property, we prove a forbidden subgraph characterization for the class of edge-perfect graphs.     

A new view toward vertex decomposable graphs

In this paper, we bring a new view about closed neighbourhood to show the vertex decomposability of graphs. Making use of the characterization of hereditary vertex decomposable graphs, we introduce a class of vertex decomposable graphs, which include some well-known classic vertex decomposable graphs such as clique-whiskered graphs and Cameron-Walker graphs.     

An extrinsic characterization of addressable data graphs

Previous characterizations of the class of addressable data graphs have been intrinsic in nature. In this note, the auxiliary concept of a monoid system is used to derive an extrinsic characterization of the class. Specifically, a partial transformation of the class of data graphs is found which fixes (up to isomorphism) precisely the addressable data graphs.     

Partial Characterizations of 1‐Perfectly Orientable Graphs

We study the class of 1‐perfectly orientable graphs, that is, graphs having an orientation in which every out‐neighborhood induces a tournament. 1‐perfectly orientable graphs form a common generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this article, we develop several results on 1‐perfectly orientable graphs. In particular, we (i) give a characterization of 1‐perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1‐perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1‐perfectly orientable graphs, and (iv) characterize the class of 1‐perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1‐perfectly orientable cobipartite graphs coincides with the class of cobipartite circular arc graphs.     

Edge and vertex intersection of paths in a tree

In this paper we continue the investigation of the class of edge intersection graphs of a collection of paths in a tree (EPT graphs) where two paths edge intersect if they share an edge. The class of EPT graphs differs from the class known as path graphs, the latter being the class of vertex intersection graphs of paths in a tree. A characterization is presented here showing when a path graph is an EPT graph. In particular, the classes of path graphs and EPT graphs coincide on trees all of whose vertices have degree at most 3. We then prove that it is an NP-complete problem to recognize whether a graph is an EPT graph.     

A graphical characterization of the largest chain graphs

The paper presents a graphical characterization of the largest chain graphs which serve as unique representatives of classes of Markov equivalent chain graphs. The characterization is a basis for an algorithm constructing, for a given chain graph, the largest chain graph equivalent to it. The algorithm was used to generate a catalog of the largest chain graphs with at most five vertices. Every item of the catalog contains the largest chain graph of a class of Markov equivalent chain graphs and an economical record of the induced independency model.     

On the mean value of probability measures on circular graphs

We introduce and discuss a class of difference equations motivated by a problem from combinatorial optimization on graphs. The local behavior at stationary points is investigated in detail, and in the course of this investigation we prove a stability result for certain types of non-isolated stationary points. Results include a complete characterization of the behavior on chain graphs, and a characterization of the local behavior for circular graphs.     

On orthogonal ray graphs

An orthogonal ray graph is an intersection graph of horizontal and vertical rays (half-lines) in the xy-plane. An orthogonal ray graph is a 2-directional orthogonal ray graph if all the horizontal rays extend in the positive x-direction and all the vertical rays extend in the positive y-direction. We first show that the class of orthogonal ray graphs is a proper subset of the class of unit grid intersection graphs. We next provide several characterizations of 2-directional orthogonal ray graphs. Our first characterization is based on forbidden submatrices. A characterization in terms of a vertex ordering follows immediately. Next, we show that 2-directional orthogonal ray graphs are exactly those bipartite graphs whose complements are circular arc graphs. This characterization implies polynomial-time recognition and isomorphism algorithms for 2-directional orthogonal ray graphs. It also leads to a characterization of 2-directional orthogonal ray graphs by a list of forbidden induced subgraphs. We also show a characterization of 2-directional orthogonal ray trees, which implies a linear-time algorithm to recognize such trees. Our results settle an open question of deciding whether a (0,1)-matrix can be permuted to avoid the submatrices .     

On graphs having domination number half their order

In this paper we present a characterization of connected graphs of order 2n with domination numbern. Using this class of graphs, we determine an infinite class of graphs with the property that the domination number of the product of any two is precisely the product of the domination numbers.     

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.     

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.     

On degree sequences of undirected,directed, and bidirected graphs

Bidirected graphs generalize directed and undirected graphs in that edges are oriented locally at every node. The natural notion of the degree of a node that takes into account (local) orientations is that of net-degree. In this paper, we extend the following four topics from (un)directed graphs to bidirected graphs:

• –Erdős–Gallai-type results: characterization of net-degree sequences,
• –Havel–Hakimi-type results: complete sets of degree-preserving operations,
• –Extremal degree sequences: characterization of uniquely realizable sequences, and
• –Enumerative aspects: counting formulas for net-degree sequences.

To underline the similarities and differences to their (un)directed counterparts, we briefly survey the undirected setting and we give a thorough account for digraphs with an emphasis on the discrete geometry of degree sequences. In particular, we determine the tight and uniquely realizable degree sequences for directed graphs.     

Distance monotone graphs and a new characterization of hypercubes

The aim of this paper is to study the class of s.c. distance monotone graphs which arise naturally when investigating some intersection properties of graphs. A new characterization of hypercubes is also obtained.     

Recognizing near-bipartite Pfaffian graphs in polynomial time

A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e₁ and e₂ such that G−e₁−e₂ is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

Bipartite almost distance-hereditary graphs

The notion of distance-heredity in graphs has been extended to construct the class of almost distance-hereditary graphs (an increase of the distance by one unit is allowed by induced subgraphs). These graphs have been characterized in terms of forbidden induced subgraphs [M. Aïder, Almost distance-hereditary graphs, Discrete Math. 242 (1–3) (2002) 1–16]. Since the distance in bipartite graphs cannot increase exactly by one unit, we have to adapt this notion to the bipartite case.In this paper, we define the class of bipartite almost distance-hereditary graphs (an increase of the distance by two is allowed by induced subgraphs) and obtain a characterization in terms of forbidden induced subgraphs.     

Split digraphs

We generalize the class of split graphs to the directed case and show that these split digraphs can be identified from their degree sequences. The first degree sequence characterization is an extension of the concept of splittance to directed graphs, while the second characterization says a digraph is split if and only if its degree sequence satisfies one of the Fulkerson inequalities (which determine when an integer-pair sequence is digraphic) with equality.     

Perfect elimination orderings for symmetric matrices

We introduce a new class of structured symmetric matrices by extending the notion of perfect elimination ordering from graphs to weighted graphs or matrices. This offers a common framework capturing common vertex elimination orderings of monotone families of chordal graphs, Robinsonian matrices and ultrametrics. We give a structural characterization for matrices that admit perfect elimination orderings in terms of forbidden substructures generalizing chordless cycles in graphs.