Search

This paper discusses a certain graph, called the 'dependence graph' ('the DPG'), that can be defined naturally for a given independent set in a matroid. The author is mainly concerned with the DPG of bases, and the author studies what the DPG of a base tells about the matroid. It is shown that there is a nice connection between the DPG and duality, and between the DPG and connectivity for matroids. This last fact leads to an algorithm for determining the connected components of a matroid and also to one for computing a circuit containing two given distinct elements in the same such component. A simple algorithm using depth-first search is given for solving this last problem for graphic matroids.

The partition problem is that step in the layout problem in which it must be decided which of the elementary digital circuits are to be coalesced into a single, electronic package. A solution of the partition problem must satisfy constraints on the maximum number of elementary circuits that can be put into a single package, and on the number of external connections that can be attached to the package. A solution due to Lawler et al, which minimizes delay caused by clustering electronic elements, is extended to cyclic networks. A new algorithm to extract from a graph the maximal strongly-connected subgraphs (lobes) is developed, and a new approach to clustering the digital elements of a lobe is presented. The digital circuit is represented by a bipartite graph, and solutions are expressed in terms of graph theory. (Author)

If G is a (finite, undirected) graph, its line graph (also called the interchange graph, and the adjoint graph) is the graph G whose vertices are the edges of G, with two vertices of G adjacent if the corresponding edges of G are adjacent. Let pi be a projective plane with n 1 points on a line, and let G(pi) be the bipartite graph whose vertices are the 2(n squared n 1) points and lines of pi, with two vertices adjacent if and only if one of the vertices is a point, the other ine, and the point is on the line. The graph (G(pi)) is studied.

Let G be a random directed bipartite graph with n nodes in each class and outward degree d at each node. The probability G contains a matching is shown to approach one for large n if d > or = 2, but to approach zero if d = 1. This result complements and contrasts with a result of Erdos and Renyi which implies the probability of a matching does to zero if the number of arcs (chosen at random without regard to regularity) grows more slowly than n log n.

Necessary and sufficient conditions for a pair of sequences to be realized by a bipartite graph without 1-factor are given. It is shown that k phi = (k(a sub 1),...,k(a sub n)) has a realization with a phi-factor, provided k phi and phi are realizable. It is shown that if phi has a realization with a k-factor it is also realizable by a graph having a k-factor which has a l-factor, for l = or < k, l dot n even. (Author)

Pairs of sequences which have a unique realization by bipartite graphs (up to isomorphism) are characterized. (Author)

A characterization of line graphs G of graphs with no triangles is given in terms of the clique structure of G. This in turn leads to a rather surprising result about iterated clique graphs of graphs with no triangles. (Author), Report on the Theory and Applications of Automaton Theory.

A problem of partitioning a given graph into a minimal number of subgraphs subject to edge and node constraints is considered. Two parameters associated with the subgraph, one corresponding to the maximum number of nodes and the other to the maximum number of external edges, define a feasible partition element. Complete graphs, complete bipartite graphs, and two families of infinite graphs are considered, and relations between the parameters are used to obtain the results. For the infinite graphs, the problem is somewhat different. A largest feasible partition element is found and can be used in determining the minimal number of feasible elements in a finite graph with the same structure as the infinite one. (Author)

A (0, 1)-matrix M has the consecutive 1's property for columns if the rows of M can be permuted so that the l's in each column appear consecutively. A graph-theoretic approach is used to characterize matrices with this property in terms of forbidden submatrices. Graphs whose adjacency matrix has this property are also characterized. (Author)

A class of graphs is defined which is naturally suggested by a classical theorem of Konig-Egervary on (0,1)-matrices. Several characterizations of this class of graphs are obtained which reveal close connections between these graphs and line graphs, clique graphs, bipartite graphs and Berge's perfect graphs. Finally, as a result of these characterizations and another well-known theorem of Konig we obtain the following result: if the clique graph K(G) of a graph G is bipartite, then the chromatic number chi(G) of G equals the number of points omega(G) in the largest complete subgraph of G. (Author), Report on the Theory and Applications of Automaton Theory.

The problem studied in this paper is that of determining conditions for color-feasibility of a list P in a bipartite graph G. Necessary and sufficient conditions are obtained in case the n-list P contains at most two distinct positive integers. It is shown that these conditions (while necessary in the general case) are not sufficient if P contains three or more distinct positive integers. For the case of two distinct integers in P, the method of proof leads to an efficient edge-coloring algorithm. The main results can be interpreted in terms of sum decompositions of (0,1)-matrices or in terms of multicommodity flows in certain kinds of directed networks.