A classification of 4-connected graphs

Having observed Tutte's classification of 3-connected graphs as those attainable from wheels by line addition and point splitting and Hedetniemi's classification of 2-connected graphs as those obtainable from K₂ by line addition, subdivision and point addition, one hopes to find operations which classify n-connected graphs as those obtainable from, for example, K_n+1. In this paper I give several generalizations of the above operations and use Halin's theorem to obtain two variations of Tutte's theorem as well as a classification of 4-connected graphs.     

Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

A generalization of Tutte's 1-factor theorem to countable graphs

A criterion is proved for a countable graph to possess a perfect matching, in terms of “marriage” in bipartite graphs associated with the graph. In the finite case, this yields Tutte's 1-factor theorem. The criterion is conjectured to be valid for general graphs.     

A characterization of 3-connected graphs containing a given graph

It is shown, as a complement to Tutte's theorem, that for a given 3-connected graph K which is not a wheel, a graph G is 3-connected and has a subgraph contractible to K if and only if G can be obtained from K by a finite sequence of line-additions and 3-point-splittings.     

Antipodal covering graphs

A graph $\text{Γ}$ of valency k with a group G of automorphisms may be studied via the action of G on the vertex set $\text{V}\text{Γ}$. If G acts transitively on $\text{V}\text{Γ}$, then the notions of primitivity and imprimitivity are meaningful. We consider a natural notion of “block system” for a general graph $\text{Γ}$, which allows us to derive a “quotient” graph Γ whose vertices correspond to the blocks. The ideas are applied to antipodal systems in antipodal graphs: in particular we prove that for an antipodal distance-regular graph, the block size r cannot exceed the valency k; we further show that an antipodal distance-regular graph with r = k is (i) a circuit graph, (ii) a complete bipartite graph, or (iii) a threefold covering of Tutte's trivalent eight-cage.     

Note on Halin's theorem on minimally connected graphs

In this note it is shown that any finite directed graph of strong connectivity n contains either a vertex with indegree n, a vertex with outdegree n, or an edge whose removal does not decrease the connectivity. This is a directed graph counterpart of Halin's theorem on undirected graphs. It is pointed out that only a few preparations and modifications are necessary to make his proof valid for directed graphs.     

On matroid connectivity

Three types of matroid connectivity, including Tutte's, are defined and shown to generalize corresponding notions of graph connectivity. A theorem of Tutte on cyclically 3-connected graphs, is generalized to matroids.     

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.     

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.     

Graphs with a common eigenvalue deck

In this paper, we consider graphs whose deck consists of cards (which are the vertex-deleted subgraphs) that share the same eigenvalue, say μ. We show that, the characteristic polynomial can be reconstructed from the deck, providing a new proof of Tutte’s result for this class of graphs. Moreover, for the subclass of non-singular graphs, the graph can be uniquely reconstructed from the eigenvectors of the cards associated with the eigenvalue μ. The remaining graphs in this class are shown to be μ-cores graphs.     

Two characterizations of interchange graphs of complete m-partite graphs

A graph G is m-partite if its points can be partitioned into m subsets V₁,…,V_m such that every line joins a point in V_i with a point in V_j, i ≠ j. A complete m-partite graph contains every line joining V_i with V_j. A complete graph K_p has every pair of its p points adjacent. The nth interchange graph I_n(G) of G is a graph whose points can be identified with the K_n+1's of G such that two points are adjacent whenever the corresponding K_n+1's have a K_n in common.Interchange graphs of complete 2-partite and 3-partite graphs have been characterized, but interchange graphs of complete m-partite graphs for m > 3 do not seem to have been investigated. The main result of this paper is two characterizations of interchange graphs of complete m-partite graphs for m ≥ 2.     

The set of irreducible graphs for the projective plane is finite

In 1930 Kuratowski proved that a graph does not embed in the real plane R² if and only if it contains a subgraph homeomorphic to one of two graphs, K₅ or K_{3, 3}. For positive integer n, let I_n (P) denote a smallest set of graphs whose maximal valency is n and such that any graph which does not embed in the real projective plane contains a subgraph homeomorphic to a graph in I_n (P) for some n. Glover and Huneke and Milgram proved that there are only 6 graphs in I₃ (P), and Glover and Huneke proved that I_n (P) is finite for all n. This note proves that I_n (P) is empty for all but a finite number of n. Hence there is a finite set of graphs for the projective plane analogous to Kuratowski's two graphs for the plane.     

On Petersen's graph theorem

In this paper we prove the following: let G be a graph with e_G edges, which is (k ? 1)-edge- connected, and with all valences ?k. Let 1?r?k be an integer, then G contains a spanning subgraph H, so that all valences in H are ?r, with no more than ?re_G?k? edges. The proof is based on a useful extension of Tutte's factor theorem [4,5], due to Lovász [3]. For other extensions of Petersen's theorem, see [6,7,8].     

Graphs of given genus and arbitrarily large maximum genus

The maximum genus of a connected graph G is the maximum among the genera of all compact orientable 2-manifolds upon which G has 2-cell embeddings. In the theorems that follow the use of an edge-adding technique is combined with the well-known Edmonds' technique to produce the desired results. Planar graphs of arbitrarily large maximum genus are displayed in Theorem 1. Theorem 2 shows that the possibility for arbitrarily large difference between genus and maximum genus is not limited to planar graphs. In particular, we show that the wheel graph, the standard maximal planar graph, and the prism graph are upper embeddable. We then show that given m and n, there is a graph of genus n and maximum genus larger than mn.     

Connectedness and classification of certain graphs

G. A. Dirac gives a necessary arc family condition for a graph to be n-vertex connected. The converse of this theorem of Dirac is false. Mesner and Watkins obtained partial results for additional conditions that the converse be true. A graph G which satisfies Dirac's arc family condition is now completely classified in terms of the order of V(G), the structure of parts of minimum cutsets of G and consequent lower bounds for vertex-connectivity of G. Examples show that all lower bounds are best possible. Several distinct extensions of Whitney's necessary and sufficient condition for a graph to be n-vertex connected also appear as corollaries. Finally, examples are presented to show a graph which satisfies a given n-family arc condition. However, the same graph does not satisfy a very similar (n ? 1)-family arc condition where exactly one arc has been eliminated from the statement of the original n-family arc conditon.     

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.     

The enumeration of bipartite graphs

The standard construction of graphs with n connected components is modified here for bicolored graphs by letting S_n × H act on the function space $\text{Y}{}^1\text{where}\text{X={1,2,…,n}, Y}$ is the set of connected bicolored graphs, and H is the group that interchanges the vertex colors. Then DeBruijn's Generalization of Polya's Theorem is applied to arrive at a direct algebraic relationship between the generating functions for bicolored and connected bicolored graphs. As the former generating function is easily computable, this relationship gives us the latter generating function which is precisely the generating function for connected bipartite graphs.     

On Reid's characterization of the ternary matroids

In this paper we prove a stronger version of a result of Ralph Reid characterizing the ternary matroids (i.e., the matroids representable over the field of 3 elements, GF(3)). In particular, we prove that a matroid is ternary if it has no seriesminor of type L_n for n ≥ 5 (n cells and n circuits, each of size n ? 1), and no series-minor of type $\text{L}{}_5{}^1$ (dual of L₅), BII (Fano matroid) or BI (dual of type BII). The proof we give does not assume Reid's theorem. Rather we give a direct proof based on the methods (notably the homotopy theorem) developed by Tutte for proving his characterization of regular matroids. Indeed, the steps involved in our proof closely parallel Tutte's proof, but carrying out these steps now becomes much more complicated.     

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.     

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.