Search

We find a graph of genus $5$ and its drawing on the orientable surface of genus $4$ with every pair of independent edges crossing an even number of times. This shows that the strong Hanani-Tutte theorem cannot be extended to the orientable surface of genus $4$. As a base step in the construction we use a counterexample to an extension of the unified Hanani-Tutte theorem on the torus., 12 pages, 4 figures; minor revision, new section on open problems

A graph is planar if it has a drawing in which no two edges cross. The Hanani-Tutte Theorem states that a graph is planar if it has a drawing $D$ such that any two edges in $D$ cross an even number of times. A graph $G$ is a non-separating planar graph if it has a drawing $D$ such that (1) edges do not cross in $D$, and (2) for any cycle $C$ and any two vertices $u$ and $v$ that are not in $C$, $u$ and $v$ are on the same side of $C$ in $D$. Non-separating planar graphs are closed under taking minors and hence have a finite forbidden minor characterisation. In this paper, we prove a Hanani-Tutte type theorem for non-separating planar graphs. We use this theorem to prove a stronger version of the strong Hanani-Tutte Theorem for planar graphs, namely that a graph is planar if it has a drawing in which any two disjoint edges cross an even number of times or it has a chordless cycle that enables a suitable decomposition of the graph.

We introduce the notion of a delta-matroid perspective. A delta-matroid perspective consists of a triple ( M , D , N ) , where M and N are matroids and D is a delta-matroid such that there are strong maps from M to the upper matroid of D and from the lower matroid of D to N . We describe two Tutte-like polynomials that are naturally associated with delta-matroid perspectives and determine various properties of them. Furthermore, we show when the delta-matroid perspective is read from a graph in a surface our polynomials coincide with B. Bollobas and O. Riordan's ribbon graph polynomial and the more general Krushkal polynomial of graphs in surfaces. This is analogous to the fact that the Tutte polynomial of a graph G coincides with the Tutte polynomial of its cycle matroid. We use this new framework to prove results about the topological graph polynomials that cannot be realised in the setting of cellularly embedded graphs.

Self-similar graphs were widely studied in both combinatorics and statistical physics. Motivated by the construction of the well-known 3-dimensional Sierpinski gasket graphs, in this paper we introduce a family of recursively constructed self-similar graphs whose inner duals are of the self-similar property. By combining the dual property of the Tutte polynomial and the subgraph-decomposition trick, we show that the Tutte polynomial of this family of graphs can be computed in an iterative way and in particular the exact expression of the formula of the number of their spanning trees is derived. Furthermore, we show our method is a general one that is easily extended to compute Tutte polynomials for other families of self-similar graphs such as Farey graphs, 2-dimensional Sierpinski gasket graphs, Hanoi graphs, modified Koch graphs, Apollonian graphs, pseudofractal scale-free web, fractal scale-free network, etc.

Tutte–Grothendieck invariants of graphs are mappings from a class of graphs to a commutative ring that are characterized recursively by contraction-deletion rules. Well known examples are the Tutte, chromatic, tension and flow polynomials. Suppose that an edge cut C divides a graph G into two parts G1, G1′ and that G1, G1′ are the sets of minors of G whose edge sets consist of C and edges of G1, G1′, respectively. We study determinant formulas evaluating a Tutte–Grothendieck invariant of G from the Tutte–Grothendieck invariants of graphs from G1 and G1′.

We obtain a sharp result that for any even n ? 34, every {Dn,Dn+1}-regular graph of order n contains ?n/4? disjoint perfect matchings, where Dn = 2?n/4?-1. As a consequence, for any integer D ? Dn, every {D, D+1}- regular graph of order n contains (D-?n/4?+1) disjoint perfect matchings.

The Tutte polynomial of a graph, or equivalently the q-state Potts model partition function, is a two-variable polynomial graph invariant of considerable importance in both statistical physics and combinatorics. The computation of this invariant for a graph is NP-hard in general. In this paper, we focus on two iteratively growing scale-free networks, which are ubiquitous in real-life systems. Based on their self-similar structures, we mainly obtain recursive formulas for the Tutte polynomials of two scale-free networks (lattices), one is fractal and “large world”, while the other is non-fractal but possess the small-world property. Furthermore, we give some exact analytical expressions of the Tutte polynomial for several special points at (x, y)-plane, such as, the number of spanning trees, the number of acyclic orientations, etc.

Let $c_n$ denote the number of vertex-labeled connected graphs on $n$ vertices. Using group actions and elementary number theory, we show that the infinite sequence, $c_n : n \ge 1,$ is ultimately periodic modulo every positive integer. We state and prove our results for sequences defined by a weighted generalization of $c_n$ and conjecture that these results are suggestive of similar periodic behavior of the Tutte polynomial evaluations of the complete graph $K_n$ at integer points.

We establish a relation between the Bollobas–Riordan polynomial of a ribbon graph with the relative Tutte polynomial of a plane graph obtained from the ribbon graph using its projection to the plane in a nontrivial way. Also we give a duality formula for the relative Tutte polynomial of dual plane graphs and an expression of the Kauffman bracket of a virtual link as a specialization of the relative Tutte polynomial.

Using two related parameters, ζ and γ, we extend the recursion for com- puting the Tutte polynomial of any graph to the computation of the Tutte polynomial of any multigraph. With this recursion, we found explicit formulae for several fami- lies of multigraphs. In particular, the Tutte polynomials of some cyclic multigraphs, 2−tree multigraphs, and any l−bridge multigraph.

We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph $G$ has a drawing $D$ in the plane where every pair of independent edges crosses an even number of times, then $G$ has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in $D$. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof.

A gain graph is a graph whose edges are orientably labelled from a group. A weighted gain graph is a gain graph with vertex weights from an abelian semigroup, where the gain group is lattice ordered and acts on the weight semigroup. For weighted gain graphs we establish basic properties and we present general dichromatic and forest-expansion polynomials that are Tutte invariants (they satisfy Tutte's deletion-contraction and multiplicative identities). Our dichromatic polynomial includes the classical graph one by Tutte, Zaslavsky's two for gain graphs, Noble and Welsh's for graphs with positive integer weights, and that of rooted integral gain graphs by Forge and Zaslavsky. It is not a universal Tutte invariant of weighted gain graphs; that remains to be found. An evaluation of one example of our polynomial counts proper list colorations of the gain graph from a color set with a gain-group action. When the gain group is Z^d, the lists are order ideals in the integer lattice Z^d, and there are specified upper bounds on the colors, then there is a formula for the number of bounded proper colorations that is a piecewise polynomial function of the upper bounds, of degree nd where n is the order of the graph. This example leads to graph-theoretical formulas for the number of integer lattice points in an orthotope but outside a finite number of affinographic hyperplanes, and for the number of n x d integral matrices that lie between two specified matrices but not in any of certain subspaces defined by simple row equations., 32 pp. Submitted in 2007, extensive revisions in 2013 (!). V3: Added references, clarified examples. 35 pp

We reprove the strong Hanani-Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi, our method is constructive and does not rely on the characterization of forbidden minors, which gives hope to extend it to other surfaces. Moreover, our approach can be used to provide an efficient algorithm turning a Hanani-Tutte drawing on the projective plane into an embedding., This is the full version of the paper. Its extended abstract appeared in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

The reliability of the Internet of Things is critical because the services of it will be concerned with real life, although the low cost may limit the number of links of each computer. In this paper, we analyze the all-terminal reliability of wireless regular graphs of which the number of links of each node is bounded. We derive the exact reliability polynomials for four regular graphs that are important candidates. The reliability polynomials are directly derived from the Tutte polynomial, which is the seminal work of the algebraic graph theory. To make the Tutte polynomials for graphs, we use the fastest program that was recently developed. As a result, we found that the torus graph of width three or more is the most reliable bounded degree network.

Brylawski proved the coefficients of the Tutte polynomial of a matroid satisfy a set of linear relations. We extend these relations to a generalization of the Tutte polynomial that includes greedoids and antimatroids. This leads to families of new identities for antimatroids, including trees, posets, chordal graphs and finite point sets in $\mathbb{R}^n$. It also gives a "new" linear relation for matroids that is implied by Brylawski's identities.

We show that a factor-critical graph of order n has exactly n near-perfect matchings if and only if it is a connected graph whose blocks are all odd cycles. This characterizes the factor-critical graphs with the minimum number of near-perfect matchings.