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.     

On the number of cycles in local tournaments

A digraph without loops, multiple arcs and directed cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. A vertex of a strongly connected digraph is called a non-separating vertex if its removal preserves the strong connectivity of the digraph in question.In 1990, Bang-Jensen showed that a strongly connected local tournament does not have any non-separating vertices if and only if it is a directed cycle. Guo and Volkmann extended this result in 1994. They determined the strongly connected local tournament with exactly one non-separating vertex. In the first part of this paper we characterize the class of strongly connected local tournaments with exactly two non-separating vertices.In the second part of the paper we consider the following problem: Given a strongly connected local tournament D of order n with at least n+2 arcs and an integer 3≤r≤n. How many directed cycles of length r exist in D? For tournaments this problem was treated by Moon in 1966 and Las Vergnas in 1975. A reformulation of the results of the first part shows that we have characterized the class of strongly connected local tournaments with exactly two directed cycles of length n−1. Among other things we show that D has at least n−r+1 directed cycles of length r for 4≤r≤n−1 unless it has a special structure. Moreover, we characterize the class of local tournaments with exactly n−r+1 directed cycles of length r for 4≤r≤n−1 which generalizes a result of Las Vergnas.     

Connected hyperplanes in binary matroids

For a 3-connected binary matroid M, let dim_A(M) be the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of M avoiding A, where A⊆E(M). When A=∅, Bixby and Cunningham, in 1979, showed that dim_A(M)=r(M). In 2004, when |A|=1, Lemos proved that dim_A(M)=r(M)-1. In this paper, we characterize the 3-connected binary matroids having a pair of elements that meets every non-separating cocircuit. Using this result, we show that 2dim_A(M)?r(M)-3, when M is regular and |A|=2. For |A|=3, we exhibit a family of cographic matroids with a 3-element set intersecting every non-separating cocircuit. We also construct the matroids that attains McNulty and Wu’s bound for the number of non-separating cocircuits of a simple and cosimple connected binary matroid.     

On circuit decomposition of planar Eulerian graphs

We give a common generalization of P. Seymour's “Integer sum of circuits” theorem and the first author's theorem on decomposition of planar Eulerian graphs into circuits without forbidden transitions.     

The maximum genus of a 3-regular simplicial graph

In this paper, the relationship between non-separating independent number and the maximum genus of a 3-regular simplicial graph is presented. A lower bound on the maximumgenus of a 3-regular graph invalving girth is provided. The lower bound is tight, it improves a bound of Huang and Liu.     

Non-separating 2-factors of an even-regular graph

For a 2-factor F of a connected graph G, we consider G−F, which is the graph obtained from G by removing all the edges of F. If G−F is connected, F is said to be a non-separating 2-factor. In this paper we study a sufficient condition for a 2r-regular connected graph G to have such a 2-factor. As a result, we show that a 2r-regular connected graph G has a non-separating 2-factor whenever the number of vertices of G does not exceed 2r²+r.     

Short proofs of classical theorems

We give proofs of Ore's theorem on Hamilton circuits, Brooks' theorem on vertex coloring, and Vizing's theorem on edge coloring, as well as the Chvátal-Lovász theorem on semi-kernels, a theorem of Lu on spanning arborescences of tournaments, and a theorem of Gutin on diameters of orientations of graphs. These proofs, while not radically different from existing ones, are perhaps simpler and more natural. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 159–165, 2003     

Chromatic polynomials and whitney's broken circuits

The theorem of Hassler Whitney, which gives the chromatic polynomial of a graph in terms of “broken circuits,” is used to derive a new formula for the coefficients of chromatic polynomials.     

The polynomial and linear time hierarchies in V0

We show that the bounded arithmetic theory V⁰ does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Hamiltonian cycles in polyhedral maps

We present a necessary and sufficient condition for existence of a contractible, non-separating and non-contractible separating Hamiltonian cycle in the edge graph of polyhedral maps on surfaces. We also present algorithms to construct such cycles whenever it exists where one of them is linear time and another is exponential time algorithm.     

The Klein bottle and multicommodity flows

LetG be an eulerian graph embedded on the Klein bottle. Then the maximum number of pairwise edge-disjoint orientation-reversing circuits inG is equal to the minimum number of edges intersecting all orientation-reversing circuits. This generalizes a theorem of Lins for the projective plane. As consequences we derive results on disjoint paths in planar graphs, including theorems of Okamura and of Okamura and Seymour.     

关于平面图（3，1）＊-可选性的一个注记

给出了平面图的一个结构性定理,并证明了每个没有5-圈,相邻三角形,相邻四边形的平面图是（3,1）＊-可选色的．     

On the cone of nonnegative circuits

We discuss three equivalent formulations of a theorem of Seymour on nonnegative sums of circuits of a graph, and present a different (but not shorter) proof of Seymour's resut.Research supported, in part, by an IBM Postdoctoral Fellowship, a grant of the Alexander von Humboldt-Stiftung, and NSF grant DMS-8504050.     

Shorted Operators Relative to a Partial Order in a Regular Ring

In this article, the explicit form of maximal elements, known as shorted operators, in a subring of a von Neumann regular ring, has been obtained. As an application of the main theorem, the unique shorted operator (of electrical circuits), which was introduced by Anderson–Trapp, has been derived.     

Green's Functions for Quasi-Hyperbolic Metrics on Degenerating Riemann Surfaces with a Separating Node

In this article, we consider a family of compact Riemann surfaces of genus q 2 degenerating to a Riemann surface with a separating node and many non-separating nodes. We obtain the asymptotic behavior of Green's functions associated to a continuous family of quasi-hyperbolic metrics on such degenerating Riemann surfaces.     

Limit cycles of a class of Liénard systems derived from state-dependent impulses

Discontinuous phenomena, in which objects may behave continuously and sometimes discretely are not only found in nature and under laboratory conditions but also in simple, familiar contexts. For example, this phenomenon is skillfully incorporated into the internal structure of mechanical wristwatches. Unless an extremely small amount of state-dependent impulse is applied intermittently, the reciprocating rotational movement of the balance and hairspring, which is the heart of the mechanical wristwatch, cannot be maintained. The small amount of state-dependent impulse, which is often overlooked, can make a significant difference; however, very few studies have examined this subject. This study assumes the underlying cause of discontinuous behaviors as impulses generated when an object reaches a particular state, assuming that the continuous behavior follows the Liénard system, which is widely studied in the field of electrical circuits. The main theorem provides the conditions under which the effect of the impulses causes a stable limit cycle in the Liénard system, even if no limit cycle exists when there are no impulses. The Poincaré–Bendixson theorem for discontinuous dynamical systems and phase plane analysis are used to prove the main theorem. Several examples and their simulations are provided to illustrate the main theorem.     

Synchronized stationary distribution for stochastic multi-links systems with Markov jump

This paper is concerned with the existence of a synchronized stationary distribution for stochastic multi-links systems with Markov jump (SMMJs). By employing Lyapunov method, Kirchhoff’s Matrix Tree Theorem in graph theory as well as M-matrix method, several criteria are given to guarantee the existence of a synchronized stationary distribution of SMMJs, including the Lyapunov-type theorem and a coefficients-type theorem. As a subsequent, the theoretical results are applied to a class of stochastic Markov jump oscillators with multi-links and stochastic multi-links Chua’s circuits with Markov jump, which indicates the results present widely applied prospect in various physical systems. Eventually, two examples together with numerical simulations are provided to validate the effectiveness of the theoretical results.     

Qualitative behavior of solutions of Liénard-type systems with state-dependent impulses

State-dependent impulsive differential equations can be used to describe phenomena in which the velocity of an object suddenly changes when the object enters a predetermined state. This study examines the effect of state-dependent impulses on the rotation of all orbits of the Liénard system, which plays an important role in many research areas, including electrical circuits, diverse engineering fields, economics, ecology, and physiology. Determining whether all orbits of the Liénard system other than the origin, which is the only fixed point, rotate around the origin, is the basis of other properties of the orbit and has become a significant research subject; however, very few studies have examined the effects of state-dependent impulses on this behavior, and the main theorem presented in this paper addresses this. This rotation problem is reduced to establishing whether all orbits intersect the vertical isocline, which is discussed in detail. To facilitate the understanding of the proof of the main theorem, an overview is presented before providing the actual proof. The main theorem and some lemmas are proved using phase plane analysis. The application of the main theorem to Euler’s equations is also described.     

Ear decompositions of join covered graphs

Join covered graphs are ±1-weighted graphs, without negative circuits, in which every edge lies in a zero-weight circuit. Join covered graphs are a natural generalization of matching covered graphs. Many important properties of matching covered graphs have been generalized to join covered graphs. In this paper, we generalize Lovász and Plummerʼs ear decomposition theorem of matching covered graphs to join covered graphs.     

Incompressible surfaces in handlebodies and boundary reducible 3-manifolds

We study the existence of incompressible embeddings of surfaces into the genus two handlebody. We show that for every compact surface with boundary, orientable or not, there is an incompressible embedding of the surface into the genus two handlebody. In the orientable case the embedding can be either separating or non-separating. We also consider the case in which the genus two handlebody is replaced by an orientable 3-manifold with a compressible boundary component of genus greater than or equal to two.