Dominating sets and domatic number of circular arc graphs

A dominating set of a graph G = (N,E) is a subset S of nodes such that every node is either in S or adjacent to a node which is in S. The domatic number of G is the size of a maximum cardinality partition of N into dominating sets. The problems of finding a minimum cardinality dominating set and the domatic number are both NP-complete even for special classes of graphs. In the present paper we give an O(n∣E∣) time algorithm that finds a minimum cardinality dominating set when G is a circular arc graph (intersection graph of arcs on a circle). The domatic number problem is solved in O(n² log n) time when G is a proper circular arc graph, and it is shown NP-complete for general circular arc graphs.     

The complexity of some acyclic improper colourings

In this paper we will consider acyclic bipartition of the vertices of graphs, where acyclic means that the edges whose endpoints are in different parts of the partition induce a forest. We will require that the vertices belonging to the same partition induce graphs from particular class. We will search for acyclic bipartitions of cubic and subcubic graphs.     

Edge domatic numbers of complete n- partite graphs

An edge dominating set of a graph is a set of edgesD such that every edge not inD is adjacent to an edge inD. An edge domatic partition of a graph G =(V, E) is a collection of pairwise disjoint edge dominating sets of G whose union isE. The maximum size of an edge domatic partition of G is called the edge domatic number of G. In this paper we study the edge domatic numbers of completen-partite graphs. In particular, we give exact values for the edge domatic numbers of complete 3-partite graphs and balanced complete n-partite graphs with oddn.     

Domatic partitions of computable graphs

Given a graph G, we say that a subset D of the vertex set V is a dominating set if it is near all the vertices, in that every vertex outside of D is adjacent to a vertex in D. A domatic k-partition of G is a partition of V into k dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two types of questions for the case when k = 3. First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be ${\Pi^{0}_{1}}$ -, ${\Pi^{0}_{2}}$ -, and ${\Sigma^{1}_{1}}$ -complete, respectively.     

Star partitions and the graph isomorphism problem

A canonical basis of Rⁿ associated with a graph G on n vertices has been defined in [15] in connection with eigenspaces and star partitions of G. The canonical star basis together with eigenvalues of G determines G to an isomorphism. We study algorithms for finding the canonical basis and some of its variations. The emphasis is on the following three special cases; graphs with distinct eigenvalues, graphs with bounded eigenvalue multiplicities and strongly regular graphs. We show that the procedure is reduced in some parts to special cases of some well known combinatorial optimization problems, such as the maximal matching problem. the minimal cut problem, the maximal clique problem etc. This technique provides another proof of a result of L. Babai et al. [2] that isomorphism testing for graphs with bounded eigenvalue multiplicities can be performend in a polynomial time. We show that the canonical basis in strongly regular graphs is related to the graph decomposition into two strongly regular induced subgraphs. Examples of distinguishing between cospectral strongly regular graphs by means of the canonical basis are provided. The behaviour of star partitions of regular graphs under operations of complementation and switching is studied.     

Exact Bounds for Judicious Partitions of Graphs

has a bipartite subgraph of size at least . We show that every graph of size has a bipartition in which the Edwards bound holds, and in addition each vertex class contains at most edges. This is exact for complete graphs of odd order, which we show are the only extremal graphs without isolated vertices. We also give results for partitions into more than two classes. Received: December 27, 1996/Revised: Revised June 10, 1998     

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.     

图的星临界性

图的星着色是图的正常着色的推广。本文对图的星临界性及其与图的临界性之间的关系进行研究，给出了两类星临界但非临界的平面图。     

Digraph matrix partitions and trigraph homomorphisms

Matrix partitions generalize graph colourings and homomorphisms. Their study has so far been confined to symmetric matrices and undirected graphs. In this paper we make an initial study of list matrix partitions for digraphs; in other words our matrices are not necessarily symmetric. We motivate future conjectures by classifying the complexity of all list matrix partition problems for matrices of size up to three. We find it convenient to model the problem in the language of trigraph homomorphisms.     

Consensus of partitions : a constructive approach

Given a profile (family) ?? of partitions of a set of objects or items X, we try to establish a consensus partition containing a maximum number of joined or separated pairs in X that are also joined or separated in the profile. To do so, we define a score function, S _?? associated to any partition on X. Consensus partitions for ?? are those maximizing this function. Therefore, these consensus partitions have the median property for the profile and the symmetric difference distance. This optimization problem can be solved, in certain cases, by integer linear programming. We define a polynomial heuristic which can be applied to partitions on a large set of items. In cases where an optimal solution can be computed, we show that the partitions built by this algorithm are very close to the optimum which is reached in practically all the cases, except for some sets of bipartitions.     

Connected Domatic Number in Planar Graphs

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.     

Partitions of Graphs into Cographs

Cographs from the minimal family of graphs containing K₁ which are closed with respect to complements and unions. We discuss vertex partitions of graphs into the smallest number of cographs, where the partition is as small as possible. We shall call the order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show both bounds are sharp, for graphs with arbitrarily high girth. This provides an alternative proof to a result in [3]; there exist triangle-free graphs with arbitrarily large c-chromatic numbers. We show that any planar graph with girth at least 11 has a c-chromatic number of at most two. We close with several remarks on computational complexity. In particular, we show that computing the c-chromatic number is NP-complete for planar graphs.     

Minimum node covers and 2-bicritical graphs

The problem of finding a minimum cardinality set of nodes in a graph which meet every edge is of considerable theoretical as well as practical interest. Because of the difficulty of this problem, a linear relaxation of an integer programming model is sometimes used as a heuristic. In fact Nemhauser and Trotter showed that any variables which receive integer values in an optimal solution to the relaxation can retain the same values in an optimal solution to the integer program. We define 2-bicritical graphs and give several characterizations of them. One characterization is that they are precisely the graphs for which an optimal solution to the linear relaxation will have no integer valued variables. Then we show that almost all graphs are 2-bicritical and hence the linear relaxation almost never helps for large random graphs.This research was supported in part by the National Research Council of Canada.     

On Induced Subgraphs with All Degrees Odd

 Gallai proved that the vertex set of any graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We prove that every connected graph of even order has a vertex partition into sets inducing subgraphs with all degrees odd, and give bounds for the number of sets of this type required for vertex partitions and vertex covers. We also give results on the partitioning and covering problems for random graphs. Received: October 5, 1998?Final version received: October 20, 2000     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

Bounded max-colorings of graphs

In a bounded max-coloring of a vertex/edge weighted graph, each color class is of cardinality at most b and of weight equal to the weight of the heaviest vertex/edge in this class. The bounded max-vertex/edge-coloring problems ask for such a coloring minimizing the sum of all color classes' weights. These problems generalize the well known max-coloring problems by taking into account the number of available resources (i.e., the cardinality of color classes) in practical applications. In this paper we present complexity results and approximation algorithms for the bounded max-coloring problems on general graphs, bipartite graphs and trees.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

On the construction of the self-complementary graphs on 12 nodes

We briefly describe how we compiled a catalog of all the 720 self-complementary graphs on 12 nodes. In our first attempt at this compilation one graph was inadvertently omitted. The missing graph was subsequently found by making use of a theoretical formula due to Parthasarathy and Sridharan for counting self-complementary graphs with given partitions.     

Clique partitioning with value-monotone submodular cost

We consider the problem of partitioning a graph into cliques of bounded cardinality. The goal is to find a partition that minimizes the sum of clique costs where the cost of a clique is given by a set function on the nodes. We present a general algorithmic solution based on solving the problem variant without the cardinality constraint. We obtain constant factor approximations depending on the solvability of this relaxation for a large class of submodular cost functions which we call value-monotone submodular functions. For special graph classes we give optimal algorithms.