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     

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     

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 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     

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)     

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     

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     

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     

The cover time of random geometric graphs

We study the cover time of random geometric graphs. Let $I(d)=[0,1]^{d}$ denote the unit torus in d dimensions. Let $D(x,r)$ denote the ball (disc) of radius r. Let $\Upsilon_d$ be the volume of the unit ball $D(0,1)$ in d dimensions. A random geometric graph $G=G(d,r,n)$ in d dimensions is defined as follows: Sample n points V independently and uniformly at random from $I(d)$ . For each point x draw a ball $D(x,r)$ of radius r about x. The vertex set $V(G)=V$ and the edge set $E(G)=\{\{v,w\}: w\ne v,\,w\in D(v,r)\}$ . Let $G(d,r,n),\,d\geq 3$ be a random geometric graph. Let $C_G$ denote the cover time of a simple random walk on G. Let $c>1$ be constant, and let $r=(c\log n/(\Upsilon_dn))^{1/d}$ . Then whp the cover time satisfies © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 324–349, 2011     

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     

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     

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 the existence of a rainbow 1‐factor in 1‐factorizations of K

Let be a 1‐factorization of the complete uniform hypergraph with and . We show that there exists a 1‐factor of whose edges belong to n different 1‐factors in . Such a 1‐factor is called a “rainbow” 1‐factor or an “orthogonal” 1‐factor. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 487–490, 2007     

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     

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     

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     

Small complete caps in PG(N,q), q even

A new family of small complete caps in PG(N,q), q even, is constructed. Apart from small values of either N or q, it provides an improvement on the currently known upper bounds on the size of the smallest complete cap in PG(N,q): for N even, the leading term is replaced by with , for N odd the leading term is replaced by with . © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 420–436, 2007