Tearing a strip off the plane

In this article we examine some homomorphic properties of certain subgraphs of the unit-distance graph. We define G_r to be the subgraph of the unit-distance graph induced by the subset (−∞, ∞) × [0, r] of the plane. The bulk of the article is devoted to examining the graphs G_r, when r is the minimum width such that G_r contains an odd cycle of given length. We determine for each odd n the minimum width r_n such that contains an n-cycle C_n, and characterize the embeddings of C_n in $G_{r_{n}}$. We then show that is homomorphically equivalent to C_n when n ≡ 3 (mod 4), but is a core when n ≡ 1 (mod 4). We begin by showing that G_r is homomorphically compact for each r ≥ 0, as defined in [1]. We conclude with some other interesting results and open problems related to the graphs G_r. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 17–33, 1998     

Q5‐factorization of λKn

Q_k is the simple graph whose vertices are the k‐tuples with entries in {0, 1} and edges are the pairs of k‐tuples that differ in exactly one position. In this paper, we proved that there exists a Q₅‐factorization of λK_n if and only if (a) n ≡ 0(mod 32) if λ ≡ 0(mod 5) and (b) n ≡ 96(mod 160) if λ ? 0(mod 5).     

On the parity of crossing numbers

For an integer n ? 1, a graph G has an n-constant crossing number if, for any two good drawings ? and ?′ of G in the plane, μ(?) ≡ μ(?′) (mod n), where μ(?) is the number of crossings in ?. We prove that, except for trivial cases, a graph G has n-constant crossing number if and only if n = 2 and G is either K_p or K_q,r, where p, q, and r are odd.     

Small Uniformly Resolvable Designs for Block Sizes 3 and 4

A uniformly resolvable design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k, such a class is denoted k‐pc and for a given k the number of k‐pcs is denoted r_k. In this paper, we consider the case of block sizes 3 and 4 (both existent). We use v to denote the number of points, in this case the necessary conditions imply that v ≡ 0 (mod 12). We prove that all admissible URDs with v < 200 points exist, with the possible exceptions of 13 values of r₄ over all permissible v. We obtain a URD({3, 4}; 276) with r₄ = 9 by direct construction use it to and complete the construction of all URD({3, 4}; v) with r₄ = 9. We prove that all admissible URDs for v ≡ 36 (mod 144), v ≡ 0 (mod 60), v ≡ 36 (mod 108), and v ≡ 24 (mod 48) exist, with a few possible exceptions. Recently, the existence of URDs for all admissible parameter sets with v ≡ 0 (mod 48) was settled, this together with the latter result gives the existence all admissible URDs for v ≡ 0 (mod 24), with a few possible exceptions.     

Circular flow numbers of regular multigraphs

The circular flow number F_c(G) of a graph G = (V, E) is the minimum r ϵ ℚ such that G admits a flow ϕ with 1 ≤ ϕ (e) ≤ r − 1, for each e ϵ E. We determine the circular flow number of some regular multigraphs. In particular, we characterize the bipartite (2t+1)‐regular graphs (t ≥ 1). Our results imply that there are gaps for possible circular flow numbers for (2t+1)‐regular graphs, e.g., there is no cubic graph G with 3 < F_c(G) < 4. We further show that there are snarks with circular flow number arbitrarily close to 4, answering a question of X. Zhu. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 24–34, 2001     

On the decomposition of λK into regular tournaments of order 5

An RTD[5,λ; v] is a decomposition of the complete symmetric directed multigraph, denoted by λK, into regular tournaments of order 5. In this article we show that an RTD[5,λ; v] exists if and only if (v?1)λ ≡ 0 (mod 2) and v(v?1)λ ≡ 0 (mod 10), except for the impossible case (v,λ) = (15,1). Furthermore, we show that for each v ≡ 1,5 (mod 20), v ≠ 5, there exists a B[5,2; v] which is not RT₅-directable. © 1994 John Wiley & Sons, Inc.     

1‐Rotational Steiner triple systems over arbitrary groups

Phelps and Rosa introduced the concept of 1‐rotational Steiner triple system, that is an STS(ν) admitting an automorphism consisting of a fixed point and a single cycle of length ν ? 1 [Discrete Math. 33 ( 12 ), 57–66]. They proved that such an STS(ν) exists if and only if ν ≡ 3 or 9 (mod 24). Here, we speak of a 1‐rotational STS(ν) in a more general sense. An STS(ν) is 1‐rotational over a group G when it admits G as an automorphism group, fixing one point and acting regularly on the other points. Thus the STS(ν)'s by Phelps and Rosa are 1‐rotational over the cyclic group. We denote by ??_1r, ??_1r, ??_1r, ??_1r, the spectrum of values of ν for which there exists a 1‐rotational STS(ν) over an abelian, a cyclic, a dicyclic, and an arbitrary group, respectively. In this paper, we determine ??_1r and find partial answers about ??_1r and ??_1r. The smallest 1‐rotational STSs have orders 9, 19, 25 and are unique up to isomorphism. In particular, the only 1‐rotational STS(25) is over SL₂(3), the special linear group of dimension 2 over Z₃. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 215–226, 2001     

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     

Equimatchable Regular Graphs

A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3‐regular graphs are K₄ and K_{3, 3}. We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r‐regular graph, then . Also it is proved that for an even r, a connected triangle‐free equimatchable r‐regular graph is isomorphic to one of the graphs C₅, C₇, and .     

An infinite family of biprimitive semisymmetric graphs

A regular and edge-transitive graph that is not vertex-transitive is said to be semisymmetric. Every semisymmetric graph is necessarily bipartite, with the two parts having equal size and the automorphism group acting transitively on each of these two parts. A semisymmetric graph is called biprimitive, if its automorphism group acts primitively on each part. In this article, a classification of biprimitive semisymmetric graphs arising from the action of the group PSL(2, p), p ≡ ±1 (mod 8) a prime, acting on cosets of S₄ is given, resulting in several new infinite families of biprimitive semisymmetric graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 217–228, 1999     

Group‐divisible designs with block size k having k + 1 groups,for k = 4, 5

We investigate the spectrum for k‐GDDs having k + 1 groups, where k = 4 or 5. We take advantage of new constructions introduced by R. S. Rees (Two new direct product‐type constructions for resolvable group‐divisible designs, J Combin Designs, 1 (1993), 15–26) to construct many new designs. For example, we show that a resolvable 4‐GDD of type g⁵ exists if and only if g ≡ 0 mod 12 and that a resolvable 5‐GDD of type g⁶ exists if and only if g ≡ 0 mod 20. We also show that a 4‐GDD of type g⁴m¹ exists (with m > 0) if and only if g ≡ m ≡ 0 mod 3 and 0 < m ≤ 3g/2, except possibly when (g,m) = (9,3) or (18,6), and that a 5‐GDD of type g⁵m¹ exists (with m > 0) if and only if g ≡ m ≡ 0 mod 4 and 0 < m ≤ 4g/3, with 32 possible exceptions. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 363–386, 2000     

Polychromatic colorings of bounded degree plane graphs

A polychromatic k‐coloring of a plane graph G is an assignment of k colors to the vertices of G such that every face of G has all k colors on its boundary. For a given plane graph G, one seeks the maximum number k such that G admits a polychromatic k ‐coloring. In this paper, it is proven that every connected plane graph of order at least three, and maximum degree three, other than K₄ or a subdivision of K₄ on five vertices, admits a 3‐coloring in the regular sense (i.e., no monochromatic edges) that is also a polychromatic 3‐coloring. Our proof is constructive and implies a polynomial‐time algorithm. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 269‐283, 2009     

The A4‐structure of a graph

We define the A₄‐structure of a graph G to be the 4‐uniform hypergraph on the vertex set of G whose edges are the vertex subsets inducing 2K₂, C₄, or P₄. We show that perfection of a graph is determined by its A₄‐structure. We relate the A₄‐structure to the canonical decomposition of a graph as defined by Tyshkevich [Discrete Math 220 (2000) 201–238]; for example, a graph is indecomposable if and only if its A₄‐structure is connected. We also characterize the graphs having the same A₄‐structure as a split graph.     

Tree decompositions of graphs without large bipartite holes

A recent result of Condon, Kim, Kühn, and Osthus implies that for any , an n‐vertex almost r‐regular graph G has an approximate decomposition into any collections of n‐vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost αn‐regular graph G with any α>0 and a collection of bounded degree trees on at most (1?o(1))n vertices if G does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into n‐vertex trees. Moreover, this implies that for any α>0 and an n‐vertex almost αn‐regular graph G, with high probability, the randomly perturbed graph has an approximate decomposition into all collections of bounded degree trees of size at most (1?o(1))n simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey‐Turán theory and the randomly perturbed graph model.     

On the perfect orderability of unions of two graphs

A graph G is perfectly orderable, if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (H, <) of (G, <). A graph is a threshold graph, if it contains no P₄, 2K₂, and C₄ as induced subgraph. A theorem of Chvátal, Hoàng, Mahadev, and de Werra states that a graph is perfectly orderable, if it is the union of two threshold graphs. In this article, we investigate possible generalizations of the above theorem. Hoàng has conjectured that, if G is the union of two graphs G₁ and G₂, then G is perfectly orderable whenever G₁ and G₂ are both P₄‐free and 2K₂‐free. We show that the complement of the chordless cycle with at least five vertices cannot be a counter‐example to this conjecture, and we prove a special case of it: if G₁ and G₂ are two edge‐disjoint graphs that are P₄‐free and 2K₂‐free, then the union of G₁ and G₂ is perfectly orderable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 32–43, 2000     

On Cyclic Decompositions of Complete Graphs into Tripartite Graphs

We introduce two new labelings for tripartite graphs and show that if a graph G with n edges admits either of these labelings, then there exists a cyclic G‐decomposition of for every positive integer x. We also show that if G is the union of two vertext‐disjoint cycles of odd length, other than , then G admits one of these labelings.     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998     

3‐Flows and Combs

Tutte's 3‐Flow Conjecture states that every 2‐edge‐connected graph with no 3‐cuts admits a 3‐flow. The 3‐Flow Conjecture is equivalent to the following: let G be a 2‐edge‐connected graph, let S be a set of at most three vertices of G; if every 3‐cut of G separates S then G has a 3‐flow. We show that minimum counterexamples to the latter statement are 3‐connected, cyclically 4‐connected, and cyclically 7‐edge‐connected.     

Strong difference families over arbitrary graphs

The concept of a strong difference family formally introduced in Buratti [J Combin Designs 7 (1999), 406–425] with the aim of getting group divisible designs with an automorphism group acting regularly on the points, is here extended for getting, more generally, sharply‐vertex‐transitive Γ‐decompositions of a complete multipartite graph for several kinds of graphs Γ. We show, for instance, that if Γ has e edges, then it is often possible to get a sharply‐vertex‐transitive Γ‐decomposition of K_{m × e} for any integer m whose prime factors are not smaller than the chromatic number of Γ. This is proved to be true whenever Γ admits an α‐labeling and, also, when Γ is an odd cycle or the Petersen graph or the prism T₅ or the wheel W₆. We also show that sometimes strong difference families lead to regular Γ‐decompositions of a complete graph. We construct, for instance, a regular cube‐decomposition of K_16m for any integer m whose prime factors are all congruent to 1 modulo 6. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 443–461, 2008     

Facial non‐repetitive edge‐coloring of plane graphs

A sequence r₁, r₂, …, r_2n such that r_i=r_{n+ i} for all 1≤i≤n is called a repetition. A sequence S is called non‐repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non‐repetitive if the sequence of colors of its edges is non‐repetitive. If G is a plane graph, a facial non‐repetitive edge‐coloring of G is an edge‐coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′_f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′_f(G)≤8 for any plane graph G. We also get better upper bounds for π′_f(G) in the cases when G is a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010