Upon the removal of the edges of a 1-factor from an even circuit in a 2-connected graph

Let G be a 2-connected graph with minimum degree at least 3. We prove that there exists an even circuit C in G with factorization F={F₁,F₂} such that G−E(F₁) is 2-connected.     

Connected even factors in claw-free graphs

A connected even [2,2s]-factor of a graph G is a connected factor with all vertices of degree i (i=2,4,…,2s), where s?1 is an integer. In this paper, we show that every supereulerian K_1,s-free graph (s?2) contains a connected even [2,2s-2]-factor, hereby generalizing the result that every 4-connected claw-free graph has a connected [2,4]-factor by Broersma, Kriesell and Ryjacek.     

Finding Hamiltonian circuits in quasi-adjoint graphs

This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothermic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718–729]. This paper presents a class of digraphs: the quasi-adjoint graphs. This class includes the ones used in the paper cited above. A polynomial recognition algorithm in O(n³), as well as a polynomial algorithm in O(n²+m²) for finding a Hamiltonian circuit in these graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a path with three vertices) are discussed.     

The structure of even factors in claw-free graphs

Recently, Jackson and Yoshimoto proved that every bridgeless simple graph G with δ(G)≥3 has an even factor in which every component has order at least four, which strengthens a classical result of Petersen. In this paper, we give a strengthening of the above result and show that the above graphs have an even factor in which every component has order at least four that does not contain any given edge. We also extend the above result to the graphs with minimum degree at least three such that all bridges lie in a common path and to the bridgeless graphs that have at most two vertices of degree two respectively. Finally we use this extended result to show that every simple claw-free graph G of order n with δ(G)≥3 has an even factor with at most components. The upper bound is best possible.     

A lower bound on the number of removable ears of 1-extendable graphs

Let G be a 1-extendable graph distinct from K₂ and C_2n. A classical result of Lovász and Plummer (1986) [5, Theorem 5.4.6] states that G has a removable ear. Carvalho et al. (1999) [3] proved that G has at least Δ(G) edge-disjoint removable ears, where Δ(G) denotes the maximum degree of G. In this paper, the authors improve the lower bound and prove that G has at least m(G) edge-disjoint removable ears, where m(G) denotes the minimum number of perfect matchings needed to cover all edges of G.     

拟阵的可去圈

本首先用拟阵语言将图论的新概念定义成了拟阵的新概念，然后用拟阵语言将Goddyn和Heuevl所得的图论上的新结果平移成了拟阵的新结果，最后用拟阵的方法对它们给出了新的证明。     

On maximal circuits in directed graphs

An exact bound is obtained for the number of edges in a directed graph which ensures the existence of a circuit exceeding a prescribed length.Another proof of an analogous result of Erdös and Gallai for undirected graphs is supplied in the Appendix.     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

On even circuit decompositions of eulerian graphs

Let G be an eulerian graph without odd block. It was proved by P. D. Seymour that if G is planar, then E(G) has a circuit decomposition F such that each circuit of F is of even length. In this paper the theorem of Seymour is generalized: If G contains no subgraph contractible to K₅, then E(G) has an even circuit decomposition.     

On circuits and pancyclic line graphs

Clark proved that L(G) is hamiltonian if G is a connected graph of order n ≥ 6 such that deg u + deg v ≥ n – 1 – p(n) for every edge uv of G, where p(n) = 0 if n is even and p(n) = 1 if n is odd. Here it is shown that the bound n – 1 – p(n) can be decreased to (2n + 1)/3 if every bridge of G is incident with a vertex of degree 1, which is a necessary condition for hamiltonicity of L(G). Moreover, the conclusion that L(G) is hamiltonian can be strengthened to the conclusion that L(G) is pancyclic. Lesniak-Foster and Williamson proved that G contains a spanning closed trail if |V(G)| = n ≥ 6, δ(G) ≥ 2 and deg u + deg v ≥ n – 1 for every pair of nonadjacent vertices u and v. The bound n – 1 can be decreased to (2n + 3)/3 if G is connected and bridgeless, which is necessary for G to have a spanning closed trail.     

Cycles of even length in graphs

In this paper we solve a conjecture of P. Erdös by showing that if a graph Gⁿ has n vertices and at least $\text{100kn}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}$ edges, then G contains a cycle C^2l of length 2l for every integer $\text{l ∈ [k, kn}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}\text{]}$. Apart from the value of the constant this result is best possible. It is obtained from a more general theorem which also yields corresponding results in the case where Gⁿ has only cn(log n)^α edges (α ≥ 1).     

Even circuits in planar graphs

We prove that a planar graph can be partitioned into edge-disjoint circuits of even length, if and only if every vertex has even valency and every block has an even number of edges.     

Hamiltonian circuits in Cayley graphs

The following result is proved: If either G is a finite abelian group or a semidirect product of a cyclic group of prime order by a finite abelian group of odd order, then every connected Cayley graph of G is hamiltonian.     

Characterization of even directed graphs

We present a precise characterization of the diagraphs D withthe property that any subdivision of D contains of a cycle of even length.