A S(3, {4, 6}, 18) with a subdesign S(3, 4, 8) does not exist

For , a S(t,K,v) design is a pair, , with |V| = v and a set of subsets of V such that each t‐subset of V is contained in a unique and for all . If , , , and is a S(t,K,u) design, then we say has a subdesign on U. We show that a S(3,{4,6},18) design with a subdesign S(3,4,8) does not exist. © 2007 Wiley Periodicals, Inc. J Combin Designs 17: 36–38, 2009     

An improvement on H design

An H(m, g, 4, 3) is a triple , where X is a set of mg points, is a partition of X into m disjoint sets of size g, and is a set of 4‐element transverses of , such that each 3‐element transverse of is contained in exactly one of them. Such a design was introduced by Hanani 2 , who used it to study Steiner quadruple systems. Mills showed that for , an H(m, g, 4, 3) exists if and only if mg is even and is divisible by 3, and that for , an H(5, g, 4, 3) exists if g is divisible by 4 or 6 10 . In this article, we shall show that an H(5, g, 4, 3) exists if g is even, and . © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 25–35, 2009     

Existence of 3‐chromatic Steiner quadruple systems

A Steiner quadruple system of order v (briefly SQS (v)) is a pair (X, ), where X is a v‐element set and is a set of 4‐element subsets of X (called blocks or quadruples), such that each 3‐element subset of X is contained in a unique block of . The chromatic number of an SQS(v)(X, ) is the smallest m for which there is a map such that for all , where . The system (X, ) is equitably m‐chromatic if there is a proper coloring with minimal m for which the numbers differ from each other by at most 1. Linek and Mendelsohn showed that an equitably 3‐chromatic SQS(v) exists for v ≡ 4, 8, 10 (mod 12), v ≥ 16. In this article we show that an equitably 3‐chromatic SQS(v) exists for v ≡ 2 (mod 12) with v > 2. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 469–477, 2007     

Maximum number of colorings of (2k,k2)‐graphs

Let consist of all simple graphs on 2k vertices and edges. For a simple graph G and a positive integer , let denote the number of proper vertex colorings of G in at most colors, and let . We prove that and is the only extremal graph. We also prove that as . © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 135–148, 2007     

Cutting two graphs simultaneously

Consider two graphs, and , on the same vertex set V, with and having edges for . We give a simple algorithm that partitions V into sets A and B such that and . We also show, using a probabilistic method, that if and belong to certain classes of graphs, (for instance, if and both have a density of at least 2/, or if and are both regular of degree at most with n sufficiently large) then we can find a partition of V into sets A and B such that for . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 19–32, 2008     

Disjoint cycles with chords in graphs

Let be integers, , , and let for each , be a cycle or a tree on vertices. We prove that every graph G of order at least n with contains k vertex disjoint subgraphs , where , if is a tree, and is a cycle with chords incident with a common vertex, if is a cycle. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 87–98, 2009     

Circular chromatic index of Cartesian products of graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are incident. Let □ , where □ denotes Cartesian product and H is an ‐regular graph of odd order, with (thus, G is s‐regular). We prove that , where is the minimum, over all bases of the cycle space of H, of the maximum length of a cycle in the basis. When and m is large, the lower bound is sharp. In particular, if , then □ , independent of m. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 7–18, 2008     

A system of equations for describing cocyclic Hadamard matrices

Given a basis for 2‐cocycles over a group G of order , we describe a nonlinear system of 4t‐1 equations and k indeterminates over , whose solutions determine the whole set of cocyclic Hadamard matrices over G, in the sense that ( ) is a solution of the system if and only if the 2‐cocycle gives rise to a cocyclic Hadamard matrix . Furthermore, the study of any isolated equation of the system provides upper and lower bounds on the number of coboundary generators in which have to be combined to form a cocyclic Hadamard matrix coming from a special class of cocycles. We include some results on the families of groups and . A deeper study of the system provides some more nice properties. For instance, in the case of dihedral groups , we have found that it suffices to check t instead of the 4t rows of , to decide the Hadamard character of the matrix (for a special class of cocycles f). © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 276–290, 2008     

Uniqueness of weak solutions in critical space of the 3‐D time‐dependent Ginzburg‐Landau equations for superconductivity

We prove the uniqueness of weak solutions of the 3‐D time‐dependent Ginzburg‐Landau equations for super‐conductivity with initial data (ψ₀, A₀)∈ L² under the hypothesis that (ψ, A) ∈ L^s(0, T; L^r,∞) × (0, T; with Coulomb gauge for any (r, s) and satisfying + = 1, + = 1, ≥ , ≥ and 3 < r ≤ 6, 3 < ≤ ∞. Here L^r,∞ ≡ is the Lorentz space. As an application, we prove a uniqueness result with periodic boundary condition when ψ₀ ∈ , A₀ ∈ L³ (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Tangency sets in PG(3, q)

A tangency set of PG (d,q) is a set Q of points with the property that every point P of Q lies on a hyperplane that meets Q only in P. It is known that a tangency set of PG (3,q) has at most points with equality only if it is an ovoid. We show that a tangency set of PG (3,q) with , or points is contained in an ovoid. This implies the non‐existence of minimal blocking sets of size , , and of with respect to planes in PG (3,q), and implies the extendability of partial 1‐systems of size , , or to 1‐systems on the hyperbolic quadric . © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 462–476, 2008     

Ore‐type condition for the existence of connected factors

In this article, we obtain some Ore‐type sufficient conditions for a graph to have a connected factor with degree restrictions. Let α and k be positive integers with if and if . Let G be a connected graph with a spanning subgraph F, each component of which has order at least α. We show that if the degree sum of two nonadjacent vertices is greater than then G has a connected subgraph in which F is contained and every vertex has degree at most . From the result, we derive that a graph G has a connected ‐factor if the degree sum of two nonadjacent vertices is at least . © Wiley Periodicals, Inc. J. Graph Theory 56: 241–248, 2007     

Upper chromatic number of finite projective planes

For a finite projective plane , let denote the maximum number of classes in a partition of the point set, such that each line has at least two points in the same partition class. We prove that the best possible general estimate in terms of the order of projective planes is , which is tight apart from a multiplicative constant in the third term :

• (1) As holds for every projective plane of order q.
• (2) If q is a square, then the Galois plane of order q satisfies .

Our results asymptotically solve a ten‐year‐old open problem in the coloring theory of mixed hypergraphs, where is termed the upper chromatic number of . Further improvements on the upper bound (1) are presented for Galois planes and their subclasses. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 221–230, 2008     

Vertex suppression in 3‐connected graphs

To suppress a vertex in a finite graph G means to delete it and add an edge from a to b if a, b are distinct nonadjacent vertices which formed the neighborhood of . Let be the graph obtained from by suppressing vertices of degree at most 2 as long as it is possible; this is proven to be well defined. Our main result states that every 3‐connected graph G has a vertex x such that is 3‐connected unless G is isomorphic to , , or to a wheel for some . This leads to a generator theorem for 3‐connected graphs in terms of series parallel extensions. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 41–54, 2008     

Enumeration of generalized Hadamard matrices of order 16 and related designs

We investigate signings of symmetric GDD( , 16, )s over for . Beginning with , at each stage of this process a signing of a GDD( , 16, ) produces a GDD( , 16, ). The initial GDDs ( ) correspond to Hadamard matrices of order 16. For , the GDDs are semibiplanes of order 16, and for the GDDs are semiplanes of order 16 which can be extended to projective planes of order 16. In this article, we completely enumerate such signings which include all generalized Hadamard matrices of order 16. We discuss the generation techniques and properties of the designs obtained during the search. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 119–135, 2009     

Simple Signed Steiner Triple Systems

Let X be a v‐set, be a set of 3‐subsets (triples) of X, and be a partition of with . The pair is called a simple signed Steiner triple system, denoted by ST, if the number of occurrences of every 2‐subset of X in triples is one more than the number of occurrences in triples . In this paper, we prove that exists if and only if , , and , where and for , . © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 332–343, 2012     

A note on complete subdivisions in digraphs of large outdegree

Mader conjectured that for all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order . In this note, we observe that if the minimum outdegree of a digraph is sufficiently large compared to its order then one can even guarantee a subdivision of a large complete digraph. More precisely, let be a digraph of order n whose minimum outdegree is at least d. Then contains a subdivision of a complete digraph of order . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 1–6, 2008     

On k‐detour subgraphs of hypercubes

A spanning subgraph G of a graph H is a k‐detour subgraph of H if for each pair of vertices , the distance, , between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k‐detour subgraphs of the n‐dimensional cube, , with few edges or with moderate maximum degree. Let denote the minimum possible maximum degree of a k‐detour subgraph of . The main result is that for every and On the other hand, for each fixed even and large n, there exists a k‐detour subgraph of with average degree at most . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55–64, 2008     

Graph classes characterized both by forbidden subgraphs and degree sequences

Given a set of graphs, a graph G is ‐free if G does not contain any member of as an induced subgraph. We say that is a degree‐sequence‐forcing set if, for each graph G in the class of ‐free graphs, every realization of the degree sequence of G is also in . We give a complete characterization of the degree‐sequence‐forcing sets when has cardinality at most two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 131–148, 2008     

Hereditary properties of combinatorial structures: Posets and oriented graphs

A hereditary property of combinatorial structures is a collection of structures (e.g., graphs, posets) which is closed under isomorphism, closed under taking induced substructures (e.g., induced subgraphs), and contains arbitrarily large structures. Given a property , we write for the collection of distinct (i.e., non‐isomorphic) structures in a property with n vertices, and call the function the speed (or unlabeled speed) of . Also, we write for the collection of distinct labeled structures in with vertices labeled , and call the function the labeled speed of . The possible labeled speeds of a hereditary property of graphs have been extensively studied, and the aim of this article is to investigate the possible speeds of other combinatorial structures, namely posets and oriented graphs. More precisely, we show that (for sufficiently large n), the labeled speed of a hereditary property of posets is either 1, or exactly a polynomial, or at least . We also show that there is an initial jump in the possible unlabeled speeds of hereditary properties of posets, tournaments, and directed graphs, from bounded to linear speed, and give a sharp lower bound on the possible linear speeds in each case. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 311–332, 2007     

On conjectures of Frankl and El‐Zahar

An induced subgraph of a graph is called a derived subgraph of if contains no isolated vertices. An edge e of is said to be residual if e occurs in more than half of the derived subgraphs of . In this article, we prove that every simple graph with at least one edge contains a non‐residual edge. This was conjectured by El‐Zahar in 1997. © 2008 Wiley Periodicals, Inc. J Graph Theory 57: 344–352, 2008