Characterizing and computing minimal cograph completions

A cograph completion of an arbitrary graph G is a cograph supergraph of G on the same vertex set. Such a completion is called minimal if the set of edges added to G is inclusion minimal. In this paper we present two results on minimal cograph completions. The first is a characterization that allows us to check in linear time whether a given cograph completion is minimal. The second result is a vertex incremental algorithm to compute a minimal cograph completion H of an arbitrary input graph G in O(|V(H)|+|E(H)|) time. An extended abstract of the result has been already presented at FAW 2008 [D. Lokshtanov, F. Mancini, C. Papadopoulos, Characterizing and computing minimal cograph completions, in: Proceedings of FAW’08-2nd International Frontiers of Algorithmics Workshop, in: LNCS, vol. 5059, 2008, pp. 147158. [1]].     

Obstructions for acyclic local tournament orientation completions

The orientation completion problem for a fixed class of oriented graphs asks whether a given partially oriented graph can be completed to an oriented graph in the class. Orientation completion problems have been studied recently for several classes of oriented graphs, including local tournaments. Local tournaments are intimately related to proper circular-arc graphs and proper interval graphs. In particular, proper interval graphs are precisely those which can be oriented as acyclic local tournaments. In this paper we determine all obstructions for acyclic local tournament orientation completions. These are in a sense minimal partially oriented graphs that cannot be completed to acyclic local tournaments. Our results imply that a polynomial time certifying algorithm exists for the acyclic local tournament orientation completion problem.     

Dynamically maintaining split graphs

We present an algorithm that supports operations for modifying a split graph by adding edges or vertices and deleting edges, such that after each modification the graph is repaired to become a split graph in a minimal way. In particular, if the graph is not split after the modification, the algorithm computes a minimal, or if desired even a minimum, split completion or deletion of the modified graph. The motivation for such operations is similar to the motivation for fully dynamic algorithms for particular graph classes. In our case we allow all modifications to the graph and repair, rather than allowing only the modifications that keep the graph split. Fully dynamic algorithms of the latter kind are known for split graphs [L. Ibarra, Fully dynamic algorithms for chordal graphs and split graphs, Technical Report DCS-262-IR, University of Victoria, Canada, 2000].Our results can be used to design linear time algorithms for some recognition and completion problems, where the input is supplied in an on-line fashion.     

Minimal comparability completions of arbitrary graphs

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes Π for which Π completion of arbitrary graphs can be achieved through such a vertex incremental approach.     

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.     

分裂图的区间图完全化问题（英文）

The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.     

Positive graphs

We study “positive” graphs that have a nonnegative homomorphism number into every edge-weighted graph (where the edgeweights may be negative). We conjecture that all positive graphs can be obtained by taking two copies of an arbitrary simple graph and gluing them together along an independent set of nodes. We prove the conjecture for various classes of graphs including all trees. We prove a number of properties of positive graphs, including the fact that they have a homomorphic image which has at least half the original number of nodes but in which every edge has an even number of pre-images. The results, combined with a computer program, imply that the conjecture is true for all but one graph up to 10 nodes.     

Graph decompositions definable in monadic second-order logic

We prove that the split decomposition of a graph is definable by Monadic Second-Order formulas. We also prove that the set of graphs having the same cycle matroid as a given graph is definable from this graph by Monadic Second-Order formulas. These results are consequences of general results on the logical definability of graph decompositions of various types.     

Two characterisations of the minimal triangulations of permutation graphs

A minimal triangulation of a graph is a chordal supergraph with an inclusion-minimal edge set. Minimal triangulations are obtained from adding edges only to minimal separators, completing minimal separators into cliques. Permutation graphs are the comparability graphs whose complements are also comparability graphs. Permutation graphs can be characterised as the intersection graphs of specially arranged line segments in the plane, which is called a permutation diagram. The minimal triangulations of permutation graphs are known to be interval graphs, and they can be obtained from permutation diagrams by applying a geometric operation, that corresponds to the completion of separators into cliques. We precisely specify this geometric completion process to obtain minimal triangulations, and we completely characterise those interval graphs that are minimal triangulations of permutation graphs.     

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.     

Netlike partial cubes, V: Completion and netlike classes

We define a completion of a netlike partial cube G by replacing each convex 2n-cycle C of G with n≥3 by an n-cube admitting C as an isometric cycle. We prove that a completion of G is a median graph if and only if G has the Median Cycle Property (MCP) (see N. Polat, Netlike partial cubes III. The Median Cycle Property, Discrete Math.). In fact any completion of a netlike partial cube having the MCP is defined by a universal property and turns out to be a minimal median graph containing G as an isometric subgraph. We show that the completions of the netlike partial cubes having the MCP preserves the principal constructions of these graphs, such as: netlike subgraphs, gated amalgams and expansions. Conversely any netlike partial cube having the MCP can be obtained from a median graph by deleting some particular maximal finite hypercubes. We also show that, given a netlike partial cube G having the MCP, the class of all netlike partial cubes having the MCP whose completions are isomorphic to those of G share different properties, such as: depth, lattice dimension, semicube graph and crossing graph.     

Decomposition of 3-connected graphs

Cunningham and Edmonds [4[ have proved that a 2-connected graphG has a unique minimal decomposition into graphs, each of which is either 3-connected, a bond or a polygon. They define the notion of a good split, and first prove thatG has a unique minimal decomposition into graphs, none of which has a good split, and second prove that the graphs that do not have a good split are precisely 3-connected graphs, bonds and polygons. This paper provides an analogue of the first result above for 3-connected graphs, and an analogue of the second for minimally 3-connected graphs. Following the basic strategy of Cunningham and Edmonds, an appropriate notion of good split is defined. The first main result is that ifG is a 3-connected graph, thenG has a unique minimal decomposition into graphs, none of which has a good split. The second main result is that the minimally 3-connected graphs that do not have a good split are precisely cyclically 4-connected graphs, twirls (K _3,n for somen3) and wheels. From this it is shown that ifG is a minimally 3-connected graph, thenG has a unique minimal decomposition into graphs, each of which is either cyclically 4-connected, a twirl or a wheel.Research partially supported by Office of Naval Research Grant N00014-86-K-0689 at Purdue University.     

Incrementally extensible hypercube networks and their fault tolerance

The incrementally extensible hypercube or IEH graph, a generalization of the hypercube, was introduced in [1]. It is shown that IEH graphs are incrementally extensible in steps of 1, optimally fault tolerant and its diameter is logarithmic in the number of nodes. Moreover, for any given number of nodes, the difference of the maximum and the minimum degree of a node in the graph is ≤ 1; i.e., the graph is almost regular. We also analyze these graphs in presence of node failures. We develop a fault tolerant routing algorithm which can compute a minimal path between two arbitrary nodes in an IEH graph in the presence of the maximum number of allowable faults. We also determine the fault diameter of the graph. Thus, we show that the IEH graphs, while they can be defined for any integer number of computing nodes, retain all the desirable properties of regular hypercubes including fault tolerance and a tight fault diameter.     

The splittance of a graph

The splittance of an arbitrary graph is the minimum number of edges to be added or removed in order to produce a split graph (i.e. a graph whose vertex set can be partitioned into a clique and an independent set). The splittance is seen to depend only on the degree sequence of the graph, and an explicit formula for it is derived. This result allows to give a simple characterization of the degree sequences of split graphs. Worst cases for the splittance are determined for some classes of graphs (the class of all graphs, of all trees and of all planar graphs).     

Coincidence of the sets of minimal and irreducible join graphs over primary structure of algebraic Bayesian networks

An algebraic Bayesian network (ABN) is a probabilistic-logic graphical model of bases of knowledge patterns with uncertainty. A primary structure of an ABN is a set of knowledge patterns, that are ideals of conjunctions of positive literals except the empty conjunction endowed with scalar or interval probability estimates. A secondary ABN structure is represented by a graph constructed over the primary structure, which is called a join graph. From the point of view of learning of a global ABN structure, of interest are join graphs with the minimum number of edges and irreducible join graphs. A theorem on the coincidence of the sets of minimal and irreducible join graphs over the same primary structure is proved. A greedy algorithm constructing an arbitrary minimal join graph from a given primary structure is described. A theorem expressing the number of edges in a minimal join graph as the sum of the ranks of the incidence matrices of strong restrictions of a maximal join graph minus the number of significant weights is stated and proved. A generalized graph of maximal knowledge patterns (GGMKP) is a graph with the same vertex set as the join graph which is not subject to any constraints concerning the possibility of joining two vertices by an edge. It is proved that the pair consisting of the edge set of a maximal GGMKP and the set of all subsets of this graph such that the subtraction of any such subset from the maximal GGMKP yields an edge of the join graph on the same vertex set is a matroid.     

Homomorphisms of graphs and of their orientations

Consider a set of graphs and all the homomorphisms among them. Change each graph into a digraph by assigning directions to its edges. Some of the homomorphisms preserve the directions and so remain as homomorphisms of the set of digraphs; others do not. We study the relationship between the original set of graph-homomorphisms and the resulting set of digraph-homomorphisms and prove that they are in a certain sense independent. This independence result no longer holds if we start with a proper class of graphs, or if we require that only one direction be given to each edge (unless each homomorphism is invertible, in which case we again prove independence). We also specialize the results to the set consisting of one graph and prove the independence of monoids (groups) of a graph and the corresponding digraph.With 1 Firgure     

Packing cycles in complete graphs

We introduce a new technique for packing pairwise edge-disjoint cycles of specified lengths in complete graphs and use it to prove several results. Firstly, we prove the existence of dense packings of the complete graph with pairwise edge-disjoint cycles of arbitrary specified lengths. We then use this result to prove the existence of decompositions of the complete graph of odd order into pairwise edge-disjoint cycles for a large family of lists of specified cycle lengths. Finally, we construct new maximum packings of the complete graph with pairwise edge-disjoint cycles of uniform length.     

Graph structural properties of non-Yutsis graphs allowing fast recognition

Yutsis graphs are connected simple graphs which can be partitioned into two vertex-induced trees. Cubic Yutsis graphs were introduced by Jaeger as cubic dual Hamiltonian graphs, and these are our main focus.Cubic Yutsis graphs also appear in the context of the quantum theory of angular momenta, where they are used to generate summation formulae for general recoupling coefficients. Large Yutsis graphs are of interest for benchmarking algorithms which generate these formulae.In an earlier paper we showed that the decision problem of whether a given cubic graph is Yutsis is NP-complete. We also described a heuristic that was tested on graphs with up to 300,000 vertices and found Yutsis decompositions for all large Yutsis graphs very quickly.In contrast, no fast technique was known by which a significant fraction of bridgeless non-Yutsis cubic graphs could be shown to be non-Yutsis. One of the contributions of this article is to describe some structural impediments to Yutsisness. We also provide experimental evidence that almost all non-Yutsis cubic graphs can be rapidly shown to be non-Yutsis by applying a heuristic based on some of these criteria. Combined with the algorithm described in the earlier paper this gives an algorithm that, according to experimental evidence, runs efficiently on practically every large random cubic graph and can decide on whether the graph is Yutsis or not.The second contribution of this article is a set of construction techniques for non-Yutsis graphs implying, for example, the existence of 3-connected non-Yutsis cubic graphs of arbitrary girth and with few non-trivial 3-cuts.