Search

This is partly joint work with Khaled Al-Khnaifes from Damascus who investigated relations between graph theory and linear algebra in his doctoral dissertation [1].

We generalize and unify results on parametrized and coloured Tutte polynomials of graphs and matroids due to Zaslavsky, and Bollobas and Riordan. We give a generalized Zaslavsky–Bollobas–Riordan theorem that characterizes parametrized contraction–deletion functions on minor-closed classes of matroids, as well as the modifications necessary to apply the discussion to classes of graphs. In general, these parametrized Tutte polynomials do not satisfy analogues of all the familiar properties of the classical Tutte polynomial. We give conditions under which they do satisfy corank-nullity formulas, and also conditions under which they reflect the structure of series-parallel connections.

It is a classical result of Jaeger, Vertigan and Welsh that evaluating the Tutte polynomial of a graph is nP-hard in all but a few special points. On the other hand, several papers in the past few years have shown that the Tutte polynomial of a graph can be efficiently computed for graphs of bounded tree-width. In this paper we present a recursive formula computing the Tutte polynomial of a matroid $M$ represented over a finite field (which includes all graphic matroids), using a so called parse tree of a branch-decomposition of $M$. This formula provides an algorithm computing the Tutte polynomial for a representable matroid of bounded branch-width in polynomial time with a fixed exponent.

Compound matrices which list the entire set of matchings in a bigraph are used to prove the theorem of Hall.

A bipolar orientation of a graph appears often in the algorithm literature as a first step for the generation of a particular drawing. Here the properties of bipolar orientations are systematically explored in terms of circuits, cocircuits, rank activities, Tutte polynomial, poset dimension, angle bipartition and max flow-min cut theorem. Efficient algorithms are described to list, generate or extend bipolar orientations for general graphs or plane ones, with or without constraints. (Joint work with Patrice de Mendez.)

In this paper we give theorems of the existence of T-joins with degrees bounded above in general simple graphs and in trees. The results generalize Tutte's perfect matching theorem and Amahashi's results on odd factors.

In 1966, Tutte presented a problem about matroids which contained as special cases the four-colour problem and two graph-theoretic extensions of it and he gave a conjecture as to the general solution. In this paper we reduce the matroid problem to one of the graph-theoretic special cases (the so-called 4-flow problem), and we show that his general conjecture is correct if it is true in this special case.

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.

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.

We give a combinatorial interpretation of the evaluation at (3, 3) of the Tutte polynomial of a planar graph. As a corollary we obtain a divisibility property.

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.

We prove that every graph with no isthmus has a nowhere-zero 6-flow, that is, a circulation in which the value of the flow through each edge is one of ±1, ±2,…, ±5. This improves Jaeger's 8-flow theorem, and approaches Tutte's 5-flow conjecture.

Let M M be a ternary matroid, t ( M , x , y ) t\left ( {M,x,y} \right ) be its Tutte polynomial and d ( M ) d\left ( M \right ) be the dimension of the bicycle space of any representation of M M over GF ( 3 ) {\text {GF}}\left ( 3 \right ) . We show that, for j = e 2 i π / 3 j = {e^{2i\pi /3}} , the modulus of the complex number t ( M , j , j 2 ) t\left ( {M,j,{j^2}} \right ) is equal to ( 3 ) d ( M ) {\left ( {\sqrt 3 } \right )^{d\left ( M \right )}} . The proof relies on the study of the weight enumerator W C ( y ) {W_\mathcal {C}}\left ( y \right ) of the cycle space C \mathcal {C} of a representation of M M over GF ( 3 ) {\text {GF}}\left ( 3 \right ) evaluated at y = j y = j . The main tool is the concept of principal quadripartition of C \mathcal {C} which allows a precise analysis of the evolution of the relevant invariants under deletion and contraction of elements. Soit M M un matroïde ternaire, t ( M , x , y ) t\left ( {M,x,y} \right ) son polynôme de Tutte et d ( M ) d\left ( M \right ) la dimension de l’espace des bicycles d’une représentation quelconque de M M sur GF ( 3 ) {\text {GF}}\left ( 3 \right ) . Nous montrons que, pour j = e 2 i π / 3 j = {e^{2i\pi /3}} , le module du nombre complexe t ( M , j , j 2 ) t\left ( {M,j,{j^2}} \right ) est égal à ( 3 ) d ( M ) {\left ( {\sqrt 3 } \right )^{d\left ( M \right )}} . La preuve s’appuie sur l’étude de l’énumérateur de poids W C ( y ) {W_\mathcal {C}}\left ( y \right ) de l’espace des cycles C \mathcal {C} d’une représentation de M M sur GF ( 3 ) {\text {GF}}\left ( 3 \right ) pour la valeur y = j y = j . L’outil essentiel est le concept de quadripartition principale de C \mathcal {C} qui permet une analyse précise de l’évolution des invariants concernés relativement à la suppression ou contraction d’éléments.

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 K2 by line addition, subdivision and point addition, one hopes to find operations which classify n-connected graphs as those obtainable from, for example, Kn+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.

The de Bruijn—van Aardenne Ehrenfest— Smith—Tutte theorem [1] is a theorem which connects the number of Eulerian dicircuits in a directed graph with the number of rooted spanning arborescences. In this paper we obtain a proof of this theorem by considering sequences over a finite alphabet, and we show that the theorem emerges from the generating function for a certain type of sequence. The generating function for the set of sequences is obtained as the solution of a linear system of equations in Section 2. The power series expansion for the solution of this system is obtained by means of the multivariate form of the Lagrange theorem for implicit functions, and is given in Section 3, together with a restatement of the theorem as a matrix identity.

Tutte generalized some well-known coloring problems in graph theory into a single geometric problem and made a conjecture about the existence of tangential 2-blocks in the finite projective geometry PG(n,2) over the Galois field of order 2. An affirmative solution of Tutte's conjecture will imply an affirmative solution of the 4-color problem. In this paper some general results have been developed to attack the general problem, posed by Tutte, and finally an analysis of tangential 2-blocks of dimensions 4 and 5 has been made in order to illustrate the applications of these results.

Short proofs of two theorems are given: (i) Whitney's 2-isomorphism theorem characterizing all graphs with the same cycle matroid, and (ii) Tutte's excluded minor characterization of those binary matroids that are graphic. Graph connectivity plays an important role in both proofs.

A unified way is described of constructing two 5-are-transitive graphs of valency 3, the Tutte 8-cage, and the Conder graph. It well illustrates the method of constructing symmetric graphs described in P. Lorimer “Vertex Transitive Graphs: Symmetric Graphs of Prime Valency,” Journal of Graph Theory, 8 (1984, 55–68).

Heawood proved that every planar graph with no 1-cycles is vertex 5-colorable, which is equivalent to the statement that every planar graph with no 1-bonds has a nowhere-zero 5-flow. Tutte has conjectured that every graph with no 1-bonds has a nowhere-zero 5-flow. We show that Tutte's 5-Flow Conjecture is true for all graphs embeddable in the real projective plane.

A general criterion is proved for a graph of any cardinality to possess a perfect matching. The criterion is used to prove an extension of Tutte's 1-factor theorem for general 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.

We prove the following theorem: A binary matroid is regular (totally unimodular) if and only if it has no submatroid that is a series extension of a Fano matroid or its dual. This theorem may be viewed as strengthening Tutte's celebrated characterization of regular matroids in the spirit of Kuratowski's theorem on planar graphs.

The number of linearly independent perfect matchings of a graph — or, equivalently, the dimension of the perfect matching polytope — is determined in various senses. First it is shown that the fact that every linear objective function can be optimized over the perfect matchings in polynomial time implies the existence of a polynomial-time algorithm to determine the dimension of this set. This observation also yields polynomial algorithms to determine, among others, the number of linearly independent common bases of two matroids and the number of linearly independent maximum stable sets in claw-free or perfect graphs. For the case of perfect matchings, Naddef’s minimax theorem for the dimension of the perfect matching polytope is strengthened and it is shown how the decomposition theory of matchings in graphs can be applied to derive a particularly simple formula for this dimension. This formula is based upon the number of constituents of a certain decomposition of the graph which we call a brick decomposition. Finally, these results are applied to obtain a description of the facets of the perfect matching polytope.

of the general theorem about the existence of subgraphs with prescribed local degrees. The criterion obtained is related to a criterion established by Tutte but it is considerably simpler in its application, through the fact that it refers only to the properties of single subsets of the vertex set, while the criterion of Tutte involves the choice of pairs of subsets. The proof is based on the alternating path method originally introduced by Petersen in graph theory, and subsequently used by most writers studying the existence of subgraphs, let us mention only the more recent papers by Baebler, Beick, Gallai and Tutte. Due to the applications our presentation of the alternating path theory differs in certain respects from the previous ones, but to save space the proofs have been based, as far as possible, upon those given by the preceding authors. The references are made to the paper by Tutte [12] which should be readily available to most readers. In Chapter 3 one finds various new explicit factorizations for nonregular graphs of certain types. It is pointed out how all the known results on the factorization of regular graphs, in particular those by Baebler, Gallai and Tutte, follow as special cases. To conclude one finds an example to show that a certain limit for the factorization of odd regular graphs given by Baebler is

In this paper we consider finite graphs without loops and multiple edges. A graph is considered to be an ordered pair 〈G, *〉 where G is a finite set the elements of which are called the vertices of while * is a subset of [G]2 (where [G]2 is the set of all subsets of two elements of G). The elements of * are called the edges of . If {P, Q} ∊ *, we say that Q is adjacent to P. The degree of a vertex is the number of vertices adjacent to it. Let k be an integer. We say that is the complete k-graph if G has k elements and * = [G]2.

$q$-Matroids are defined on complemented modular support lattices. Minors of length 2 are of four types as in a "classical" matroid. Tutte polynomials $\tau(x,y)$ of matroids are calculated either by recursion over deletion/contraction of single elements, by an enumeration of bases with respect to internal/external activities, or by substitution $x \to (x-1),\; y \to (y-1)$ in their rank generating functions $\rho(x,y)$. The $q$-analogue of the passage from a Tutte polynomial to its corresponding RGF is straight-forward, but the analogue of the reverse process $x \to (x-1),\; y \to (y-1)$ is more delicate. For matroids $M(S)$ on a set $S$, and relative to any linear order on the points, the concept of internal/external activity of a point relative to a basis gives rise to a partition of the underlying Boolean algebra $B(S)$ into a set of "prime-free" (or "structureless") minors, such minors being direct sums of loops and isthmi (coloops), with one such prime-free minor for each basis. What usually goes unnoticed is that each prime-free minor has a unique clopen flat. The latter property carries over to $q$-matroids, but each prime-free minor will contain many bases. So internal and external activity in $q$-matroids must be defined not for points relative to bases, but rather for coverings in the underlying complemented modular lattice. Following lattice paths from arbitrary subspaces $A$ along active coverings (downward for internally active, upward for externally active) will lead to the unique clopen subspace in the prime-free minor containing the subspace $A$. There are a number of interesting questions concerning $q$-matroids that remain unsolved.

A matching of a graph is a near-perfect matching if it covers all but one vertex. A connected graph G is said to be factor-critical if G − v has perfect matchings for every vertex v of G. In this paper, the enumeration problems for near-perfect matchings in special factor-critical graphs are solved. From this, the exact values of the number of perfect matchings in special bicritical graphs are obtained.

Let B + (2k) be the set of all bicyclic graphs on 2 k ( k ⩾2) vertices with perfect matchings. In this paper, we discuss some properties of the connected graphs with perfect matchings, and then determine graphs with maximal index in B + (2k) .

Tutte made the conjecture in 1966 that every 2-connected cubic graph not containing the Petersen graph as a minor is 3-edge-colourable. The conjecture is still open, but we show that it is true, in general, provided it is true for two special kinds of cubic graphs that are almost planar.

The notion of activities with respect to spanning trees in graphs was introduced by W.T. Tutte, and generalized to activities with respect to bases in matroids by H. Crapo. We present a further generalization, to activities with respect to arbitrary subsets of matroids. These generalized activities provide a unified view of several different expansions of the Tutte polynomial and the chromatic polynomial.

For each pair of algebraic numbers (x,y) and each fieldF, the complexity of computing the Tutte polynomialT(M;x,y) of a matroidMrepresentable overFis determined. This computation is found to be#P-complete except when (x−1)(y−1)=1 or when |F| divides (x−1)(y−1) and (x,y) is one of the seven points (0,−1), (−1,0), (i,−i), (−i,i), (j,j2), (j2,j) or (−1,−1), wherej=e2πi/3. Expressions are given for the Tutte polynomial in the exceptional cases. These expressions involve the bicycle dimension ofMoverF. A related result determines when this bicycle dimension is well defined.

Recently, Bauer et al. (J Graph Theory 55(4) (2007), 343--358) introduced a graph operator $D(G)$, called the $D$-graph of $G$, which has been useful in investigating the structural aspects of maximal Tutte sets in $G$ with a perfect matching. Among other results, they proved a characterization of maximal Tutte sets in terms of maximal independent sets in the graph $D(G)$ and maximal extreme sets in $G$. This was later extended to graphs without perfect matchings by Busch et al. (Discrete Appl. Math. 155 (2007), 2487--2495). Let $\theta$ be a real number and $\mu(G,x)$ be the matching polynomial of a graph $G$. Let $\textnormal{mult} (\theta, G)$ be the multiplicity of $\theta$ as a root of $\mu(G,x)$. We observe that the notion of $D$-graph is implicitly related to $\theta=0$. In this paper, we give a natural generalization of the $D$-graph of $G$ for any real number $\theta$, and denote this new operator by $D_{\theta}(G)$, so that $D_{\theta}(G)$ coincides with $D(G)$ when $\theta=0$. We prove a characterization of maximal $\theta$-Tutte sets which are $\theta$-analogue of maximal Tutte sets in $G$. In particular, we show that for any $X \subseteq V(G)$, $|X|>1$, and any real number $\theta$, $\m(\theta, G \setminus X)=\m(\theta, G)+|X|$ if and only if $\m(\theta, G \setminus uv)=\m(\theta, G)+2$ for any $u, v \in X$, $u \not = v$, thus extending the preceding work of Bauer et al. and Busch et al. which established the result for the case $\theta=0$., Comment: 22 pages

We introduce the concept of matching connectivity as a notion of connectivity in graph admitting perfect matchings which heavily relies on the structural properties of those matchings. We generalise a result of Robertson, Seymour and Thomas for bipartite graphs with perfect matchings (see [Neil Roberts, Paul D Seymour, and Robin Thomas. Permanents, pfaffian orientations, and even directed curcuits. Annals of Mathematics, 150(2):929-975, 1999]) in order to obtain a concept of alternating paths that turns out to be sufficient for the description of our connectivity parameter. We introduce some basic properties of matching connectivity and prove a Menger-type result for matching n-connected graphs. Furthermore, we show that matching connectivity fills a gap in the investigation of n-extendable graphs and their connectivity properties. To be more precise we show that every n-extendable graph is matching n-connected and for the converse every matching (n+1)-connected graph either is n-extendable, or belongs to a well described class of graphs: the brace h-critical graphs., Error in main proof

We define an r - bounded cover of a graph G to be a subgraph T ⊆ G such that T contains all vertices of G and each component of T is a complete subgraph of G of order at most r . A 2-bounded cover of a graph G corresponds to a matching of G , and an ω ( G )-bounded cover of G corresponds to a colouring of the vertices of the complement G . We generalise a number of results on matching and colouring of graphs to r -bounded covers, including the Gallai–Edmonds Structure Theorem, Tutte's 1-Factor Theorem, and Gallai's theorem on the minimal order of colour-critical graphs with connected complements.

Let Ĝ be a graph obtained from a graph G with no loops or coloops by replacing each edge e=uw of G by a connected graph He that has only the vertices u and w in common with the rest of Ĝ. Two mutually dual formulas are proved for the Tutte polynomial of Ĝ in terms of parameters of the graphs He and (in the one case) flow polynomials of subgraphs of G or (in the other case) tension polynomials of contractions of G. This generalizes the results of Read and Whitehead on homeomorphism classes of graphs.

An explicit construction is given which produces all the proper flats and the Tutte polynomial of a geometric lattice (or, more generally, a matroid) when only the hyperplanes are known. A further construction explicitly calculates the polychromate (a generalization of the Tutte polynomial) for a graph from its vertex-deleted subgraphs.

We develop a Tutte decomposition theory for matrices and their combinatorial abstractions, bimatroids. As in the graph or matroid case, this theory is based on a deletion–contraction decomposition. The contribution from the deletion, derived by an inclusion–exclusion argument, consists of three terms. With one more term contributed from the contraction, the decomposition has four terms in general. There are universal decomposition invariants, one of them being a corank–nullity polynomial. Under a simple change of variables, the corank–nullity polynomial equals a weighted characteristic polynomial. This gives an analog of an identity of Tutte. Applications to counting and critical problems on matrices and graphs are given.

This paper develops a theory of Tutte invariants for 2-polymatroids that parallels the corresponding theory for matroids. It is shown that such 2-polymatroid Invariants arise in the enumeration of a wide variety of combinatorial structures including matchings and perfect matchings in graphs, weak colourings in hypergraphs, and common bases in pairs of matroids. The main result characterizes all such invariants proving that, with some trivial exceptions, every 2-polymatroid Tutte invariant can be easily expressed in terms of a certain two-variable polynomial that is closely related to the Tutte polynomial of a matroid.

An edge-coloration theorem for bipartite graphs, announced in [4], is proved from which some well-known theorems due to Konig [5] and the author [2, 3] are deduced. The theorem is further applied to prove the “dual” of a theorem due to Lovasz [6].

In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let $\omega$ be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph. Tutte's conjecture is equivalent to its restriction to cubic graphs with $\omega \geq 2$. We show that if a cubic graph $G$ has no edge cut with fewer than $ {5/2} \omega - 1$ edges that separates two odd cycles of a minimum 2-factor of $G$, then $G$ has a nowhere-zero 5-flow. This implies that if a cubic graph $G$ is cyclically $n$-edge connected and $n \geq {5/2} \omega - 1$, then $G$ has a nowhere-zero 5-flow.

The V -functions of Tutte [1] are generalized to U -functions on graphs with a distinguished subset of vertices. The class of U -functions of two variables generalize dichromatic polynomials as well as the W -functions defined by Tutte [2]. The values of U -functions on a graph G are characterized in terms of spanning subgraphs of G and also in terms of collections of simple graphs constructed from G . Decompositions of dichromatic polynomials as well as dichromatic U -functions are obtained in terms of decompositions of G .

We consider generalizations of the Tutte polynomial on multigraphs obtained by keeping the main recurrence relation T(G)=T(G/e)+T(G−e) for e∈E(G) neither a bridge nor a loop and dropping the relations for bridges and loops. Our first aim is to find the universal invariant satisfying these conditions, from which all others may be obtained. Surprisingly, this turns out to be the universal V-function Z of Tutte (1947, Proc. Cambridge Philos. Soc.43, 26–40) defined to obey the same relation for bridges as well. We also obtain a corresponding result for graphs with colours on the edges and describe the universal coloured V-function, which is more complicated than Z. Extending results of Tutte (1974, J. Combin. Theory Ser. B16, 168–174) and Brylawski (1981, J. Combin. Theory Ser. B30, 233–246), we give a simple proof that there are non-isomorphic graphs of arbitrarily high connectivity with the same Tutte polynomial and the same value of Z. We conjecture that almost all graphs are determined by their chromatic or Tutte polynomials and provide mild evidence to support this.

The greedoid Tutte polynomial of a tree is equivalent to a generating function that encodes information about the number of subtrees with I internal (non-leaf) edges and L leaf edges, for all I and L. We prove that this information does not uniquely determine the tree T by constructing an infinite family of pairs of non-isomorphic caterpillars, each pair having identical subtree data. This disproves conjectures of [S. Chaudhary, G. Gordon, Tutte polynomials for trees, J. Graph Theory 15 (1991) 317–331] and [G. Gordon, E. McDonnell, D. Orloff, N. Yung, On the Tutte polynomial of a tree, Congr. Numer. 108 (1995) 141–151] and contrasts with the situation for rooted trees, where this data completely determines the rooted tree.

This paper characterizes, for each i and j , the matroids that are minor-minimal among connected matroids M with b ij ( M ) > 0, where t ( M ) = Σb ij ( M ) x i y j is the Tutte polynomial of M . One consequence of this characterization for a connected matroid M is that b 11 ( M ) > 0 if and only if the two-wheel is a minor of M . Similar results are obtained for other small values of i and j . A generalization of these results leads to new combinatorial proofs which strengthen known results on the coefficients. These results imply that if M is simple and representable over GF( q ), then there are coefficients of its Tutte polynomial which count the flats of M of each rank that are projective spaces. Similarly, for a simple graphic matroid M ( G ), there are coefficients that count the number of cliques of each size contained in G .

Given a graph @C and an automorphism group [email protected]?Aut(@C), we define some polynomials which count and classify the orbits of G on various structures on @C, as counted by the Tutte polynomial, while also specialising to the Tutte polynomial.

A bipartite graph G=(A,B) is said to have positive surplus (as viewed from A) if the number of neighbors of X is bigger than the size of X for any non-empty subset X of A. In this paper, two lower bounds on the number of maximum matchings in bipartite graphs with positive surplus are obtained. The enumeration problems for maximum matchings in special bipartite graphs are solved. From this, the number of perfect matchings of some elementary bipartite graphs is given.

The two variable greedoid Tutte polynomialf(G;t,z), which was introduced in previous work of the authors, is studied via external activities. Two different partitions of the Boolean lattice of subsets are derived and a feasible set expansion off(G) is developed. All three of these results generalize theorems for matroids. One interval partition yields a characterization of antimatroids among the class of all greedoids. As an application, we prove that whenGis the directed branching greedoid associated with a rooted digraphD, then the highest power of (z+1) which dividesf(G) equals the minimum number of edges which can be removed fromDto produce an acyclic digraph in which all vertices ofDare still accessible from the root. The unifying theme behind these results is the idea of a computation tree.

A counterexample is given to a conjecture by Tutte on the minimum number of spanning trees that a 3-connected planar graph with a prescribed number of edges may have.