Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. Let m = 4 or m = 5 and let D be a strongly connected in‐tournament of order such that each arc belongs to a directed path of order at least m. In 2000, Volkmann showed that if D contains an arc e such that the longest directed path through e consists of exactly m vertices, then e is the only arc of D with that property. In this article we shall see that this proposition is true for , thereby validating a conjecture of Volkmann. Furthermore, we prove that if we ease the restrictions on the order of D to , the in‐tournament D in question has at most two such arcs. In doing so, we also give a characterization of the in‐tournaments with exactly two such arcs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 130–148, 2009     

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     

Critical graphs for subpancyclicity of 3‐connected claw‐free graphs

Let be the family of graphs G such that all sufficiently large k ‐connected claw‐free graphs which contain no induced copies of G are subpancyclic. We show that for every k≥3 the family is infinite and make the first step toward the complete characterization of the family . © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 263–278, 2009     

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     

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     

Ore‐type degree conditions for a graph to be H‐linked

Given a fixed multigraph H with V(H) = {h₁,…, h_m}, we say that a graph G is H‐linked if for every choice of m vertices v₁, …, _vm in G, there exists a subdivision of H in G such that for every i, v_i is the branch vertex representing h_i. This generalizes the notion of k‐linked graphs (as well as some other notions). For a family of graphs, a graph G is ‐linked if G is H‐linked for every . In this article, we estimate the minimum integer r = r(n, k, d) such that each n‐vertex graph with is ‐linked, where is the family of simple graphs with k edges and minimum degree at least . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 14–26, 2008     

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     

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     

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     

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     

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     

Optimal Regularity for the No‐Sign Obstacle Problem

In this paper we prove the optimal $C^{1,1}(B_{1/2})$ ‐regularity for a general obstacle‐type problem under the assumption that $f*N$ is $C^{1,1}(B_1)$ , where N is the Newtonian potential. This is the weakest assumption for which one can hope to get $C^{1,1}$ ‐regularity. As a by‐product of the $C^{1,1}$ ‐regularity we are able to prove that, under a standard thickness assumption on the zero set close to a free boundary point $x^0$ , the free boundary is locally a $C^1$ ‐graph close to $x^0$ provided f is Dini. This completely settles the question of the optimal regularity of this problem, which has been the focus of much attention during the last two decades. © 2012 Wiley Periodicals, Inc.     

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     

Non‐rainbow colorings of 3‐, 4‐ and 5‐connected plane graphs

We study vertex‐colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3 ‐connected plane graph with n vertices, then the number of colors in such a coloring does not exceed . If G is 4 ‐connected, then the number of colors is at most , and for n≡3(mod8), it is at most . Finally, if G is 5 ‐connected, then the number of colors is at most . The bounds for 3 ‐connected and 4 ‐connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129–145, 2010     

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     

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)     

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     

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     

Density of universal classes of series‐parallel graphs

A class of graphs ordered by the homomorphism relation is universal if every countable partial order can be embedded in . It is known (see [ 1 , 3 ]) that the class of k‐colorable graphs, for any fixed , induces a universal partial order. In 4 , a surprisingly small subclass of which is a proper subclass of the series‐parallel graphs (the K₄‐minor‐free graphs) is shown to be universal. On another side, Pan and Zhu in 7 proved a density result that for each rational number , there is a K₄‐minor‐free graph with circular chromatic number equal to a/b. In this note, we show for each rational number a/b within this interval the class of K₄‐minor‐free graphs with circular chromatic number a/b is universal if and only if , 5/2 or 3. This shows yet another surprising richness of the K₄‐minor‐free class that it contains universal classes as dense as the rational numbers. © 2006 Wiley Periodicals, Inc. J Graph Theory     

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