Even cycles in graphs

Let G be a 3‐connected simple graph of minimum degree 4 on at least six vertices. The author proves the existence of an even cycle C in G such that G‐V(C) is connected and G‐E(C) is 2‐connected. The result is related to previous results of Jackson, and Thomassen and Toft. Thomassen and Toft proved that G contains an induced cycle C such that both G‐V(C) and G‐E(C) is 2‐connected. G does not in general contain an even cycle such that G‐V(C) is 2‐connected. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 163–223, 2004     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

Cycle‐Continuous Mappings—Order Structure

Given two graphs, a mapping between their edge‐sets is cycle‐continuous , if the preimage of every cycle is a cycle. The motivation for this definition is Jaeger's conjecture that for every bridgeless graph there is a cycle‐continuous mapping to the Petersen graph, which, if solved positively, would imply several other important conjectures (e.g., the Cycle double cover conjecture). Answering a question of DeVos, Ne?et?il, and Raspaud, we prove that there exists an infinite set of graphs with no cycle‐continuous mapping between them. Further extending this result, we show that every countable poset can be represented by graphs and the existence of cycle‐continuous mappings between them.     

Hamilton cycle decompositions of the tensor product of complete multipartite graphs

In this paper, tensor product of two regular complete multipartite graphs is shown to be Hamilton cycle decomposable. Using this result, it is immediate that the tensor product of two complete graphs with at least three vertices is Hamilton cycle decomposable thereby providing an alternate proof of this fact.     

Reconstruction of Discrete Sets from Four Projections: Strong Decomposability

In this paper we introduce the class of strongly decomposable discrete sets and give an efficient algorithm for reconstructing discrete sets of this class from four projections. It is also shown that every Q-convex set (along the set of directions {x, y}) consisting of several components is strongly decomposable. As a consequence of strong decomposability we get that in a subclass of hv-convex discrete sets the reconstruction from four projections can be solved in polynomial time.     

Hamilton cycle decomposition of 6‐regular circulants of odd order

The circulant G = C(n,S), where , is the graph with vertex set Z_n and edge set . It is shown that for n odd, every 6‐regular connected circulant C(n, S) is decomposable into Hamilton cycles. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Splitting Mixed Groups of Finite Torsion-Free Rank

Abstract

First, we give a necessary and sufficient condition for torsion-free finite rank subgroups of arbitrary abelian groups to be purifiable. An abelian group G is said to be a strongly ADE decomposable group if there exists a purifiable T(G)-high subgroup of G. We use a previous result to characterize ADE decomposable groups of finite torsion-free rank. Finally, in an extreme case of strongly ADE decomposable groups, we give a necessary and sufficient condition for abelian groups of finite torsion-free rank to be splitting.     

Cyclic even cycle systems of the complete graph

In this article, it is proved that for each even integer m?4 and each admissible value n with n>2m, there exists a cyclic m‐cycle system of K_n, which almost resolves the existence problem for cyclic m‐cycle systems of K_n with m even. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:23–39, 2012     

Resolvable even‐cycle systems with a 1‐rotational automorphism

In this article, necessary and sufficient conditions for the existence of a 1‐rotationally resolvable even‐cycle system of λK_v are given, which are eventually for the existence of a resolvable even‐cycle system of λK_v. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 394–407, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10058     

Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor

Let n≥2 be an integer. The complete graph K_n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K_n−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph K_{n, n} has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K_{n, n}, then K_{n, n}−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010     

A complete solution to the existence problem for 1‐rotational k‐cycle systems of Kv

The necessary and sufficient conditions for the existence of a 1‐rotational k‐cycle system of the complete graph K_v are established. The proof provides an algorithm able to determine, directly and explicitly, an odd k‐cycle system of K_v whenever such a system exists. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 283–293, 2009     

Cycles passing through k + 1 vertices in k‐connected graphs

In this article, we prove the following theorem. Let k ≥ 3 be an integer, G be a k‐connected graph with minimum degree d and X be a set of k + 1 vertices on a cycle. Then G has a cycle of length at least min {2d,|V(G)|} passing through X. This result gives the positive answer to the Question posed by Locke [8]. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:179–190, 2008     

Infinite paths in planar graphs IV,dividing cycles

Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if, and only if, the deletion of any finite set of vertices results in at most two infinite components. In this article, we prove this conjecture for graphs with no dividing cycles and for graphs with infinitely many vertex disjoint dividing cycles. A cycle in an infinite plane graph is called dividing if both regions of the plane bounded by this cycle contain infinitely many vertices of the graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 173–195, 2006     

Strong Decomposition of Random Variables

A random variable X is called strongly decomposable into (strong) components Y,Z, if X=Y+Z where Y=φ(X), Z=X−φ(X) are independent nondegenerate random variables and φ is a Borel function. Examples of decomposable and indecomposable random variables are given. It is proved that at least one of the strong components Y and Z of any random variable X is singular. A necessary and sufficient condition is given for a discrete random variable X to be strongly decomposable. Phenomena arising when φ is not Borel are discussed. The Fisher information (on a location parameter) in a strongly decomposable X is necessarily infinite.     

Coloring 4‐cycle systems

An m‐cycle system of order n is a partition of the edges of the complete graph K_n into m‐cycles. We investigate k‐colorings of 4‐cycle systems in which no 4‐cycle is monochromatic. For any k ≥ 3, we construct a k‐chromatic 4‐cycle system. We also show that for any k ge; 2, there exists an integer w_k such that for all admissible n ≥ w_k, there is a k‐chromatic 4‐cycle system of order n. © 2005 Wiley Periodicals, Inc. J Combin Designs     

On hamiltonian cycles in the prism over the odd graphs

The Kneser graph K(n, k) has as its vertex set all k‐subsets of an n‐set and two k‐subsets are adjacent if they are disjoint. The odd graph O_k is a special case of Kneser graph when n = 2k + 1. A long standing conjecture claims that O_k is hamiltonian for all k>2. We show that the prism over O_k is hamiltonian for all k even. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:177‐188, 2011     

Hamiltonian cycles in -circulant digraphs

Let D be the circulant digraph with n vertices and connection set {2,3,c}. (Assume D is loopless and has outdegree 3.) Work of S. C. Locke and D. Witte implies that if n is a multiple of 6, c{(n/2)+2,(n/2)+3}, and c is even, then D does not have a hamiltonian cycle. For all other cases, we construct a hamiltonian cycle in D.     

Irreducible 2‐fold cycle systems

In this paper, it is shown that for any pair of integers (m,n) with 4 ≤ m ≤ n, if there exists an m‐cycle system of order n, then there exists an irreducible 2‐fold m‐cycle system of order n, except when (m,n) = (5,5). A similar result has already been established for the case of 3‐cycles. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 324–332, 2006     

Embedding partial odd‐cycle systems in systems with orders in all admissible congruence classes

For odd m, relatively little is known about embedding partial m‐cycle systems into m‐cycle systems of small orders not congruent to 1 or m modulo 2m. In this paper we prove that any partial m‐cycle system of order u can be embedded in an m‐cycle system of order v if v≥m(2u+1)+(m?1)/2, v is odd and $\left( {_{2}^{V} } \right) \equiv 0\left( {\bmod {\rm }m} \right)$. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 202–208, 2010     

On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

Erdős has conjectured that every subgraph of the n‐cube Q_n having more than (1/2 + o(1))e(Q_n) edges will contain a 4‐cycle. In this note we consider ‘layer’ graphs, namely, subgraphs of the cube spanned by the subsets of sizes k − 1, k and k + 1, where we are thinking of the vertices of Q_n as being the power set of {1,…, n}. Observe that every 4‐cycle in Q_n lies in some layer graph. We investigate the maximum density of 4‐cycle free subgraphs of layer graphs, principally the case k = 2. The questions that arise in this case are equivalent to natural questions in the extremal theory of directed and undirected graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 66–82, 2000