Complete subgraphs of the graphs of convex polytopes

It is shown that if three vertices of the graph G(l') of a convex 3-polytope P are chosen, then G(P) contains a refinement of the complete graph C₄ on four vertices, for which the three chosen vertices are principal (that is, correspond to vertices of C₄ in the refinement). In general, all four vertices may not be preassigned as principal. For dimensions d?4, simple (simplicial) d-polytopes are constructed whose graphs contain sets of three (four) vertices, which cannot all be principal in any refinement of C₄₊₁.     

Matrices of zeros and ones with fixed row and column sum vectors

Let m and n be positive integers, and let R=(r₁,…,r_m) and S=(s₁,…,s_n) be nonnegative integral vectors. We survey the combinational properties of the set of all m × n matrices of 0's and 1's having r_i1's in row i ands_i 1's in column j. A number of new results are proved. The results can be also be formulated in terms of a set of bipartite graps with bipartition into m and n vertices having degree sequence R and S, respectively. They can also be formulated in terms of the set of hypergraphs with m vertices having degree sequence R and n edges whose cardinalities are given by S.     

Wagner's theorem for Torus graphs

Wagner's theorem (any two maximal plane graphs having p vertices are equivalent under diagonal transformations) is extended to maximal torus graphs, graphs embedded in the torus with a maximal set of edges present. Thus any maximal torus graph having p vertices may be diagonally transformed into any other maximal torus graph having p vertices. As with Wagner's theorem, a normal form representing an intermediate stage in the above transformation is displayed. This result, along with Wagner's theorem, may make possible constructive characterizations of planar and toroidal graphs, through a wholly combinatorial definition of diagonal transformation.     

Brooks' graph-coloring theorem and the independence number

Let h denote the maximum degree of a connected graph H, and let _χ(H) denote its chromatic, number. Brooks' Theorem asserts that if h ≥ 3, then _χ(H) ≤ h, unless H is the complete graph K_h+1. We show that when H is not K_h+1, there is an h-coloring of H in which a maximum independent set is monochromatic. We characterize those graphs H having an h-coloring in which some color class consists of vertices of degree h in H. Again, without any loss of generality, this color class may be assumed to be maximum with respect to the condition that its vertices have degree h.     

The diagonal hypergraph of a matrix (bipartite graph)

Let A be an n x n matrix of 0's and 1's (a bipartite graph). The diagonal hypergraph of A is the hypergraph whose vertices correspond to the 1's (edges) of A and whose edges correspond to the positive diagonals (1-factors) of A. The numerical invariants of this hypergraph are investigated.     

Line-digraphs,arborescences, and theorems of tutte and knuth

The line-digraph of a digraph D with vertices V₁, …, V_n is the digraph $\text{D}{}^1$ obtained from D by associating with each edge of D a vertex of $\text{D}{}^1$, and then directing an edge from vertex (V_i, V_j) of $\text{D}{}^1$ to vertex (V_k, V_m) if and only if j = k. This paper extends a characterization given by Harary and Norman for linedigraphs. It is also possible to repeatedly contract vertices of the line-digraph (with a new contraction procedure) so as to obtain the digraph derived from D by deleting all vertices with no incoming edges. Several new identities for arborescences are presented, leading to a combinatorial proof of Knuth's formula for the number of arborescences of a line-digraph. A new proof is given for the fact that in a digraph with every vertex having indegree equal to outdegree, the number of arborescences with root V_j is independent of j. Finally a new proof is presented for Tutte's Matrix Tree Theorem which shows the theorem to be a special case of the principle of inclusion-exclusion.     

The reconstruction of outerplanar graphs

Ulam's conjecture is that a graph G with at least three vertices can be reconstructed from the family of subgraphs of G obtained by deleting single vertices of G. This paper proves the conjecture for G outerplanar, by working first with partially labeled graphs and then applying the results obtained to the unlabeled case.     

Sur le nombre transversal des hypergraphes uniformes

The transversal number of a given hypergraph is the cardinality of the smallest set of vertices meeting all the edges. What is the maximal possible value of the transversal number of a r-uniform hypergraph on n vertices with maximal degree p? The problem is solved here for p = 2, by using Berge's theorem on matchings.     

Matrices with isomorphic diagonal hypergraphs

Let A be an n×n matrix of 0's and 1's with total support. The diagonal hypergraph of A is the hypergraph whose vertices are the positive positions of A and whose edges are the positive diagonals of A. We investigate which n×n matrices with total support have diagonal hypergraphs isomorphic to that of A, and the structure of such isomorphisms.     

Neighbourhoods of transitive graphs and GRR's

Let X be a vertex-transitive graph with complement $\text{X}$. We show that if both N, the neighbourhood of a vertex in X, and $\text{N}$, the neighbourhood of a vertex in $\text{X}$, are disconnected, then either X is isomorphic to K₃ × K₃ or both N and $\text{N}$ contain isolated vertices. We characterize the graphs which satisfy this last condition and show in consequence that they admit automorphisms of the form (12)(34). It follows that if X is a GRR for some graph G then at least one of N and $\text{N}$ is connected. (X is said to be a graphical regular representation, or GRR, for G if its automorphism group is isomorphic to G and acts regularly on its vertices.) Using this result we determine those groups generated by their involutions which do not have a GRR. The largest such group has order 18. As a corollary we conclude that all non-abelian simple groups have GRR's.     

A generalization of Turán's theorem to directed graphs

We consider an extremal problem for directed graphs which is closely related to Turán's theorem giving the maximum number of edges in a graph on n vertices which does not contain a complete subgraph on m vertices. For an integer n?2, let T_n denote the transitive tournament with vertex set X_n={1,2,3,…,n} and edge set {(i,j):1?i<j?n}. A subgraph H of T_n is said to be m-locally unipathic when the restriction of H to each m element subset of X_n consisting of m consecutive integers is unipathic. We show that the maximum number of edges in a m-locally unipathic subgraph of T_n is ($\text{q}\text{2}\text{)(m?1)}{}^2\text{+q(m?1)r+?}\text{1}\text{4}\text{r}{}^2\text{?}$ where n= q(m?1+r and $\text{?}\text{1}\text{2}\text{(m?1)??r<?}\text{3}\text{2}\text{(m?1)?}$. As is the case with Turán's theorem, the extremal graphs for our problem are complete multipartite graphs. Unlike Turán's theorem, the part sizes will not be uniform. The proof of our principal theorem rests on a combinatorial theory originally developed to investigate the rank of partially ordered sets.     

On regular graphs and Hamiltonian circuits,including answers to some questions of Joseph Zaks

A graph is called l-ply Hamiltonian if it admits l edge-disjoint Hamiltonian circuits. The following results are obtained: (1) When n ≥ 3 and 0 ≤ 2l ≤ n there exists an n-connected n-regular graph that is exactly l-ply Hamiltonian. (2) There exist 5-connected 5-regular planar graphs that are not doubly (i.e. 2-ply) Hamiltonian, one with only 132 vertices and another with only three types of face, namely 3-, 4- and 12-gons. (3) There exist 3-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 76 vertices and another that has no Hamiltonian paths and has only 128 vertices. (4) There exist 5-edge-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 176 vertices and another that has no Hamiltonian paths and has only 512 vertices. Result (1) was known in the special cases $\text{l = [}\text{n}\text{2}\text{]}$ (an old result) and l = 0 (due to G. H. J. Meredith, 1973). The special case l = 1 provides a negative answer to question 4 in a recent paper by Joseph Zaks and implies Corollary 1 to Zaks' Theorem 1. Results (2) and (3) involve graphs with considerably fewer vertices (and, in one case, fewer types of face) than Zaks' corresponding graphs and provide partial answers to his questions 1 and 3. Result (4) involves graphs that satisfy a stronger condition than those of Zaks but still have fewer vertices.     

Chapter 1. Extension of the fundamental theorem of finite semigroups

This paper proves that some useful commutivity relations exist among semigroup wreath product factors that are either groups or combinatorial “units” U₁, U₂, or U₃. Using these results it then obtains some characterizations of each of the classes of semigroups buildable from U₁'s, U₂'s, and groups (“buildable” meaning “dividing a wreath product of”).We show that up to division U₁'s can be moved to the right and U₂'s, and groups to the left over other units and groups, if it is allowed that the factors involved be replaced by their direct products, or in the case of U₂, even by a wreath product. From this it is deduced that U₁'s and U₂'s do not affect group complexity, that any semigroup buildable from U₁'s, U₂'s, and groups has group complexity 0 or 1, and that all such semigroups can be represented, up to division, in a canonical form—namely, as a wreath product with all U₁'s on the right, all U₂'s on the left, and a group in the middle. This last fact is handy for developing charactérizations.An embedding theorem for semigroups with a unique 0-minimal ideal is introduced, and from this and the commutivity results and some constructions proved for RLM semigroups, there is obtained an algebraic characterization for each class of semigroups that is a wreath product-division closure of some combination of U₁'s, U₂'s, and the groups. In addition it is shown, for i = 1,2,3, that if the unit U_i does not divide a semigroup S, then S can be built using only groups and units not containing U_i. Thus, it can be deduced that any semigroup which does not contain U₃ must have group complexity either 0 or 1. This then establishes that indeed U₃ is the determinant of group complexity, since it is already proved that both U₁ and U₂ are transparent with regard to the group complexity function, and it is known that with U₃ (and groups) one can build semigroups with complexities arbitrarily large. Another conclusion is a combinatorial counterpart for the Krohn-Rhodes prime decomposition theorem, saying that any semigroups can be built from the set of units which divide it together with the set of those semigroups not having unit divisors. Further, one can now characterize those semigroups which commute over groups, showing a semigroup commutes to the left over groups iff it is “R₁” (i.e., does not contain U₁, i.e., is buildable form U₂'s and groups), and commutes to the right over groups iff it does not contain U₂ (i.e., is buildable from groups and U₁'s). Finally, from the characterizations and their proofs one sees some ways in which groups can do the work of combinatorials in building combinatorial semigroups.     

Counting rooted maps by genus III: Nonseparable maps

A map on an orientable surface is called separable if its underlying graph can be disconnected by splitting a vertex into two pieces, each containing a positive number of edge-ends consecutively ordered with respect to counter-clockwise rotation around the original vertex. This definition is shown to be equivalent for planar maps to Tutte's definition of a separable planar map. We develop a procedure for determining the generating functions N_g,b(x) = Σ_p=0^∞n_g,b,px^p, where n_g,b,p is the number of rooted nonseparable maps with b + p edges and p + 1 vertices on an orientable surface of genus g. Similar results are found for tree-rooted maps.     

On monochromatic paths in edge-coloured digraphs

Let G be a directed graph whose edges are coloured with two colours. Call a set S of vertices of Gindependent if no two vertices of S are connected by a monochromatic directed path. We prove that if G contains no monochromatic infinite outward path, then there is an independent set S of vertices of G such that, for every vertex x not in S, there is a monochromatic directed path from x to a vertex of S. In the event that G is infinite, the proof uses Zorn's lemma. The last part of the paper is concerned with the case when G is a tournament.     

Three-graphs without two triples whose symmetric difference is contained in a third

Katona conjectured that if a three-graph has 3n vertices and n³+1 triples, then there are two triples whose symmetric difference is contained in a third triple. This conjecture can be considered as a natural generalization of Turán's theorem [4] for edge graphs. The aim of this note is to prove this conjecture.     

An algorithmic proof of Tutte's f-factor theorem

Let G be a multigraph on n vertices, possibly with loops. An f-factor is a subgraph of G with degree f_i at the ith vertex for i = 1, 2,…, n. Tutte's f-factor theorem is proved by providing an algorithm that either finds an f-factor or shows that it does not exist and does this in O(n³) operations. Note that the complexity bound is independent of the number of edges of G and the degrees f_i. The algorithm is easily altered to handle the problem of looking for a symmetric integral matrix with given row and column sums by assigning loops degree one. A (g,f)-factor is a subgraph of G with degree d_i at the ith vertex, where g_i ? d_i ? f_i, for i = 1,2,…, n. Lovasz's (g,f)-factor theorem is proved by providing an O(n³) algorithm to either find a (g,f)-factor or show one does not exist.     

Gray codes in graphs of subsets

Let G(n,k) be a graph whose vertices are the k-element subsets of an n-set represented as n-tuples of “O's” and “1's” with k “1's”. Two such subsets are adjacent if one can be obtained from the other by switching a “O” and a “1” which are in adjacent positions, where the first and nth positions are also considered adjacent. The problem of finding hamiltonian cycles in G(n,k) is discussed. This may be considered a problem of finding “Gray codes” of the k-element subsets of an n-set. It is shown that no such cycle exists if n and k are both even or if k=2 and n?7 and that such a cycle does exist in all other cases where k?5.     

Intersection theory for graphs

An intersection theory developed by the author for matroids embedded in uniform geometries is applied to the case when the ambient geometry is the lattice of partitions of a finite set so that the matroid is a graph. General embedding theorems when applied to graphs give new interpretations to such invariants as the dichromate of Tutte. A polynomial in n + 1 variables, the polychromate, is defined for graphs with n vertices. This invariant is shown to be strictly stronger than the dichromate, it is edge-reconstructible and can be calculated for proper graphs from the polychromate of the complementary graph. By using Tutte's construction for codichromatic graphs (J. Combinatorial Theory 16 (1974), 168–174), copolychromatic (and therefore codichromatic) graphs of arbitrarily high connectivity are constructed thereby solving a problem posed in Tutte's paper.     

A simple version of Karzanov's blocking flow algorithm

Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n²). Karzanov devised the first O(n²)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n²)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.